Vehicle routing problem (VRP)

The vehicle routing problem (VRP) is a mathematical process meant to find the most efficient routes for vehicular deliveries and related tasks. Mathematicians and business managers use VRP principles to determine how, when, and where to send vehicles to complete their tasks with minimum use of time, fuel, or other expenses. The ideas behind VRP appeared in the early 1800s, and the modern understanding of the concept began to develop around 1959. Since then, researchers have applied VRP principles to increasingly difficult and complicated scenarios. Successful VRP can allow trucks, taxis, airplanes, waste management trucks, and any other vehicles to complete their assigned tasks more quickly and efficiently.

Background

Some of the greatest innovations of the modern era have taken place in transportation technology. The automobile is a prime example. Developed in stages throughout the 1800s, the automobile was set to change the world by the early twentieth century. Continually updated and improved, automobiles became accessible to average people in many countries thanks to the American mass-production system. Cars, trucks, motorcycles, and other road vehicles became increasingly common throughout the early 1900s, and following World War II (1939–1945), a period of economic prosperity in many countries made automobiles a staple of everyday life.

Alongside the automobile, many other forms of transportation grew and developed. Overseas shipping crisscrossed the oceans, while advancements in the air transport industry allowed passengers and cargo to cross the globe in hours instead of months. These vehicles revolutionized the shipping industry and had a huge impact on human life. Vehicles came to serve purposes ranging from entertainment, such as NASCAR racing and stunt flying, to delivering precious cargo, such as transplant organs. The proliferation of vehicles in the mid-twentieth century also led to a restructuring of much of the planetary surface to accommodate roads, highways, airports, shipping ports, and many other such structures.

Vehicles created and contributed to enormous economic and industrial booms. They allowed people to move quickly and efficiently between locations and cargo to be picked up and delivered at countless facilities. The demand for vehicles and the fuels that powered them created billions of dollars in financial transactions. All this activity, however, also led to some major logistical challenges. When millions of vehicles must travel to millions of locations for millions of tasks each day—and modern consumers expect high efficiency in all of their vehicle-related dealings—it becomes difficult for vehicle operators and business owners to achieve their goals efficiently.

Overview

With vehicles becoming vital for the effective operation of an increasingly complex world, businesses and other organizations struggled to find ways to make vehicles work as efficiently as possible. One of the most important discoveries of their research is known as the vehicle routing problem (VRP). The VRP is a mathematical process that aims to determine the most time- and cost-effective routes for various vehicular tasks. These vehicles are most commonly trucks but may also be taxis, buses, passenger cars, aircraft, or any other vehicles that must reach certain destinations at certain times. One important example would be a waste management truck that must cover all the streets of a town within a single day.

The main variables used in the VRP are the number and type of vehicles, the people or goods being carried by them, and the customers or other facilities to which the deliveries will be made. Typically, a VRP plan starts at the home depot of the vehicle and creates the best route to meet its daily requirements. Then, it brings the vehicle back to the home depot for refueling and restocking with the least expenditure of time, mileage, or fuel. A successful VRP plan can allow deliveries to be made faster, thus satisfying customers and saving delivery organizations money. Vehicle operators may also benefit from fewer hours on the road and reduced stress relating to tight delivery deadlines.

Prior to the development of the VRP, people attempted to choose the best delivery or travel routes with paper maps and basic measuring devices. This process worked to an extent but proved to be extremely difficult when approaching complex situations. One of the earliest attempts to form a VRP equation took the shape of the so-called traveling salesperson problem (TSP). This was a mathematical question dating to the early nineteenth century that used the scenario of a door-to-door salesperson to demonstrate the complexities of finding efficient routes.

The modern VRP first appeared in print in 1959 during the research of mathematicians John Ramser and George Dantzig. Ramser and Dantzig created the idea to address the problem of how a gasoline delivery company can restock service stations in a particular region in the most efficient manner. The introduction of the VRP opened a formerly overlooked field of study, and many researchers began applying the idea to an array of math and map problems. In the coming years, researchers such as G. Clarke and J. W. Wright expanded on the 1959 work to create forms of VRP that could address increasingly varied and difficult delivery scenarios.

By the twenty-first century, VRP has become an enormously complex field of study. Mathematically, VRP is known as an NP-hard problem, which indicates that it becomes much more difficult to solve as new factors are introduced. Modern businesses have added many factors, leading to many new complications and variations of VRP calculation. These variations include VRP when vehicles have multiple home depots, VRP when vehicles both pick up and deliver cargo during their routes, VRP when vehicles have different hauling capacities, VRP when vehicles are driverless, and VRP when clients have differing time windows for deliveries. Artificial Intelligence and Machine Learning have also influenced VPR in the twenty-first century.

For these reasons, VRP is accomplished almost exclusively by computers. Digital VRP systems appear on many websites, applications, and devices, such as global-positioning devices that calculate the shortest routes for travelers. Computer programmers and mathematicians continue to study and revise the various VRP processes.

Bibliography

"Automotive Industry: A Research Guide." Library of Congress Research Guides, www.loc.gov/rr/business/BERA/issue2/history.html. Accessed 8 Jan. 2025.

Caric, Tonci, and Hrvoje Gold. Vehicle Routing Problem. In-Teh, 2008.

Dantzig, George B., and John H. Ramser. "The Truck Dispatching Problem." Management Science, vol. 6, no. 1, Oct. 1959, pp. 80-91.

“How to Solve Vehicle Routing Problems: Route Optimization Software and Their APIs.” Altexsoft, 21 Aug. 2019, www.altexsoft.com/blog/business/how-to-solve-vehicle-routing-problems-route-optimization-software-and-their-apis. Accessed 8 Jan. 2025.

Kabcome, Panupong, and Thapanapong Mouktonglang. "Vehicle Routing Problem for Multiple Product Types, Compartments, and Trips with Soft Time Windows." International Journal of Mathematics and Mathematical Sciences, 2015.

Puri, Komal. “What is Vehicle Routing Problem? How to Solve VRP with Routing Software.” Far Eye, 13 July 2023, fareye.com/resources/blogs/vehicle-routing-problem-how-to-solve-it. Accessed 7 Jan. 2025.

Seshadri, Anand. “Vehicle Routing Problems 101.” Medium, 8 Mar. 2019, medium.com/opex-analytics/opex-101-vehicle-routing-problems-262a173f4214. Accessed 8 Jan. 2025.

“Vehicle Routing Problem.” Google OR-Tools, 28 Aug. 2024, developers.google.com/optimization/routing/vrp. Accessed 8 Jan. 2025.