Solving Traveling Salesman Problem

10 min readNov 28, 2022

Optimize the routes to deliver parcels using python to save delivery costs (Study case: parcels delivery in Bandung, Indonesia with simple data)

Photo by José Martín Ramírez Carrasco on Unsplash

Traveling Salesman Problem or TSP is a combinatorial optimization problem that tries to answer the question “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”. In a simple way, TSP is tasked to find the shortest route between a set of points that must be visited. It becomes a real issue in the supply chain and logistics industry as they rocketed following e-commerce rises.

So, why is TSP important? In essence, it helps the company to gain more profit by saving time and resources. In the logistics industry, one of the ways to generate more profit is by efficiency in delivery costs and time. There are various ways to achieve that, one of them is by solving the Traveling Salesman Problem (TSP), where you are trying to find the most efficient routes to take on the road. The more efficiently it is resolved, the less time is spent driving, the more fuel is saved, the fewer hours are needed, and even the more packages are delivered. As a result, the balance sheet of any delivery-based business activity will benefit twice.

Therefore, I am trying to create a demo of this Traveling Salesman Problem for a courier of a parcel delivery company in Bandung to reduce the delivery costs.

Note: as this is a simple demo, the data used is only 8 delivery dummy points and the data are data generated randomly.

Scenario

You are a manager in a parcel delivery service center in Bandung. You should deliver packages to some of the customers from your depot with 1 vehicle. The distribution of the delivery points and the depot can be seen below (Figure 1).

Figure 1. Spatial distribution of delivery points

**Anyway, you can adjust the number of vehicles and the number of delivery points as you wish by editing the source code below

Objectives

Find the best routes to deliver all the parcels to customers.

To track how good the model or solution we are trying to implement is, it is better to define the business metrics. Since the data of related cases is not available, I will only mention the potential without measuring how good the solution is. Those potential business metrics are:

Delivery costs
Time spent
On-time delivery rate
Customers Satisfaction score (CSAT score)

Result

Utilizing the Google OR-Tools, the best route with one vehicle is:

Depot -> Address 5 -> Address 6 -> Address 7 -> Address 4 -> Address 3 -> Address 2 -> Address 1 -> Depot

Distance of the route: 7.44 km

Technical Steps

Figure 3. Flowchart of processing in Python

The full code is provided here.

I. Import Library and Read Data

Before all, we have to import the libraries to Google Colab. We are going to use some libraries.

numpy and pandas: for numerical operations and data manipulation
itertools: to create iterators for efficient looping
ast: to process trees of the Python abstract syntax grammar
requests: to make HTTP requests
json: to work with JSON data
networkx: for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks
osmnx: to download geospatial data from OpenStreetMap and model, project, visualize, and analyze real-world street networks and any other geospatial geometries
folium: to visualize data that’s been manipulated in Python on an interactive leaflet map
ortools: to solve combinatorial optimization problems

In Google Colab, not all libraries are available. So, we have to install some of them using pip (or conda).

# Install and Import Library
pip install osmnx
pip install ortools

import numpy as np
import pandas as pd
import itertools
import ast
import requests
import json
import networkx as nx
import osmnx as ox
import folium
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

from google.colab import drive
drive.mount('/content/drive')

import warnings 
warnings.filterwarnings('ignore')

After importing all libraries, I import the data from my Google Drive. The path may be different based on where you save the dataset.

# Read data
df_points = pd.read_excel('/content/drive/MyDrive/dataset/delivery_destinations.xlsx')

Let’s take a look at the data (Figure 4). The data include 8 points: 7 delivery points and 1 depot point. The fields in this dataset are tracking_id (define the parcel tracking id), point_name (the name of the point), and address (the address of the delivery location).

II. Geocoding

Geocoding is the process of transforming a description of a location — such as a pair of coordinates, an address, or a name of a place — to a location on the earth’s surface. In brief, we are trying to retrieve the latitude and longitude from the address of the dataset. This latitude and longitude will be used later to calculate the travel distance between points and determine the best delivery route.

I am using HERE API for the Geocoding considering that it is pretty accurate and free to use (with limited calls). You can read this article for the details of this process.

# Define variables
apikey = '<YOUR-API-KEY-HERE>'
url = 'https://discover.search.hereapi.com/v1/discover'
headers = {'Content-Type': 'application/json'}
origin_point = '-6.8918336,107.6103212'
latlong_origin = []
latlong_points = []

# Get lat long using HERE Map API
for i, data in df_points.iterrows():
  # your place name is defined below
  place_name = data.address
  my_params = {'at' : origin_point,
               'limit' : 1,
               'apikey' : apikey,
               'q' : place_name}
  r = requests.get(url, params=my_params, headers=headers)
  output = json.loads(r.text)
  latlong_dict = output['items'][0]['position']
  latlong = ', '.join(map(str, latlong_dict.values()))
  latlong_points += [latlong]

