旅行推销员:使用矩阵路由API (HERE Maps)

Travelling Salesman: Using Matrix Routing API (HERE Maps)

本文关键字：API HERE Maps 路由旅行推销员更新时间：2023-09-26

我的公司最近购买了HERE平台的企业许可证。在我正在开发的应用程序中，我需要解决旅行推销员问题，这意味着给定一个起点，一个目的地和它们之间的几个"路径点"，它必须计算出从A-n-B出发的最优路线。

例如，如果我有以下三个地址

1. London
2. Moscow
3. Paris

如果不优化它，我将得到一条从伦敦到莫斯科，再从那里回到巴黎的路线。这些地址的最佳路由是

1. London
2. Paris
3. Moscow

一个真实的例子是

- Start: Budapest
- End: Paris
- Waypoint 1: Berlin
- Waypoint 2: Vienna
- Waypoint 3: Stockholm
- Waypoint 4: Madrid
- Waypoint 5: Rome
- Waypoint 6: Bucharest
- Waypoint 7: Frankfurt
- Waypoint 8: Munchen
- Waypoint 9: Caen
- Waypoint 10: Barcelona

应用程序接收地址并输出最短的a.k.a.即从布达佩斯到巴黎的"最佳"路线。

我已经和HERE的支持人员谈过了，他们告诉我，我需要使用矩阵路由API(开发者指南PDF在这里)，但是我真的不明白它怎么能解决我的问题。

在文档中，据我所知，你可以定义多个起点和多个目的地，所以它会计算这些之间的距离，但我不认为有任何方法有一个固定的起点位置和另一个固定的目的地之间有多个路点。我们需要的是矩阵路由API吗?如果是，谁能给我一些伪代码如何使用它?

你所指向的PDF文件

" API的输出经常被用作其他API的输入优化方法，如:•计算一组位置的最短往返行程"

我由此推断，你不能单独使用他们的API来解决TSP，因为这样就没有什么可以留给"其他优化方法"去做了。我怀疑他们希望你使用他们的API来计算节点之间的点对点距离，然后将其提供给TSP算法来完成困难的部分。

有一天我看到一个需求，我们应该建立一个系统来解决TSP，我有点困惑。事实证明，有GIS软件可以很好地做到这一点，实际上很有用，我们按照要求安装了客户实际上在其他系统中用于此目的的软件。例如，参见http://webhelp.esri.com/arcgisdesktop/9.3/index.cfm?TopicName=Algorithms_used_by_Network_Analyst"TSP是一个组合问题，这意味着没有直接的方法来找到最佳序列。启发式用于在短时间内找到这些类型问题的良好解决方案. ...禁忌搜索的确切实现是专有的，但它已经在ESRI内部进行了广泛的研究和开发，可以快速产生良好的结果。"

PS -尽管ESRI说有可处理的组合问题，尽管TSP不是，据我们所知，其中之一。

寻找优化访问不同地点的时间或距离的路径问题是一个非常困难的问题，因为它需要分析N个阶乘解(其中N是要访问的地点的数量)。例如，如果N = 7，则有5040个解，如果N = 8则有40320，如果N = 9则有362880，等等。

这是计算机科学中的一个难题，因为它不能在多项式时间内解决。这是一个np困难(非确定性多项式时间困难)，您可以使用启发式和近似算法找到次优解决方案。我使用其中一种算法来解决iPhone/iPad的问题http://igioel.com/app/OptimalRoute/