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

Yuxin Liu (), Zihang Qin and Jin Liu
Additional contact information
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

Mathematics, 2023, vol. 11, issue 15, 1-15

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.

Keywords: vehicle routing problem; granularity; split; simultaneous delivery and pickup; simulated annealing; genetic algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/15/3328/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/15/3328/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:15:p:3328-:d:1205652

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().