History

The problem of vehicle routing or routing (VRP) dates from the year of 1959 and was introduced by Dantzig and Ramser, who described an application actual delivery of gasoline to service stations and proposed a formulation math. Five years later, Clarke and Wright proposed the first algorithm that It proved effective to solve it.

And this is how great research began and work in the area of ​​vehicle routing. This problem can be understood as the intersection of two known problems of combinatorial optimization. The first, the traveling agent (TSP, traveling salesman problem) considering the capacity of each automobile as infinite and that of packaging in compartments (BPP, bin packing problem).

The problem of optimizing vehicle routes involves determining a route plan, frequencies, schedules, allocation of personnel and fleet, as far as possible optimal. This process is can decompose in stages as follows: Route design: number of lines and the layout of its routes. Determination of frequencies: of passes for each line, eventually variable in time.