Vehicle routing problem
From Wikipedia, the free encyclopedia
The vehicle routing problem or VRP is a combinatorial optimization problem seeking to service a number of customers with a fleet of vehicles. Often the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. Implicit is the goal of minimizing the cost of distributing the goods. Many methods have been developed for searching for good solutions to the problem, but for all but the smallest problems, finding global minimum for the cost function is computationally complex.
[edit] Variations
Several variations and specializations of the vehicle routing problem exist:
- Vehicle Routing Problem with Pickup and Delivery (VRPPD): A number of goods need to be moved from certain pickup locations to other delivery locations. The goal is to find optimal routes for a fleet of vehicles to visit the pickup and drop-off locations.
- Vehicle Routing Problem with LIFO: In this context LIFO stands for Last In First Out. Similar to the VRPPD, except an additional restriction is placed on the loading of the vehicles: at any delivery location, the item being delivered must be the item most recently picked up. This scheme reduces the loading and unloading times at delivery locations because there is never any need to temporarily unload items to get to the items needing to be dropped off.
