A New Exact Algorithm for Single-Commodity Vehicle Routing with Split Pickups and Deliveries

Jiliu Li (), Zhixing Luo (), Roberto Baldacci (), Hu Qin () and Zhou Xu ()
Additional contact information
Jiliu Li: School of Management, Northwestern Polytechnical University, Xi’an 710072, China
Zhixing Luo: School of Management and Engineering, Nanjing University, Nanjing 210008, China
Roberto Baldacci: Engineering Management and Decision Sciences, College of Science and Engineering, Hamad Bin Khalifa University, Doha 34110, Qatar
Hu Qin: School of Management, Huazhong University of Science and Technology, Wuhan 430074, China
Zhou Xu: Faculty of Business, The Hong Kong Polytechnic University, Hong Kong

INFORMS Journal on Computing, 2023, vol. 35, issue 1, 31-49

Abstract: We present a new exact algorithm to solve a challenging vehicle routing problem with split pickups and deliveries, named as the single-commodity split-pickup and split-delivery vehicle routing problem (SPDVRP). In the SPDVRP, any amount of a product collected from a pickup customer can be supplied to any delivery customer, and the demand of each customer can be collected or delivered multiple times by the same or different vehicles. The vehicle fleet is homogeneous with limited capacity and maximum route duration. This problem arises regularly in inventory and routing rebalancing applications, such as in bike-sharing systems, where bikes must be rebalanced over time such that the appropriate number of bikes and open docks are available to users. The solution of the SPDVRP requires determining the number of visits to each customer, the relevant portions of the demands to be collected from or delivered to the customers, and the routing of the vehicles. These three decisions are intertwined, contributing to the hardness of the problem. Our new exact algorithm for the SPDVRP is a branch-price-and-cut algorithm based on a pattern-based mathematical formulation. The SPDVRP relies on a novel label-setting algorithm used to solve the pricing problem associated with the pattern-based formulation, where the label components embed reduced cost functions, unlike those classical components that embed delivered or collected quantities, thus significantly reducing the dimension of the corresponding state space. Extensive computational results on different classes of benchmark instances illustrate that the newly proposed exact algorithm solves several open SPDVRP instances and significantly improves the running times of state-of-the-art algorithms.

Keywords: vehicle routing; single commodity; split pickups; split deliveries; branch-price-and-cut; label-setting algorithm; exact algorithm (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)
http://dx.doi.org/10.1287/ijoc.2022.1249 (application/pdf)

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:inm:orijoc:v:35:y:2023:i:1:p:31-49

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().