[供应链调度]装卸一体化车辆路径问题的自适应并行遗传算法

摘要/Abstract

摘要： 为了同时实现总配送成本最低、车辆行驶距离最短、车辆数最小等目标，综合考虑车辆指派成本及运输路径成本，建立了装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性，提出了一种自适应并行遗传算法。算法以C-W节约法为基础,设计了三种基于双重需求的启发式种群初始化方法，缩小搜索空间并优化初始解；引入多样性种群和高质量种群的双种群并行策略，实现深度与广度的同步搜索；设计自适应交叉变异操作，改善高质量种群个体搜索停滞，并针对全局最优个体采用特殊变异的后优化操作以进一步提高全局优化性能。采用标准数据集作为算例进行寻优测试，验证了所提算法的可行性和有效性。

关键词: 装卸一体化车辆路径问题, 自适应并行遗传算法, 双种群并行策略, 后优化

Abstract: Considering both of dispatching costs of vehicles and travelling costs of routes，a mixed integer mathematical formulation of the VRPSPD was established to make the total delivery costs，the number of vehicles and the travel costs minimize simultaneously. An adaptive parallel genetic algorithm was proposed for solving the VRPSPD. Inspired by the C-W saving algorithm，three heuristic methods with two kinds of demands for initializing population were presented to reduce the search scopes and optimize the initial solutions. A bi-group parallel strategy with diversity population and high quality population was proposed to realize the synchronous search of depth and breadth. The adaptive genetic operations of crossover and mutation were applied to improve the stagnation of the search in high quality population. And based on a kind of special mutation a post-optimization was carried out for the global best individuals to further improve the global optimal performance. The feasibility and effectiveness of the proposed algorithm were verified by two instances based on standard dataset.

Key words: vehicle routing problem with simultaneous pickup and delivery(VRPSPD), adaptive parallel genetic algorithm, bi-group parallel strategy, post-optimization

中图分类号:

周蓉, 沈维蕾. [供应链调度]装卸一体化车辆路径问题的自适应并行遗传算法[J]. 中国机械工程.

ZHOU Rong, SHEN Weilei. An Adaptive Parallel Genetic Algorithm for VRPSPD[J]. China Mechanical Engineering.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: https://www.cmemo.org.cn/CN/

https://www.cmemo.org.cn/CN/Y2018/V29/I22/2740

参考文献

[1]THIERRY M，SALOMON M，VAN N J，et al.Strategic Issues in Product Recovery Management [J].Califonia Management Review，1995，37(2):114-135.
[2]郎茂祥.物流配送车辆调度问题的模型和算法研究[D].北京：北方交通大学，2002.
LANG Maoxiang.Study on Model and Algorithms of Logistics Distribution Vehicle Scheduling Problem [D].Beijing:Beijing Jiaotong University，2002.
[3]王科峰，叶春明，唐国春.节点具有双重需求的车辆路径问题及其性质[J].系统科学与数学，2011，31(10):1185-1196.
WANG Kefeng，YE Chunming，TANG Guochun.The Vehicle Routing Problem and Its Property with Nodes Having Double Demands [J].Journal of System Science and Mathematical，2011，31(10):1185-1196.
[4]TASAN A S，GEN M.A Genetic Algorithm Based Approach to Vehicle Routing Problem with Simultaneous Pick-up and Deliveries [J].Computers and Industrial Engineering，2012，62(3):755-761.
[5]NAGY G，SALHI S.Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Deliveries [J].European Journal of Operational Research，2005，162 (1):126-141.
[6]柳毅，余福茂，俞武扬.同时取送货车辆路径问题的改进人工鱼群算法[J].杭州电子科技大学学报，2014,34(3):34-37.
LIU Yi，YU Fumao，YU Wuyang.The Improved AFSA Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pickup [J].Journal of Hangzhou Dianzi University，2014，34(3):34-37.
[7]彭春林，梁春华，周泓.求解同时取货和送货车辆路径问题的改进遗传算法[J].系统仿真学报，2008，20(9):2266-2270.
PENG Chunlin，LIANG Chunhua，ZHOU Hong.Improved Genetic Algorithm for Vehicle Routing Problem with Simultaneous Pickups and Deliveries [J].Journal of System Simulation，2008，20(9):2266-2270.
[8]龙磊，陈秋双，华彦宁，等.具有同时集送货需求的车辆路径问题的粗粒度并行遗传算法[J].系统仿真学报，2009，21(7):1962-1968.
LONG Lei，CHEN Qiushuang，HUA Yanning，et al.Coarse-grained Parallel Genetic Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pick-up[J].Journal of System Simulation，2009，21(7):1962-1968.
[9]TANG F A，GALVO R D.A Tabu Search Algorithm for the Vehicle Routing Problems with Simultaneous Pickup and Delivery Service [J].Computers and Operations Research，2006，33(3):595-619.
[10]WASSAN N A，WASSAN A H，NAGY G.A Reactive Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pickups and Deliveries [J].Journal of Combinatorial Optimization，2008，15(4):368-386.
[11]WANG H F，CHEN Y Y.A Genetic Algorithm for the Simultaneous Delivery and Pickup Problems with Time Window [J].Computers and Industrial Engineering，2012,62 (1):84-95.
[12]POTVIN J，DUHAMEL C，GUERTIN F.A Genetic Algorithm for Vehicle Routing with Backhauling [J].Applied Intelligence，1996,6(4):345-355.
[13]PRINS C．A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem [J].Computers and Operations Research，2004，31(12):1985-2002.
[14]DUHAMEL C，LACOMME P，PRODHON C．A Hybrid Evolutionary Local Search with Depth First Search Split Procedure for the Heterogeneous Vehicle Routing Problems [J].Engineering Applications of Artificial of Intelligence，2012,25(2):345-358.
[15]CLARKE G，WRIGHT J W.Scheduling of Vehicles from a Central Depot to a Number of Delivery Points [J].Operations Research，1964，12(4):568-581.
[16]MESTER D，BRAYSY O，DULLAERT W.A Multi-parametric Evolution Strategies Algorithm for Vehicle Routing Problems [J].Expert Systems with Applications，2007，32(2):508-517.
[17]OSMAN I.Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problems [J].Annals of Operations Research，1993，41(4):421-451.
[18]STARKWEATHER T，MCDANIEL S，WHITLEY C，et al.A Comparison of Genetic Sequencing Operators [C]//Proceedings of the Fourth International Conference on Genetic Algorithms.San Diego，1991:69-76.
[19]PAN Q K，TASGETIREN M F，LIANG Y C.A Discrete Particle Swarm Optimization Algorithm for the No-wait Flowshop Scheduling Problem [J].Computers and Operations Research，2008，35(9):2807-2839.
[20]李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社，2001.
LI JUN，GUO Yaohuang.Theory and Methodology of Logistics Distribution Vehicle Optimization Scheduling[M].Beijing:China Materials Press，2001.
[21]AUGERAT P，BELENGUER J M，BENAVENT E，et al.Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem [R].Grenoble：ARTEMIS-IMAG，1998:1-24.