Create a route optimization algorithm with zero costs using google's OR-tools and OSRM Part 3

This is a continuation to the route optimization series.

First we define the function that will be used by the optimizer to get the distances between points.

  def distance_callback(from_index, to_index):         

       from_node = manager.IndexToNode(from_index)          

       to_node      = manager.IndexToNode(to_index)                  

       if from_node == to_node:               

                return 0                  

       return data['distance_matrix'][from_node][to_node]

IndexToNode is used to correlate between a location as a node index inside the being tested/optimized route by the solver and the index of the location in our own array.
To see the full list of nodes on the route try GetIndexToNodeMap 

You can argue that checking if from_node == to_node is useless since it is equal to 0 in the distances_matrix anyways but i thought that checking and returning 0 will be less expensive than accessing the array to get the same value, 

so the difference may be unnoticeable if its done a few times, but when there are thousands of locations, it can make a difference.

Next we check for the durations matrix in the same way.

  def time_callback(from_index, to_index):         

       from_node = manager.IndexToNode(from_index)          

       to_node      = manager.IndexToNode(to_index)                  

       if from_node == to_node:               

                return 0                  

       return data['time_matrix'][from_node][to_node]

Next we create a function that returns the size of the requests at each location,

some clients of mine wanted a feature where two requests could be on the same location and want to be together so their size will be 2 not 1.

If you have two types of items to be picked up then you can create two different callbacks for that, we can call one demand_callback and the other demand_c_callback for instance.

def demand_callback(from_index):
     from_node = manager.IndexToNode(from_index)
     return data['size'][from_node]

That function will read from a different sizes array and it will fill a different capacity array which will be explained later.

def demand_c_callback(from_index):
     from_node = manager.IndexToNode(from_index)
     return data['size_c'][from_node]

Below is the function to initialize the OR-tools algorithm and print the output returned by it. 

Fast = True
def Route(data):

  Max_drive                 = 8 * 60           # mins
  Max_travel_distance = 100 * 1000   # metres
  Max_waiting_time    = 15                 # mins  

  manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),                                                                              data['num_vehicles'],

                                                                          data['starts'], data['ends'])

  routing = pywrapcp.RoutingModel(manager)  

  distance_callback_index =  routing.RegisterTransitCallback(distance_callback) 

  time_callback_index = routing.RegisterTransitCallback(time_callback)

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)

    demand_c_callback_index = routing.RegisterUnaryTransitCallback(demand_c_callback)

routing.AddDimensionWithVehicleCapacity(demand_callback_index, 0, data['capacity'], True, 'Capacity')
 

    routing.AddDimensionWithVehicleCapacity(demand_c_callback_index, 0, data['capacity_c'], True, 'Capacity_c')

 

    penalty = 214748364

    for node in range(len(data['distance_matrix'])):

        if manager.NodeToIndex(node) == -1:

              continue

        routing.AddDisjunction([manager.NodeToIndex(node)], penalty)

    

    routing.SetArcCostEvaluatorOfAllVehicles(time_callback_index)
    routing.SetArcCostEvaluatorOfAllVehicles(distance_callback_index)

    dimension_name = 'Distance'

    routing.AddDimension(distance_callback_index,

                         0,

                         max_travel_distance,

                         True,

                         dimension_name)

    distance_dimension = routing.GetDimensionOrDie(dimension_name)

    Time = 'Time'

    routing.AddDimension(time_callback_index,

                         Max_waiting_time,

                         Max_drive,

                         True,

                         Time)

    time_dimension = routing.GetDimensionOrDie(Time)

    # Instantiate route start and end times to produce feasible times.

    for vehicle_id in range(data['num_vehicles']):

            routing.AddVariableMinimizedByFinalizer(

                time_dimension.CumulVar(routing.End(vehicle_id)))

            routing.AddVariableMinimizedByFinalizer(

                time_dimension.CumulVar(routing.Start(vehicle_id)))

         

    # Setting first solution heuristic (cheapest addition).

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    if Fast is True:

         search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)

         #print("Fast")

    else:

         search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.BEST_INSERTION)#PATH_MOST_CONSTRAINED_ARC)

         #print("Best")

    #print("Starting")

    # Solve the problem.

    #search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

    search_parameters.time_limit.seconds = 4

    

    assignment = routing.SolveWithParameters(search_parameters)

 

    search_parameters.log_search = True

 

    # Print the solution.

    if assignment:

      #print("done")

      #print('time taken by the algorithm',time()-start_time)

      return prints_solution(data, manager, routing, assignment,pre_route, app_log)

    else:

          return pre_route

