Ant Colony Optimization to solve the Travelling Salesman Problem
The Ant Colony Optimization (ACO) for Travelling Salesman Problem solving
The rapid rise of e-commerce has caused the logistics sector to face rising consumer expectations and regional rivalry across all supply chain actors. This e-commerce boom has pushed the logistics sector to struggle with boosting logistics distribution efficiency and lowering operational costs to keep up with consumers’ rapidly increasing demand.
The Lorry, one of the top technology-enabled logistics platforms in South-East Asia, has presented The Lorry Route Optimization Project to provide flawless end-to-end data flow from hub to customers. The Traveling Salesman Problem (TSP), Vehicle Routing Problem (VRP), and Cargo Load Problem (CLP) that The Lorry faced daily inspired the development of in-house Route Optimization. To solve the TSP, we will offer a new implementation of hierarchical pheromone update for Population-based Ant Colony Optimization.
The suggested algorithm optimizes the last-mile distribution route by reducing the driver’s journey distance to increase efficiency. The traveling salesman problem (TSP) is being tackled in this research by employing population-based Ant Colony Optimization methods with innovative hierarchical pheromone updating to improve the quality of solutions.
In this article, the route optimization system was demonstrated effective by example analysis on the test dataset. The analytical results also show how the system’s algorithm can deliver superior routing solutions with shorter distances and less time, potentially lowering last-mile distribution costs.
Travelling Salesman Problem (TSP)
The Traveling Salesman Problem (TSP) is the task of determining the shortest and most efficient route for a person to take, given a list of specific destinations. In computer science and operations research, it is a well-known algorithmic problem.
There are many different routes to take, but finding the best one that requires the least distance or cost is what mathematicians and computer scientists have spent decades attempting to solve.
TSP has received a lot of attention because it’s so simple to describe but difficult to solve. TSP belongs to the NP-complete class of combinatorial optimization problems. That TSP is NP-hard because there is no “quick” solution, and the complexity of calculating the best route grows as more destinations are added to the problem, as shown in Figure 1.
As shown in Figure 1, there are many possible solutions available, and they should be measured and compared to each other to get the shortest path or distance. It is impossible to do manually without an algorithm to help it.
Ant Colony Optimization (ACO)
Ant colony optimization (ACO) is a population-based meta-heuristic for combinatorial optimization problems. It is inspired by the ability of ants to find the shortest path between their nest and a source of food. Marco Dorigo first introduced ACO in his Ph.D. thesis and applied it to the Traveling Salesman Problem (TSP). It has been applied to the quadratic assignment problem, the vehicle routing problem, bin packing, stock cutting, and RNA secondary structure prediction.
Let’s start with coding in Jupyter Notebook
The Jupyter notebook we used in this tutorial can be found here.
We start with the file of data.csv
In data.csv, we have 27 drop-point in which all data belong to cluster 0, and each data has information about latitude and longitude. tracking_id is the unique id for each row of data.
Ok, let us start reading the data and loading it into pandas dataframe and then, we grouped the data by the cluster and counted the number of data in each cluster.
# read csv data and load into pandas
import pandas as pdfile_url = 'dataset/data.csv'
df = pd.read_csv(file_url)_job = df.groupby('cluster')
['tracking_id'].count().sort_values(ascending=[False])
print(_job)
we can get the result as shown here
cluster
0 27
Name: tracking_id, dtype: int64We only have one cluster, which has 27 data points.
Ok, let us prepare the distance matrix from our latitude and longitude of data.
# construct the distance matrix based on haversine
from haversine import haversine, Unitdistance = []
for i in range(len(_data)):
lat = _data.iloc[i]['lat']
lng = _data.iloc[i]['lng']
from_node = (lng, lat)
result = []
for j in range(len(_data)):
lat = _data.iloc[j]['lat']
lng = _data.iloc[j]['lng']
to_node = (lng, lat)
if i == 0:
dist = 0
elif j == 0:
dist = 0
else:
dist = round(haversine(from_node, to_node,
unit=Unit.METERS))
result.append(dist/1000)
distance.append(result)
print(distance)
The distance matrix we get, shown in below
[[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
[0.0, 0.0, 0.157, 0.402, 0.443, 0.987, 1.13, 1.205, 1.177, 1.175, 1.19, 1.367, 1.519, 1.808, 2.16, 2.039, 1.829, 1.717, 1.324, 1.052, 1.136, 1.174, 1.215, 1.215, 1.67, 1.67, 1.603, 1.666],
[0.0, 0.157, 0.0, 0.247, 0.287, 0.835, 0.979, 1.071, 1.046, 1.065, 1.109, 1.341, 1.532, 1.809, 2.039, 1.897, 1.674, 1.561, 1.167, 0.912, 1.039, 1.06, 1.076, 1.076, 1.522, 1.522, 1.453, 1.512],
[0.0, 0.402, 0.247, 0.0, 0.042, 0.628, 0.773, 0.914, 0.895, 0.965, 1.066, 1.385, 1.631, 1.886, 1.898, 1.711, 1.443, 1.324, 0.931, 0.681, 0.876, 0.869, 0.845, 0.845, 1.279, 1.279, 1.208, 1.265], ...[0.0, 1.666, 1.512, 1.265, 1.225, 0.867, 0.814, 1.072, 1.103, 1.344, 1.603, 2.111, 2.483, 2.632, 1.64, 1.176, 0.562, 0.42, 0.495, 0.703, 1.042, 0.884, 0.591, 0.591, 0.242, 0.242, 0.175, 0.0]]
We use haversine to get distance among the geo-location. We set the result in unit meter, but later we divide it by 1000 convert it into unit km. So, our result will show in km.
The main process in our tutorial is using ACO Class and trying to get the best solution. Ok, let us code it.
nk = 5 # number of k = ants
maxIterations = 100
beta = 4 # Heuristic constant
zeta = 0.4 # local Pheromone decay
rho = 0.2 # global Pheromone decay
q0 = 0.7 # randomnize
plot=False
verbose = Falseoptimizer = ACO()best_paths, result = optimizer.Fit(distance, nk, maxIterations,
beta, zeta, rho, q0, plot, verbose)optimizer.Plot()
First, we define the parameter for nk, maxIteration, beta, zeta, rho, q0, plot and verbose. Later, we create an optimizer object from ACO Class. Then we use the Fit method to get the result and the best paths. Finally, we plot the convergence matrix of the optimization process. Here is the process result and the best path obtained from the process.
0 ... 16.786 : 11.178999999999998
1 ... 14.449 : 11.178999999999998
2 ... 11.78 : 11.178999999999998
3 ... 12.541 : 11.178999999999998
4 ... 11.668 : 11.178999999999998
5 ... 14.588999999999999 : 10.786999999999999
6 ... 14.059000000000001 : 10.786999999999999
7 ... 18.742 : 10.786999999999999
8 ... 14.786 : 10.786999999999999
9 ... 15.571 : 10.442999999999998
10 ... 17.169 : 10.442999999999998
11 ... 17.250999999999998 : 10.442999999999998
12 ... 15.714999999999996 : 10.442999999999998
13 ... 13.332999999999997 : 10.442999999999998
14 ... 16.741 : 10.442999999999998
15 ... 16.089999999999996 : 10.442999999999998
16 ... 18.807000000000006 : 10.442999999999998
17 ... 14.315000000000001 : 10.442999999999998
18 ... 14.733 : 10.442999999999998
19 ... 12.709 : 10.442999999999998
20 ... 15.51 : 10.442999999999998
21 ... 17.689 : 10.442999999999998
22 ... 16.209 : 10.442999999999998
23 ... 11.263999999999998 : 10.442999999999998
24 ... 9.584999999999997 : 9.584999999999997
25 ... 11.914000000000001 : 9.584999999999997
26 ... 15.671000000000001 : 9.584999999999997
27 ... 10.497 : 9.584999999999997
28 ... 15.360999999999999 : 9.584999999999997
29 ... 12.519 : 9.584999999999997
30 ... 10.916999999999998 : 9.584999999999997
31 ... 16.718999999999998 : 9.584999999999997
32 ... 13.908999999999999 : 9.584999999999997
33 ... 19.976 : 9.584999999999997
34 ... 14.19 : 8.532
35 ... 17.176 : 8.532
36 ... 14.707999999999998 : 8.532
37 ... 14.43 : 8.532
38 ... 17.616999999999997 : 8.532
39 ... 14.764000000000003 : 8.532
40 ... 10.348 : 8.532
41 ... 16.087999999999997 : 8.532
42 ... 12.985000000000001 : 8.532
43 ... 13.781 : 8.532
44 ... 14.686 : 8.532
45 ... 15.886999999999999 : 8.532
46 ... 10.658 : 8.532
47 ... 15.128 : 8.532
48 ... 11.84 : 8.532
49 ... 13.414 : 8.532
50 ... 10.36 : 8.532
51 ... 13.024999999999999 : 8.532
52 ... 13.546 : 8.532
53 ... 13.014999999999999 : 8.532
54 ... 11.768999999999998 : 8.532
55 ... 13.614 : 8.532
56 ... 15.457999999999997 : 8.532
57 ... 15.555999999999997 : 8.532
58 ... 16.462 : 8.532
59 ... 12.403 : 8.532
60 ... 14.364999999999998 : 8.532
61 ... 15.111 : 8.532
62 ... 10.492999999999999 : 8.532
63 ... 17.953000000000003 : 8.532
64 ... 18.746000000000002 : 8.532
65 ... 12.171999999999999 : 8.532
66 ... 19.408 : 8.532
67 ... 18.56500000000001 : 8.532
68 ... 13.652 : 8.532
69 ... 18.108999999999998 : 8.532
70 ... 16.068 : 8.532
71 ... 13.835000000000003 : 8.532
72 ... 17.691000000000003 : 8.532
73 ... 13.824999999999998 : 8.532
74 ... 17.625 : 8.532
75 ... 11.214 : 8.532
76 ... 14.809 : 8.532
77 ... 15.036 : 8.532
78 ... 13.767 : 8.532
79 ... 13.439000000000002 : 8.532
80 ... 13.826999999999998 : 8.532
81 ... 14.885 : 8.532
82 ... 12.035 : 8.532
83 ... 14.636999999999999 : 8.532
84 ... 13.159999999999998 : 8.532
85 ... 13.600999999999999 : 8.532
86 ... 9.831000000000001 : 8.532
87 ... 12.470999999999998 : 8.532
88 ... 15.771 : 8.532
89 ... 11.030000000000003 : 8.532
90 ... 16.076000000000004 : 8.532
91 ... 13.691999999999998 : 8.532
92 ... 18.329 : 8.532
93 ... 9.317 : 8.532
94 ... 13.237999999999998 : 8.532
95 ... 12.823999999999996 : 8.532
96 ... 15.064000000000002 : 8.532
97 ... 16.816 : 8.532
98 ... 17.909 : 8.532
99 ... 13.828999999999999 : 8.532
All Process --- 0.5002748966217041 seconds ---
Best path
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 27, 26, 24, 25, 23, 22, 19, 21, 20]
Best distance
8.532For 100 iterations and 27 data points, we need about 0.49 seconds. It is quite fast. In the result shown above, we see the result for each iteration, and the best path and the best distance we obtained is 8.565 km.
Here is the convergence matrix from the result.
From that result, we can see the solution already gets convergence before iteration 40th. Before iteration 40th, the optimizer is quite fast to get better results.
Conclusion
We have already discussed Travelling Salesman Problem (TSP) is short, and then we discuss one algorithm that can be used to solve that problem. Then we jump into the code, pre-process the data, and get the distance matrix using the haversine library. Using this distance and a few parameters, we create an optimizer object from ACO class and optimize the result using the fit method. The result shown in this tutorial is promising and can solve the problem well.
Reference
S. Oliveira, M. S. Hussin, T. Stützle, A. Roli, and M. Dorigo, A detailed analysis of the population-based ant colony optimization algorithm for the TSP and the QAP. 2011.
M. Guntsch and M. Middendorf, Applying Population Based ACO to Dynamic Optimization Problems, vol. 2463. 2002.
M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Trans. Evol. Comput., vol. 1, pp. 53–66, 1997.
Z. Ibrahim, T. B. Kurniawan, N. K. Khalid, and M. Khalid, “Implementation of ant colony system for DNA sequence optimization,” Proc. 14th Int. Symp. Artif. Life Robot. AROB 14th’09, vol. 2009, pp. 712–715, 2009.
Google API, “Web Services — Geocoding API.” [Online]. Available: https://developers.google.com/maps/documentation/geocoding/overview.
ORS, “Open Route Service API.”
OR-Tools, “Traveling Salesperson Problem.” [Online]. Available: https://developers.google.com/optimization/routing/tsp.
