Minimax optimization approach for the robust vehicle routing problem with time windows and uncertain travel times

Abstract

This paper focuses on the robust vehicle routing problem with time windows (RVRPTW). It involves servicing a set of customers, with earliest and latest time deadlines, and a constant service time when the vehicle arrives to the customers. The various demands are served by capacitated vehicles with limited travel time to return to the depot. The objective is to find a robust solution that has the best worse-case performance over a set of possible scenarios under a robustness criterion. This paper proposes a two-phase algorithm to solve a minimax optimization problem with uncertain travel times. The algorithm includes the Modified Push-Forward Insertion Heuristic (MPFIH), a -interchange local search descent method (-LSD) and tabu search (TS). The experiments are based on a modified version of the VRPTW benchmarking problem R101 of Solomon by adding a level of uncertainty through a number of scenarios. The results show that the two-phase algorithm can find robust solutions in all conditions.