Delivery Vehicle Route Planning with Ant Colony Optimization

Delivery Vehicle Route Planning with Ant Colony Optimization

Many real world optimization problems are not simple and linear that’s amenable to neat closed form solution. For such problems there are various heuristic optimization techniques. These heuristics algorithms find good enough sub optimal solutions while limiting computing cost. Many of the heuristic optimization techniques are nature inspired. The book Clever Algorithms Nature Inspired Programming Recipes by Jason Brownlee is a wonderful resource on the topic. The link has a download link for the book. There is one class of nature inspired optimization algorithms called Swarm Intelligence. Ant Colony Optimization is technique that falls under the category of Swarm Optimization.

In this post we will solve the problem of delivery route planning with Ant Colony Optimization (AOC). The implementation is available in my Python package arotau. This package contains several heuristic optimization algorithm implementation. Here is the GitHub repository.

Ant Colony Optimization

Swarm optimization is a computational optimization technique inspired by the collective behavior of social animals, such as ants, bees, and birds. Each agent represents a potential solution to the problem and moves in the search space according to a set of rules that take into account its own experience and the experiences of its neighbors. Solution emerges as a result of interaction and cooperation among the agents.

Ant Colony Optimization is a kind of Swarm Optimization algorithm. The inspiration for ACO is foraging behavior of real ant colonies. When ant leaves the nest looking for food it leaves a pheromone trail in the path. When it finds food, it takes the same path back to the nest dropping pheromone again, further strengthening the pheromone trail. Pheromone naturally evaporates as time goes by, resulting in weakening of the Pheromone trail in less fruitful paths.

Pheromone strength provides cue to other ants to follow a particular path. Ant colony behavior is characterized by indirect communication between the ants by means of chemical pheromone trails, which enables them to find the shortest paths between their nests and food sources. Here is the algorithm.

for all iterations
  for all nodes
    for all ants
      select the next node to visit based a distribution derived from edge weights
  find the least cost ant path from current iteration
  set global best solution if current iteration best solution is better
  update pheromone weights

The edge weight has 2 components. The heuristic part does not change and is based on the graph topology. For example it could be the inverse of the edge length. The other component is the pheromone weight, which gets updated after each iteration. The edges that fall on the fruitful ant paths gain more pheromone weight. After each iteration, pheromones weights for all edges are reduced to simulate pheromone evaporation, before the weights are increased.

The next node selection based on the edge weights to neighbors is done with a random greedy approach. With some probability (1 – p), the most promising edge is chosen and with probability p, a random edge is selected by sampling the normalized weight distribution i.e probability distribution of the edges. Higher value of p encourages more exploration and less exploration and vice versa.

For adding Pheromone weight to any edge there are many policies. The following 3 policies more popular. All of them are available in the implementation.

• Consider paths for ants in the current iteration. Add to the pheromone weight for any edge that falls on the path for an ant. This is repeated for all the ants
• Consider current iteration best solution. Add to the pheromone weight for all edges that coincide with the path of the ant corresponding to the current iteration best solution.
• Consider best solution so far. Add to the pheromone weight for all edges that coincide with the path of the ant for the globally best solution. Choosing this option may cause premature convergence.

There are several variants of the canonical ACO algorithm presented here. They mainly differ in how pheromone weights are added.

• Elitist ant system
• Rank based ant system
• Max Min based ant system
• Ant colony system
• Hyper cube framework

To improve the search space for the next node to visit, any of these algorithms could be used with beam search. Beam search allows the extension of the sequence of the nodes in several possible ways. ACO can be used to solve various problems. Here are some examples

• Traveling salesman
• Quadratic assignment
• Scheduling
• Vehicle routing
• Time tabling
• Set packing
• Shortest super sequence
• Sequential ordering
• Cell placement in circuit design
• Communication network design

Delivery Vehicle Scheduling

Choosing the shortest path to visit all location as in the case of a delivery vehicle is a complex optimization problem and it’s combinatorially explosive. The only way to find the truly optimum path is try all of them, which could be computationally prohibitive depending on the problem size. ACO is appropriate for any problem that can be framed as a graph and the solution requires graph traversal.

There are 10 locations, named A through J. The location A is the warehouse or store. The rest 9 locations are customer locations. The journey starts at A and ends at A, having traveled to all the locations for delivery. The parameter ac.graph.data in the configuration file defines the edges along with edge length. The graph is fully connected. Here is the explanation for all configuration parameters along with sample values

When you run the optimizer as per the tutorial, you will see output like below. It tracks the best solution found so far and shows the final best solution.

global best soln at iteration 0 path ['A', 'B', 'C', 'D', 'G', 'I', 'J', 'H', 'F', 'E', 'A'] weight 33.476977  cost 3.335526
global best soln at iteration 4 path ['A', 'E', 'F', 'H', 'J', 'I', 'G', 'D', 'C', 'B', 'A'] weight 33.476977  cost 3.335526
final global best soln  path ['A', 'E', 'F', 'H', 'J', 'I', 'G', 'D', 'C', 'B', 'A'] weight 33.476977  cost 3.335526

In this case it converged after the 5th iteration. Since the number of ants was set to 30 in the configuration, by the 5th iteration 150 candidate solutions were generated. Here is the configuration file, the Python implementation and the Python driver code. Here is the optimum path found shown with dotted lines. The travel starts with A and ends with A. The graph for this problem is fully connected. In the graph definition, only the shortest path between any 2 locations have been provided.

Travel Time Based Optimization

What if we wanted to optimize based on the travel time between locations from Google Map instead of distances. Unlike distance, travel time is dynamic and changes with traffic conditions during the day. One option is to get the optimum path based on travel time before the delivery vehicle leaves the warehouse.

Then during the day, once or twice we could run the optimizer based on the latest travel time data for the locations yet to be visited. Various unexpected conditions could also be handled. If there is unexpected delay for some location due to traffic, it could be temporarily removed and the optimizer couple be re executed. That way the delivery vehicle could continue with other locations. Later on, that location could be added back for the next optimizer run.

With travel time based route planning, there is an added advantage. Customers can be provided with estimated time window for arrival.

Wrapping Up

We have gone through an example of Ant Colony Optimization and learnt how it can used to solve complex optimization problems. The AOC implementation in arotau is applicable for any problem that can be modeled as a graph traversal problem. The graph topology data is provided through the configuration file.