Routing Optimization with Generalized Consistency Requirements

Kai Wang (), Lu Zhen (), Jun Xia (), Roberto Baldacci () and Shuaian Wang ()
Additional contact information
Kai Wang: Heinz College of Information Systems and Public Policy, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Lu Zhen: School of Management, Shanghai University, Shanghai 200444, China
Jun Xia: Sino-US Global Logistics Institute, Antai College of Economics & Management, Shanghai Jiao Tong University, Shanghai 200030, China
Roberto Baldacci: Department of Electrical, Electronic, and Information Engineering “Guglielmo Marconi,” University of Bologna, 47521 Cesena, Italy
Shuaian Wang: Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hong Kong

Transportation Science, 2022, vol. 56, issue 1, 223-244

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.

Keywords: vehicle routing; generalized consistency requirements; exact method; service efficiency (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.1072 (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:ortrsc:v:56:y:2022:i:1:p:223-244

Access Statistics for this article

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