Routing Optimization with Generalized Consistency Requirements

Kai Wang, Lu Zhen, Jun Xia, Roberto Baldacci, Shuaian Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

The consistent vehicle routing problem (ConVRP) aims to design synchronized routes on multiple days to serve a group of customers while minimizing the total travel cost. It stipulates that customers should be visited at roughly the same time (time consistency) by several familiar drivers (driver consistency). This paper generalizes the ConVRP for any level of driver consistency and additionally addresses route consistency, which means that each driver can traverse at most a certain proportion of different arcs of routes on planning days, which guarantees route familiarity. To solve this problem, we develop two set partitioning-based formulations, one based on routes and the other based on schedules. We investigate valid lower bounds on the linear relaxations of both of the formulations that are used to derive a subset of columns (routes and schedules); within the subset are columns of an optimal solution for each formulation. We then solve the reduced problem of either one of the formulations to achieve an optimal solution. Numerical results show that our exact method can effectively solve most of the medium-sized ConVRP instances in the literature and can also solve some newly generated instances involving up to 50 customers. Our exact solutions explore some managerial findings with respect to the adoption of consistency measures in practice. First, maintaining reasonably high levels of consistency requirements does not necessarily always lead to a substantial increase in cost. Second, a high level of time consistency can potentially be guaranteed by adopting a high level of driver consistency. Third, maintaining high levels of time consistency and driver consistency may lead to lower levels of route consistency.

Original languageEnglish
Pages (from-to)223-244
Number of pages22
JournalTransportation Science
Volume56
Issue number1
DOIs
Publication statusPublished - Jan 2022

Keywords

  • Exact method
  • Generalized consistency requirements
  • Service efficiency
  • Vehicle routing

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Fingerprint

Dive into the research topics of 'Routing Optimization with Generalized Consistency Requirements'. Together they form a unique fingerprint.

Cite this