Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo‐polynomial model

Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo‐polynomial model

0.00 Avg rating0 Votes
Article ID: iaor20117325
Volume: 214
Issue: 3
Start Page Number: 536
End Page Number: 545
Publication Date: Nov 2011
Journal: European Journal of Operational Research
Authors: , , , ,
Keywords: time windows
Abstract:

In this paper, we address a variant of the vehicle routing problem called the vehicle routing problem with time windows and multiple routes. It considers that a given vehicle can be assigned to more than one route per planning period. We propose a new exact algorithm for this problem. Our algorithm is iterative and it relies on a pseudo‐polynomial network flow model whose nodes represent time instants, and whose arcs represent feasible vehicle routes. This algorithm was tested on a set of benchmark instances from the literature. The computational results show that our method is able to solve more instances than the only other exact method described so far in the literature, and it clearly outperforms this method in terms of computing time.

Reviews

Required fields are marked *. Your email address will not be published.