Paired cooperative reoptimization strategy for the vehicle routing problem with stochastic demands
Paired cooperative reoptimization strategy for the vehicle routing problem with stochastic demands
复制标题
DOI：
10.1016/j.cor.2014.03.027
复制
发表时间：
2014-10
期刊：
影响因子：
--
通讯作者：
Lin Zhu;Louis-Martin Rousseau;W. Rei;Bo Li
中科院分区：
文献类型：
--
作者：
Lin Zhu;Louis-Martin Rousseau;W. Rei;Bo Li
提出了一种成对合作重优化策略来求解随机需求车辆路径问题。该策略可以实现车辆间协作下的再优化策略，适用于多车辆情况。PCR反复触发通信和分区，以根据实时客户需求更新车辆分配。我们提出了一个两层马尔可夫决策过程模型的协调下的PCR策略的一对车辆。我们还提出了一个启发式，动态地改变访问序列和车辆分配更新的信息。我们比较我们的方法与文献中最近的合作策略。结果表明，我们的PCR策略表现更好，成本节省约20- 30%。此外，嵌入通信可以平均节省1.22%，而应用我们的分区方法而不是替代方法可以平均节省3.96%。
In this paper, we develop a paired cooperative reoptimization (PCR) strategy to solve the vehicle routing problem with stochastic demands (VRPSD). The strategy can realize reoptimization policy under cooperation between a pair of vehicles, and it can be applied in the multivehicle situation. The PCR repeatedly triggers communication and partitioning to update the vehicle assignments given real-time customer demands. We present a bilevel Markov decision process to model the coordination of a pair of vehicles under the PCR strategy. We also propose a heuristic that dynamically alters the visiting sequence and the vehicle assignment given updated information. We compare our approach with a recent cooperation strategy in the literature. The results reveal that our PCR strategy performs better, with a cost saving of around 20–30%. Moreover, embedding communication can save an average of 1.22%, and applying our partitioning method rather than an alternative can save an average of 3.96%.