周期性带驾驶员一致性约束的车辆路径规划问题（Periodic Vehicle Routing Problem with Driver Consistency, PVRP-DC）的可变邻域搜索与路径重连方法

《Expert Systems with Applications》：Variable Neighborhood Search with Path Relinking for the Periodic Vehicle Routing Problem with Driver Consistency

　　

周期性车辆路径问题（Periodic Vehicle Routing Problem, PVRP）及其变体在标准容量约束车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）基础上引入了物流场景中的现实特征。在PVRP中，配送路线在多个天数上规划，每位客户须按照预先指定的访问组合在特定天数接受服务，目标是寻找满足客户需求的最小成本路线。研究人员针对PVRP的一个挑战性扩展开展研究，其中每位客户在计划周期内多次访问时必须由同一车辆（驾驶员）服务（驾驶员一致性）。同驾驶员要求对应饮料配送、集成订单交付、零售陈列与医疗服务等系统中需要培养驾驶员—客户关系并保持服务质量的现实情形。研究人员提出若干基于可变邻域搜索（Variable Neighborhood Search, VNS）方法的启发式算法求解带驾驶员一致性的周期性容量车辆路径问题（Periodic Capacitated Vehicle Routing Problem with Driver Consistency, PVRP-DC），并在一组已识别高质量解（含最优值）的算例上测试性能，此外提出路径重连（Path Relinking, PR）后处理以改进结果。实验测试表明所述启发式相较于近期发表方法以及已知最优解均具有效性。

研究背景方面，容量约束车辆路径问题（CVRP）属于NP难组合优化问题，标准版本中每位客户恰好访问一次，每辆车路线总需求不超过车辆容量Q。物流研究逐步引入现实特征，形成多准则、软约束或随机行程时间等模型。周期性车辆路由问题（PVRP）在多个周期（天数）上规划配送，每位客户依预指定访问日程服务，需同时决定日程与路线以最小化总成本。PVRP-DC在PVRP基础上增加侧约束：同一客户在计划期内多次访问必须由同一车辆（驾驶员）完成，该约束使跨周期路线相互依赖，不能按单周期独立求解。该变体见于饮料配送、集成订单交付、零售陈列与居家照护等场景，Rodríguez-Martín等（2019）给出同构车队、单位需求、允许访问日程集的建模与分支切割（branch-and-cut）最优算法及10至70客户基准240例（5例不可行，235例可用）。精确法在中大型实例上计算代价过高，需短时而高质量的启发式。论文发表于《Expert Systems with Applications》。

关键技术方法方面，研究人员采用三类模板构造法生成初始解：基于CVRP的模板（调用HGS-CVRP并设人工容量n/m）、基于几何扇区旋转的模板（绕仓库等分角度k次旋转后簇内解TSP）、基于GRASP的随机聚类模板（α=0.2控制贪心随机性，k=20次构造）。日程分配用极小化各路线类最大日工作量的混合整数模型。改进阶段用可变邻域下降（Variable Neighborhood Descent, VND）依次探索四个邻域N₁改日程、N₂ intra-route插入、N₃ inter-route插入、N₄ inter-route交换，先修复容量越界再用VND降成本。后处理用路径重连（PR）：建精英集（elite set, ES），选发起解与最远引导解，用二部图最大权匹配对齐两模板路线类，沿三类邻域（改日程/移客户/换客户）向引导解移动并嵌VND。参数经72例训练—测试切分调定：α=0.2，GRASP k=20，GEO k=20，三构造法并集记VND，再接PR记VND-PR。基准用Rodríguez-Martín等235例（n=10–70，τ=2–5，m=2–4，q=?0.75·n/m?，坐标均匀[0,100]2，仓库(50,50)，欧氏距离）。

