Optimizing Delivery Routes in Bangalore: A Python Implementation Using OR-Tools and Folium

In today’s fast-paced world of logistics and delivery services, route optimization has become crucial for businesses looking to maximize efficiency and minimize costs. I recently developed a solution using Python to tackle this challenge, focusing on optimizing delivery routes across major locations in Bangalore.

The Challenge

Imagine you’re managing deliveries across five major locations in Bangalore:

• Hebbal
• Yeshwantpur
• Indiranagar
• Sarjapura
• KR Puram

The challenge is to find the most efficient route that visits all these locations once and returns to the starting point, essentially solving the Traveling Salesman Problem (TSP).

Technical Implementation

Key Technologies Used

1. Google OR-Tools: For solving the TSP optimization problem
2. Folium: For creating interactive maps
3. GeoPy: For calculating geodesic distances between locations
4. Python: As the primary programming language

Core Components

1. Distance Calculation

The solution uses geodesic distances (the shortest distance between two points on a sphere) to create a realistic distance matrix between locations. This is particularly important in urban environments like Bangalore where straight-line distances can be misleading.

def compute_distance_matrix(locations):
    matrix = []
    for from_coord in locations:
        row = []
        for to_coord in locations:
            distance_km = geodesic(from_coord, to_coord).kilometers
            row.append(int(distance_km * 1000))
        matrix.append(row)
    return matrix

2. Route Optimization

The code leverages Google OR-Tools’ powerful constraint solver to find the optimal route. It uses the PATH_CHEAPEST_ARC strategy, which is particularly effective for TSP problems.

3. Visualization

The solution provides two key visualizations:

• An interactive map showing the optimized route with numbered markers
• A detailed table showing distances between consecutive stops and cumulative distance

The Output

The program generates an HTML file that displays:

An interactive map with:

• Numbered markers for each stop
• A blue line showing the complete route
• Popup labels for each location

A detailed route table showing:

• Start and end points for each segment
• Individual segment distances
• Cumulative distance traveled

Real-world Applications

This solution can be particularly valuable for:

• Last-mile delivery services
• Logistics companies
• Food delivery services
• Field service operations
• Sales route planning

Future Enhancements

The current implementation could be extended to include:

1. Real-time traffic data integration
2. Time windows for deliveries
3. Vehicle capacity constraints
4. Multiple vehicle routing
5. API integration for automatic address geocoding

Technical Details

The complete implementation is available in Python and uses the following core libraries:

• folium for map visualization
• ortools for route optimization
• geopy for distance calculations

The solution accounts for Bangalore’s unique geography and provides accurate distance calculations between locations using actual coordinates.

Conclusion

Route optimization is a critical component in modern logistics operations. This Python implementation demonstrates how powerful open-source tools can be combined to create practical solutions for real-world problems. While this example uses locations in Bangalore, the solution can be easily adapted for any other city or set of coordinates.

The Github repo for this project can be found here: https://github.com/shelwyn/route-optimization