How Do You Send Everyone To Work On Time?

The vehicle routing problem is a complex one and is extremely difficult to solve. For 150 passengers on 8 buses, the number of possible solutions is not in the hundreds or thousands, but is 136 digits long! In SWAT’s algorithm, there are additional constraints to consider: guaranteed seats for everyone, total journey time to not exceed a specified time depending on where they live, passenger walking distance, total distance travelled, etc.

So how does our algorithm work?

To generate optimal routes, 2 matrices are first created, one for the travel time between every pair of stops, and one for the distance travelled between every pair of stops. Possible routes are generated from the 2 matrices, with the total time and total distance travelled derived from each matrix. As you can imagine, each matrix is exceedingly large, and if we were to solve for every combination, the computing resources and time needed would be impractically high. As a result, SWAT uses a stochastic meta-heuristic approach to find an optimal solution for this problem. In layman terms, this method produces a multidimensional space with each node representing a “cost”, and the optimal solution is the one with the least “cost”. Cost here, for example, can refer to the drive time, or the distance travelled.

Our algorithm, which is the heart of our routing technology, is highly efficient and can solve for 500 bookings in approximately 30 seconds. In fact, SWAT holds several records for the Li & Lim Benchmark, the global benchmark that keeps track of top solutions for this routing and resource allocation challenge.

We hope this article is able to give you an extremely simplified peek into our technology, and how we are able to optimise rides effectively for all our clients.

‍