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

Jiliu Li, Zhixing Luo, Roberto Baldacci, Hu Qin, Zhou Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)31-49
Number of pages19
JournalINFORMS Journal on Computing
Volume35
Issue number1
DOIs
Publication statusPublished - Jan 2023

Keywords

  • branch-price-and-cut
  • exact algorithm
  • label-setting algorithm
  • single commodity
  • split deliveries
  • split pickups
  • vehicle routing

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'A New Exact Algorithm for Single-Commodity Vehicle Routing with Split Pickups and Deliveries'. Together they form a unique fingerprint.

Cite this