Real-Time Vehicle Routing: Solution Concepts, Algorithms and Parallel Computing Strategies - Ghiani, Guerriero, Laporte, Musmanno
Vehicle Routing Problems (VRPs) are central to logistics management both in the private and public sectors. They consist of determining optimal vehicle routes through a set of users, subject to side constraints. The most common operational constraints impose that the total demand carried by a vehicle at any time does not exceed a given capacity, the total duration of any route is not greater than a prescribed bound, and service time windows set by customers are respected. In wide area routing, vehicles are typically assigned one task at a time while in local area routing, tasks are of short duration (much shorter than a work shift) and a tour is to be built through a sequence of tasks.
There exist several important problems that must be solved in real time. In what follows, we review the main applications that motivate the research in the field of the real-time VRPs.
Dynamic fleet management
Several large scale trucking operations require realtime dispatching of vehicles for the purpose of collecting or delivering shipments. Important savings can be achieved by optimizing these operations.
Vendor-managed distribution systems
In vendor-managed systems, distribution companies estimate customer inventory level in such a way to replenish them before they run out of stock. Hence, demands are known beforehand in principle and all customers are static. However, because demand is uncertain, some customers (usually a small percentage) may run out of stock and have to be serviced urgently.
Long-distance courier need to collect locally outbound parcels before sending them to a remote terminal to consolidate loads. Also, loads coming from remote terminals have to be distributed locally. Most pick-up requests are dynamic and have to be serviced the same day if possible.
Rescue and repair service companies
There are several companies providing rescue or repair services (broken car rescue, appliance repair, etc.).
Dial-a-ride systems provide transportation services to people between given origin-destination pairs. Customers can book a trip one day in advance (static customers) or can try to be serviced few minutes in advance (dynamic customers).
Emergency services comprise police, fire fighting and ambulance services. By definition, all customers are dynamic. Moreover, the demand rate is usually low so that vehicles become idle from time to time. In this context, relocating idle vehicles in order to anticipate future demands or to escape from downtown rush hour traffic jam is a major issue.
Taxi Cab Services
In taxi cab services, almost every customer is dynamic. As in emergency services, relocating temporary idle vehicles is an issue.