Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW

Vitória Pureza, Reinaldo Morabito*, Marc Reimann

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

75 Citations (Scopus)


In real life distribution of goods, relatively long service times may make it difficult to serve all requests during regular working hours. These difficulties are even greater if the beginning of the service in each demand site must occur within a time window and violations of routing time restrictions are particularly undesirable. We address this situation by considering a variant of the vehicle routing problem with time windows for which, besides routing and scheduling decisions, a number of extra deliverymen can be assigned to each route in order to reduce service times. This problem appears, for example, in the distribution of beverage and tobacco in highly dense Brazilian urban areas. We present a mathematical programming formulation for the problem, as well as a tabu search and an ant colony optimization heuristics for obtaining minimum cost routes. The performance of the model and the heuristic approaches are evaluated using instances generated from a set of classic examples from the literature.

Original languageEnglish
Pages (from-to)636-647
Number of pages12
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 1 May 2012


Dive into the research topics of 'Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW'. Together they form a unique fingerprint.

Cite this