Vehicle routing problem: Difference between revisions

Revision as of 10:22, 3 July 2025

Latest revision as of 11:21, 26 August 2025

(16 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Optimization problem}}

{{like essay|date=December 2021}}

[[File:FigureIllustration illustratingof the vehicleVehicle routingRouting problemProblem.pngsvg|thumb|AAn figureillustration illustratingof an instance of the vehicle routing problem in a road network, containing routes for three vehicles to deliver goods from a central depot (D) to 11 locations.]]

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,<ref name=DantzigRamser1959>{{cite journal|last=Dantzig|first=George Bernard|author2=Ramser, John Hubert |title=The Truck Dispatching Problem|journal=Management Science|date=October 1959|volume=6|issue=1|pages=80–91|url=http://andresjaquep.files.wordpress.com/2008/10/2627477-clasico-dantzig.pdf|doi=10.1287/mnsc.6.1.80}}</ref> 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.<ref>{{cite journal |last1=Fisher |first1=Marshall L. |last2=Jaikumar |first2=Ramchandran |title=A generalized assignment heuristic for vehicle routing |journal=Networks |date=June 1981 |volume=11 |issue=2 |pages=109–124 |doi=10.1002/net.3230110205}}</ref> However, variants of the problem consider, e.g, collection of [[Municipal solid waste|solid waste]]<ref>{{cite book |last1=Shuster |first1=Kenneth A. |last2=Schur |first2=Dennis A. |title=Heuristic Routing for Solid Waste Collection Vehicles |date=1974 |publisher=U.S. Environmental Protection Agency}}</ref> and the transport of the elderly and the sick to and from health-care facilities.<ref>{{cite journal |last1=Cordeau |first1=Jean-François |last2=Laporte |first2=Gilbert |title=The dial-a-ride problem: models and algorithms |journal=Annals of Operations Research |date=July 2007 |volume=153 |issue=1 |pages=29-46 |doi=10.1007/s10479-007-0170-8}}</ref><ref>{{cite journal |last1=Cappart |first1=Quentin |last2=Thomas |first2=Charles |last3=Schaus |first3=Pierre |last4=Rousseau |first4=Louis-Martin |title=A Constraint Programming Approach for Solving Patient Transportation Problems |journal=Principles and Practice of Constraint Programming |date=2018 |volume=11008 |pages=490–506 |doi=10.1007/978-3-319-98334-9_32|hdl=2078.1/202079 |hdl-access=free }}</ref> The standard objective of the VRP is to minimizeminimise the total route cost.<ref Inname="toth" 1964/>{{rp|5}} Other objectives, Clarkesuch andas Wrightminimising improvedthe onnumber Dantzigof andvehicles Ramser'sused approachor usingtravelled andistance effectiveare [[greedyalso algorithm]]considered.<ref>{{cite calledjournal the|last1=Gaskell savings|first1=T. algorithmJ.{{Citation needed|title=Bases for Vehicle Fleet Scheduling |journal=Journal of the Operational Research Society |date=September 1967 |volume=18 |issue=3 |pages=281–295 |doi=10.1057/jors.1967.44}}</ref>

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.<ref name=toth>{{cite book |editor=Toth, P. |editor2=Vigo, D. |title=The Vehicle Routing Problem |volume=9 |series=Monographs on Discrete Mathematics and Applications |year=2002 |publisher=Society for Industrial and Applied Mathematics |___location=Philadelphia |isbn=0-89871-579-2}}</ref>{{rp|5}}

VRP has many direct applications in industry. Vendors of VRP routing tools often claim that they can offer cost savings of 5%–30%.<ref name="Springer Verlag">{{cite book |url=https://books.google.com/books?id=UMI5GzcNd8wC&q=%22vendors+of+routing+tools%22 |title=Geometric Modelling, Numerical Simulation, and Optimization:: Applied Mathematics at SINTEF |date=2007 |publisher=Springer Verlag |isbn=978-3-540-68783-2 |editor=Geir Hasle |___location=Berlin |pages=397–398 |editor2=Knut-Andreas Lie |editor3=Ewald Quak}}</ref> Commercial solvers tend to use [[Heuristic|heuristics]] due to the size and frequency of real world VRPs they need to solve.{{Citation needed|date=July 2025}}

== Setting up the problem ==

Line 29:

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 citeare:

** The Team Orienteering Problem (TOP) which is the most studied variant of the VRPP,<ref>{{cite journal |last1=Chao |first1=I-Ming |last2=Golden |first2=Bruce L |last3=Wasil |first3=Edward A |title=The Team Orienteering Problem |journal=European Journal of Operational Research |date=1996 |volume=88 |issue=3 |pages=464–474 |doi=10.1016/0377-2217(94)00289-4}}</ref><ref>{{cite book|author=Archetti, C.|author2=Sperenza, G.|author3=Vigo, D. | editor1 = Toth, P. | editor2 = Vigo, D.|year=2014|chapter=Vehicle routing problems with profits|title=Vehicle Routing: Problems, Methods, and Applications | edition=Second |doi=10.1137/1.9781611973594.ch10|pages=273–297}}</ref><ref>{{cite journal |last1=Hammami|first1=Farouk |last2=Rekik |first2=Monia |last3=Coelho |first3=Leandro C. |title=A hybrid adaptive large neighborhood search heuristic for the team orienteering problem |journal=Computers & Operations Research |date=2020 |volume=123 |pages=105034 |doi=10.1016/j.cor.2020.105034|s2cid=221134904 }}</ref>

** The Capacitated Team Orienteering Problem (CTOP),

** The TOP with Time Windows (TOPTW).

*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.<ref name="deif-backhauling">{{cite journal |last1=Deif |first1=I. |last2=Bodin |first2=L. A. |editor1-last=Kidder |editor1-first=A. |title=Extension of the Clarke and Wright Algorithm for Solving the Vehicle Routing Problem with Backhauling |journal=Proceedings of the Babson College conference on software uses in transportation and logistic management |date=1984 |pages=75-96|___location=Babson Park, MA, US}}</ref> 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.<ref name="deif-backhauling"/><ref>{{cite journal |last1=Golden |first1=B. L. |last2=Baker |first2=E. |last3=Alfaro |first3=J. |last4=Schaffer |first4=J. |editor1-last=Hammesfahr |editor1-first=R. |title=The Vehicle Routing Problem with Backhauling: Two approaches |journal=Proceedings of the Twenty-First Annual Meeting of S.E. TIMS |date=1985 |pages=90-92 |___location=Myrtle Beach, SC, US}}</ref>

*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 (computing)|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.

Line 49 ⟶ 50:

==Exact solution methods==

There are three main different approaches to modelling the VRP using [[Integer Programming|mixed-integer linear programming]] (MILP):<ref name=toth />

#'''Vehicle flow formulations'''—this uses integer variables associated with each arc that count the number of times that the edge is traversed by a vehicle. It is generally used for basic VRPs. This is good for cases where the solution cost can be expressed as the sum of any costs associated with the arcs. However it can't be used to handle many practical applications.<ref name=toth />

#'''Commodity flow formulations'''—additional integer variables are associated with the arcs or edges which represent the flow of commodities along the paths travelled by the vehicles. This has only recently been used to find an exact solution.<ref name=toth />

#'''Set-partitioning'''—This approach models the VRP as a [[set cover problem]], in which the locations make up the universe and the set of all feasible routes ([[Cycle_(graph_theory)|cycles]]) make up the collection of sets to choose from.<ref>{{cite journal |last1=Balinski |first1=M. L. |last2=Quandt |first2=R. E. |title=On an Integer Program for a Delivery Problem |journal=Operations Research |date=April 1964 |volume=12 |issue=2 |pages=300–304 |doi=10.1287/opre.12.2.300}}</ref> The problem can then be modelled using a [[Set_cover_problem#Linear_program_formulation|linear programming model for the weighted set cover problem]], with the weight of a route set to its cost. Modelling the VRP in this way will possibly result in an exponential number of binary variables in the linear program, as one is associated with each of a potentially exponential number of feasible routes.<ref name=toth />

#'''Set partitioning problem'''—These have an exponential number of [[binary data|binary variables]] which are each associated with a different feasible circuit. The VRP is then instead formulated as a set partitioning problem which asks what is the collection of circuits with minimum cost that satisfy the VRP constraints. This allows for very general route costs.<ref name=toth />

===Vehicle flow formulations===

Line 80 ⟶ 81:

which imposes that at least {{tmath|r(S)}}arcs leave each customer set <math>S</math>.<ref name=toth />

GCECs and CCCs have an exponential number of constraints so it is practically impossible to solve the linear relaxation. A possible way to solve this is to consider a limited subset of these constraints and add the rest if needed. Identification of the needed constraints is done via a separation procedure. Efficient exact separation methods for such constraints (based on [[Linear programming|mixed integer programming]]) have been developed.<ref>{{Cite journal |last1=Pavlikov |first1=K. |last2=Petersen |first2=N. C. |last3=Sørensen |first3=J. L. |year=2023 |title=Exact Separation of the Rounded Capacity Inequalities for the CapacitatedVehicle Routing Problem |journal=Networks |volume=83 |pages=197–209 |doi=10.1002/net.22183 |s2cid=263321558 |place=Networks|doi-access=free }}</ref>

A different method again is to use a family of constraints which have a polynomial cardinality which are known as the MTZ constraints, they were first proposed for the TSP <ref name=mtz>{{cite journal|last1=Miller|first1=C. E.|last2=Tucker|first2=E. W.|last3=Zemlin|first3=R. A.|title=Integer Programming Formulations and Travelling Salesman Problems|journal=J. ACM|date=1960|volume=7|pages=326–329|doi=10.1145/321043.321046|s2cid=2984845|doi-access=free}}</ref> and subsequently extended by Christofides, Mingozzi and Toth.<ref name=christof>{{cite book|last1=Christofides|first1=N.|last2=Mingozzi|first2=A.|last3=Toth|first3=P.|title=The Vehicle Routing Problem|date=1979|publisher=Wiley|___location=Chichester, UK|pages=315–338}}</ref>

Line 98 ⟶ 99:

There are many methods to solve vehicle routing problems manually. For example, optimum routing is a big efficiency issue for forklifts in large warehouses. Some of the manual methods to decide upon the most efficient route are: Largest gap, S-shape, Aisle-by-aisle, Combined and Combined +. While Combined + method is the most complex, thus the hardest to be used by lift truck operators, it is the most efficient routing method. Still the percentage difference between the manual optimum routing method and the real optimum route was on average 13%.<ref>{{cite web|url=http://locatible.com/blog/logistics/why-is-manual-warehouse-optimum-routing-so-unefficient/ |title=Why Is Manual Warehouse Optimum Routing So Inefficient? |website=Locatible.com |date=2016-09-26 |access-date=2016-09-26}}</ref><ref>{{cite web|last=Roodbergen |first=Kees Jan |url=http://roodbergen.com/publications/IJPR2001.pdf |title=Routing methods for warehouses with multiple cross aisles |website=roodbergen.com |date=2001 |access-date=2016-09-26}}</ref>

==Approximate solutions==

==Metaheuristic==

Many real-world applications use computational methods that produce approximate solutions, due to the computational complexity of the VRP. These methods are typically [[Heuristic_(computer_science)|heuristic]]-based and belong to one of two classes:<ref name="toth"/>{{rp|109}}

* '''Classical heuristics'''–perform a set of relatively simple operations to quickly construct a relatively good solution.

* '''Metaheuristics'''–classify and explore the most promising parts of the solution space.

===Metaheuristic===

Due to the difficulty of solving to optimality large-scale instances of vehicle routing problems, a significant research effort has been dedicated to [[metaheuristic]]s such as [[Genetic algorithms]], [[Tabu search]], [[Simulated annealing]] and Adaptive Large Neighborhood Search (ALNS). Some of the most recent and efficient metaheuristics for vehicle routing problems reach solutions within 0.5% or 1% of the optimum for problem instances counting hundreds or thousands of delivery points.<ref>{{cite journal|vauthors=Vidal T, Crainic TG, Gendreau M, Prins C|year=2014|title=A unified solution framework for multi-attribute vehicle routing problems