供需未匹配的多车场多车型多货品可拆分取送货车辆路径问题

doi:10.16381/j.cnki.issn1003-207x.2021.01.012

摘要/Abstract

摘要： 取送货车辆路径问题在多点调拨系统普遍存在，属于NP-hard问题。该问题研究通常需考虑车场数、车型种类、货品种类、客户服务次数等诸多因素，已有文献多假设客户间供需已匹配、单车场、单车型、单货品和取送货需求一次性满足，优化目标多设置为总路径最短。而从企业运营实践来看，运输方案不仅要规划客户间访问路径，还需进行客户间供需匹配；运输成本不仅与运距有关，还涉及运输货品的重量和派车成本；运输网络中多车场、多车型和多货品更加常见，且客户需求量往往大于车辆装载能力。因此，本文首次尝试基于"运距×运量"的车辆路径成本和基于额定吨位的固定派车成本之和最小为优化目标，建立同时考虑多车场、多车型、多货品、客户间供需未匹配和需求可拆分的取送货车辆路径问题模型，并设计基于大规模邻域搜索的迭代局部搜索求解算法。该算法采用基于运输效率提升的贪婪思想来快速构建高质量初始可行解，并通过引入四种移除算子、两种修复算子和车场车型调整优化策略形成大规模可行搜索邻域以增强全局寻优能力。基于18个文献算例和6个企业实例的数值实验结果表明：1）本文提出的算法在求解质量和求解效率方面均优于相关文献中的算法；2）相对人工调拨方案，本文设计的方案能够帮助企业节约33%的运输成本和21%的车次。本研究不仅可拓展取送货车辆路径问题现有理论，而且可为企业实际运营提供决策支持。

关键词: 车辆路径, 可拆分取送货, 供需未匹配, 多车场, 多车型

Abstract: In order to extend market shares and provide high quality services for regional customers, numerous large manufacturers and chain retailers have built nationwide production or selling networks.For instance, for a Chinese manufacturer with several regional factories across the whole country,each factory stores a certain amount of different materials. Frequently, some factories face the shortages of specific certain materials but are abundant with other materials. Hence, the manufacturer needs to make proper allocations among these factories to their demand. This problem has already drawn great attention from the academic world and is named as the vehicle routing problem with pickup and delivery(VRPPD).Current researches on VRPPD conventionally involving several factors, e.g., depot numbers,trucks types, commodity categories, service times of customers.Relevant literature generally assumes the paired supply-demand, single truck parking depot, homogeneous vehicles, single commodity and one-time service of the pickup and delivery request with the aim of obtaining the shortest total travelling distance.However, from the perspective of practical operations, a good planned transportation scheme not only includes well-arranged visiting routes of customers, but also comprises well-connected supply-demand pairs among customers. Moreover, it is rational to jointly consider the travelling distance and the weights of the commodities when evaluating the logistics transportation costs. Besides, multi-depot, heterogeneous trucks and multi-commodity are all common practices in transportation networks and customers' demands usually larger than the capacity of a single truck, all these should be considered for modeling.Therefore, a new VRPPD is buitt to minimize the total of the transportation cost (given by the travelling distances×the weight of transportation commodities) and the fixed cost of the dispatching trucks (based on tonnage) under the conditions of multi-depot, heterogeneous trucks, multi-commodity, unpaired supply-demand and the split request of pickup and delivery. An iterated local search algorithm based on a large neighborhood search strategy is presented, in which a greedy strategy for improving transportation efficiency to quickly obtain high-quality initial feasible solutions is applied. Moreover, to enhance the global searching ability of the proposed algorithm, four removal operators, two repair operators, depots &type-based truck adjustment strategies are introduced, which helps expand the large-scale feasible search neighborhood to the utmost. The effectiveness of the above model and algorithm is verified by 18 instances in related literature and 6 actual cases in an enterprise. The experimental results demonstrate that:1) The proposed algorithm is superior to the existing algorithm in terms of solution quality and solution time, when solving the closely related problem in the literature. 2) Comparing to the manual allocation scheme, the allocation scheme proposed in this paper can help enterprises to save 33% of transportation costs and 21% of vehicle number. The research not only extends the existing theory of VRPPD, but also provides decision support for enterprises at the practical interactive allocation operations.

