### A Tight Approximation Algorithm for Multi-Vehicle CVRP with Unsplittable Demands on a Line

WU Yuanxiao, LU Xiwen

1. School of Science, East China University of Science and Technology, Shanghai 200237, China
• Received:2020-11-05 Revised:2021-08-18 Online:2022-10-25 Published:2022-10-12
• Supported by:
This research was supported by the National Natural Science Foundation of China under Grant Nos.11871213 and 71431004

WU Yuanxiao, LU Xiwen. A Tight Approximation Algorithm for Multi-Vehicle CVRP with Unsplittable Demands on a Line[J]. Journal of Systems Science and Complexity, 2022, 35(5): 1902-1909.

In this paper,the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable demand.The objective is to find a transportation scheme to minimize the longest distance traveled by a single vehicle such that all the customers are served without violating the capacity constraint.The authors show that this problem has no polynomialtime algorithm with performance ratio less than 2 on condition that PNP,and then provide a 2-approximation algorithm.
 [1] Gao Q and Lu X W, The complexity and on-line algorithm for automated storage and retrieval system with stacker cranes on one rail, Journal of Systems Science&Complexity, 2016, 29(5):1302-1319.[2] Hamaguchi S and Katoh N, A capacitated vehicle routing problem on a tree, International Symposium on Algorithms and Computation, Springer, Berlin, Heidelbarg, 1998, 399-407.[3] Zhang T H, Zhao F, Zhang J L, et al., An approximation of the customer waiting time for online restaurants owning delivery system, Journal of Systems Science&Complexity, 2019, 32(3):907-931.[4] Dantzig G and Ramser J, The truck dispatching problem, Management Science, 1959, 6(1):80-91.[5] Altinkemer K and Gavish B, Heuristics for unequal weight delivery problem with a fixed error guarantee, Operational Research Letters, 1987, 6:149-158.[6] Altinkemer K and Gavish B, Heuristics for delivery problems with constant error guarantees, Transportation Science, 1990, 24:294-297.[7] Asano T, Katoh N, and Kawashima K, A new approximation algorithm for the capacitated vehicle routing problem on a tree, Journal of Combinatorial Optimization, 2001, 5(2):213-231.[8] Becker A, A tight 4/3 approximation for capacitated vehicle routing in trees, Leibniz International Proceedings in Informatics, 2018, 116(1):3-13.[9] Labbé M, Laporte G, and Mercure H, Capacitated vehicle routing on trees, Operations Research, 1991, 39(4):616-622.[10] Zhang G C, Cai X Q, Lee C Y, et al., Minimizing makespan on a single batch processing machine with nonidentical job sizes, Naval Research Logistics, 2001, 48(3):226-240.[11] Dósa G, Tan Z Y, Tuza Z, et al., Improve bounds for batch scheduling with nonidentical job sizes, Naval Research Logistics, 2014, 61(5):351-358.[12] Dósa G and Sgall J, First fit bin packing:A tight analysis, Proceedings of the 30th Symposium on Theoretical Aspects of Computer Science (ed. by Portier N and Wilke T), Kiel, 2013.[13] Wu Y X and Lu X W, Capacitated vehicle routing problem on line with unsplittable demands, Journal of Combinatorial Optimization, 2020, DOI:10.1007/s10878-020-00565-5.
 [1] GAO Jie, ZHAO Junchan. Fixed-Time Synchronization of Complex Networks via Intermittent Control Without Sign Function [J]. Journal of Systems Science and Complexity, 2022, 35(5): 1748-1760. [2] FAN Naqi, ZHANG Lijun, ZHANG Shenggui, LIU Jiuqiang. Matching Algorithms of Minimum Input Selection for Structural Controllability Based on Semi-Tensor Product of Matrices [J]. Journal of Systems Science and Complexity, 2022, 35(5): 1808-1823. [3] BAI Yun, WANG Shouyang, ZHANG Xun. Foreign Trade Survey Data:Do They Help in Forecasting Exports and Imports? [J]. Journal of Systems Science and Complexity, 2022, 35(5): 1839-1862. [4] ZHU Juanping, MENG Qi, CHEN Wei, WANG Yue, MA Zhiming. Constructing the Basis Path Set by Eliminating the Path Dependency [J]. Journal of Systems Science and Complexity, 2022, 35(5): 1944-1962. [5] LIU Mingshuo, FANG Yong, DONG Huanhe. Equilibria and Stability Analysis of Cohen-Grossberg BAM Neural Networks on Time Scale [J]. Journal of Systems Science and Complexity, 2022, 35(4): 1348-1373. [6] WU Fan, KONG Xinbing, XU Chao. Test on Stochastic Block Model: Local Smoothing and Extreme Value Theory [J]. Journal of Systems Science and Complexity, 2022, 35(4): 1535-1556. [7] WANG Chen, WANG Lu, XUE Yanbo, LI Ruiqi. Revealing Spatial Spillover Effect in High-Tech Industry Agglomeration from a High-Skilled Labor Flow Network Perspective [J]. Journal of Systems Science and Complexity, 2022, 35(3): 839-859. [8] LUO Jing, QIN Hong. Asymptotic in the Ordered Networks with a Noisy Degree Sequence [J]. Journal of Systems Science and Complexity, 2022, 35(3): 1137-1153. [9] ZHAO Yuzhuo, MA Dan, MA Hongwei. Adaptive Neural Network Control of Thermoacoustic Instability in Rijke Tube: A Fully Actuated System Approach [J]. Journal of Systems Science and Complexity, 2022, 35(2): 586-603. [10] GUO Yingxin, GE Shuzhi Sam, ARBI Adnène. Stability of Traveling Waves Solutions for Nonlinear Cellular Neural Networks with Distributed Delays [J]. Journal of Systems Science and Complexity, 2022, 35(1): 18-31. [11] MO Lipo, YU Yongguang, REN Guojian, YUAN Xiaolin. Constrained Consensus of Continuous-Time Heterogeneous Multi-Agent Networks with Nonconvex Constraints and Delays [J]. Journal of Systems Science and Complexity, 2022, 35(1): 105-122. [12] ZHANG Xuxin · LIU Yanzhang · ZHANG Ya. A Secure Clock Synchronization Scheme for Wireless Sensor Networks Against Malicious Attacks [J]. Journal of Systems Science and Complexity, 2021, 34(6): 2125-2138. [13] NIAN Fuzhong · LI Jia. The Module-Phase Synchronization of Complex-Valued Neural Networks with Time-Varying Delay and Stochastic Perturbations [J]. Journal of Systems Science and Complexity, 2021, 34(6): 2139-2154. [14] ZHU Juanping · MENG Qi · CHEN Wei · MA Zhiming. Interpreting the Basis Path Set in Neural Networks [J]. Journal of Systems Science and Complexity, 2021, 34(6): 2155-2167. [15] LUAN Yangyang · BAO Zhongkui · ZHANG Haifeng. Identifying Influential Spreaders in Complex Networks by Considering the Impact of the Number of Shortest Paths [J]. Journal of Systems Science and Complexity, 2021, 34(6): 2168-2181.
Viewed
Full text

Abstract