Vehicle Scheduling Using Mathematical Models
As we develop advanced solutions for our clients, we face new challenges every day that require innovative approaches to optimize processes, reduce costs and deliver a better end-user experience. In the past posts, we shared how we can use AI in areas such as lotteries, insurance, and telecommunications. In one of the most recent projects, we faced a challenge from a company that deals with transportation where we solved the problem with the help of more analog solutions.
This time we will not talk about artificial intelligence, but about the in-depth mathematical knowledge, reflection, and processes we performed, without which we would not have arrived at the desired result.
Vehicle scheduling challenges
Managing transportation routes is a much more demanding task than it may seem at first glance. If in the past, for example, taxi drivers had to know their city like the back of their hand, knowing all the streets and congestion points, this problem has been partially solved some time ago by navigation systems such as Google Maps, which enabled practically anyone with a driver's license to do a taxi driver's job. With the use of modern technologies, algorithms, and the right data, however, we can go one step further.
Several variables affect the routing of a transportation company's vehicles. Road conditions are just one of the external factors, and then there are many internal factors, such as scheduling different customers and time allocation for transportation. Therefore, we looked for a solution to our client's challenge while considering both internal and external factors, knowing that a satisfactory one-size-fits-all, off-the-shelf solution does not exist because every larger company has specific requirements that require a specific approach. We quickly realized that the final solution would require "raw" computation before we could integrate the technology into the project.
In the search for a suitable solution
Our main task was to summarise all the complexity of the problem into a mathematical equation and to find a suitable algorithm or mathematical model that would be able to process this equation in a way that would lead us to a suitable solution. To simplify the whole process, we divided it into two phases.
Challenge 1: How to write down all the complex constraints and specific requirements of our client in order to explain them to the mathematical model through calculations?
Challenge 2: Which algorithm or mathematical model to use to solve this problem?
Not everything is that simple, of course, because first, you need to understand the problem in detail, which requires working together with the client. The formulation of the problem happens in the first, exploratory phase, where, through discussions with the client, we identify the challenges that would be worth addressing to improve the company's performance and its services. Only once we understand the problem can we convert it into a mathematical form that becomes part of the algorithm. Designing the equation is anything but a routine task, as it requires an in-depth knowledge of the Java language, advanced mathematical skills, and contextual knowledge of the vehicle scheduling problem. Studying the appropriate procedure for solving the formulated mathematical models, which follows the research phase, is what brings us one step closer to the final solution, and our great advantage in this is the experience and prior knowledge of solving such problems.
Once the problem has been transformed into a mathematical calculation, the task is far from over. What follows is the search for the right mathematical model or algorithm. At Medius, we are committed to open-source solutions, so we again looked for an algorithm that would meet our standards. Among solutions such as SCPSolver, CLP (COIN-OR Foundation), and OR-Tools, we opted for the latter. During the testing phase of the different algorithms within OR-Tools, we found that certain algorithms can solve the problem for a small number of vehicles, but when the number of vehicles increases, we have to replace the algorithm with another one. After a lot of testing, we found an algorithm that understood our mathematical calculus and answered our client's problem.
Validation and future upgrades
When looking at the process from the point of view of the final solution, the steps seem logical and straightforward. However, it is a highly complex process and without the Medius team's in-depth knowledge and experience from past projects, the solution would not have emerged as quickly or been as effective. Of course, all of this is just the beginning. By using the vehicle scheduling system, the amount of processed data and scheduled transportation events continually increases, which is a crucial starting point for the implementation of machine learning (artificial intelligence) that can, in turn, further improve the scheduling of vehicles over time.
In practice, this means that we continue to determine what works and what doesn't, and use feedback from the client to refine the solution. Finally, let us emphasize once again what we believe to be the key to satisfaction for everyone involved — cooperation, understanding, and expertise.