First we initialize the mapping function for the nodes indices inside the solver vs the indices of the locations in our own array pywrapcp.RoutingIndexManager and we initialize it with the number of locations len(data['distance_matrix']) , the number of vehicles data['num_vehicles']  and  optionally the start and end locations data['starts'], data['ends']. 
When the routing solver is working, it tries different nodes on the route to get to the best solution,and it keeps a map between the nodes and their location indices in our array, the routingindexmanager saves us the effort of reading that map ,which constantly changes, to know the corresponding location index to each node.
Next we initialize our routing solver with that index manager pywrapcp.RoutingModel(manager). 
Then we register our  function as function of a form that the routing solver can understand  routing.RegisterTransitCallback(distance_callback)
Then we register our other function for determining the size of a location but unary here means that the function takes only one node as input which is the from_node  RegisterUnaryTransitCallback.
Next we add a function that evaluates an accumulating cost along a route against a constraint  AddDimensionWithVehicleCapacity , we initialize it with the function that returns the cost of a respective location demand_callback_index  ,a slack variable which is basically a constant cost that is added with each node on the route, we don't need it here, but you could need it for something like a waste of space or weight because of a box containing the item for example 0 , and an array that has the constraint for each vehicle's cost  data['capacity'] ,We choose also whether the vehicle starts with no weight(cost) or has some weight on it initially True ,and we give a name to the whole function to be able to trace it later 'Capacity'.
We could add a different capacity for something different, maybe our clients prefer to pickup the same gender or maybe a vehicle can pickup a type of items and another vehicle can carry a different type of items.
So if a vehicle can carry for example 5 items of both then it gets a 5 in both capacity and capacity_c  but if a vehicle can carry only one type then it gets a 0 in the capacity of the other type,
And we add AddDimensionWithVehicleCapacity with demand_c_callback_index
and data['capacity_c'] and we give it a different name 'Capacity_c'.


Not adding the below part means the solver must route for all the nodes otherwise if a node can't exist on any of the routes then it will return no solution.
The part below adds a penalty to the solver in case it ignores a node to discourage it from excluding any nodes on the route, adding a negative penalty to a node tells the solver that the node must exist while a positive penalty just adds a penalty in case the solver chooses to exclude that node.
We don't add a penalty to a start or end point since we opt for the least number of vehicles.

penalty = 214748364

    for node in range(len(data['distance_matrix'])):
         if manager.NodeToIndex(node) == -1    or
            manager.NodeToIndex in data['starts'] or
            manager.NodeToIndex in data['ends'] :
                    continue                   
         routing.AddDisjunction([manager.NodeToIndex(node)], penalty)     

We add a function that is called to set a cost on each arc (path between two nodes)   SetArcCostEvaluatorOfAllVehicles

We add dimensions that take care of accumulating the different costs on the route like waiting time, loading/unloading time, route distance, etc.
First we add the dimension(function) AddDimension that will be used to calculate the costs on arcs between nodes, 
Then there is slack_max which is 0 for our distances in my case but for durations it represents the max waiting time to be accumulated on the route.
Then there is the max accumulation which is the maximum cost that can be accumulated over a route, 
Then the name of the dimension to be able to track it later.
Then we use GetDimensionOrDie on the name of the dimension to return us a function that we can use later to track the behaviour of the solver.

dimension_name = 'Distance' routing.AddDimension(distance_callback_index,
                                      0,
                                      max_travel_distance,
                                      True,
                                      dimension_name)
 distance_dimension = routing.GetDimensionOrDie(dimension_name)

Next we tell the solver to minimize the cost AddVariableMinimizedByFinalizer
accumulated by the end of each route time_dimension.CumulVar(routing.End(vehicle_id)), if your vehicles start with a non zero cost(slack) then we add a minimizer for the start as well routing.Start(vehicle_id). 
Sometimes you want to add a pickup and delivery option where basically two locations must be passed by the same vehicle and the pickup location must be passed first, we can use AddPickupAndDelivery function offered by OR-tools but we have to tell the the solver that the pickup location must be before the dropoff location as well, by telling it that the cumulvar of the pickup location must be less than the cumulvar of the dropoff location which is logical.
Next we use a solution strategy for the solver, some of the strategies simply don't work with some features, you should keep an eye for that and not blame yourself always for that part, try different strategies first.
Next we print and plot the solution using leaflet in the next part.