VRP variants
A map showing the relationship between common VRP subproblems.
Several variations and specializations of the vehicle routing problem exist:
Vehicle Routing Problem with Profits (VRPP): A maximization problem where it is not mandatory to visit all customers. The aim is to visit once customers maximizing the sum of collected profits while respecting a vehicle time limit. Vehicles are required to start and end at the depot. Among the most known and studied VRPP, we cite:
The Team Orienteering Problem (TOP) which is the most studied variant of the VRPP,[5][6][7]
The Capacitated Team Orienteering Problem (CTOP),
The TOP with Time Windows (TOPTW).
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: 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 no need to temporarily unload items other than the ones that should be dropped off.
Vehicle Routing Problem with Time Windows (VRPTW): The delivery locations have time windows within which the deliveries (or visits) must be made.
Capacitated Vehicle Routing Problem: CVRP or CVRPTW. The vehicles have a limited carrying capacity of the goods that must be delivered.
Vehicle Routing Problem with Multiple Trips (VRPMT): The vehicles can do more than one route.
Open Vehicle Routing Problem (OVRP): Vehicles are not required to return to the depot.
Inventory Routing Problem (IRP): Vehicles are responsible for satisfying the demands in each delivery point [8]
Multi-Depot Vehicle Routing Problem (MDVRP): Multiple depots exist from which vehicles can start and end.[9]
Several software vendors have built software products to solve various VRP problems. Numerous articles are available for more detail on their research and results.
Although VRP is related to the Job Shop Scheduling Problem, the two problems are typically solved using different techniques.[10]