Vehicle Routing and Scheduling

Introduction The Vehicle Routing Problem (VRP) was introduced by Dantzig and Ramser (1959) as the truck dispatching problem. They presented the problem of distributing gasoline from a bulk terminal to a set of service stations. The VRP, as defined by Dantzig and Ramser (1959), modeled a distribution problem where goods had to be delivered from a central depot to a set of customers or demand points. The VRP differs from the Traveling Salesman Problem (TSP) (Applegate et al., 2006) because a fleet of vehicles is stationed at the depot. Each vehicle can deliver goods to customers, but the goods carried by a vehicle cannot exceed its capacity. The VRP requires that we generate a route for each vehicle (a closed circuit starting and ending at the depot) such that the demand of each customer is satisfied and the transportation costs are minimized.