The robust vehicle routing problem with time window assignments

Maaike Hoogeboom, Yossiri Adulyasak, Wout Dullaert, Patrick Jaillet

Research output: Contribution to JournalArticleAcademicpeer-review

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.

Original languageEnglish
Pages (from-to)395-413
Number of pages19
JournalTransportation Science
Volume55
Issue number2
Early online date15 Feb 2021
DOIs
Publication statusPublished - Mar 2021

Bibliographical note

Funding Information:
Funding: This research was enabled, in part, by support provided by Compute Canada and the Netherlands Organisation for Scientific Research [Grant 407-13-050]. This support is gratefully acknowledged. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2020.1013.

Publisher Copyright:
© 2021 INFORMS Inst.for Operations Res.and the Management Sciences. All rights reserved.

Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

Keywords

  • Robust optimization
  • Time window assignment
  • Uncertain travel times
  • Vehicle routing

Fingerprint

Dive into the research topics of 'The robust vehicle routing problem with time window assignments'. Together they form a unique fingerprint.

Cite this