Introduction

The effects of a changing climate are visible: droughts, reduced harvests, destruction of critical infrastructure, and displacement of communities. Situations like those are forcing different countries to commit to achieving carbon neutrality by 2050 (Paris Agreement). As a consequence, the digital transformation of different sectors (energy, transportation, etc), to attain sustainability, becomes an urgent necessity.

Globally, the transportation sector is one of the most difficult to decarbonize. Electric vehicles are often cited as a mitigation strategy for Greenhouse Gas (GHG) emissions. But there are other factors to take into account that go from the material used in batteries and electronic equipment, to whether the infrastructure for the distribution of electrical energy depends on fossil sources. Furthermore, other palliative approaches such as ride-sharing and autonomous vehicles may potentially increase GHG emissions due to the Jevons’ effect.

Perhaps an effective method is route optimization, as passenger and freight transportation are responsible for about half of transport GHG emissions and much of this mileage occurs inefficiently which ultimately increases the amount of traffic on the roads. Machine Learning (ML) combined with  Operations Research (OR) can help both by making long trips less necessary and avoiding congestion, and by optimizing the complex interaction of shipment sizes and transport modes. 

Problem statement

Carryt, the project organizer, is a last-mile logistics provider with a technology product empowering the gig economy, providing drivers with a livable wage, and offering delivery services to customers. They joined Omdena’s incubator for impact startups.

The delivered project consisted of building a solution to find optimal routes (least total distance) for a fleet of vehicles that either deliver packages picked from a depot to a set of sites, or pick up and deliver packages from and to a set of locations; while honoring a set of constraints:

1. Vehicle start and stop locations (longitude and latitude).

2. Vehicle capacity: the maximum capacity of items they can transport.

3. Pickup time interval for each pickup location (start and end times in HH:MM, e.g. 08:00 to 14:00).

4. Dropoff time interval for each dropoff location (start and end times).

5. Time spent at each location (considering the time it takes to service a location).

6. Priority: the vehicles must pay a penalty for each visit that is dropped.

Therefore, the purpose of this article is:

• To explain the importance of route optimization in last mile logistics, and its impact on reducing GHG emissions.
• To elaborate on Graph Theory and how it was used to model a routing solution.
• To illustrate how combinatorial optimization, specifically Vehicle Routing Problem (VRP) and its variations, can be combined with ML.
  

What is last-mile logistics and why is it important?

Last-mile is the final step of the delivery process, in other words, the point at which the packet arrives at the buyer’s door. It is the most expensive and time-consuming part of the shipping process because it requires numerous stops with low drop sizes. For example, in urban areas there are constant delays because of traffic congestion; meanwhile, in rural areas, the delivery locations could be several miles apart with only a couple of parcels for each one. Other key problems are failed deliveries and poor granular tracking.

Customers have progressively turned to e-commerce for all their purchasing needs, forcing retailers and logistics partners to develop new technologies and to assume the costs for fast and free delivery. Therefore, by optimizing routing, the number of vehicle miles traveled and fuel costs can be reduced and, as a collateral effect, transportation GHG emissions. 

What is Graph Theory?

It is the study of graphs, which are diagrams involving lines (edges) and points (nodes), used to model pairwise relations between objects. For example, identifying optimal routes in logistics planning like Vehicle Routing Problem (VRP) and its variations. Graphs vary in type (see Figure 2), have many attributes, and exhibit different classes of algorithms. 

Common attributes of graphs

• Unweighted graphs versus Weighted graphs: whether there are values on edges or nodes. These values represent cost, time distance, capacity, or even domain-specific prioritization. There are differences in performance and results when weights are ignored. For example, in Figure 3 the shortest path from A to E in the Weighted graph would be a distance of 50 km crossing A, C, D, E. Meanwhile in the Unweighted graph, the shortest one would be calculated using the number of hops between each node (2 hops crossing A, D, E).

• Undirected graphs versus Directed graphs: whether or not edges explicitly define a start and end node. Directions add more context to the graph to infer more information. For example, if the directed graph in Figure 4 was a network of delivery points, and the edges were “roads”, then between A and C there are 2 roads or it is a bidirectional one.

Classes of Graph Algorithms

There are 3 areas of analysis: a) Pathfinding and search, b) Centrality computation, and c) Community detection. Being the first one relevant for this Omdena challenge.

