用图论在车辆路径问题中的应用

Question

我正在使用单个仓库处理车辆路径问题.问题定义如下.有n个vechiles需要前往m个站点.每个站点都有其特定的限制,例如只有具有一定容量的车辆才能为站点提供服务,有些站点需要在一天中的特定时间提供服务.此外,车辆将具有不同的容量并且将具有不同的开始和结束时间.

我们的想法是尽量减少从车厂出发的车辆的行程时间.

我正在构建问题的成本矩阵.虽然不是图论的专家,但我知道如果它陷入经典的旅行商问题,我可以使用哈密顿循环来解决问题.但是,因为它涉及多个旅行推销员问题,我想知道如何使用哈密顿循环解决问题,或者是否有另一个专门针对问题设计的流程？

任何帮助将非常感激.

Answer 1

场地需要一定容量的车辆的限制使得该问题也类似于背包问题。请参阅此处：维基百科上的背包问题

这个问题看起来非常独特，所以我认为您需要结合使用多种技术来解决背包问题和最短路径问题。首先，弄清楚要分配给每个站点的车辆（背包）。然后按容量降序计算车辆到达站点的最短路径是否与其他车辆的路径相交，并根据需要重新分配职责。