Solving logistic challenges with A Better Routeplanner

The changing climate of our planet is one of the most urgent challenges we are facing as a society. While we can not predict the results of the warming, the effects will be mainly negative. As with most complex challenges, there does not exist a simple solution. Instead, nations, organizations, and individuals must take collective responsibility to counteract and minimize their effect on the climate. While most would agree that reducing global warming is an important issue, the tricky part is that other important issues conflict in interest. An example of two often counteracting aspects is economic profitability and environmental sustainability, but that is not always the case - as we will see here.

One area with large economic and environmental effects is logistics. As a provider of an electric vehicle (EV) routeplanner, we have an interest in how logistic solutions can be improved with the usage of EVs. There are lots of challenges to be overcome to gain the maximum benefits from including EVs within courier fleets. New limitations will become clear, organizations will have to adapt, and infrastructure support will need to be improved. There are, however, many possible benefits that will outweigh the disadvantages. One of the main strengths of EVs, in the context of logistics, is that they are profitable both economically and environmentally. They are simply cheaper to drive, produce fewer emissions, and do not need the same amount of maintenance. Including EVs within logistic solutions does, therefore, not require a compromise between economic and sustainability aspects. And it is fair to say that this is kind of a big deal in the context of logistics.

The problem

The purpose of this article is to share the results of our research on how ABRP can be applied to a common logistical problem. The investigated problem is called the electric vehicle routing problem (E-VRP), and it is a generalization of a more well-known optimization problem called the traveling salesman problem. The E-VRP is a combinatorial optimization problem in which one is to optimize the routes taken by a courier fleet consisting of EVs. Given a set of customers, all of which is to be visited once, the optimal sequence of customer visits is to be determined. As the problem is related to EVs, recharging stations can and recharging time is also to be accounted for in calculating the cost of a sequence of visits.

A typical solution to the E-VRP. The blue dots are customers, the red dot is the start/end position, and the green dots are chargers. Each line describes the path of a specific vehicle (there are nine vehicles in total). The path from and to the depot is omitted.

Available algorithms

There are many algorithms available that can be used to find a reasonable solution to an E-VRP problem. Within the category of most successful algorithms, we find algorithms commonly denoted by their abbreviations, such as VNS, ACO, and PSO. These algorithms have in common that they are metaheuristics. A metaheuristic is a general procedure that aims to find a sufficiently good solution to an optimization problem. The two latter are examples of nature-inspired algorithms using swarm intelligence. ACO is short for ant colony optimization, and PSO is short for particle swarm optimization.

A summary of how one can categorize algorithms commonly applied to the E-VRP.

Where ABRP can provide value

Let us now return to the main problem of solving the E-VRP and discuss how the knowledge gained with ABRP can be applied. When trying to solve the problem, it is important to create an accurate model. This is not trivial since it is a well-known fact that predicting the consumption of EVs is a complex and difficult task. To make things even more difficult, many relevant parameters are dynamic, time-dependent, and stochastic. For example, weather conditions, traffic conditions, and charger availability.

However, a lot of the difficulties in assigning attributes with correct values for EV models arise in a wide set of problems. At Iternio, we have been facing these challenges for more than five years and have had millions of unique users using our application to plan their EV trips. As a result, we have lots of data and experience when it comes to creating consumption and charging models. Furthermore, to be able to provide the best planning service possible, we have had to solve challenges with live data regarding charger status, vehicle status, weather, and traffic conditions. Lastly, we are also capable of providing turn-by-turn instructions for a calculated route.

Solving the E-VRP

The E-VRP is a very hard problem to solve (even NP-hard). The number of combinations for the order of customer visits grows extremely quickly. The number of possible combinations in the simpler traveling salesman problem is approximately a factorial of the number of included customers. That is to say, at approximately 60 customers, the number of possible combinations is somewhere close to the number of atoms in the universe.

After implementing a couple of algorithms, we concluded that the one working best for us was to use a conceptually very simple algorithm. It can be described as follows:

1. Find an initial solution in a naive manner.

2. Try to improve the solution using a series of simple actions, such as relocating and swapping customers in the visit order. This is performed for a fixed number of iterations or until no improved solution is found.

3. Either (a) exit the algorithm or (b) perform a larger alteration to the best-found solution, which is allowed to make it worse, and start over from 2 with the new solution.
   

The main motivation for preferring the algorithm described above is that it is very flexible and can easily be adapted to different versions of the problem by simply changing the actions taken in steps 2 and 3b. There is a lot more to be said about the situational approach but for the sake of brevity, we will not go any further. We do, however, plan to publish a more in-depth series on this problem and our solution, targeted at the more technical reader.

A solution to a real-world problem modeled using ABRP.

Conclusion

Trying to optimize problems, including EVs, is, in general, a complex task. Collecting the relevant data and estimating the model parameters is challenging. The good news is that there already exist many solutions for a wide range of these difficulties. At Iternio, we have required lots of experience and familiarity within these fields. Our knowledge and resources can be applied to a wide set of problems, where the E-VRP is such an example. While each new problem comes with its own set of challenges, each solution does not have to solve everything from the beginning. Through collaborating, we can collectively move towards a more efficient adoption of EVs.

For the interested reader, we can recommend a master's thesis written in collaboration with ABRP.