在一定天数内寻找穿越城市的最佳行程的算法

Question

我有一个城市列表，以及两个相邻城市之间的距离。给定起点和终点城市，我需要找到它们之间的最佳路线，前提是它必须在一定天数内完成。

可以实现这一目标的算法是什么？

编辑:例如，您从 city1 开始，在 city7 结束。你有这个和前一个城市之间的距离。您有 2 天的时间完成旅程，并且您希望每天的距离大致相等。路线也已定义，即您将按照已定义的顺序穿过城市，唯一的变化是您每天经过哪些城市以及经过多少个城市。

城市 1, 0城市 2, 3城市 3, 4城市 4, 1城市 5, 4城市 6, 3城市 7, 2

Answer 1

这是旅行商问题 (TSP) 的约束版本:https://en.m.wikipedia.org/wiki/Travelling_salesman_problem

这是一篇描述时间受限版本算法的论文:

http://pubsonline.informs.org/doi/pdf/10.1287/opre.31.5.938

作者使用分支定界法来解决问题。