Home About APEM Events News Sponsorship
Advances in Production Engineering & Management

Archives > Volume 17 | Number 1 | March 2022 > pp 121–133

Advances in Production Engineering & Management
Volume 17 | Number 1 | March 2022 | pp 121–133


A two-stage construction heuristic approach for vehicle routing problem with split deliveries and pickups: Case studies and performance comparison
Jin, C.; Lu, L.J.; Min, J.N.

The vehicle routing problem with split deliveries and pickups is a hot research topic in recent years, where a customer can be served multiple times with split deliveries and pickups. The objective is to minimize the travel distance, use the fewest number of vehicles and increase the load rate, which will further reduce the carbon emissions that damage the environment. In this paper, we use a two-stage construction heuristic approach to solve this problem. First, partitioning algorithms based on the multi-restart-iterative sweep algorithm are adopted to partition the customer domain into sub-domains according to the vehicle capacity, and to determine the split points and the corresponding values. Second, a modified Clarke-Wright savings algorithm is used to check the possibility of each point in each route based on the load of each point and the vehicle load limitation. The three case studies with 12 instances per each from the reconstructed Solomon benchmark datasets were conducted to evaluate the effectiveness and feasibility of the proposed approaches-Unsplit, Both-Split and Enhanced-Both-Split. The comparison among these approaches reveals that the splits reduce the total travel cost and vehicles used, and increase the average loading rate considerably, especially when customers have larger demand values. Our computation results proves that the vehicle routing problem with split deliveries and pickups is highly beneficial for transportation and logistics enterprises.

A R T I C L E   I N F O
Keywords • Vehicle routing; Split deliveries and pickups; Two-stage construction heuristic; Clustering first and routing later; Partitioning algorithms; Modified Clarke-Wright savings algorithm
Corresponding authorMin, J.N.
Article history • Received 15 October 2021, Revised 27 February 2022,Accepted 5 March 2022
Published on-line • 29 April 2022

E X P O R T   C I T A T I O N
» RIS format (EndNote, ProCite, RefWorks, and most other reference management software)
» BibTeX (JabRef, BibDesk, and other BibTeX-specific software)
» Plain text