# Create dataframe
df_points['lat_lng'] = latlong_points
df_points['lat_lng'] = df_points.lat_lng.apply(ast.literal_eval)

This step will result in a DataFrame like this:

Notice that now we have a field called lat_lng which contains the latitude and longitude of the points.

III. Calculate Travel Distance Between Points

Next is to calculate the travel distance between points. It is important in the Traveling Salesman Problem since the shortest route is generated from the total distance taken from every possible route. Instead of using euclidean distance (drawing a line between points), we will use a more relevant distance which is creating a path following the road between points. This path will represent the distance between points.

To do this, we will utilize the shortest_path method from networkx. But before that, we should create the origin-destination DataFrame to make it easier to calculate the distance between points. This DataFrame is generated by making all possible combinations/permutations of origin and destination points.

# Create dataframe of origin-destination #

# Create variables
list_points_name = df_points['point_name']
# list_points_latlong = df_points['lat_long']
list_points_latlong = df_points['lat_lng']

# All points combinations
list_pair_name = [i for i in itertools.product(list_points_name, repeat=2)]
list_pair_latlong = [i for i in itertools.product(list_points_latlong, repeat=2)]
df_nodes = pd.DataFrame({'pair_name': list_pair_name, 'pair_latlong': list_pair_latlong})

# Source/Target
df_nodes['origin'] = df_nodes['pair_name'].apply(lambda t: t[0])
df_nodes['destination'] = df_nodes['pair_name'].apply(lambda t: t[1])
df_nodes['latlong_origin'] = df_nodes['pair_latlong'].apply(lambda t: t[0])
df_nodes['latlong_destination'] = df_nodes['pair_latlong'].apply(lambda t: t[1])
df_nodes.drop(['pair_name', 'pair_latlong'], axis =1, inplace = True)

The code above will produce a DataFrame like this:

Figure 6. Origin and destination DataFrame

Now, we can calculate the distance between points using networkx.

# Calculate distance from point to point using networkx #

# Location where you want to find your route
place     = 'Bandung, West Java, Indonesia'
# Find shortest route based on the mode of travel
mode      = 'drive'        # 'drive', 'bike', 'walk'
# Find shortest path based on distance or time
optimizer = 'length'        # 'length','time'
# Create graph from OSM within the boundaries of some geocodable place(s)
graph = ox.graph_from_place(place, network_type = mode)

# Create lists
list_route = []
list_route_length = []

# Determining distance and route
for i in range(len(df_nodes)):
  # find the nearest node to the start location
  orig_node = ox.get_nearest_node(graph, df_nodes.iloc[i]['latlong_origin'])
  # find the nearest node to the end location
  dest_node = ox.get_nearest_node(graph, df_nodes.iloc[i]['latlong_destination'])
  #  find the shortest path
  shortest_route = nx.shortest_path(graph,
                                    orig_node,
                                    dest_node,
                                    weight=optimizer)
  shortest_route_length = nx.shortest_path_length(graph, orig_node, dest_node, weight=optimizer)
  # append list
  list_route.append(shortest_route)
  list_route_length.append(shortest_route_length)

After running the code, we will get a distance matrix. But to simplify the understanding, I will display it in a DataFrame form. The value represents the distance between two points in meters. For instance, take a look at row 1 and column 2. It means the distance from Depot to Address 1 is around 1,301 meters or 1.3 km. The distance from Depot to Address 1 might be different than the distance from Address 1 to Depot given that the most effective path could be different as well. Road conditions like one-way streets and road closures could be the reason for this.

Figure 7. Distance between points DataFrame

IV. Determine the Best Vehicle Route

Then, we can determine the best route to deliver parcels to all customers utilizing Google OR-Tools. First, we have to define the functions to help us find the shortest route. It refers to this page with some modifications.

def create_data_model(distance_matrix, num_vehicles, depot_order):
    """Stores the data for the problem."""
    data = {}
    data['distance_matrix'] = distance_matrix
    data['num_vehicles'] = num_vehicles
    data['depot'] = depot_order
    return data

def distance_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['distance_matrix'][from_node][to_node]

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    max_route_distance = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_distance = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(manager.IndexToNode(index))
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
        plan_output += '{}\n'.format(manager.IndexToNode(index))
        plan_output += 'Distance of the route: {}m\n'.format(route_distance)
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
    print('Maximum of the route distances: {} m'.format(max_route_distance))

