基于带容量约束Memetic算法的动态车辆调度问题研究

曹云+向凤红+毛剑琳+郭宁

摘要：针对物流配送过程中带容量约束的动态车辆调度问题，提出一种Memetic算法，旨在最小化成本。Memetic算法中采用量子与遗传算法混合进行全局搜索，并根据搜索点目标函数变化率，设计了一种自适应量子旋转门更新方式，通过子代种群适应度变化确定量子旋转角大小与方向，明确了种群进化方向，扩展了全局搜索范围，引入了一种变异操作，使算法种群多样性得以保持，提高全局搜索宽度，采用2opt法结合swap法增强算法局部搜索能力。仿真实验验证了所提算法的有效性与优越性。

关键词关键词：动态车辆调度；Memetic算法；量子旋转门；全局搜索；局部搜索

DOIDOI：10.11907/rjdk.171984

中图分类号：TP319

文献标识码：A文章编号文章编号：16727800（2017）011012904

0引言

车輛调度问题（Vehicle Scheduling Problem， VSP）是典型NPhard问题，由Dantzing与Ramser[1]于1959年提出。动态车辆调度问题是指调度中心在优化之前所有与之相关信息是随时间变化的。由于动态车辆路径问题（Dynamic Vehicle Routing Problem， DVRP）更贴近于实际生活，其模型及研究算法与静态车辆调度有很大区别，近些年引起许多专家学者青睐。

带容量约束的动态车辆调度问题（Capacitated Dynamic Vehicle Routing Problem，DCVRP）广泛存在于物流配送行业。例如，快递公司收发业务、出租车公司预约电话服务、外卖订取以及垃圾收集等，随时会有新客户需求或原有客户需求量变更的情况，这时配送中心需要根据配送车辆容量、运输成本以及行驶路程进行配送。另外，为尽快达到配送要求，需实时调整配送路线。这个过程就是典型带容量约束的动态车辆调度问题。其优化目标主要包括最短行车路程、最小配送成本、最快完成时间以及最少配送车辆等。由于DVRP本身模型复杂性及求解难度，在理论以及应用上都有很高研究价值。

目前，用于解决DVRP的主流智能优化算法主要包括遗传算法（GA）[23]、模拟退火算法[45]、蚁群算法（ACA）[78]、粒子群算法（PSO）[9]、量子进化算法[1013]等。使用智能算法求解组合优化问题，已成为智能计算领域研究热点。

Memetic算法（ Memetic Algorithm，MA）是近年来进化计算领域一种新兴算法，由Moscato与Norman等[14]在1992年正式提出，并成功应用于TSP求解问题。Memetic算法提出一种灵活框架，在这个框架下，采用不同搜索策略可构成不同Memetic算法。在Memetic算法框架内，进化算法（Evolutionary Algorithm，EA）算子被用于执行广域搜索，局域搜索（Local Search，LS）策略被用于对某些个体执行局部改善，使得算法能够在探索与开发能力之间保持较好平衡。Memetic算法非常适合求解静态优化问题，研究者现已在函数优化问题、组合优化问题、车间调度问题、物流与供应链、神经网络训练、模糊系统控制等领域取得了良好效果，但在动态车辆调度中应用还很少。鉴于Memetic算法具有很强自适应能力、灵活性、高效性、可移植、并行性、鲁棒性、收敛性等特点，在研究动态问题上有很大优势。所以根据不同模型特点在模因算法框架内设计合适的进化迭代策略与局部搜索，提出有效解决方案非常有意义。

本文全局优化算法选择量子遗传混合算法，作为一种新混合量子算法，没有遗传算法选择、交叉、变异等操作，而是通过与种群中相邻两代优秀个体进行对比，并依据变化率构造与更新调整策略，然后根据新调整策略产生新种群，从而引导算法搜索方向。相对于遗传算法等传统智能优化算法，能从更宏观角度对问题解空间进行搜索，具有较好全局搜索性能。其局部搜索是选择了针对单条线路优化的2opt法与针对多条线路优化的swap算法，对初始状态与实时状态进行优化。仿真实验与算法比较验证了算法有效性与优越性。

1DCVRP问题描述及数学模型

一个车场有K辆车对m名客户进行服务，每辆车最大载重量为Q，每个各户需求量为qi，客户间距离为cij。服务过程中，客户需求实时动态变化，表现为新客户出现及原有客户需求量变化。优化目标为最小配送成本。将问题分为2个阶段解决，即预优化阶段与实时优化阶段，针对阶段不同分别建立不同数学模型。决策变量如下：

swap法局部搜索：采用swap算法对2条线路进行改进。对当前解中2条不同路径中的1点相互交换。若交换后解值相较原来解更优，则以swap法形成的新路线为更优解，否则以原行车路线为更优解，原理如图2所示。

图2swap法原理

2.4适应度值计算

根据染色体解码生成的调度路线，计算初始阶段与实时优化阶段行车路程与运输成本，若路线不满足要求，即超出容量限制，则赋给fitness一个很大的值。

2.5Memetic算法步骤

Memetic算法步骤如下：

step1：种群初始化，随机产生初始种群；

step2：染色体解码得到车辆配送路线；

step3：2opt法结合swap法对路径进行局部优化；

step4：计算适应值，保留最优个体；

