Introducing the Vehicle Routing Playground

Background

Over the past two decades, e-commerce and other convenience services like food delivery and ride sharing services have become more ubiquitous in our daily lives. Over time the market place has become increasingly more competitive as services try to differentiate themselves with promises of more convenience in the form of faster delivery, promised delivery periods, free returns and all of this at an ever decreasing cost for the customer.

Now, the cost of logistics is not low as it requires a lot of capital to source the warehouse(s), vehicles and manpower to fulfill the supply chain. Unsurprisingly, streamlining and reducing the cost of logistics is paramount for any organisation’s long-term economic viability. Using the advancement in computational technologies and the ever-increasing available data, organisations can turn the efficiency of their logistics into a competitive advantage - enter operations research.

Operations Research

Operations research (OR) is what I like to describe as the older, less sexy field of applied mathematics that has been overshadowed by its younger cousins, machine learning and its sub-field deep learning, which have gone and made headlines with deep fake videos or music generated by computers. Nonetheless, the resurgence of machine learning also paved a way for more and greater exposure to OR. Now, more than ever, organisations are discovering how models formulated by researchers decades ago can help them improve strategical, tactical and operational decision-making. Examples of use-cases would be using it to manage optimal inventory levels, decide where to manufacture goods or source from in supply chains, manage ticket prices, schedule resources and workforce management, decide which destinations to open or close in the airline industry, and routing in urban logistics among many examples.

The traveling salesman problem (TSP) and by extension the vehicle routing problem (VRP) are maybe one of the most prolific examples of how OR models can be used to improve efficiency and reduce cost. The TSP is formulated as a combinatorial problem where given a list of cities and distances between these cities, find the shortest route possible such that each city is visited exactly once and the route to the city of origin. Although a theoretical problem, it has applications in for example ride-sharing applications (shortest route to pick up passengers A, B, and C and drop them off at their destination), the manufacturing of microchips and even DNA-sequencing. The VRP is a generalization of the TSP and is formulated in a way where instead of one salesman there are multiple vehicles with each vehicle having a maximum capacity. The problem now becomes finding the optimal set of routes that visit all the cities and deliver (or pickup) the orders while respecting the vehicle capacity (i.e. vehicle cannot carry more items than a certain amount). Optimal is then often defined as a minimum number of vehicles, or the minimum total travel distance required to accomplish this. Of course, this definition is but only one and what is optimal may differ from use-case to use-case.

While, these problems are easy enough to understand, in theory at least, they are extremely hard to solve (for optimality). The number of solutions for the TSP is factorial, which for a problem set of 20 cities means that there are 2,432,902,008,176,640,000 (a number I don’t know how to pronounce) combinations possible! Add to that constraints such as time windows (can only visit a city in a certain time period) and capacity restrictions (can only cary so much) and it becomes extremely hard, for both humans and computers, to find a good (let alone optimal) solution.

The vehicle routing playground

Luckily, researchers have developed sophisticated approaches to find optimal or near-optimal solutions to these problems. And others, such as RedHat and Google, have implemented these algorithms in re-usable libraries that enables us to model these problems and find solutions without having to do all the hard work. Having said that, being able to do so still requires a lot of effort. Often one needs to preprocess the data, model the problem, tune the libraries and export the solution. Not just that. For anyone interested in how one library compares to another all this work needs to be repeated. Having done that a lot over the past year or two I want to make it easy for anyone interested enough to get their hands dirty, to have a go at modeling the vrp and using the popular libraries to solve it. Hence, today I am releasing the vehicle routing playground.

The vehicle routing playground is an environment that models the VRP on top of the libraries OR-tools and Optaplanner. I hope by doing so, it can help anyone to get started with these problems rather quickly and also, to set a potential framework where different libraries can be benchmarked against one another. The project supports running against a folder with many files where the output can be stored and analysed further. I have used it to compare OR-tools and Optaplanner, but the results of that I will likely share in a separate post.

Hope it becomes of use for anyone!