Two-Level Bat Algorithm with Variable Neighborhood Search for Capacitated Vehicle Routing Problem in Supply Chain
QI Yuan-hang1, CAI Yan-guang2, CAI Hao3, YANG Liang1, YAO Yeboah2
1. School of Computer Science, University of Electronic Science and Technology of China, Zhongshan Institute, Zhongshan, Guangdong 528402, China;
2. School of Automation, Guangdong University of Technology, Guangzhou, Guangdong 510006, China;
3. Department of Health Science and Technology, Aalborg University, Aalborg 9220, Denmark
摘要 本文考虑了多个供应商、多个制造商和多个零售商的三级供应链物流运输调度，以最大限度地降低采购、加工和运输成本为目标，提出了带容量约束的供应链物流运输调度模型（Capacitated Vehicle Routing Problem in Supply Chain，CVRPSC）.进一步地，本文构造了求解CVRPSC的双层变邻域蝙蝠算法（Two-Level Bat Algorithm with Variable Neighborhood Search，TLBAVNS）.该算法提出了一种双层蝙蝠位置的定义，引入了相应的蝙蝠算法的更新操作，采用变邻域局部搜索策略加强算法的寻优能力.实验证明：TLBAVNS能在合理的时间内求解CVRPSC；在大部分测试算例中，该算法相对于对比算法均表现出了更强的寻优能力和稳定性.
Abstract：Considering a two-level vehicle routing problem in a three-echelon supply chain with multiple suppliers,multiple manufacturers and multiple stockists,with the aim of minimizing the cost of purchasing,production and transportation,this paper proposes a model for the capacitated vehicle routing problem in supply chain (CVRPSC).Further,a two-level bat algorithm with variable neighborhood search (TLBAVNS) is presented to solve CVRPSC.The algorithm proposes a definition of two-level bat position and introduces the corresponding operations of the bat algorithm.In addition,a variable neighborhood local search is proposed to enhance the optimizing capability of TLBAVNS.The experiments have shown that TLBAVNS can effectively solve the instances of CVRPSC within a suitable amount of time and significantly outperforms all the other alternatives in most of the cases.
戚远航, 蔡延光, 蔡颢, 杨亮, YAO Yeboah. 带容量约束的供应链物流运输调度问题的双层变邻域蝙蝠算法[J]. 电子学报, 2019, 47(7): 1434-1442.
QI Yuan-hang, CAI Yan-guang, CAI Hao, YANG Liang, YAO Yeboah. Two-Level Bat Algorithm with Variable Neighborhood Search for Capacitated Vehicle Routing Problem in Supply Chain. Acta Electronica Sinica, 2019, 47(7): 1434-1442.
[1] CÓCCOLA M E,ZAMARRIPA M,MÉ NDEZ C A,et al.Toward integrated production and distribution management in multi-echelon supply chains[J].Computers & Chemical Engineering,2013,57(41):78-94.
[2] PAPAGEORGIOU L G.Supply chain optimisation for the process industries:Advances and opportunities[J].Computers & Chemical Engineering,2009,33(12):1931-1938.
[3] SETAK M,HABIBI M,KARIMI H,et al.A time-dependent vehicle routing problem in multigraph with FIFO property[J].Journal of Manufacturing Systems,2015,35(35):37-45.
[4] Uday M APTE,VISWANATHAN S.Effective cross docking for improving distribution efficiencies[J].International Journal of Logistics Research & Applications,2000,3(3):291-302.
[5] RAFIE-MAJD Z,PASANDIDEH S H R,NADERI B.Modelling and solving the integrated inventory-location-routing problem in a multi-period and multi-perishable product supply chain with uncertainty:Lagrangian relaxation algorithm[J].Computers & Chemical Engineering,2018,109:9-22.
[6] POURHEJAZY P,KWON O K.The new generation of operations research methods in supply chain optimization:A review[J].Sustainability,2016,8(10):1033.
[7] KUMAR A,ZHANG K Y J.A cross docking pipeline for improving pose prediction and virtual screening performance[J].Journal of Computer-Aided Molecular Design,2018,32(1):163-173.
[8] QIU Y,WANG L,XU X,et al.Formulations and branch-and-cut algorithms for multi-product multi-vehicle production routing problems with startup cost[J].Expert Systems with Applications,2018,98:1-10.
[9] ENDERER F,CONTARDO C,CONTRERAS I.Integrating dock-door assignment and vehicle routing with cross-docking[J].I Computers & Operations Research,2017,88:30-43.
[10] Golshahi-Roudbaneh A,Hajiaghaei-Keshteli M,Paydar M M.Developing a lower bound and strong heuristics for a truck scheduling problem in a cross-docking center[J].Knowledge-Based Systems,2017,129:17-38.
[11] WEN M,LARSEN J,CLAUSEN J,et al.Vehicle routing with cross-docking[J].Journal of the Operational Research Society,2009,60(12):1708-1718.
[12] ROHRER M.Simulation and cross docking[A].Proceedings of the 1995 Simulation Conference[C].USA:IEEE,1995.846-849.
[13] SHARMA S.Supply chain management:Concepts,practices & implementation,1/e[J].Journal of Cellular Biochemistry,2008,105(2):524-533.
[14] YU W,EGBELUB P J.Scheduling of inbound and outbound trucks in cross docking systems with temporary storage[J].European Journal of Operational Research,2008,184(1):377-396.
[15] CHANDRA P,FISHER M L.Coordination of production and distribution planning[J].European Journal of Operational Research,1994,72(3):503-517.
[16] LIU S.On the integrated production,inventory,and distribution routing problem[J].ⅡE Transactions,2006,38(11):955-970.
[17] QIU Y,QIAO J,PARDALOS P M.A branch-and-price algorithm for production routing problems with carbon cap-and-trade[J].Omega,2017,68:49-61.
[18] KONUR D,GOLIAS M M.Cost-stable truck scheduling at a cross-dock facility with unknown truck arrivals:A meta-heuristic approach[J].Transportation Research Part E Logistics & Transportation Review,2013,49(1):71-91.
[19] 戚远航,蔡延光,蔡颢,等.旅行商问题的混沌混合离散蝙蝠算法[J].电子学报,2016,44(10):2543-2547. QI Yuan-hang,CAI Yan-guang,CAI Hao,et al.Chaotic hybrid discrete bat algorithm for traveling salesman problem[J].Acta Electronica Sinica,2016,44(10):2543-2547.(in Chinese)
[20] 戚远航,蔡延光,蔡颢,等.带时间窗的车辆路径问题的离散蝙蝠算法[J].电子学报,2018,46(3):672-679. QI Yuan-hang,CAI Yan-guang,CAI Hao,et al.Discrete bat algorithm for vehicle routing problem with time window[J].Acta Electronica Sinica,2018,46(3):672-679.(in Chinese)
[21] YANG X S.A new metaheuristic bat-inspired algorithm[J].Computer Knowledge & Technology,2010,284:65-74.
[22] RIZK-ALLAH R M,HASSANIEN A E.New binary bat algorithm for solving 0-1 knapsack problem[J].Complex & Intelligent Systems,2018,4(1):31-53.
[23] WANG G G,CHU H C E,MIRJALILI S.Three-dimensional path planning for UCAV using an improved bat algorithm[J].Aerospace Science & Technology,2016,49:231-238.
[24] 李阳,范厚明.求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法[J].控制与决策,2018,33(7):1190-1198. LI Yang,FAN Hou-ming.Hybrid variable neighborhood symbiotic organisms search for capacitated vehicle routing problem[J].Control and Decision,2018,33(7):1190-1198.(in Chinese)
[25] ISHIBUCHI H,YOSHIDA T,MURATA T.Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling[J].IEEE Transactions on Evolutionary Computation,2003,7(2):204-223.
[26] JABIR E,PANICKER V V,SRIDHARAN R.Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem[J].Transportation Research Part D Transport & Environment,2017,57:422-457.
[27] SICILIA J A,QUEMADA C,ROYO B.An optimization algorithm for solving the rich vehicle routing problem based on Variable Neighborhood Search and Tabu Search metaheuristics[J].Journal of Computational & Applied Mathematics,2016,291(C):468-477.
[28] XIAO Y,ZHAO Q,KAKU I,et al.Variable neighbourhood simulated annealing algorithm for capacitated vehicle routing problems[J].Engineering Optimization,2014,46(4):562-579.
[29] HIERMANN G,PUCHINGER J,ROPKE S,et al.The electric fleet size and mix vehicle routing problem with time windows and recharging stations[J].European Journal of Operational Research,2016,252(3):995-1018.
[30] 周永权,黄正新,刘洪霞.求解TSP问题的离散型萤火虫群优化算法[J].电子学报,2012,40(6):1164-1170. ZHOU Yong-quan,HUANG Zheng-xin,LIU Hong-xia.Discrete glowworm swarm optimization algorithm for TSP problem[J].Acta Electronica Sinica,2012,40(6):1164-1170.(in Chinese)
[31] ZHANG Y,WANG S,JI G.A comprehensive survey on particle swarm optimization algorithm and its applications[J].Mathematical Problems in Engineering,2015,1:1-38.
[32] SRIKANTH G U,GEETHA R.Task scheduling using ant colony optimization in multicore architectures:a survey[J].Soft Computing,2018,22(15):5179-5196.
2019, Vol. 47 
