Decomposition approach for the distributionally robust vehicle routing problem with time window assignments
Maaike Hoogeboom  1, *@  , Yossiri Adulyasak  2@  , Wout Dullaert  1@  , Patrick Jaillet  3@  
1 : VU University Amsterdam  -  Website
De Boelelaan 1105, 1081 HV Amsterdam -  Netherlands
2 : HEC Montréal  (HEC Montréal)  -  Website
3 : Massachusetts Institute of Technology  (MIT)  -  Website
77 Massachusetts Ave, Cambridge, MA 02139 -  United States
* : Corresponding author

We present a solution framework for the robust vehicle routing problem with time window assignments under travel time uncertainty. The objective of the routing and time window decisions 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. The exact distributions of the uncertain travel time is not known whereas some statistics including the mean, minimum and maximum travel time are available. We extend the robust framework based on the requirements violation index and derive new subgradient cuts for the reformulation, which is solved by a branch-and-cut algorithm. Computational experiments were performed to demonstrate the performance of our approach and present the trade-off between expected travel time and risk of violating the time windows.

Online user: 1 RSS Feed