求解最短运输顺序路径的图算法

Question

我有一个简单的网络应用程序，这是建模运输公司的信息系统。我想实现自动计算给定订单的最短路径的功能。

new order form

订单由一组货物表示，每一批货物都有出发/到达点。我将城市和每对城市之间的距离存储在数据库中。问题是找到一条最短的路线来运输所有这些货物。开始和结束城市并不重要，唯一有趣的是最短的路径，这将包括装卸每一批货物。

有没有适合解决这类问题的图算法？

Answer 1

如果条目数量相对较少(正如您的评论所建议的那样)，您可以将问题减少到Traveling Salesman Problem。

首先，如果你没有每对城市之间的最短距离-你可以使用Floyd-Warshall algorithm找到它。如果您已经拥有每对城市之间的距离，则可以跳过此步骤。

现在，您有了一个合适的TSP问题，对于数量较少的城市，可以使用暴力或更复杂的动态编程解决方案轻松解决。

如果我是你，我会从简单的解决方案开始，如果这还不够-实现更复杂的解决方案。

如果以后许多城市的规模变得很大，您将需要更复杂的TSP算法，甚至可能由于问题的性质而不得不选择非最优解。也就是说，虽然您只在少数几个城市的领域-现有的解决方案应该能做到这一点。