基于特殊路径的局内车辆路径问题混合策略研究

摘要

针对运输途中遇到的某一或一系列无法预知的堵塞事件对决策者路径选择策略的影响,考虑堵塞只发生在一条特殊路径上且可恢复的情况,采用局内竞争分析的思想,建立了局内车辆路径问题的数学模型,对车辆到达堵塞点时堵塞恢复时间未知这一情形下的路径选择问题,提出了两种混合策略,给出了相应的竞争比,并对其竞争性能进行了理论分析.%This paper studies the vehicle routing problem with a series of unexpected congested nodes. First, an online model is formulated for the case that the congested nodes only occur on a special road. It is assumed that a congested node can only be known after the vehicle reaches it, and its recovery time is uncertain (I. E. , the information about both the congested node and its recovery time is released in an online fashion). After that, two mixed strategies are proposed to address the problem. Furthermore, the competitive analysis of these two strategies and their competitive ratios are provided.