几个限制条件下的旅行推销员问题

Question

我正在尝试找到最优的方式通过点A、B、C和D，但有一些额外的限制——必须先到达某些点。比如说，在到达B之前必须先到达D，也就是对某些点进行排序。

如果没有其他限制，Google Maps API可以帮助解决这个问题。是否有其他服务可以帮助解决这个问题？是否有我错过的使用Google Maps API的方法？

- Noam

Answer 1

一个旅行推销员问题可以被表述为整数规划问题（此链接提供了一种表述）或约束规划问题，因此您可以使用任何MIP或CP求解器，例如CBC或Gecode来解决TSP问题，并添加任何额外的约束条件。但是，如果您需要在Google地图上绘制结果，则必须使用Google Maps API手动完成。

如果您更喜欢基于Web的解决方案，则可以使用用于优化的NEOS服务器，该服务器通过XML-RPC API提供对各种求解器的访问。作为额外的优势，此方法允许使用高级建模语言（例如AMPL）提交问题，而无需直接处理低级求解器API。

- vitaut

---

如果您沿着这条道路前进，您可能想考虑另一个求解器：Drools Planner（修改车辆路径问题的约束条件的视频）。 - Geoffrey De Smet

Answer 2

你说谷歌有一个API函数，我们将其命名为bestWay(point a, point b)：

你有{A,B,C,D}作为点，并且必须按以下顺序访问它们：

A,C,D,B

找出从 (A,C) 到 (C,D)，再到 (D,B) 的最佳路径，然后构建你的路径。

如果你只有在 (D,B) 之前的约束条件 C，你可能需要检查所有排列组合：

A->C->B->D
A->B->C->D
...
B->A->C->D

- 0x90

---

检查所有这些排列组合将成为一个可扩展性问题。 - Geoffrey De Smet

你说得对，这是一个NP完全问题。但如果你只有5个点，那就没问题了。 - 0x90

问题在于每个bestWay计算都是另一个HTTP请求，这将会非常昂贵。 - Noam

Answer 3

这里有一个Javascript的精确求解器：http://www.iaindunning.com/?page_id=39。它使用线性规划和割平面方法，就像这里 http://www.tsp.gatech.edu/methods/dfj/index.html 一样。

- Micromega

Answer 4

看看这个 http://xsolve.info/TSP.html。这是一个JAVA程序。你可以修改它来添加自己的限制条件。

- Kunal Das

Answer 5

有一个开源的旅行商问题实现可在http://www.openopt.org/TSP中获得-尽管它使用Python编写。

我已经将上述OpenOpt TSP和Google Directions合并到一起，提供了一个网站，可以完成您所需的功能(除了订购限制)，请前往http://www.speedyroute.co.uk/查看。

- yorkshirespud