Dynamic Vehicle Routing Problem: How Do You Solve It?

You probably never pause to consider the science going on behind the scenes in your dynamic vehicle routing software – at least not when things are going well.

But no software is foolproof. What happens if your specific software no longer suits your needs? Do you even know how to identify, much less explain, what your dynamic vehicle routing problems are?

If not, you’ve found the right article. We’re going to explain all of the different techniques used in routing software to help you plan and route your deliveries. We’ll explain how your route planning app arrives at the results it does and how to identify which vehicle routing features are missing if your current solution isn’t working for you.

Vehicle Routing Problems Are Nothing New

Every tremendous scientific advancement arises from a specific problem that needs to be solved. Today’s software solutions to dynamic vehicle routing problems are no exception. Before GPS and computer spreadsheets, a more mundane dilemma took more than 150 years to solve adequately.

The problem was this:

“If provided with a list of cities/downs and the distances between each, how can you compute the shortest route possible that: visits each city listed only once, and returns a traveling salesman to his city of origin?”

Does this problem sound familiar? It should. It’s the fundamental routing problem facing every multi-stop delivery in history ¬– from the Pony Express to today’s gig-economy, food deliveries. Any time you want to figure out the shortest route among more than a handful of places, you will run into this problem. Humans, including you, are cognitively incapable of quickly determining the most efficient route.

The Traveling Salesman Problem (TSP)

The Traveling Salesman Problem (TSP) originated in an 1830s, German-language, traveling salesman handbook. Years ago, the TSP problem was identified because the most obvious solution – traveling from closest point to next closest point – simply didn’t work.

It doesn’t take long for the traveling salesman problem to drive anyone managing modern deliveries to look for a software solution. The simplicity with which software solves TSP today belies how difficult it was to find a solution. It took over 150 years of scientific endeavor.

TSP was finally kicked to the curb in 1993, with the release of the open-source Concorde program. The software remains free and downloadable. Still being optimized, Concorde was recently used to solve an 85,900-city routing problem with 100% efficiency.

Modifications and adaptations of Concorde are found in almost every routing application available today. With today’s computing technology, determining the most efficient routes on a network of roads is simple. The keyword being “simple”.

What about when your business needs something more dynamic? For example, how can you find the most efficient routes to and from particular locations in real-time? After all, traveling salesmen in the 1800s didn’t have a lot of traffic to contend with. You do.

The Dynamic Vehicle Routing Problem

Static solutions to TSP are now irrelevant for many vehicle routing tasks. Third-party location data have increased the complexity of vehicle routing problems. This complexity could only be solved using a new model. Something robust enough to answer questions like:

  • How can you update vehicle routes to make them optimal based on current traffic?
  • How can your drivers reroute their deliveries to circumvent unforeseen delivery issues?
  • How can you update delivery routes after a vehicle has left the warehouse?

Today’s dynamic vehicle routing problems can only be solved with third-party data, geo-intelligence, online databases, and ants – millions of ants.

Ant Colony Optimization (ACO): A Primer

Ants are, arguably, the world’s best route finders. Scientists have long analyzed how ant colonies use individual marching ants to find, collect, and return food to the colony. They are efficient at finding the shortest, most direct route and rerouting around obstacles. But how do they do this?

When an ant leaves its colony, it will wander completely randomly, searching for resources (e.g., food) or pheromones left by another ant. Each ant literally goes its own way in search of food.

Humans tend to do the opposite. We prefer to conduct searches in an ordered fashion. It’s much more likely a group of humans looking for a particular resource will send workers in different directions. Just as moving from point to nearest point in the Traveling Salesman Problem seems rational at first, sending people in specific directions is often inefficient – at least for ants.

Solving the Dynamic Vehicle Routing Problem with Digital Pheromones

Ants have a wayfinding advantage over humans. When an individual ant finds a resource it wants, it will grab a bit and immediately return to its colony. As the ant returns, it emits a pheromone. This scent acts as a trail of crumbs that other ants can subsequently smell and follow.

From there, the entire ant colony can make haste back-and-forth to the resource – each ant adding to the pheromone scent, reinforcing the most direct route. However, ant pheromone depreciates in strength with time. Longer routes emit weaker pheromones than shorter ones, which leads ants to follow the most efficient routes – biological route optimization.

Humans don’t leave pheromones that others can follow. Since the turn of the century, we leave something better – digital footprints.

The Development of Ant Colony Optimization Algorithms

