How to build a food delivery route optimization system with Python?

Building a food delivery route optimization system requires strong programming knowledge in Python and understanding of algorithms to optimize routing problems such as the Traveling Salesman Problem (TSP) or Vehicle Routing Problem (VRP). Furthermore, we'll also need access to some sort of map data; for this example, we're going to use the OpenStreetMap data and a Python library called osmnx to manipulate this data.

Follow the steps below:

Step 1: Install required Python libraries:

The first step is to install the required libraries. You can install all required libraries by using pip.

pip install numpy pandas matplotlib networkx osmnx

Step 2: Import libraries:

Import the required libraries as displayed below.

import osmnx as ox
import networkx as nx
import pandas as pd
from scipy.spatial.distance import pdist, squareform

Step 3: Fetch Location Data:

With OSMnx we can fetch the street network data for a city or place. We'll use Manhattan for this example.

location_point = (40.758896, -73.985130) # GPS coordinates for Manhattan, NYC.
G = ox.graph_from_point(location_point, dist=600, dist_type='bbox', network_type='drive')
fig, ax = ox.plot_graph(G)

Step 4: Fetch and Assign Delivery Points:

For the purpose of this example, let's assume we've 10 random locations we need to deliver to in Manhattan. You'll most likely replace this with your actual delivery addresses.

delivery_points = np.random.random((10,2))

# let's assign these points to the nearest node in the road network.
nodes = np.array(G.nodes())
closest_nodes = [int(nodes[cKDTree(nodes).query(point)[1]]) for point in delivery_points]

Step 5: Computing the Distance Matrix:

We need to calculate the distance between all pairs of Node Points.

def compute_distance_matrix(graph, nodes):
    distance_matrix = np.zeros((len(nodes), len(nodes)))
    for i in range(len(nodes)):
        for j in range(len(nodes)):
            distance_matrix[i,j] = nx.shortest_path_length(graph, nodes[i], nodes[j], weight='length')
    return distance_matrix

distance_matrix = compute_distance_matrix(G, closest_nodes)

Step 6: Route Optimization:

Now that we have our distance matrix, we can apply a solution algorithm for the TSP such as a Genetic Algorithm, Simulated Annealing, Ant Colony, etc.

For this example, we'll be using the Google OR-Tools, a software library for combinatorial optimization.

• You will need to install the OR-Tools using pip.

pip install ortools

• Then, import it into your Python project.

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

# Set OR-Tools Parameters
def create_data_model():
    """Define data for the route problem."""
    data = {}
    data['distance_matrix'] = distance_matrix
    return data

*CreateTimeMatrix() and CreateRouteModel():

def getTimeMatrix(self):
        time_matrix = []
        for i in range(0, len(self.address_list)):
            temp_matrix = []
            time.sleep(1)
            for j in range(0, len(self.address_list)):
                temp_matrix.append(self.getDistanceDuration(i, j)['duration'])
            time_matrix.append(temp_matrix)
        self.time_matrix = time_matrix

def CreateRouteModel(self):
        data = {}
        data["distance_matrix"] = self.time_matrix
        return data

*Main function:

def main():
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           1, 0)
    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)
    
    # Create and register a transit callback
    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        return data['distance_matrix'][manager.IndexToNode(from_index)][manager.IndexToNode(to_index)]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
  
    # Add Distance constraint.
    dimension_name = 'Distance'
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        3000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)
  
    # Set the parameters of the search
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
  
    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)
  
    # Print solution on console and plot the solution
    if solution:
        print_solution(manager, routing, solution)
        plot_solution(manager, routing, solution, closest_nodes, G)

Finally, calling the main function at runtime:

if __name__ == "__main__":
    main()

The above steps will construct a basic food delivery route optimization system. However, for a system to be used in a real-world application, much more needs to be considered such as traffic, multiple vehicles, delivery time windows, etc. Also, the coordinates should of course not be random but correspond with the actual delivery addresses. But this should give you a rough idea on how to tackle this problem using Python.

The optimization problem you will be looking at is known as the Vehicle Routing Problem (VRP), it is an extension of the TSP and there are various Python libraries for solving this such as OptaPlanner etc. Yet Google OR-Tools can handle most of them.

Note: This is a toy example, do not use it for production code, osmnx is not designed to handle larger road networks and computation might take a while.