• Pathfinding and search: where the shortest path is the traversal route with the fewest hops or lowest weight between two nodes. These algorithms are useful for understanding the way data is connected. Some examples are Dijkstra and A*. 

A* is an extension of Dijkstra’s algorithm, but it achieves better performance by using heuristics to guide its search. Despite its major drawback which is storing all generated nodes in memory (making it computation-intensive), it is still the best solution in many cases.

Vehicle Routing Problem (VRP)

It is a combinatorial optimization that entails finding an optimal set of routes for a fleet of vehicles to serve a set of customers. The objective is to minimize the global transportation cost, which can be monetary, distance, or the number of vehicles needed to serve all customers.

Several variations exist, for example: 

• Vehicle Routing Problem with Time Windows (VRPTW): vehicles are required to visit locations during specific time windows requested by customers.
• Capacitated Vehicle Routing Problem (CVRP): vehicles have a limited carrying capacity (weight or volume) of items.
• Vehicle Routing Problem with Pickup and Delivery (VRPPD): vehicles need to move items from certain pickup locations to other delivery locations.

The length of time it takes to solve VRPs grows exponentially with the size of the problem. Therefore, finding an optimal solution may take several years. Consequently, any routing software must return a solution that is good enough but not the best one.

In this Omdena challenge, a directed graph was created from the files provided by the client: 

• A custom built-map (.shp): roads direction, speed limit, coordinates (latitude, longitude).
• Forbidden turns (.osm): no U-turn, no Left turn, etc.

In other words, the road network was described using a graph where the edges are roads and nodes are vertices between them. The direction of edges specifies whether the connection between a pair of nodes is both ways or one (like road intersections in a typical city). Meanwhile, the nodes represent intersections and waypoints along a stretch of road. The weights (costs) on the edges correspond to the total time it will take to traverse them (distance/speed); making the global cost the sum of these on the shortest path. The A* algorithm was modified to include the list of .osm restrictions, and it was used to find the optimal route.

How can ML be integrated into VRP research?

Numerous models and algorithms have been proposed to solve VRP problems, yet few have reached a satisfactory level. The majority of existing research focuses on the use of mathematical models that are associated with unrealistic assumptions. Making it difficult to use them in real-world scenarios. To tackle the issue, there is an emerging study direction that combines ML tools with conventional optimisation-based techniques. Some approaches are:

a. ML-Guided VRP decomposition strategies

As VRPs search space grows with respect to the problem size, finding an optimal solution becomes challenging. A common strategy is to divide the problem into sub-problems. 

• Hierarchical Approach
  • Cluster First and Route Second (CFRS): for example, in the first stage customers are assigned to vehicles using the best-performing clustering algorithm (K-means, K-medoids, DBSCAN). In the second stage, Linear Programming (LP) is used to construct vehicle routes.
  • Route First and Cluster Second (RFCS): for example, implement a Genetic Algorithm (GA) to create the route, then partition it and compare it in different scenarios, using clustering algorithms (K-means, K-medoids, K-modes).

b. Predictive Models for Uncertainties in VRP

In VRP, customer demands and vehicle travel time are not deterministic. Therefore, a solution based on ML algorithms can be used to predict them.

c. Learning to configure algorithms

VRP algorithms have a great number of hyperparameters that need to be carefully adjusted to obtain a good performance. For example, clustering was employed for fine-tuning a multi-depot vehicle routing problem.

Conclusions

The transportation sector is one of the most difficult to decarbonize. Different approaches have been proposed in order to mitigate GHG emissions such as ride-sharing and autonomous vehicles. But due to the Jevons Paradox those solutions may potentially worsen the situation. 

Route optimization is perhaps a better fix, as freight transportation increases traffic on roads and is responsible for about half of GHG emanations. In this project, Graph Theory was used for modeling a last-mile logistics delivery application to identify optimal routes for a fleet of vehicles. Also, an adapted version of the A* algorithm was implemented.

VRP is one of the most studied combinatorial optimization problems because of its relevance in the transportation sector. As there are not yet satisfactory solutions, a new research branch has appeared combining ML with VRP algorithms. The end goal is to automate the modeling process and algorithmic performance for real-life VRP scenarios.

Ready to test your skills?

If you’re interested in collaborating, apply to join an Omdena project at: https://www.omdena.com/projects