IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0195457.html
   My bibliography  Save this article

Tabu search algorithm for the distance-constrained vehicle routing problem with split deliveries by order

Author

Listed:
  • Yangkun Xia
  • Zhuo Fu
  • Lijun Pan
  • Fenghua Duan

Abstract

The vehicle routing problem (VRP) has a wide range of applications in the field of logistics distribution. In order to reduce the cost of logistics distribution, the distance-constrained and capacitated VRP with split deliveries by order (DCVRPSDO) was studied. We show that the customer demand, which can’t be split in the classical VRP model, can only be discrete split deliveries by order. A model of double objective programming is constructed by taking the minimum number of vehicles used and minimum vehicle traveling cost as the first and the second objective, respectively. This approach contains a series of constraints, such as single depot, single vehicle type, distance-constrained and load capacity limit, split delivery by order, etc. DCVRPSDO is a new type of VRP. A new tabu search algorithm is designed to solve the problem and the examples testing show the efficiency of the proposed algorithm. This paper focuses on constructing a double objective mathematical programming model for DCVRPSDO and designing an adaptive tabu search algorithm (ATSA) with good performance to solving the problem. The performance of the ATSA is improved by adding some strategies into the search process, including: (a) a strategy of discrete split deliveries by order is used to split the customer demand; (b) a multi-neighborhood structure is designed to enhance the ability of global optimization; (c) two levels of evaluation objectives are set to select the current solution and the best solution; (d) a discriminating strategy of that the best solution must be feasible and the current solution can accept some infeasible solution, helps to balance the performance of the solution and the diversity of the neighborhood solution; (e) an adaptive penalty mechanism will help the candidate solution be closer to the neighborhood of feasible solution; (f) a strategy of tabu releasing is used to transfer the current solution into a new neighborhood of the better solution.

