Previous Articles     Next Articles

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