路径长度受限的随机需求VRP的节省算法及其策略分析

Modified saving-algorithm and strategy analysis for path length constrained vehicle routing problem with stochastic demand

在保证每条路径长度限制,至多只能服务失败一次和不允许部分服务的策略下,定义了一个新的节省路径,给出了一个精确的节省算法,对中等规模和大规模问题进行了数值试验,数值试验表明算法有效。对所采用的策略进行了分析,得到了一些理论结果。

Under the strategy of keeping path length constrained tightly and only one time routing service failure and no part service, a new routing-saving path was defined and a saving- algorithm is proposed. The algorithm was tested under middle and large-scale PSVRP numerically; numerical result indicated the algorithm is valid. The strategy analysis was discussed and theoretical results were obtained.