Mathematicians and computer scientists expanded on the static Traveling Salesman Problem by exploring Ant Colony Optimization (ACO). They have since developed route optimization algorithms to solve various routing problems, including dynamic vehicle routing. The most robust solutions make use of artificial intelligence and real-time mobile device geolocation.

All ACO software algorithms follow the same general pattern. The software sends out virtual ants – data packets – along a weighted grid. The grid is then is created from a supplied road network. Each virtual ant wanders the grid randomly. If it stumbles upon the desired location (e.g., a route destination), it returns directly to its origin – creating an optimized route. The computerized ant leaves virtual pheromones along the grid vertices it travels. The route-finding software calculates the optimized route based on which edges have the most pheromones.

ACO allows businesses, and their fleets, to make real-time adjustments while carrying out deliveries. For example, if there is a major traffic jam keeping your truck from getting to its next, optimized delivery, ACO software can help you plan a new route ¬– on the fly. It will likely use third-party traffic data, your delivery database, and perhaps your truck inventory to create a new, more optimized route.

The availability of location-based data, and third-party APIs, allowed newer, more powerful dynamic vehicle routing software to be created. Almost as fast as researchers find solutions, however, businesses present new problems to solve.

The Time-Dependent Vehicle Routing Problem

The key difference between ant colony optimization and dynamic vehicle route optimization isn’t pheromone-related. It’s about time and volume.

Unlike your delivery service, an ant colony has thousands of delivery vehicles, each worker ant carrying a single package. Delivery services require optimizing routes based on a limited number of vehicles with certain package capacities.

Punctual deliveries depend on efficiently managing routes with fixed delivery capacities. ACO represents another example of scientists creating a new problem by solving a previous one – the time-dependent vehicle routing problem. How do you make sure your scheduled deliveries are as efficient as possible?

ACO Solutions to the Time-Dependent Vehicle Routing Problem

Scientists quickly began to adapt their ACO algorithms to improve dynamic vehicle route optimization. The new algorithmic problem was given a name only a scientist could love: time-dependent vehicle routing problem with time windows (TDVRPTW). The solution to TDVRPTW is found in its name. Time windows and vehicle capacity data were added as variables to the ACO vehicle routing algorithms.

Delivery time windows – e.g., morning, midday, afternoon, evening – allow companies to optimize their deliveries into sequential routes. ACO can therefore be reconfigured to find the most efficient delivery routes across a sequence of time periods. It can also consider vehicle capacity to maximize the number of deliveries possible in a specific time window.

Today businesses delivering perishables or time-specific services can incorporate ACO-based software with time windows. Using this software breaks down the complexity of routing different items throughout the day, allowing routes for specific time periods to be easily adjusted and modified dynamically.

The Multi Ant Colony Routing Problem

The Traveling Salesman Problem took more than 150 years to resolve when it was put to rest for good in 1993. It seems downright quaint given the complexity of the vehicle routing problems that have arisen over the past 30 years. Until recently, this problem was the new TSP: What if you need to create routes for a large fleet of trucks, all servicing the same city but leaving from different warehouses?

Researchers writing in the European Journal of Operations Research recently expanded ACO algorithms to allow for multi ant colony optimization. Multi ant colony optimization allows companies to solve the dynamic vehicle routing problem from multiple origins (i.e., warehouses) simultaneously. This breakthrough will allow routing software vendors to create apps that can simplify company logistics. No longer does a salesman’s route need to be plotted individually. Nor is a company limited to planning the routes of all the salespeople from a single office.

Today’s software allows businesses to plan their entire fleets’ dynamic vehicle delivery routes – in sync.

Your Dynamic Vehicle Routing Solution is 150-Plus Years in the Making

Vehicle routing problems are nothing new. Mathematicians and computer scientists have tackled them for well over a century. Every time they make progress, new problems to be solved arise. With the power of post-Cold War technology, researchers are finding software solutions to new vehicle routing problems almost as fast as they arise.

You now know how to identify and explain what types of dynamic vehicle routing problems your delivery business may face to stay competitive. You understand what the problems are and how dynamic routing software can your company solve them.

The next time you use your dynamic vehicle routing app, please pause a moment to think of the ants that made it possible. And be grateful scientists keep solving these routing problems as fast as they do. After all, three-dimensional, drone-based dynamic delivery routing is upon us.

Save time and money with faster deliveries everyday.

Delivery Route Planning
Route Planning for Teams of 2+ Drivers
Have a team of multiple drivers? Need to create multiple routes from many stops?