def get_routes(solution, routing, manager):
  """Get vehicle routes from a solution and store them in an array."""
  # Get vehicle routes and store them in a two dimensional array whose
  # i,j entry is the jth location visited by vehicle i along its route.
  routes = []
  for route_nbr in range(routing.vehicles()):
    index = routing.Start(route_nbr)
    route = [manager.IndexToNode(index)]
    while not routing.IsEnd(index):
      index = solution.Value(routing.NextVar(index))
      route.append(manager.IndexToNode(index))
    routes.append(route)
  return routes

Next, use the function to get the shortest route.

# Instantiate the data problem.
data = create_data_model(distance_matrix=distance_matrix, 
                         num_vehicles=1, 
                         depot_order=0)

# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                        data['num_vehicles'], data['depot'])

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)

# Create and register a transit callback.
transit_callback_index = routing.RegisterTransitCallback(distance_callback)

# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Add Distance constraint.
dimension_name = 'Distance'
routing.AddDimension(
    transit_callback_index,
    0,  # no slack
    50000,  # vehicle maximum travel distance
    True,  # start cumul to zero
    dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)

# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)

# Print solution on console.
if solution:
    print_solution(data, manager, routing, solution)
else:
    print('No solution found !')

BAM! Finally, we get the shortest route for this simple case. The shortest possible route is:

Depot -> Address 5 -> Address 6 -> Address 7 -> Address 4 -> Address 3 -> Address 2 -> Address 1 -> Depot

This shortest route will take a distance of around 7.44 km.

V. Create a Path for the Most Effective Route

Data visualization is one of the best ways to make it easier to comprehend this case. Therefore, in this last step, we will make a spatial data visualization to depict the best route. We should create a new DataFrame that includes the best route only, then create the path.

# Create path for the most effective route #

# Create DataFrame of route order
df_nodes_best = pd.DataFrame({'origin' : route_name[:-1], 
                              'destination': route_name[1:]})
df_nodes_best = df_nodes_best.merge(df_nodes, on=['origin', 'destination'], how='inner')
df_nodes_best["route_order"] = [f"Route {i}" for i in range(1, len(df_nodes_best)+1)]
df_nodes_best

# Create lists
list_route_best = []
list_route_length_best = []

# Determining distance and route
for i in range(len(df_nodes_best)):
  # find the nearest node to the start location
  orig_node_best = ox.get_nearest_node(graph, df_nodes_best.iloc[i]['latlong_origin'])
  # find the nearest node to the end location
  dest_node_best = ox.get_nearest_node(graph, df_nodes_best.iloc[i]['latlong_destination'])
  #  find the shortest path
  shortest_route_best = nx.shortest_path(graph,
                                    orig_node_best,
                                    dest_node_best,
                                    weight=optimizer)
  shortest_route_length_best = nx.shortest_path_length(graph, orig_node_best, dest_node_best, weight=optimizer)
  # append list
  list_route_best.append(shortest_route_best)
  list_route_length_best.append(shortest_route_length_best)

# Store best route distance in a list
distance_result_best = list_route_length_best.copy()

Finally, we can visualize the shortest route using folium:

# Convert nodes code into lat long
all_list_nodes_latlong = []

for i in range(len(list_route_best)):
  list_nodes_latlong = []
  for j in range(len(list_route_best[i])):
    tuple_nodes_latlong = (graph.nodes[list_route_best[i][j]]['y'], graph.nodes[list_route_best[i][j]]['x'])
    list_nodes_latlong.append(tuple_nodes_latlong)
  all_list_nodes_latlong.append(list_nodes_latlong)

# Load map
my_map = folium.Map(location=[-6.897097, 107.621903],
                    zoom_start=15,
                    tiles='cartodbpositron')

# Plot route polyline
for i in range(len(all_list_nodes_latlong)):
  folium.PolyLine(all_list_nodes_latlong[i],
                  tooltip=f"{df_nodes_best['route_order'].iloc[i].upper()}:\
                  {df_nodes_best['origin'].iloc[i]} to {df_nodes_best['destination'].iloc[i]}\
                  - Distance: {round(distance_result_best[i]/1000, 2)} km",
                  # color=random_color(),
                  weight=5).add_to(my_map)

# Plot points
for i in range(len(df_points)):
  if i != 0:
    folium.Marker(location = df_points['lat_lng'][i], 
                  popup = df_points['point_name'][i]).add_to(my_map)
  else:
    folium.Marker(location = df_points['lat_lng'][i], 
                  popup = df_points['point_name'][i],
                  icon = folium.Icon(color='crimson')).add_to(my_map) # mark depot with red symbology

print(f'Total distance: {round(sum(distance_result_best)/1000, 2)} km')
my_map

Conclusions

The solution can help us to find the best routes to deliver all the parcels to customers. The shortest distance to travel is 7.44 km with the following route:

Depot -> Address 5 -> Address 6 -> Address 7 -> Address 4 -> Address 3 -> Address 2 -> Address 1 -> Depot

The potential business implications or benefits from this project are: