有一些限制的旅行推销员

Question

我正在尝试找到驾驶通过 A、B、C 和 D 点的最佳方式

有一些额外的限制 - 必须先达到某些点。说 D 必须在 B 之前到达。换句话说，对某些点进行排序。

如果没有额外的限制，Google Maps apis 可以帮助解决这个问题。是否有其他服务可以帮助解决此问题？有没有办法用我错过的谷歌地图 api 来做到这一点？

Answer 1

旅行商问题可以表述为整数规划问题（此链接提供了公式）或约束规划问题，因此您可以使用任何 MIP 或 CP 求解器（例如CBC或Gecode）来解决带有任何您想要的额外约束的 TSP 问题加上。但是，如果您需要在 Google 地图上绘制结果，则必须使用 Google 地图 API 手动完成。

如果您更喜欢基于 Web 的解决方案，那么您可以使用NEOS 服务器进行优化，该服务器通过XML-RPC API提供对各种求解器的访问。该方法的另一个优点是允许使用高级建模语言（例如AMPL）提交问题，而不是直接处理低级求解器 API。