Key words: vehicle routing, split pickup and delivery, unpaired supply-demand, multi-Depot, multi-typetrucks

中图分类号:

徐东洋, 李昆鹏, 崔利刚, 田倩南. 供需未匹配的多车场多车型多货品可拆分取送货车辆路径问题[J]. 中国管理科学, 2021, 29(1): 127-137.

XU Dong-yang, LI Kun-peng, CUI Li-gang, TIAN Qian-nan. Multi-commodity Unpaired Supply-demandand Split Pickup and Delivery Vehicle Routing Problem with Multi-depot and Multi-type Trucks[J]. Chinese Journal of Management Science, 2021, 29(1): 127-137.

参考文献

[1] 侯立文,谭家美,赵元.求解带时间窗的客户需求可分条件下的车辆路径问题[J].中国管理科学,2007,15(6):46-51.
[2] 符卓,刘文,邱萌.带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J].中国管理科学,2017,25(5):78-86.
[3] Battara M, Cordeau J F, Iori M. Chapter 6:Pickup-and-delivery problems for goods transportation[M]//Toth P Vigo D. (Eds.). Vehicle Routing:MOS-SIAM Series on Optimization-Society for Industrial and Applied Mathematics, 2014:161-192.
[4] Chen Qingfeng, Li Kunpeng, Liu Zhixue. Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads[J]. Transportation Research Part E:Logistics & Transportation Review, 2014, 69(3):218-235.
[5] Xu Dongyang, Li Kunpeng, Zou Xuxia, et al. An unpaired pickup and delivery vehicle routing problem with multi-visit[J]. Transportation Research Part E:Logistics & Transportation Review, 2017, 103:218-247.
[6] 陈希琼,胡大伟,杨倩倩,等.多目标同时取送货车辆路径问题的改进蚁群算法[J].控制理论与应用,2018,35(9):135-144.
[7] Nagy G, Wassan N A, Speranza M G, et al. The vehicle routing problem with divisible deliveries and pickups[J]. Transportation Science, 2015, 49(2):271-294.
[8] 王超,刘超,穆东,等.基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题[J].计算机集成制造系统,2018,24(03):570-582.
[9] Wang Chao, Mu Dong, Zhao Fu, et al. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows[J]. Computers & Industrial Engineering, 2015, 83:111-122.
[10] Wang Jiahai, Zhou Ying, Wang Yong, et al. Multiobjective vehicle routing problems with simultaneous delivery and pickup and time Windows:formulation, instances, and algorithms[J].IEEE Transactions on Cybernetics, 2015, 46, 582-594.
[11] 王旭坪,李新宇,张珺.考虑时空距离的异车型同时集送车辆路径优化[J].管理学报,2018, 15(6):918-926.
[12] Avci M, Topaloglu S. A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery[J]. Expert Systems with Applications, 2016, 53:160-171.
[13] 吴腾宇,陈嘉俊,蹇洁,等.O2O模式下的配送车辆实时取送货路径选择问题[J].系统工程理论与实践,2018,38(11):167-173.
[14] Agarwal Y K, Venkateshan P. A new model for the asymmetric vehicle routing problem with simultaneous pickup and deliveries[J]. Operations Research Letters, 2020, 48(1):48-54.
[15] Hernández-Pérez H, Salazar-Gonzalez J J. A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery[J]. Discrete Applied Mathematics, 2004a, 145:126-139.
[16] Hernández-Pérez H, Salazar-Gonzalez J J. The one-commodity pickup-and-delivery traveling salesman problem:Inequalities and algorithms[J]. Networks, 2007, 50(4):258-272.
[17] Salazar-Gonzalez J J, Santos-Hernández B. The split-demand one-commodity pickup-and-delivery travelling salesman problem[J]. Transportation Research Part B, 2015, 75:58-73.
[18] Hernández-Pérez H, Salazar-Gonzalez J J. Heuristics for the one-commodity pickup-and-delivery traveling salesman problem[J]. Transportation Science, 2004b, 38(2):245-255.
[19] Hernández-Pérez H, Rodríguez-Martín I, Salazar-González J J. A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery travelling salesman problem[J]. Computers & Operations Research, 2009, 36:1639-1645.
[20] Zhao Fanggeng, Li Sujian, Sun Jiangsheng, et al. Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem[J]. Computers & Industrial Engineering, 2009, 56::1642-1648.
[21] Mladenović N, Urošević D, Hanafi S, et al. A general variableneighborhood search for the one-commodity pickup-and-delivery travelling salesman problem[J]. European Journal of Operational Research, 2012,220(1):270-285.
[22] Hernández-Pérez H, Rodríguez-Martín I, Salazar-González J J. A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem[J]. European Journal of Operational Research, 2016, 251:44-52.
[23] Forma I A, Raviv T, Tzur M. A 3-step math heuristic for the static repositioning problem in bike-sharing systems[J]. Transportation Research Part B, 2015, 71:230-247.
[24] Alvarez-Valdes R, Belenguer J M, Benavent E, et al. Optimizing the level of service quality of a bike-sharing system[J]. Omega-international Journal of Management Science, 2016, 62(62):163-175.
[25] Bulhões T, Subramanian A, Erdoğan G, et al. The static bike relocation problem with multiple vehicles and visits[J]. European Journal of Operational Research, 2018, 264(2):508-523.
[26] Cui Ligang, Wang Lin, Deng Jie. RFID technology investment evaluation model for the stochastic joint replenishment and delivery problem[J]. Expert Systems With Applications, 2014, 41(4):1792-1805.
[27] Hernández-Pérez H, Salazar-González J J. The multi-commodity pickup-and-delivery traveling salesman problem[J]. Networks, 2014, 63(1):46-59.
[28] Hernández-Pérez H, Rodríguez-Martín I, Salazar-González J J. A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem[J]. European Journal of Operational Research, 2016, 251(1):44-52.
[29] Hennig F, Nygreen B, Christiansen M, et al. Maritime crude oil transportation-A split pickup and split delivery problem[J]. European Journal of Operational Research, 2012, 218(3):764-774.
[30] Hennig F, Nygreen B, Lubbecke M E. Nested column generation applied to the crude oil tanker routing and scheduling problem with split pickup and split delivery[J]. Naval Research Logistics, 2012, 59:298-310.
[31] 王征,张俊,王旭坪.多车场带时间窗车辆路径问题的变邻域搜索算法[J].中国管理科学,2011,19(2):99-109.
[32] 徐静.多时间窗的多车场同时取送货车辆路径问题研究[J]. 管理科学与工程, 2018, 7(2):125-131.
[33] 方文婷,艾时钟,王晴,等.基于混合蚁群算法的冷链物流配送路径优化研究[J].中国管理科学,2019,27(11):107-115.
[34] 潘雯雯,郭海湘,周光勇,等.基于两阶段算法的需求可拆分多车型车辆路径问题[J].中国管理科学,2016,24(SI):55-61.
[35] Tang Lixin, Wang Xianpeng. Iterated local search algorithm based on very large-scaleneighborhood for prize-collecting vehicle routing problem[J]. International Journal of Advanced Manufacturing Technology, 2006, 29:1246-1258.
[36] Coelhoa V N,Grasas A, Ramalhinhoc H. An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints[J]. European Journal of Operational Research, 2016, 250(2):367-376.
[37] Cattaruzza D, Absi N, Feillet D, et al. An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows[J]. Computers & Operations Research, 2014, 51:257-267.
[38] Brandão J. Iterated local search algorithm with ejection chains for the open vehiclerouting problem with time windows[J]. Computers & Industrial Engineering, 2018, 120:146-159.