Portal de Periódicos da CAPES

Exact Algorithms for the Vehicle Routing Problem

1987; Elsevier BV; Linguagem: Inglês

10.1016/s0304-0208(08)73235-3

2212-1048

Gilbert Laporte, Yves Nobert,

Optimization and Packing Problems

This chapter describes vehicle routing problem (VRP) as the problem of designing optimal delivery routes from one or more depots to a set of geographically scattered points, cities, or customers. Practical applications of the VRP are numerous and encompass many spheres of activity. The VRP has received the attention of many Operations researchers over the past three decades. This interest is not only because of the practical importance of the problem, but also its intrinsic difficulty. The largest problems of any complexity that had been solved by exact algorithms contained approximately 30 points. The VRP constitutes a generalization of the travelling salesman problem (TSP) that consists of determining the shortest circuit or cycle passing through each of n points only once. The TSP and the VRP are both NP-hard. However, from a practical point of view, VRPs are in general much more difficult to solve than TSPs of the same size. Effort has been devoted to the solution of the TSP by exact methods; most algorithms for the VRP are heuristics, reflecting the relative difficulty of the problem. The chapter presents a survey of exact algorithms for the VRP, emphasizing recent results.