Solving the Vehicle Routing Problem with OpenStreetMap and OR-Tools

The Vehicle Routing Problem (VRP) is a classic optimization challenge that involves finding the most efficient routes for a fleet of vehicles to visit a given set of locations while minimizing the total distance traveled. In this article, we will explore a practical solution to this problem using OpenStreetMap data and the OR-Tools library. The approach presented here utilizes a two-step optimization strategy to achieve optimal results.

Photo by José Martín Ramírez Carrasco on Unsplash

Introduction to the Vehicle Routing Problem

The Vehicle Routing Problem is of significant importance in the fields of logistics, transportation, and supply chain management. Its objective is to determine the most cost-effective way to serve a set of customers located at various locations with a fleet of vehicles. The problem becomes increasingly complex as the number of cities and points of interest increases.

Approach of Two-Step Optimization

To address the complexities of the Vehicle Routing Problem efficiently, the solution presented here employs a two-step optimization approach. The goal is to first optimize the routes between cities and then optimize the routes within each city to visit the points of sales efficiently.

The solutions have been tested with a small dataset of 414 points of sales from 8 different cities.

Optimization Between Cities

In the first step, the script calculates the most optimal route for visiting all the cities based on the input data. To achieve this, it utilizes the OpenStreetMap Routing API, which provides distance matrices between the centroids of each city. The distance matrices consider driving distance and road network information, essential factors for accurate route planning.

Once the distance matrix is obtained, the OR-Tools library comes into play. OR-Tools is an open-source optimization library by Google that provides various tools for solving optimization problems, including the Traveling Salesman Problem. It takes the distance matrix as input and finds the optimal route that minimizes the total distance traveled while ensuring each city is visited only once.

Optimization Within Cities

The second step involves optimizing the routes within each city to visit the top 10 points of sales efficiently. Similar to the first step, the script uses the OpenStreetMap Routing API to retrieve distance matrices between the selected points of sales in each city. The points of sales are chosen based on their proximity to the city centroid, ensuring an effective distribution of deliveries.

Again, the OR-Tools library is employed to find the most optimal route for visiting the selected points of sales in each city. The objective is to minimize the total distance traveled while ensuring that each point of sale is visited only once in each city. This two-step approach aims to achieve an efficient and optimal solution to the Vehicle Routing Problem, considering both inter-city travel and intra-city point of sales visits.

Visualization of Optimal Routes

To better understand and analyze the results, the solution offers interactive Folium maps for visualization. These maps display the optimal routes for visiting all cities and the selected points of sales within each city. The sequence of cities to be visited and the efficient paths within each city are clearly illustrated, providing a comprehensive view of the optimized routes.

Optimal route between cities

Optimal route within city

Python implementation

The example code implementing the solution and all the details can be found at github.

Requirements

To run the solution, you will need the following:

1. Conda (Miniconda or Anaconda): Conda is a package and environment manager, and it is used to set up the required environment for running the code.

2. Git (optional): Git is used for version control, and you may use it to clone the repository containing the solution.

Installation and Usage

Follow these steps to set up the environment and run the VRP solver notebook:

1. Clone the repository (if you haven’t already):

git clone https://github.com/albertferre/travelling-salesman-routing.git
cd travelling-salesman-routing

2. Create and activate the Conda environment using the `env.yaml` file:

conda env create -f env.yaml
conda activate travelling-salesman-routing

3. Launch the Jupyter notebook provided in the repository. The notebook demonstrates a step-by-step implementation of the VRP solver using OpenStreetMap data and OR-Tools.

Future Improvements and Extensions

The current implementation provides a solid foundation for solving the Traveling Salesman Problem and visualizing optimal routes for visiting cities and points of sales. However, there are several areas where the project can be expanded and improved to meet more complex real-world scenarios. Some potential future improvements include:

• Time Windows for Visiting: Incorporate time constraints for visiting points of sales, where each location has specific opening and closing times. This will ensure that the route adheres to the operational hours of the businesses.
• Truck Loading and Capacity: Extend the optimization to account for truck loading and capacity constraints. This enhancement will help in optimizing deliveries based on the available truck capacity and load distribution.
• Total Time Restrictions: Introduce total time restrictions for each route to limit the overall duration of deliveries for efficiency and time management.
• Multiple Vehicles and Depots: Expand the solution to handle multiple vehicles and depots, useful for scenarios with several delivery trucks starting from different locations.
• Real-Time Traffic Data: Integrate real-time traffic data to account for dynamic road conditions and further optimize route planning.
• Alternative Algorithms: Explore alternative algorithms and optimization techniques for solving the Traveling Salesman Problem, such as genetic algorithms, simulated annealing, or ant colony optimization.
• Interactive User Interface: Develop an interactive user interface that allows users to input their own datasets, visualize the optimized routes, and export the results.

By incorporating these improvements and extensions, the solution can be tailored to specific logistics and delivery scenarios, providing more accurate and practical route planning for businesses and organizations.

Resources and References

This project utilizes several libraries and APIs to solve the Traveling Salesman Problem and visualize the optimal routes. Below are the links to the resources used:

• Traveling Salesman Problem — Wikipedia: This Wikipedia page provides detailed information about the Traveling Salesman Problem, its variants, and various algorithms to solve it.
• Open Source Routing Machine (OSRM) API: OSRM is used to calculate driving distances and routes between cities and points of sales.
• Google OR-Tools: OR-Tools is an open-source library by Google for solving various optimization problems, including the Traveling Salesman Problem.
• Folium Package: Folium is a Python library used for visualizing geospatial data on interactive maps. It is used to create interactive maps to display the optimal routes.