The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" The problem first appeared, as the truck dispatching problem, in a paper by George Dantzig and John Ramser in 1959, in which it was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. However, variants of the problem consider, e.g., collection of solid waste and the transport of the elderly and the sick to and from health-care facilities. The standard objective of the VRP is to minimise the total route cost. Other objectives, such as minimising the number of vehicles used or travelled distance are also considered. The VRP generalises the travelling salesman problem (TSP), which is equivalent to requiring a single route to visit all locations. As the TSP is NP-hard, the VRP is also NP-hard. VRP has many direct applications in industry. Vendors of VRP routing tools often claim that they can offer cost savings of 5%–30%. Commercial solvers tend to use heuristics due to the size and frequency of real world VRPs they need to solve.
Setting up the problem The VRP concerns the service of a delivery company. How things are delivered from one or more depots which has a given set of home vehicles and operated by a set of drivers who can move on a given road network to a set of customers. It asks for a determination of a set of routes, S, (one route for each vehicle that must start and finish at its own depot) such that all customers' requirements and operational constraints are satisfied and the global transportation cost is minimized. This cost may be monetary, distance or otherwise. The road network can be described using a graph where the arcs are roads and vertices are junctions between them. The arcs may be directed or undirected due to the possible presence of one way streets or different costs in each direction. Each arc has an associated cost which is generally its length or travel time which may be dependent on vehicle type. To know the global cost of each route, the travel cost and the travel time between each customer and the depot must be known. To do this our original graph is transformed into one where the vertices are the customers and depot, and the arcs are the roads between them. The cost on each arc is the lowest cost between the two points on the original road network. This is easy to do as shortest path problems are relatively easy to solve. This transforms the sparse original graph into a complete graph. For each pair of vertices i and j, there exists an arc (i,j) of the complete graph whose cost is written as C i j {\displaystyle C_{ij}} and is defined to be the cost of shortest path from i to j. The travel time t i j {\displaystyle t_{ij}} is the sum of the travel times of the arcs on the shortest path from i to j on the original road graph. Sometimes it is impossible to satisfy all of a customer's demands and in such cases solvers may reduce some customers' demands or leave some customers unserved. To deal with these situations a priority variable for each customer can be introduced or associated penalties for the partial or lack of service for each customer given The objective function of a VRP can be very different depending on the particular application of the result but a few of the more common objectives are:
Minimize the global transportation cost based on the global distance travelled as well as the fixed costs associated with the used vehicles and drivers Minimize the number of vehicles needed to serve all customers Least variation in travel time and vehicle load Minimize penalties for low quality service Maximize a collected profit/score.
VRP variants
Several variations and specializations of the vehicle routing problem exist:
Vehicle Routing Problem with Profits (VRPP) A maximization problem with profits attributed to each customer and costs (usually in terms of time) attributed to each arc (travel from customer to customer), and constraints on these profits and costs. The common subproblems of VRPP are:
Orienteering Problem (OP), where a price constraint (or time constraint) is given and the goal is to maximize the sum of collected profits while respecting the cost limit. Vehicles are required to start and end at the depot. Among the most known and studied OP are: The Team Orienteering Problem (TOP) which is the most studied variant of the VRPP, The Capacitated Team Orienteering Problem (CTOP), The TOP with Time Windows (TOPTW). Collecting Traveling Salesman Problem (PCTSP), in which The goal is to minimize the total cost, subject to the requirement that the collected profit exceeds a given value. Profitable Tour Problem (PTP), in which the goal is to maximize the difference between profit and cost.
Vehicle Routing Problem with Backhauling (VRPB) Disjoint sets of delivery and pickup customers are given. Goods have to be delivered from the depot to the delivery customer and from the pickup customers to the depot. Vehicles may be forbidden from picking up goods from customers until all carried goods have been delivered to delivery customers or allowed interchanging pickups with deliveries at a potential cost.
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.
… excerpt ends here. Continue reading the full article.