step5：自适应量子门旋转门更新；

step6：量子比特种群进行变异操作；

step7：如果达到最大迭代次数，则输出最优路径，否则跳到step1。

由Memetic算法步骤可知，将量子旋转门改进为自适应量子旋转门，通过自适应量子旋转门操作，使算法获得更明确搜索方向与深度，提高算法全局搜索广泛性；通过变异操作，有效保持种群多样性，提高算法全局搜索宽泛性；通过引入针对单条线路优化的2opt法与线路间优化的swap法，提高了算法局部搜索能力。综上所述，基于Memetic算法的QGA在全局探索方式与局部搜索策略上均作了有效改进，算法有希望取得DVRP的优良解。endprint

3仿真实验与算法比较

本文为了对算法性能进行验证，将Memetic算法与量子遗传算法以及遗传算法作比较。所有算法程序均由MATLAB编码实现。每种算法均独立重复运行20次，每次最大迭代次数为100。

由于DVRP缺少标准测试实例库，所以数据是在边长为25km正方形区域内随机产生的17个固定需求客户，车场坐标为[18，70，15.29]，在t时刻随机产生3个新需求客户，其位置坐标与需求量分别为：C1（20.5，10.3），Q1=2；C2（23.0，15.0），Q2=3；C3（12.7，12.3），Q3=4。车场与17个客户坐标及其需求信息如表1所示。

对初始客户点进行求解，结果如表2所示。

t=5时，有3个新客户要求服务。其坐标位置与需求量在上面已经给出，此时对线路进行重新优化。由结果可知，车场已發出车5辆，分别位于11，10，15，7，12，除去已服务客户点9、4、14，实时阶段未服务客户与新客户是17个，根据第二阶段实时优化模型，计算结果如表3所示。

初始优化路线与在t=5时实时优化线路如图3所示。

由表4可知，Memetic算法在最优值、最劣值及平均值上都优于QGA与GA两种算法。求解DVRP时：①Memetic算法中自适应量子旋转门更新机制求解效果更为明显，因DVRP中不仅带有容量约束，而且对行车距离加以限制；②Memetic算法中加入变异操作后，解质量得以提高；③加入2opt法与swap法局部搜索，使解质量得到进一步优化。该算法表明采用改进全局搜索与有效局部搜索可获得问题优质解。

4结语

本文提出一种基于Memetic算法的量子遗传算法，用于求解动态车辆调度问题。在算法改进上，采用一种新策略更新量子旋转门，使算法搜索方向更明确；在此算法中引入了变异操作，种群多样性得以保持；加入2opt法与swap法减少子路线以及路线间交叉，使算法收敛速度得以提高。通过仿真实验比较验证了所提算法求解DVRP有效性与优越性。下一步研究将针对多车型动态车辆调度问题，设计有效全局搜索算法与局部搜索策略，并对其求解。

参考文献参考文献：

[1]G B DANTZIG， J H RAMSER.The truck dispatching problem[J].Management Science，1959（6）：8091.

[2]ALI HAGHANI，SOOJUNG JUNG.A dynamic vehicle routing problem with timedependent travel times[J].Computers & Operations Research，2005，32（11）：29592986.

[3]肖增敏.动态网络车辆路径问题研究[D].成都：西南交通大学，2005.

[4]WANG BIN，SHANG XINCHUN，LI HAIFENG.Hybrid simulated annealing algorithm for solving vehicle routing problem[J].Computer Engineering and Design，2009，30（3）：651653.

[5]SHIH WEI LIN，YU V.E，SHUO YAH CHOU.Solving the truck and trailer routing problem based on a simulated annealing heuristic[J].Computers&Operations Research，2009，36（5）：16831689.

[6]施玮.新型蚁群优化算法在带时间窗口的车辆路径问题中的应用[D].合肥：中国科学技术大学，2015.

[7]张红豆.基于蚁群算法的物流系统配送车辆路径优化问题研究[D].昆明：昆明理工大学，2015.

[8]彭勇.变需求车辆路线问题建模及基于lnverover操作的PSODP算法[J].系统工程理论与实践，2008（10）：7681.

[9]张景玲，赵燕伟，王海燕.多车型动态需求车辆路径问题建模及优化[J].计算机集成制造系统，2010，16（3）：543551.

[10]张景玲，王万良，赵燕伟.基于沿途补货的多配送中心动态需求VRP[J].计算机集成制造系统，2013，19（4）：869878.

[11]王万良，黄海鹏，赵燕伟，等.基于车辆共享的软时间窗动态需求车辆路径问题[J].计算机集成制造系统，2011，17（5）：162169.

[12]葛显龙，王旭，代应.基于混合量子遗传算法的随机需求车辆调度问题[J].系统工程，2011，29（3）：5359.

[13]王旭，葛显龙，代应.基于两阶段求解算法的动态车辆调度问题研究[J].控制与决策，2012，27（2）：175181.

[14]MOSCATO P，NORMAN M G.A memetic approach for the travelling salesman problem implementation of a computational ecology for combinatorial optimization on messagepassing systems[C]. Proceedings of the International Conference on Parallel Computing and Transport Applications，Amsterdam：IOS Press，1992：177186.

责任编辑（责任编辑：何丽）endprint