Selfimposed time windows in vehicle routing probl

Authors: Ola Jabali Roel Leus Tom Van Woensel Ton de Kok

Publish Date: 2013/10/02

Volume: 37, Issue: 2, Pages: 331-352

PDF Link

Abstract

We observe selfimposed time windows SITW whenever a logistics service provider quotes a delivery time window to his customer Once this time window is communicated the company strives to respect it as well as possible We incorporate these SITW within the framework of the vehicle routing problem VRP Essential to SITW is the fact that the time window is determined by the carrier company and not by the customer The resulting VRPSITW is inherently different from the wellstudied VRP with time windows VRPTW in that in the latter problem the time windows are exogenous constraints imposed by the customers The second important element of the problem studied in this paper is the uncertainty in the travel times The basic mechanism of dealing with this uncertainty is the allocation of time buffers throughout the routes which absorb disruptions We propose a heuristic solution approach combining an LP model and a local search heuristic A tabu search heuristic assigns customers to vehicles and establishes the order of visit of the customers per vehicle Detailed timing decisions are subsequently generated by the LP model whose output also guides the local search in a feedback loop We test our algorithm on a number of benchmark instances for the VRP and VRPTW We highlight the costs involved in integrating SITW with the VRP and we underline the advantages of SITW as compared to VRPTW

Keywords: