The History and State of Vehicle Routing!

Vehicle Routing
Unchaining Change Leadership

My undergraduate thesis in Industrial Engineering was on “Vehicle Routing Procedures, In Theory and in Application”, co-authored with fellow classmate Joel Koschitzky. As this work was researched and written almost 40 years ago it is interesting to reflect on the state of Vehicle Routing technology then and now.

It remains a very complicated problem to solve even to this day. It is actually exponentially more challenging in practice today with the explosion of E-Commerce, Online shopping, and last mile delivery direct to consumers.

Let’s discuss the state of Vehicle Routing past, present and future!

What is Vehicle Routing?

Wikipedia defines the Vehicle Routing problem as “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?”. It generalises the well-known travelling salesman problem (TSP).

It first appeared in a paper by George Dantzig and John Ramser in 1959,[1] in which the first algorithmic approach was written and 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. The objective of the VRP is to minimize the total route cost.”

Based on this definition it is very consistent with the Industrial Engineering curriculum of my youth. We had courses on Linear Programming, Operational Research, Scheduling and Control systems, Stochastic modelling, Mathematical Programming, Simulation, Heuristic modelling, Applied Statistical analysis, and much, much more.

All of this educational content made our choice of Vehicle Routing as a thesis topic a natural fit given what we had learned. While I don’t recall exactly how Joel and I stumbled on this topic it certainly held a lot of potential for a great thesis topic.

Why is it such a complicated problem to solve?

Why is it Still Important Today?

The absolute explosion of online shopping, and in turn direct to home delivery of those goods ordered online, has been incredible. Most of us could not have imagined 10 years ago how important Ecommerce would become, let alone 40 years ago.

While there are many different options for receiving goods you order online, such as pick up in store or curb side pickup, the predominant delivery platform for Ecommerce is direct delivery to the location of each individual customers choice.

And with customers expecting solid commitments on when their orders will be delivered the need for high order precision in understanding vehicle route times and vehicle tracking has never been more critical.

On top of that we have all other forms of economic growth, the expansion of outsourcing and global sourcing, all of which drive ever increasing demand on the over the road transportation of goods. In 2019 alone trucking accounted for almost $800 billion of expenditure in the U.S. alone.

The movement of goods between manufacturers, distribution centres, warehouses, retailers and consumers is happening at unprecedented levels. On top of that there are more innumerable logistics companies (local, national and international), carriers, couriers, private trucking fleets, contract trucking fleets, and more all available to move these goods.

The costs, the environmental impact, the different carriers, truck driver shortages, different types of trucking equipment all make the use of proper and efficient vehicle routing technology critical. On top of that consider, particularly in the ECommerce last mile delivery space, that the customers that you must deliver to change from hour to hour and from day to day. The number of potential delivery routes is virtually infinite.

We must also consider that determining the location of distribution centres and warehouses can only be optimized when taking into consideration the transportation implications of these decisions. Taking into account delivery expectations, costs and other resources Vehicle Routing provides mathematically optimized answers to these questions.

Now consider that in the foreseeable future we will see the advent of autonomous vehicles delivering goods. In addition to having the technology to drive without an operator they will require vehicle routing technology to ensure they are driving via the most optimal routes.

The demand for Vehicle Routing technology is bigger than ever before.

Our Thesis of 40 Years Ago

All of our research was done through books, surveys and interviewing people and companies who worked in this space. Personal computers hadn’t come into being as yet. In fact our computer programming courses were conducted creating endless stacks of punch cards. There was no satellite proliferation enabling GPS, no smart phones tracking every movement of packages or vehicles, or google to get instantaneous answers to innumerable questions.

Our thesis began with an overview of Vehicle Routing, the history at that point, a discussion of various algorithms and approaches to the problem, variations and techniques in the application of these algorithms, and a discussion of these procedures actually being used by numerous companies.

The second half of our thesis involved an in-depth analysis and case study of the state of Vehicle Routing at a very large national grocery wholesale distribution company. Further we applied various techniques using real data to identify opportunities for optimizing their current procedures and processes so as to deliver savings in time, cost, environmental impacts and improve their customer experience.

As stated in the thesis, “As the aggregate of delivery costs increases … companies are becoming more and more aware of the need to effectively and efficiently perform vehicle routing. The quality of customer service in the face of highly competitive market situations, has profound repercussions for the survival of a company. The economic implications of poor customer service combined with cost ineffective vehicle routing is obvious.”

This statement is just as true today as it was 40 years ago.

“The basic problem seen to underly the vehicle routing problem is the travelling salesman problem (TSP). The travelling salesman problem is characterized by a single depot, a single salesman (a vehicle of unlimited capacity), a set of customers (nodes) to be visited with deterministic demands of unity magnitude on an undirected network, and no timing restrictions on when a customer is to be visited.

The objective is for the salesman to traverse all nodes on a single route at minimum cost, while starting and finishing at the depot. Cost is typically measured in terms of distance travelled.”

“A natural extension the travelling salesman problem is the multiple travelling salesman problem (MTSP). In this case there are M salesmen, each of which is required to visit at least one node, subject to each node being visited by only one salesman. Each salesman starts and ends his route at a common depot. The goal is to minimized total costs (eg. costs as measured by distance) for all M salesmen.”

Complex mathematical formulations of these problems ensued. Various constraints were modelled including capacity, travel time, availability, etc.

As also referred to in the Wikipedia definition, “one of the first attempts at formulating the travelling salesman problem and applying it to a routing situation was developed in 1954 by Dantzig and Ramser. Their problem concerned the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and the associated service stations.”

“Dantzig felt that given a small number of service stations this problem could be solved optimally by plotting the different stations on a map and looking for obvious or natural clusters of stations and thus routing trucks by hand. However, given a large number of service stations it would be next to impossible to find the optimal solution. He thus proposed a linear programming formulation for obtaining a near optimal solution.”

“In 1962 Clarke and Wright presented a paper which described an algorithm for obtaining an optimal, or near-optimal, routing for a fleet of trucks. The fleet consisted of trucks of varying capacities whose purpose was to deliver merchandise from a central depot to a large number of customers. The procedure searches out the optimal grouping of points, the optimal grouping being defined as that which produces the maximum savings.” In various examples their model should improved savings over Dantzig and Ramser.

We identified numerous procedures for classifying routing problems:

  • Cluster first-route second algorithms
  • Route first-cluster second algorithms
  • Savings/Insertion or Construction/building approaches
  • Improvement/Exchange techniques
  • Mathematical programming based methods
  • Man-machine interactive techniques
  • Exact solution procedures

The mathematical modelling involved in all of these approaches is highly complex. Application of these algorithms and computation of routing solutions was further complicated by the fact that the computing power available at the time was a small fraction of that which is available today.

Only two notable software programs of note existed at the time to help with these efforts. The VSPX (Vehicle Scheduling Routing program) was developed by IBM based on the Clarke-Wright savings algorithm. And the Rover (Real Time Optimizer for Vehicle Routes) computer package produced by DART, based on research through the University of Pennsylvania with DuPont de Nemours.

Our research included studying various companies and the approaches they were taking to the vehicle routing problem. There was no standard approach across companies as each applied various considerations differently, including delivery frequency, unloading time, case size, geographic location, weight, capacity, postal (or zip) codes, delivery constraints, and more.

Finally we applied everything we had learned to a real world example of this problem with a national grocery chain wholesale distributor. We took into account all distribution centre locations, all customer locations, truck drivers, equipment (eg. trailer) characteristics, delivery constraints (eg. grocery items that do or do not require refrigerated trailers) and expectations, demand patterns, costs of all kinds, and more.

Through the application of various algorithms and techniques we identified opportunities for dramatic improvements in delivery performance and cost savings for the company, from their current operating procedures.

All in all it was a great learning experience and a great success.

The State of Vehicle Routing Today

