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

We have covered querying the server for data about events, offers and requests in the first tutorial.

Now we start building the data to be fed into OR-tools.

Offer_df      = False
Request_df  = False
while type(Offer_df)     == bool or
          type(Request_df) == bool:
                df = read_events()
                Offer_df = read_offers(df['event_id'])
                if type(Offer_df) != bool:
                       Request_df = read_requests(Offer_df['event_id'])

The reason why we check for the type of Offer_df or Request_df  instead of checking if they are equal to False is that if Offer_df is a numpy array, then python will return an error as comparing a numpy array to a value is invalid and it will ask us to be more specific.

With this loop, we check for events, if we get any events then we check for offers going to those events, if there are any offers, then we check for requests going to the same events.

Final_ids = np.unique(Offer_df['event_id']).tolist()

offers_list     = []

requests_list = []

events_list    = []

for ID in Final_ids:

        requests  =  Request_df[Request_df['event_id'] == ID]

        offers      =  Offer_df[Offer_df['event_id'] == ID]

        if len(requests) == 0 or len(offers) = 0:   # if no requests or offers then no solution for that event yet

             continue

        event       =  df[df['event_id'] == ID]

        Time       =  event['event_time'][0]

        lat           =  event['event_lat'][0]

        lon          =  event['event_lon'][0]

        offers_list.append(offers.tolist())
        request_list.append(requests.tolist())
        events_list.append([ID,Time,lat,lon])

Next we construct a python dictionary that will be fed into and used by OR-tools.

Tolerance = 30 #mins

Routes     = [] 

for i in range(len(events_list)):

         Iter            = 0

         starts         = []

         locations   = [] 

         Times        = []    

         capacity    = []

         IDs            = []

         data           = {}

         location  = (events_list[i][2], events_list[i][3])

         Time      = events_list[i]["event_time"][1].strftime("%H:%M:%S")

         Time      = int(Time[:2]) * 60+ int(Time[3:5])

         for offer in offers_list[i]:

              locations.append((offer['offer_lat'],offer['offer_lon']))

              starts.append(Iter)

              Times.append((0,Time))

               capacity.append(offer['offer_capacity'])

               IDs.append(offer['offer_acc_id'])

               Iter += 1

         for request in request_list[i]:

              locations.append((request['request_lat'],request['request_lon']))

              Times.append((0, Time))

              IDs.append(request['request_acc_id'])

         locations.append(location)

         Times.append((Time-tolerance, Time+tolerance))

         data['locations']          = locations

         data['num_vehicles']   = len(starts)

         data['time_windows'] = Times

         data['starts']                = starts

         data['capacity']           = capacity

         data['IDs']                   = IDs

         data['ev_id']                = events_list[0]

         data['distance_matrix'], data['durations'] = get_dist_dur_mat(locations)

         route = Route(data)

         if route != []:

                routes.extend(route)

For every event
We change the time of arrival into minutes Time = int(Time[:2]) * 60 + int(Time[3:5]) and we ignore the seconds as we don't need that precision anyways.
Then we start adding the locations of the offers one by one and saving the index of their location to later tell OR-tools that those are the start points for routes, and we add other relevant data.
Next we add the requests.
The Times array holds the time windows, for our case an offer can start anywhere from the beginning of the day and pickup the requests anytime of the day as well.
You might think that setting a constraint so loose will cause all sorts of problems but don't forget that he has to arrive at the location within a certain time window,
We can just later control the waiting time, waiting time is the time a driver can wait at a location until the time window of the next location is available so he can move.
For example:
Imagine our route is 
O    ======>    R    =====>  E
O 's time window  is (0,100)
R's time window  is (0,100)
E's time window  is (90,110)
If we start at time 0 and the route duration from O to R is 10 then we will arrive at R at 10, if the route duration from R to E is 20 then we have to wait at R for 60 minutes until the time is 70 then we move such that we arrive at E at 90.

We can also check for the route duration between each offer and the event and add a certain tolerance, then make that its starting time for example, a carpooling app, we can't add more than 15 mins to the original driving time, else the offer will surely refuse, so we put that as our tolerance.

Personally i do both most of the time.

Then we add the location of the event in the end and we let its time window be such that we can arrive before or after the event time by a certain tolerance, 
you can change that however you want of course.

we route for each event independently and we append the routes returned to a bigger array such that we plot all the routes in the end.

OR-tools solves tsp so we feed it distances and durations matrices to calculate the costs between routes using get_dist_dur _mat.

You can use google maps to construct those matrices or you can use OSRM.

OSRM is as fast as the resources that you give it, its single threaded though.

There are different methods to optimize the whole process though.

You can multithread the matrices construction although its a bit complex and didn't prove useful to me unless you think taking a minute or two for 2000 locations is a lot, or you are short on memory.

You can also multithread the routes optimization process altogether,
such that you optimize for each route on a separate process, that way, you can make better use of your cpu, but always remember RAM.

We have constructed everything now to feed into OR-tools which we will do in the next tutorial.

If you haven't installed OR-tools, check this google link first.