研究结果各节浓缩如下。第1节引言指明PVRP-DC因跨周期同驾驶员约束不可分解，需用模板整合周期。第2节综述PVRP自1974年垃圾收运起源至2014年Campbell & Wilson四十年综述，列中间设施、选址—路由、重分配约束等经典扩展，及2014–2026年精确法（branch-price-and-cut、Benders）、启发式（ALNS、LNS、memetic、biased-randomized ILS）、一致性路由ConVRP与PVRP-DC分支切割脉络，定位本研究于Rodríguez-Martín等基准。第3节整数规划模型复现z_ip^k、x_e^tk、y_i^tk变量与式(2)–(10)目标及连通、容量、二值约束。第4节构造法：模板含全客户、绑驾驶员、超容量路线类；CVRP法用HGS-CVRP（人工容n/m）得图2例；几何法等分m扇区旋2π/(mk)得图3异结构；GRASP法按RCL_c(α)随机加客至m簇后簇内TSP得图4；日程分配解每路线类极大最小日负载MIP。第5节改进：N₁–N₄邻域与VND顺序，可行性修复用F(S)=max(∑_t,k,iy_i^tk?q,0)计越界量，先改日程再插再换。第6节PR：ES由三构造法填充保多样，选发起解S_i与ES内最远S_g（距离D(S,S′)用日路线边Hamming和），路线匹配解赋权c_k?=|R_k(S_i)∩R_?(S_g)|贪心最大权二部匹配并对齐标号，沿N₁(x)改日程、N₂(x)移客、N₃(x)换客三邻域生成中间解并VND。第7节复杂度：单次VND Pass为O(n2(r+pτ))，单PR路径O(nI n2(r+pτ))，全PR相O(N_ES2nτ+L_PRnI n2(r+pτ))，主导指数4来自PR。第8节实验分科学调参与竞争两组。科学组72例切分定α=0.2（总偏差1.33%、#b=31、#f=0），GRASP k=20（总偏差0.69%、#b=47），GEO k=20（总偏差0.11%、#b=56），三法并集VND（总偏差0.20%、#b=50、#f=0）优于任二组合；全基准诊断CVRP快（0.17s）但偏差1.84%，GEO质量最佳（0.92%）但#f=22，GRASP鲁棒零失败（1.47%）；构造前多样度GRASP-GRASP平均159.47高于GEO-GEO 102.81，CVRP-GRASP 145.46，证GRASP补结构多样。性能剖面图5示VND在前段秒级把大例偏差从7.5%压到1.2%，PR再抛光中大字例。图6示PR阶段引入GRASP解使大例平均再改进1.31%（无GRASP仅0.55%）。竞争组表8：Branch-and-Cut近优（0.09%、181优）但均时2067.65s，大例4391.32s且5例超时；VND-PR均偏差1.39%、零失败、均时21.73s（约快95倍）。表9–10：VND-PR对Messaoudi等（2023）LNS启发式在n=60均优3.43%、n=70均优3.18%，且test71-p4-m4-c对手得?1（不可行）而VND-PR可行，均时46–60s远短于对手154–158s。第8.4节扩展性：自生n=150/200/250各12例（共36），VND-PR解33例，250客全解均时594.5s，PR封顶300s；LP松弛下界仅4/18算完，n=250偏差29.22%反映大例下界弱化而非启发式劣化。第9节结论：多起点+VNS+PR族启发式在PVRP-DC上近优、快、鲁棒，同构构造多样是核心，可拓至随机/动态/多仓周期路由。

讨论与结论翻译部分，研究人员指出：PVRP-DC捕捉了多服务日同驾驶员分配的操作需求，反映饮料、零售、医疗等连续服务现实，但显著增加求解难度；所提基于多起点范式耦合可变邻域搜索并辅以路径重连后处理的启发式族，在含已知最优的基准上获高质量解，多数场景优于近期前沿方法；结果表明从搜索起始即用多构造法生成异结构解以注入多样性具有价值；设计层面证伪了“强结构约束不可由元启发式处理”的预设。未来研究可拓展至随机、动态或多 depot 周期性路由设定，进一步弥合理论模型与操作计划需求间差距。