Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model |
| |
Authors: | Rita Macedo JM Valério de Carvalho |
| |
Institution: | a Centro de Investigação Algoritmi da Universidade do Minho, Escola de Engenharia, Universidade do Minho, 4710-057 Braga, Portugal b Université des Sciences et Technologies de Lille, LIFL UMR CNRS 8022, INRIA Bâtiment INRIA, Parc de la Haute Borne, 59655 Villeneuve d’Ascq, France c LAMIH-SIADE, UMR 8530, Université de Valenciennes et du Hainaut-Cambrésis, Le Mont Houy, 59313 Valenciennes Cedex 9, France |
| |
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. |
| |
Keywords: | Integer programming Combinatorial optimization Routing Network flows |
本文献已被 ScienceDirect 等数据库收录! |
|