Stochastic vehicle routing with random time dependent travel times subject to perturbations

O. Jabali, T. Van Woensel, C. Lecluyse, H. Peremans, A.G. De Kok

Assigning and scheduling vehicle routes in a stochastic time dependent environment is a crucial management problem. The assumption that in a real-life environment everything goes according to an a priori determined static schedule is unrealistic, resulting in a planning gap (i.e. difference in performance between planned route and actual route). Our methodology introduces the traffic congestion component based on queueing theory, thereby introducing an analytical expression for the expected travel. In real life travel times are subject to uncertainty, we solve a time dependent vehicle routing problem to find robust solutions, that can potentially absorb such uncertainties. We model uncertainty as perturbations that are randomly inserted on the routes, we optimize the perturbed solutions via Tabu Search. We conduct experiments on a set of 32 cities, and found that the perturbed solutions generally cope better with the uncertainty than the non-perturbed solutions, with a small increase in expected travel times.

« Terug