The components of a vehicle routing and scheduling (VRS) system, as reported by Gartner, includes:

The advancement and technology is also apparent. Gartner continues, “Capabilities such as territory planning, capacity planning, driver comfort and payroll features are complemented with geofencing, modeling, and telematics integration to support better planning and enhanced visibility.

In addition, VRS vendors are now applying technologies such as ML or AI to not only enhance the quality of analysis of the output results of the completed job but also improve the steps prior to when orders are dispatched. There are new data inputs that the routing algorithms can process to provide more accurate, optimal routing, resulting in almost real-time operation control and visibility.”

The route optimization software market is expected to be over $5 billion by 2023, reflecting the size and importance of this technology and capability. The size of this market has attracted far, far more players than were in the space 40 years ago. Today routing software providers include:

ALK Technologies (US), AMCS (Ireland), Caliper (US), Descartes (Canada), Esri (US), FLS (Germany), Geoconcept (France), Google (US), Portatour (Austria), Llamasoft (US), Maxoptra (UK), Microlise (UK), Omnitracs (US), Optimoroute (US), ORTEC (Netherlands), Paragon Software (UK), PTV Group (Germany), Quintiq (Netherlands), FarEye (India), Route4me (US), RouteSolutions (US), Routific (Canada), Scientific Logistics (US), Truckstops (UK), Verizon Connect (US), and Workwave (US).

Marketwatch lists the top players in this space as TMW Systems (Trimble), Paragon Software, Ortec, Omnitracs, Fleetmatics (Verizon), Oracle, Carrier Logistics, JDA Software and Maven Machines. We also see SAP, Bringg, Dassault, Locus, Manhattan, Onfleet and Route Smart in this space.

Route Optimization Software Market

According to getfareye.com modern vehicle routing software uses artificial intelligence and machine learning to: increase fleet efficiency, reduce fuel costs, increase customer satisfaction, machine learning based routing, and intelligent allocation of shipments to last mile agents.

In Gartner’s “Market Guide for Vehicle Routing and Scheduling” report they state that “VRS applications have evolved into more than a route-planning and optimizing tool. Although the routing algorithm is the core that defines and differentiates these systems from other transportation management solutions, the capabilities surrounding that core are elevating VRS solutions to the next level. Organizations commonly use more than one type of routing, whether it is a combination of static and dynamic routing or a combination of dynamic and real-time dynamic routing.”

The capabilities of Vehicle Routing software solutions are being expanded as well. Through the use of artificial intelligence and machine learning technologies, as well as big data and advanced analytics, “VRS vendors are increasing the breadth of their solutions by providing more strategic capabilities, such as transportation modeling, turn-by-turn navigation or 3D load building.

They are also including capabilities related to sustainability demands. VRS vendors focused on last-mile operations are also including newer features aiming to provide the end user a better customer experience.”

Conclusion

After over half a century of working to solve the Vehicle Routing problem it is still as important as ever before. The exponential growth of businesses requiring last mile delivery direct to consumers along with overall economic expansion and population growth, have combined to make the Vehicle Routing problem more complex than ever before.

I could never have guessed 40 years ago that I would be writing on the topic that my thesis was based on, but it has been genuinely exciting to look back on all that work and catch up on the state of this industry.

Finally I would like to extend a special thanks to Professor Michael Carter, a friend with whom I am fortunate to still be connected with after all these years. And of course a special thanks to Joel; together we created a time honoured thesis. And lastly to my tremendous classmates, my enduring friends, many of whom I still get to see “fleetingly” at our small class reunions every 5 years.

And a special thanks to Michael Massetti for providing us access to the Gartner “Market Guide for Vehicle Routing and Scheduling” report. Gartner is an incredible resource and asset for anyone and everyone.

Originally published on March 30, 2021.

One thought on “The History and State of Vehicle Routing!”

  1. I have designed a new meta heuristic approach to solve Capacitated Vehicle Routing Problem with Time Windows and Non homogeneous cars
    If you want to cooperate with me, you can call me

Comments are closed.