ABSTRACT
In the previous chapter, we discussed a sales person performing jobs scattered across a geographical region and how most efficiently to schedule them. In transportation logistics, very often there is one (or possibly more) depot where vehicles are parked. Given a set of jobs to be performed, the goal is to route the vehicles to service the jobs in a cost-optimal fashion. 1 Obviously, in settings where the cost is primarily on the number of vehicles used, if a vehicle has infinite capacity, the cheapest plan may be to simply deploy a single vehicle to serve all jobs. Realistically however, vehicles are constrained by capacity. For example, each vehicle in a courier service can only deliver packages whose total volume is constrained by the size of the vehicle. We call such problem the Capacitated Vehicle Routing Problem (CVRP) or simply the Vehicle Routing Problem (VRP).
