IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i15p3328-d1205652.html
   My bibliography  Save this article

An Improved Genetic Algorithm for the Granularity-Based Split Vehicle Routing Problem with Simultaneous Delivery and Pickup

Author

Listed:
  • Yuxin Liu

    (College of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

  • Zihang Qin

    (College of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

  • Jin Liu

    (College of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

Abstract

The Split Vehicle Routing Problem with Simultaneous Delivery and Pickup (SVRPSDP) consists of two subproblems, i.e., the Vehicle Routing Problem with Simultaneous Delivery and Pickup (VRPSDP) and the Split Delivery Vehicle Routing Problem (SDVRP). Compared to the subproblems, SVRPSDP is much closer to reality. However, some realistic factors are still ignored in SVRPSDP. For example, the shipments are integrated and cannot be infinitely subdivided. Hence, this paper investigates the Granularity-based Split Vehicle Routing Problem with Simultaneous Delivery and Pickup (GSVRPSDP). The characteristics of GSVRPSDP are that the demands of customers are split into individual shipments and both the volume and weight of each shipment are considered. In order to solve GSVRPSDP efficiently, a Genetic-Simulated hybrid algorithm (GA-SA) is proposed, in which Simulated Annealing (SA) is inserted into the Genetic Algorithm (GA) framework to improve the global search abilities of individuals. The experimental results indicate that GA-SA can achieve lower total costs of routes compared to the traditional meta-algorithms, such as GA, SA and Particle Swarm Optimization (PSO), with a reduction of more than 10%. In the further analysis, the space utilization and capacity utilization of vehicles are calculated, which achieve 86.1% and 88.9%, respectively. These values are much higher than those achieved by GA (71.2% and 74.8%, respectively) and PSO (60.9% and 65.7%, respectively), further confirming the effectiveness of GA-SA. And the superiority of simultaneous delivery and pickup is proved by comparing with separate delivery and pickup. Specifically, the costs of separate delivery and pickup are more than 80% higher than that of simultaneous delivery and pickup.

Suggested Citation

  • Yuxin Liu & Zihang Qin & Jin Liu, 2023. "An Improved Genetic Algorithm for the Granularity-Based Split Vehicle Routing Problem with Simultaneous Delivery and Pickup," Mathematics, MDPI, vol. 11(15), pages 1-15, July.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:15:p:3328-:d:1205652
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/15/3328/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/15/3328/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Sluijk, Natasja & Florio, Alexandre M. & Kinable, Joris & Dellaert, Nico & Van Woensel, Tom, 2023. "Two-echelon vehicle routing problems: A literature review," European Journal of Operational Research, Elsevier, vol. 304(3), pages 865-886.
    3. Maciek Nowak & Özlem Ergun & Chelsea C. White, 2008. "Pickup and Delivery with Split Loads," Transportation Science, INFORMS, vol. 42(1), pages 32-43, February.
    4. 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.
    5. Vincent F. Yu & Grace Aloina & Hadi Susanto & Mohammad Khoirul Effendi & Shih-Wei Lin, 2022. "Regional Location Routing Problem for Waste Collection Using Hybrid Genetic Algorithm-Simulated Annealing," Mathematics, MDPI, vol. 10(12), pages 1-23, June.
    6. Chen, Qingfeng & Li, Kunpeng & Liu, Zhixue, 2014. "Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 218-235.
    7. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    8. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    9. Khaoula Bouanane & Mohammed El Amrani & Youssef Benadada, 2022. "The vehicle routing problem with simultaneous delivery and pickup: a taxonomic survey," International Journal of Logistics Systems and Management, Inderscience Enterprises Ltd, vol. 41(1/2), pages 77-119.
    10. Kalayci, Can B. & Kulak, Osman & Günther, Hans-Otto, 2015. "A perturbation based variable neighborhood search heuristic for solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time LimitAuthor-Name: Polat, Olcay," European Journal of Operational Research, Elsevier, vol. 242(2), pages 369-382.
    11. Nowak, Maciek & Ergun, Ozlem & White III, Chelsea C., 2009. "An empirical study on the benefit of split loads with the pickup and delivery problem," European Journal of Operational Research, Elsevier, vol. 198(3), pages 734-740, November.
    12. Subramanian, Anand & Penna, Puca Huachi Vaz & Uchoa, Eduardo & Ochi, Luiz Satoru, 2012. "A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 221(2), pages 285-295.
    13. Aderemi Oluyinka Adewumi & Olawale Joshua Adeleke, 2018. "A survey of recent advances in vehicle routing problems," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(1), pages 155-172, February.
    14. Han Jiang & Yunlong Wu & Qing Zhang, 2020. "Optimization of Ordering and Allocation Scheme for Distributed Material Warehouse Based on IGA-SA Algorithm," Mathematics, MDPI, vol. 8(10), pages 1-17, October.
    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. Yang Xia & Tingying Wu & Beixin Xia & Junkang Zhang, 2023. "Truck-Drone Pickup and Delivery Problem with Drone Weight-Related Cost," Sustainability, MDPI, vol. 15(23), pages 1-15, November.

    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. Arslan, A.M. & Agatz, N.A.H. & Klapp, M., 2019. "Operational Strategies for On-demand Personal Shopper Services," ERIM Report Series Research in Management ERS-2019-009-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    2. 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.
    3. Qin, Hu & Moriakin, Anton & Xu, Gangyan & Li, Jiliu, 2024. "The generator distribution problem for base stations during emergency power outage: A branch-and-price-and-cut approach," European Journal of Operational Research, Elsevier, vol. 318(3), pages 752-767.
    4. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    5. John E. Fontecha & Oscar O. Guaje & Daniel Duque & Raha Akhavan-Tabatabaei & Juan P. Rodríguez & Andrés L. Medaglia, 2020. "Combined maintenance and routing optimization for large-scale sewage cleaning," Annals of Operations Research, Springer, vol. 286(1), pages 441-474, March.
    6. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    7. Richard Eglese & Sofoclis Zambirinis, 2018. "Disruption management in vehicle routing and scheduling for road freight transport: a review," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(1), pages 1-17, April.
    8. Regnier-Coudert, Olivier & McCall, John & Ayodele, Mayowa & Anderson, Steven, 2016. "Truck and trailer scheduling in a real world, dynamic and heterogeneous context," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 389-408.
    9. Ted Gifford & Tracy Opicka & Ashesh Sinha & Daniel Vanden Brink & Andy Gifford & Robert Randall, 2018. "Dispatch Optimization in Bulk Tanker Transport Operations," Interfaces, INFORMS, vol. 48(5), pages 403-421, October.
    10. 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.
    11. Yan Cheng Hsu & Jose L. Walteros & Rajan Batta, 2020. "Solving the petroleum replenishment and routing problem with variable demands and time windows," Annals of Operations Research, Springer, vol. 294(1), pages 9-46, November.
    12. Xian Cheng & Shaoyi Liao & Zhongsheng Hua, 2017. "A policy of picking up parcels for express courier service in dynamic environments," International Journal of Production Research, Taylor & Francis Journals, vol. 55(9), pages 2470-2488, May.
    13. Camélia Dadouchi & Bruno Agard, 2021. "Recommender systems as an agility enabler in supply chain management," Journal of Intelligent Manufacturing, Springer, vol. 32(5), pages 1229-1248, June.
    14. Briseida Sarasola & Karl Doerner & Verena Schmid & Enrique Alba, 2016. "Variable neighborhood search for the stochastic and dynamic vehicle routing problem," Annals of Operations Research, Springer, vol. 236(2), pages 425-461, January.
    15. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    16. 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).
    17. Wang, Jianxin & Lim, Ming K. & Liu, Weihua, 2024. "Promoting intelligent IoT-driven logistics through integrating dynamic demand and sustainable logistics operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 185(C).
    18. Shengbin Wang & Weizhen Rao & Yuan Hong, 2020. "A distance matrix based algorithm for solving the traveling salesman problem," Operational Research, Springer, vol. 20(3), pages 1505-1542, September.
    19. Epaminondas G. Kyriakidis & Theodosis D. Dimitrakos & Constantinos C. Karamatsoukis, 2020. "A Stochastic Single Vehicle Routing Problem with a Predefined Sequence of Customers and Collection of Two Similar Materials," Methodology and Computing in Applied Probability, Springer, vol. 22(4), pages 1559-1582, December.
    20. Roman Buil & Jesica de Armas & Daniel Riera & Sandra Orozco, 2021. "Optimization of the Real-Time Response to Roadside Incidents through Heuristic and Linear Programming," Mathematics, MDPI, vol. 9(16), pages 1-20, August.

    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:gam:jmathe:v:11:y:2023:i:15:p:3328-:d:1205652. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.