Title: Vehicle routing problem with real-time travel times

Authors: Irena Okhrin, Knut Richter

Addresses: Department of Information & Operations Management, European University Viadrina, P.O. Box 1786, 15207 Frankfurt (Oder), Germany. ' Department of Industrial Management, European University Viadrina, P.O. Box 1786, 15207 Frankfurt (Oder), Germany

Abstract: The paper considers a vehicle routing problem with time windows and real-time travel times. We assume the deployment of an information and communication system that is based on mobile technologies, which provides a real-time mobile connection between the dispatching centre and drivers, allows localising vehicles on road, and gives the online overview over traffic conditions. We explicitly incorporate the possibility to react to some dynamic events like traffic impediments and divert a vehicle en route away from its current destination. We formulated the vehicle routing problem with real-time travel times as a mixed-integer linear programming model and developed a genetic algorithm to solve it. Moreover, we performed an extensive computational study to prove the efficiency of the proposed algorithm on well-known static benchmarks and to test its performance in dynamic settings.

Keywords: vehicle routing; time-dependent; real-time travel times; mobile information systems; mobile communications; genetic algorithms; ICT; vehicle communications; vehicle localisation; traffic conditions; modelling; mixed-integer linear programming; MILP.

DOI: 10.1504/IJVICS.2009.027746

International Journal of Vehicle Information and Communication Systems, 2009 Vol.2 No.1/2, pp.59 - 77

Received: 30 Apr 2008
Accepted: 24 Mar 2009

Published online: 09 Aug 2009 *

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