Title: Minimax optimisation approach for the Robust Vehicle Routing Problem with Time Windows and uncertain travel times

Authors: Tharinee Manisri; Anan Mungwattana; Gerrit K. Janssens

Addresses: Department of Industrial Engineering, Sripatum University (Bangkhen Campus), 61 Paholyothin Rd., Chatuchak, Bangkok 10900, Thailand. ' Center of Excellence in Logistics and Department of Industrial Engineering, Kasetsart University, 50 Paholyothin Rd., Chatuchak, Bangkok 10900, Thailand. ' Transportation Research Institute (IMOB), Hasselt University, Wetenschapspark Building 5, Box 6, 3590 Diepenbeek, Belgium

Abstract: This paper focuses on the Robust Vehicle Routing Problem with Time Windows (RVRPTW). The objective is to find a robust solution that has the best worst-case performance. This paper proposes a two-phase algorithm to solve a minimax optimisation problem with uncertain travel times. The algorithm includes the Modified Push-Forward Insertion Heuristic (MPFIH), a ?-interchange local search descent method and Tabu Search (TS). The experiments are based on a modified version of the Vehicle Routing Problem (VRP) with time windows benchmarking problem of Solomon. The results show that the two-phase algorithm can find robust solutions in all conditions.

Keywords: VRPTW; vehicle routing problems; time windows; routes; minimax optimisation; robust vehicle routing; uncertainty; travel times; worst-case performance; best-case performance; PFIH; push forward insertion heuristic; modified heuristics; lambda interchanges; local search descent methods; tabu search; benchmarking; Marius Solomon; two-phase algorithms; robust solutions; logistics systems; logistics management.

DOI: 10.1504/IJLSM.2011.043105

International Journal of Logistics Systems and Management, 2011 Vol.10 No.4, pp.461 - 477

Published online: 14 Oct 2011 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article