Introducing the Problem
Consider a manufacturer of heavy machinery such as ABB. The company has several factories, each of which is located in a different city.
For the sake of this problem, imagine that when a customer orders a custom-built machine from ABB, the components are built at the various factories, but they must all be collected before being delivered to the customer where they are assembled and installed.
Finding the most efficient or optimal route that visits each of these locations, while starting from and returning to some home base, is an example of the traveling salesperson problem.
Thanks to machine learning and Google's OR-tools, these types of problems are easier to solve. In addition, we can incorporate information such as distance and real-time traffic data from GoogleMaps, and even account for weather delays thanks to data from OpenWeather.
This problem is especially relevant for logistics-heavy industries with multiple pickup or delivery points (e.g., the postal service), and is consequential when minimizing operational costs.
The most obvious source of savings for a company is the reduction in fuel expenses.
But there are additional savings that are not as readily apparent. For example, fewer miles driven and less time spent in traffic yield lower maintenance costs for the vehicle fleet.
Saving fuel, lowering emissions, reducing vehicle wear, and diminishing the need for replacement parts, all serve to advance the sustainability efforts of the company.
Perhaps most importantly, an optimal route lowers the risk of unexpected expenses associated with a delayed delivery which causes both disgruntled customers and frustrated drivers.
The Problem and its Constraints
We define a delivery route as being composed of nodes, which are the different locations being considered along the route, and segments, which are the paths linking consecutive nodes.
For the problem considered here, there are several constraints to consider:
there are 3 factories located at different latitude/longitude coordinates;
there is 1 customer located at some latitude/longitude coordinates;
each factory begins with 1 delivery truck (this is the first node in a route);
the delivery truck always ends its route at the same factory from which it began (i.e., the first and last nodes in the route are the same factory location);
each location (the 3 factories and the customer's location) must be visited exactly once, and no more;
the penultimate node in the route (i.e., the node just before the delivery truck returns to the first/last node) is always the customer's location;
a loading time of 1 hour is included for each factory that is not the starting node;
an installation time of 2 hours is included at the customer's location;
a factor to account for weather-related delays is included, e.g., to ensure the safety of drivers, a delivery on a snowy day is permitted to take twice as long as suggested by GoogleMaps traffic data.
the optimal route minimizes the total delivery time (alternatively, we could choose to minimize the total mileage if the motivating factors are fuel usage and emissions, or vehicle wear).
The three factories being considered are located in:
Geneva: address: Rue du Pré-Bouvier 25, 1242 Satigny
lat.: 46.2222467
long.: 6.0541656
Lausanne: address: Rue du Grand-Pré 2A, 1007 Lausanne
lat.: 46.5266937
long.: 6.6014798
Schaffhausen address: Fulachstrasse 150, 8200 Schaffhausen
lat.: 47.7085381
long.: 8.6388662
The customer's location is:
Gstaad: address: Promenade 55, 3780 Gstaad
lat.: 46.4742115
long.: 7.2810446
Problem: How does one find the optimal route that satisfies these constraints?
Solving the Problem with Data Science
GoogleMaps by itself will not find the optimal route when multiple starting points are possible. This would require the user to type each possible route segment into Google Maps, collect the total travel time or distance of the full route, and compare them to identify the route that's optimal. This is not only tedious, but it wastes valuable time and resources, and it does not account for weather-related adjustments nor does it consider loading and installation times.
There are several strategies for finding the optimal route. A simple, but effective, solution can be obtained by using PATH_CHEAPEST_ARC from Google's OR-Tools.
However, for cases in which the number of locations is on the order of 10 or more, this process may take too long or may even give up before a solution is found. The Global Route Optimization (GRO) tool from Google or batch calls to Google's Distance Matrix API can help scale up the optimization process to hundreds of locations.
Given the small number of nodes in this problem, it is straightforward to solve the problem using a brute-force technique. In other words, we could simply ask the computer to calculate all possible routes and then select the optimal one, rather than using an optimized solver like OR-Tools or GRO. Thus, the choice of which technique to use among brute force, OR-Tools, or GRO, depends on the initial conditions and the computational costs.
To find the optimal route, we create several Python functions whose roles are described below.
get_travel_time_and_distance
This function takes as inputs latitude and longitude coordinates for the origin and the destination nodes of a route segment, sends a query to the GoogleMaps API, and outputs the travel time and distance between these nodes.
get_weather
This function takes the latitude and longitude coordinates of a given node, sends a query to the OpenWeather API, and returns the weather conditions for that location which will be used to adjust the travel times.
build_travel_data
This function takes a list of locations in the route, and builds a matrix of travel data (distance and weather-adjusted driving time) for each origin-destination pair of nodes. Since there are weather-related adjustments to the driving times, and given that we are considering loading and installation times as part of the problem, then the travel data matrix must be updated with the new departure times from each node.
find_optimal_route
Given the travel data matrix as an input, this function uses the OR-Tools solver function (or a brute-force solver, depending on the situation) and returns the optimal route as a sequential list of node pairs each defining the origin-destination endpoints of a segment.
generate_google_maps_url
This function takes as input the optimal route as a sequential list of node pairs, and returns the GoogleMaps URL of the full route with travel distances and weather-adjusted driving times.
Results & Conclusions
These functions are run in the order given. Within seconds, the model returns an output of a complete route whose optimization is geared towards minimizing the total driving time.
Examples of this output are presented below.
First, we present a section of the standard output that was written to the log file (Fig. 1). This output shows the different segments of the optimal route and includes the weather-related adjustments and loading/installation times.

Next, we present the Google Map that shows each step in the route with the net driving distance and travel time (Fig. 2).

As illustrated in Figs. 1 and 2, the optimal route given current and predicted traffic and weather conditions recommends that the delivery truck begin its route from the factory in Lausanne (Prilly). The next stops on the route are the factories in Geneva (Satigny) and Schaffhausen in that order, then the route proceeds to the customer's location in Gstaad. Once the delivery has been made to the customer, the delivery truck returns to its home location of Lausanne.
According to GoogleMaps, the total distance of the route is 734 km for a net driving time of 8h54m. Including weather adjustments and loading/installation times, the total delivery time is 13 hours.
By comparison, a route that begins in Geneva or Schaffhausen, both of which appear to be a more intuitive choice than Lausanne since they are located at the extremities of the circuit, would take 10 minutes longer to complete for a total distance that is 10 km longer.
The optimal route represents a direct savings of a few hundred to several thousand dollars per delivery.
Keep in mind that the optimal route and its travel distances and driving times can change during the course of the day or the week depending on traffic and weather conditions.
Thus, the optimization process leads to a reduction in delivery times and distances ranging from 1% to over 50% depending on the number of locations. This represents a direct savings of a similar percentage range in delivery costs, which in dollar terms may be anywhere from a few hundred to several thousand dollars per delivery.