The Robust Vehicle Routing Problem with Time Window Assignments

Maaike Hoogeboom (), Yossiri Adulyasak (), Wout Dullaert () and Patrick Jaillet ()
Additional contact information
Maaike Hoogeboom: Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands
Yossiri Adulyasak: Group for Research in Decision Analysis and HEC Montréal, Montréal H3T 2A7, Québec, Canada
Wout Dullaert: Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands
Patrick Jaillet: Department of Electrical Engineering and Computer Science, Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Transportation Science, 2021, vol. 55, issue 2, 395-413

Abstract: In practice, there are several applications in which logistics service providers determine the service time windows at the customers, for example, in parcel delivery, retail, and repair services. These companies face uncertain travel times and service times that have to be taken into account when determining the time windows and routes prior to departure. The objective of the proposed robust vehicle routing problem with time window assignments (RVRP-TWA) is to simultaneously determine routes and time window assignments such that the expected travel time and the risk of violating the time windows are minimized. We assume that the travel time probability distributions are not completely known but that some statistics, such as the mean, minimum, and maximum, can be estimated. We extend the robust framework based on the requirements’ violation index, which was originally developed for the case where the specific requirements (time windows) are given as inputs, to the case where they are also part of the decisions. The subproblem of finding the optimal time window assignment for the customers in a given route is shown to be convex, and the subgradients can be derived. The RVRP-TWA is solved by iteratively generating subgradient cuts from the subproblem that are added in a branch-and-cut fashion. Experiments address the performance of the proposed solution approach and examine the trade-off between expected travel time and risk of violating the time windows.

Keywords: vehicle routing; time window assignment; robust optimization; uncertain travel times (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/trsc.2020.1013 (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:55:y:2021:i:2:p:395-413

Access Statistics for this article

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