The Consistent Vehicle Routing Problem considering path consistency in a road network

Yu Yao (Corresponding author), Tom van Woensel, Luuk P. Veelenturf, Pengli Mo

Research output: Contribution to journalArticleAcademicpeer-review

20 Citations (Scopus)
163 Downloads (Pure)

Abstract

This paper investigates a new variant of the consistent vehicle routing problem considering path consistency based on the underlying road network (ConVRP RN). It is the problem of determining a set of consistent paths for vehicles within a certain period (e.g. a week). We propose a flexible strategy to achieve path consistency, providing a discount for the cost of roads that are traversed every day. The objective is to minimize the total travel costs considering the discount for the paths’ consistent parts. We formulate the problem as a set partitioning model and a general arc-flow model, and then solve the problem by a branch-price-and-cut algorithm. The algorithm is based on a two-layer network, including an underlying road-network graph (lower layer) and a serial of customer-based graphs (upper layer). Furthermore, an innovative aggregation technique is proposed to accelerate the algorithm, which is specifically designed for ConVRP RN. Finally, we construct a road network based on the real road-network structure of West Jordan and demonstrate the effectiveness of our approach on a set of numerical experiments. The impact of consistency discount is also analyzed to provide information and inspiration for tactical decision making.

Original languageEnglish
Pages (from-to)21-44
Number of pages24
JournalTransportation Research. Part B: Methodological
Volume153
DOIs
Publication statusPublished - Nov 2021

Keywords

  • Branch-price-and-cut algorithm
  • Consistency
  • Road network
  • VRP

Fingerprint

Dive into the research topics of 'The Consistent Vehicle Routing Problem considering path consistency in a road network'. Together they form a unique fingerprint.

Cite this