5

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

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

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

4

5 回答 5

1

你说谷歌有一个 API 函数让我们命名它bestWay(point a, point b)：

您有{A,B,C,D}积分，您必须按以下顺序访问它们：

A,C,D,B

找到 (A,C) 的最佳方式，然后从 (C,D) 和 (D,B) 中找到最佳方式，然后构建自己的方式。

如果在您可能必须检查所有排列C之前只有这样的约束：D

A->C->B->D
A->B->C->D
...
B->A->C->D
于 2013-02-20T22:08:30.747 回答
1

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

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

于 2013-02-20T22:34:01.770 回答
0

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

于 2013-02-20T23:03:34.757 回答
0

在http://www.openopt.org/TSP上有一个旅行商问题的开源实现——不过它是用 Python 编写的。

我已将上述 OpenOpt TSP 和 Google 方向合并在一起，以提供一个可以满足您要求的网站（除了订购限制），可在http://www.speedyroute.co.uk/获得

于 2013-03-07T13:34:02.353 回答
0

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

于 2013-08-04T08:03:46.197 回答