Suggested Citation

  • Yangkun Xia & Zhuo Fu & Lijun Pan & Fenghua Duan, 2018. "Tabu search algorithm for the distance-constrained vehicle routing problem with split deliveries by order," PLOS ONE, Public Library of Science, vol. 13(5), pages 1-19, May.
    • Handle: RePEc:plo:pone00:0195457
    DOI: 10.1371/journal.pone.0195457
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0195457
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0195457&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0195457?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    2. Sana Jawarneh & Salwani Abdullah, 2015. "Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows," PLOS ONE, Public Library of Science, vol. 10(7), pages 1-23, July.
    3. Baozhen Yao & Bin Yu & Ping Hu & Junjie Gao & Mingheng Zhang, 2016. "An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot," Annals of Operations Research, Springer, vol. 242(2), pages 303-320, July.
    4. Dong, Zhijie & Turnquist, Mark A., 2015. "Combining service frequency and vehicle routing for managing supplier shipments," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 79(C), pages 231-243.
    5. Archetti, Claudia & Bianchessi, Nicola & Speranza, M. Grazia, 2014. "Branch-and-cut algorithms for the split delivery vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 685-698.
    6. Salani, Matteo & Vacca, Ilaria, 2011. "Branch and price for the vehicle routing problem with discrete split deliveries and time windows," European Journal of Operational Research, Elsevier, vol. 213(3), pages 470-477, September.
    7. Zhuo Fu & Richard Eglese & Mike Wright, 2007. "A Branch-And-Bound Algorithm For Finding All Optimal Solutions Of The Assignment Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 24(06), pages 831-839.
    8. Belfiore, PatrI´cia & Yoshida Yoshizaki, Hugo Tsugunobu, 2009. "Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil," European Journal of Operational Research, Elsevier, vol. 199(3), pages 750-758, December.
    9. Z Fu & R Eglese & L Y O Li, 2005. "A new tabu search heuristic for the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(3), pages 267-274, March.
    10. Luo, Zhixing & Qin, Hu & Zhang, Dezhi & Lim, Andrew, 2016. "Adaptive large neighborhood search heuristics for the vehicle routing problem with stochastic demands and weight-related cost," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 85(C), pages 69-89.
    11. Q Mu & Z Fu & J Lysgaard & R Eglese, 2011. "Disruption management of the vehicle routing problem with vehicle breakdown," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(4), pages 742-749, April.
    12. Dezhi Zhang & Xin Wang & Shuangyan Li & Nan Ni & Zhuo Zhang, 2018. "Joint optimization of green vehicle scheduling and routing problem with time-varying speeds," PLOS ONE, Public Library of Science, vol. 13(2), pages 1-20, February.
    13. Leonardo Berbotto & Sergio García & Francisco Nogales, 2014. "A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem," Annals of Operations Research, Springer, vol. 222(1), pages 153-173, November.
    14. Han, Anthony Fu-Wha & Chu, Yu-Ching, 2016. "A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 11-31.
    15. Maryam Mousavi & Hwa Jen Yap & Siti Nurmaya Musa & Farzad Tahriri & Siti Zawiah Md Dawal, 2017. "Multi-objective AGV scheduling in an FMS using a hybrid of genetic algorithm and particle swarm optimization," PLOS ONE, Public Library of Science, vol. 12(3), pages 1-24, March.
    16. Zhixing Luo & Hu Qin & Wenbin Zhu & Andrew Lim, 2017. "Branch and Price and Cut for the Split-Delivery Vehicle Routing Problem with Time Windows and Linear Weight-Related Cost," Transportation Science, INFORMS, vol. 51(2), pages 668-687, May.
    17. C. Archetti & M. G. Speranza & A. Hertz, 2006. "A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 40(1), pages 64-73, February.
    18. Moshe Dror & Pierre Trudeau, 1989. "Savings by Split Delivery Routing," Transportation Science, INFORMS, vol. 23(2), pages 141-145, May.
    19. Z Fu & R Eglese & L Y O Li, 2008. "A unified tabu search algorithm for vehicle routing problems with soft time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 663-673, May.
    20. Hiermann, Gerhard & Puchinger, Jakob & Ropke, Stefan & Hartl, Richard F., 2016. "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations," European Journal of Operational Research, Elsevier, vol. 252(3), pages 995-1018.
    21. Wang, Haijun & Du, Lijing & Ma, Shihua, 2014. "Multi-objective open location-routing model with split delivery for optimized relief distribution in post-earthquake," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 160-179.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yangkun Xia & Zhuo Fu & Sang-Bing Tsai & Jiangtao Wang, 2018. "A New TS Algorithm for Solving Low-Carbon Logistics Vehicle Routing Problem with Split Deliveries by Backpack—From a Green Operation Perspective," IJERPH, MDPI, vol. 15(5), pages 1-12, May.
    2. Sadati, Mir Ehsan Hesam & Çatay, Bülent, 2021. "A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    3. Horațiu Florian & Camelia Avram & Mihai Pop & Dan Radu & Adina Aștilean, 2023. "Resources Relocation Support Strategy Based on a Modified Genetic Algorithm for Bike-Sharing Systems," Mathematics, MDPI, vol. 11(8), pages 1-32, April.
    4. Diana Puspita Sari & Nur Aini Masruroh & Anna Maria Sri Asih, 2021. "Extended Maximal Covering Location and Vehicle Routing Problems in Designing Smartphone Waste Collection Channels: A Case Study of Yogyakarta Province, Indonesia," Sustainability, MDPI, vol. 13(16), pages 1-23, August.
    5. Hanafi, Saïd & Wang, Yang & Glover, Fred & Yang, Wei & Hennig, Rick, 2023. "Tabu search exploiting local optimality in binary optimization," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1037-1055.
    6. Zhang, Zhenzhen & Che, Yuxin & Liang, Zhe, 2024. "Split-demand multi-trip vehicle routing problem with simultaneous pickup and delivery in airport baggage transit," European Journal of Operational Research, Elsevier, vol. 312(3), pages 996-1010.
    7. Alarcon Ortega, Emilio J. & Schilde, Michael & Doerner, Karl F., 2020. "Matheuristic search techniques for the consistent inventory routing problem with time windows and split deliveries," Operations Research Perspectives, Elsevier, vol. 7(C).
    8. Weikang Fang & Zailin Guan & Peiyue Su & Dan Luo & Linshan Ding & Lei Yue, 2022. "Multi-Objective Material Logistics Planning with Discrete Split Deliveries Using a Hybrid NSGA-II Algorithm," Mathematics, MDPI, vol. 10(16), pages 1-30, August.
    9. Vincent F. Yu & Winarno & Achmad Maulidin & A. A. N. Perwira Redi & Shih-Wei Lin & Chao-Lung Yang, 2021. "Simulated Annealing with Restart Strategy for the Path Cover Problem with Time Windows," Mathematics, MDPI, vol. 9(14), pages 1-22, July.
    10. Min-Xia Zhang & Hong-Fan Yan & Jia-Yu Wu & Yu-Jun Zheng, 2020. "Quarantine Vehicle Scheduling for Transferring High-Risk Individuals in Epidemic Areas," IJERPH, MDPI, vol. 17(7), pages 1-17, March.
    11. Xiaxia Ma & Wenliang Bian & Wenchao Wei & Fei Wei, 2022. "Customer-Centric, Two-Product Split Delivery Vehicle Routing Problem under Consideration of Weighted Customer Waiting Time in Power Industry," Energies, MDPI, vol. 15(10), pages 1-23, May.
    12. Fan, Tijun & Pan, Qianlan & Pan, Fei & Zhou, Wei & Chen, Jingyi, 2020. "Intelligent logistics integration of internal and external transportation with separation mode," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yangkun Xia & Zhuo Fu & Sang-Bing Tsai & Jiangtao Wang, 2018. "A New TS Algorithm for Solving Low-Carbon Logistics Vehicle Routing Problem with Split Deliveries by Backpack—From a Green Operation Perspective," IJERPH, MDPI, vol. 15(5), pages 1-12, May.
    2. Gizem Ozbaygin & Oya Karasan & Hande Yaman, 2018. "New exact solution approaches for the split delivery vehicle routing problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 85-115, March.
    3. Jianli Shi & Jin Zhang & Kun Wang & Xin Fang, 2018. "Particle Swarm Optimization for Split Delivery Vehicle Routing Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(02), pages 1-42, April.
    4. Daqing Wu & Chenxiang Wu, 2022. "Research on the Time-Dependent Split Delivery Green Vehicle Routing Problem for Fresh Agricultural Products with Multiple Time Windows," Agriculture, MDPI, vol. 12(6), pages 1-28, May.
    5. Xiaxia Ma & Wenliang Bian & Wenchao Wei & Fei Wei, 2022. "Customer-Centric, Two-Product Split Delivery Vehicle Routing Problem under Consideration of Weighted Customer Waiting Time in Power Industry," Energies, MDPI, vol. 15(10), pages 1-23, May.
    6. Grigorios D. Konstantakopoulos & Sotiris P. Gayialis & Evripidis P. Kechagias, 2022. "Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification," Operational Research, Springer, vol. 22(3), pages 2033-2062, July.
    7. Bortfeldt, Andreas & Yi, Junmin, 2020. "The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 282(2), pages 545-558.
    8. Han, Anthony Fu-Wha & Chu, Yu-Ching, 2016. "A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 11-31.
    9. Xu, Dongyang & Li, Kunpeng & Zou, Xuxia & Liu, Ling, 2017. "An unpaired pickup and delivery vehicle routing problem with multi-visit," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 218-247.
    10. Weikang Fang & Zailin Guan & Peiyue Su & Dan Luo & Linshan Ding & Lei Yue, 2022. "Multi-Objective Material Logistics Planning with Discrete Split Deliveries Using a Hybrid NSGA-II Algorithm," Mathematics, MDPI, vol. 10(16), pages 1-30, August.
    11. Nicola Bianchessi & Stefan Irnich, 2016. "Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows," Working Papers 1620, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    12. Sophie N. Parragh & Jorge Pinho de Sousa & Bernardo Almada-Lobo, 2015. "The Dial-a-Ride Problem with Split Requests and Profits," Transportation Science, INFORMS, vol. 49(2), pages 311-334, May.
    13. Matteo Salani & Maria Battarra, 2018. "The opportunity cost of time window violations," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(4), pages 343-361, December.
    14. Berbotto, Leonardo & García, Sergio & Nogales, Francisco J., 2011. "A vehicle routing model with split delivery and stop nodes," DES - Working Papers. Statistics and Econometrics. WS ws110906, Universidad Carlos III de Madrid. Departamento de Estadística.
    15. Salani, Matteo & Vacca, Ilaria, 2011. "Branch and price for the vehicle routing problem with discrete split deliveries and time windows," European Journal of Operational Research, Elsevier, vol. 213(3), pages 470-477, September.
    16. Ozgur Kabadurmus & Mehmet S. Erdogan, 2023. "A green vehicle routing problem with multi-depot, multi-tour, heterogeneous fleet and split deliveries: a mathematical model and heuristic approach," Journal of Combinatorial Optimization, Springer, vol. 45(3), pages 1-29, April.
    17. Puca Huachi Vaz Penna & Anand Subramanian & Luiz Satoru Ochi & Thibaut Vidal & Christian Prins, 2019. "A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet," Annals of Operations Research, Springer, vol. 273(1), pages 5-74, February.
    18. Qiuping Ni & Yuanxiang Tang, 2023. "A Bibliometric Visualized Analysis and Classification of Vehicle Routing Problem Research," Sustainability, MDPI, vol. 15(9), pages 1-37, April.
    19. Cortes, Juan David & Suzuki, Yoshinori, 2020. "Vehicle Routing with Shipment Consolidation," International Journal of Production Economics, Elsevier, vol. 227(C).
    20. Coelho, V.N. & Grasas, A. & Ramalhinho, H. & Coelho, I.M. & Souza, M.J.F. & Cruz, R.C., 2016. "An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints," European Journal of Operational Research, Elsevier, vol. 250(2), pages 367-376.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0195457. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.