考虑同步的车辆路径优化问题研究

The applications of the vehicle routing problems with synchronization (VRPS) exist in many areas, where a task usually requires a set of vehicles or a group of workers and the task cannot be started unless all required vehicles or workers have arrived at the task location. We call this requirement synchronization constraint. The existing formulations and algorithms for the traditional vehicle routing problems (VRPs) cannot be directly applied to the VRPSs. Incorporating the synchronization constraint into the traditional VRPs increases the complexity of the problems significantly, thus the literature papers on the VRPSs are very scarce. This project investigates four representative, practical and complex VRPSs, namely (1) the manpower scheduling problem with synchronization constraints, (2) the inspector scheduling problem with synchronization constraints, (3) the movie shooting scheduling problem and (4) the electric vehicle routing problem with mobile battery swapping station. Although these four problems occur in quite different application areas, they all aim to route subjects and have to consider synchronization constraints. After carefully analyzing the synchronization and other constraints, we will design tailored exact algorithms, heuristics, meta-heuristics to obtain the optimal and near-optimal solutions of these problems. This project will promote the study of the VRPSs, create a series of new theories and methods, as well as provide practical and effective solution procedures for relevant companies.

考虑同步的车辆路径优化问题存在于许多应用领域中。在这些领域，通常任务需要多辆车或多个人来共同合作完成，并且当所需的车或人都抵达后才能开始执行任务；我们称这个要求为同步约束。现有的车辆路径模型和优化算法无法直接用来解决此类问题。引入同步约束大大增加了问题的复杂度，因此这类路径优化问题的文献非常少。本项目拟研究四个有代表性的、贴近实际的、复杂的同步路径优化问题，即（1）带同步约束的人员调度问题，（2）考虑同步的质检员排班问题，（3）电影场景拍摄顺序优化问题，（4）使用移动电池交换站的电动车路径问题。虽然这些问题来自不同应用领域，但它们的目的都是优化路径，且必须考虑同步约束。我们将针对同步及问题的其它约束，设计新颖的精确算法、启发式算法、元启发式算法求解问题的近似解和最优解。本项目有利于将此类问题推向国际学术前沿，研究出一系列新理论、新方法，同时也可以为相关企业提供切实可行的、有效的解决方案。

本项目主要目标是研究考虑协同约束的路径规划问题，该类问题在服务业、生产制造业及物流行业经常被遇到。原申请书中拟研究4个路径规划问题，但是由于第4个问题难度较大，我们目前只在前3个问题上取得了成功，并且取得了相应的研究成果。此外，在项目开展期间，我们对其它10类组合优化问题也开展了研究，即(1)考虑不确定需求和计重收费的车辆路径规划问题,(2)考虑分段线性成本函数的二维装箱问题,(3)非紧急救护服务中的人员分配和救护车调度问题,(4)考虑线性计重收费、货物可拆分和时间窗的车辆路径规划问题,(5)考虑组群约束的两层车辆路径规划问题,(6)病人运输中的Dial-a-ride问题,(7)零售中的取货派货车辆路径规划问题,(8)需求可拆分的弧路径规划问题,(9)考虑带时间窗和拍卖机制的车辆路径规划问题,和（10）经典一维装箱问题，并且取得了丰富的研究成果。对每个优化问题，我们通常首先将其建模成混合整数优化模型，然后分析其问题的结构和性质，接着设计精确求解算法或者启发式算法求解问题，最后通过计算时间来评估我们提出的算法的性能。项目组在运筹学，管理科学，交通运输等领域的国际顶级或知名期刊上发表（含接收）相关学术论文12篇。项目组积极地将研究成果推广到企业，力争为企业创造实际价值，目前已获得三家企业的正式合同，金额近200万元，合作企业包括华为科技有限公司和美的集团。