<jupyter_start><jupyter_text>**Problem definition:**\The Drop off ridesharing problem is researched. The problem is formulated into a mathematical model with decision variables, an objective functions and constrains. The simulated annealing (SA) algorithm is implemented to solve this problem. An experiment with the real world data sets is done to test the performance of this algorithm. It is required to generate an optimal schedule for each dropoff to serve the passengers of Toronto in such a way that optimizes at least two of the following criteria, preferably all:• Minimizing the total number of SAVs required.\• Minimizing the total travel distance/time of SAVs’ trips.\• Minimizing the total travel time of passengers’ trips.\• Maximizing the number of matched (served) requests.\• Minimizing the cost for the SAVs’ trips/loss during uncharged driving\• Maximizing the SAV's earning/total profit.\• Minimizing the cost for the passengers’ trips.\• Minimizing passenger’s waiting time.\• Balancing the routes of SAV load.\<jupyter_code>import pandas as pd
import math
import numpy as np
import random
import time
import matplotlib.pyplot as plt
import osmnx as ox
from utilities import *
# You can use different excel data
#file_path = './data/Maven_stations_saved.csv'
file_path = './data/Dropoff_locations.csv'
df = pd.read_csv(file_path)
numberOfStops = len(df)
df
# store the values into a numpy array
addresses  = df.iloc[:, 2].values
POIS = []
for address in addresses:
    POIS.append(poi(address,"canada"))
POIS
drawPOIS(POIS, zoom=10)
G = nx.DiGraph()
G.add_nodes_from(POIS)
# this will take 1-2 minutes because you need to find
# two routes between each pair of POIs
durations = []
for source in G.nodes():
    duration = []
    for destination in G.nodes():
        if source == destination: 
            duration.append(0)
            continue
        G.add_edge(source, destination, route = source.route_to(destination))
        route = source.route_to(destination)
        duration.append(route['duration'])
    durations.append(duration)
durations = np.array(durations)
durations
# Define a function to compute the cost of the solution
# It gets you the sum for the solution
def cost(m, sol):
    M = np.zeros(numberOfStops-1)
    for i in range(numberOfStops-1):
        M[i] = m[sol[i]-1,sol[i+1]-1]
    fitness = np.sum(M)
    return fitness
# parameters
iteration = 200000   # number of iterations
temp = 5   # initial temperature
# create an array to store all individuals
sol_hist = np.zeros([iteration+1,numberOfStops])

# create an array to store all fitness values corresponding to the individual
fitness_hist = np.zeros(iteration+1)

# initialize the fitness array
for i in range(iteration+1):
    fitness_hist[i] = 99999
# generate the initial solution
initial_sol = np.arange(1,numberOfStops+1)
random.shuffle(initial_sol)
initial_sol = initial_sol.astype(int)
# compute the fitness of the initial solution
sol_hist[0] = initial_sol
fitness_hist[0] = cost(durations, initial_sol)
running_time = np.zeros(iteration)
best_outputs = []
# implementation of simulated annealing
# implementation of simulated annealing
for i in range(1,iteration+1):

    # record the starting time
    start_time = time.time()

    # generate new solution
    a = random.randint(0,numberOfStops-1)
    b = random.randint(0,numberOfStops-1)
    sol_hist[i] = sol_hist[i-1]
    sol_hist[i,a] = sol_hist[i-1,b]
    sol_hist[i,b] = sol_hist[i-1,a]
    sol = sol_hist[i]
    sol = sol.astype(int)

    # compute the fitness of the new solution
    fitness_hist[i] = cost(durations, sol)

    if fitness_hist[i] > fitness_hist[i-1]:
        prob = math.exp(-(abs(fitness_hist[i]-fitness_hist[i-1]))/temp)
        r = np.random.random()
        if r > prob:
            sol_hist[i] = sol_hist[i-1]

    # update the annealing temperature
    temp = temp*0.999

    # record the best output for every iteration
    best_outputs.append(np.min(fitness_hist))

    # compute and store the running time
    running_time[i-1] = time.time() - start_time

# return the index of the solution corresponding to the best fitness
best_index = np.where(fitness_hist == np.min(fitness_hist))

running_time = running_time.cumsum()

# to get the index of iteration when the fitness reaches its minimum value (convergence point of the algorithm)
convergence_index = np.where(best_outputs == np.min(best_outputs))
convergence_time = running_time[convergence_index]

print("The best solution is:", sol_hist[best_index].astype(int))
print('The best fitness value is:', fitness_hist[best_index])
print("The algorithm converges in", np.min(convergence_index), "iterations.")
print("The algorithm converges in", np.min(convergence_time), "seconds.")

fig, ax = plt.subplots(2, figsize = (8,15))
ax[0].plot(best_outputs, 'green')
ax[0].set_xlabel("Iteration", fontsize = 10)
ax[0].set_ylabel("Cost", fontsize = 10)
ax[0].set_title("SA (Fitness vs # of iterations)   1 station", fontsize = 12)

ax[1].plot(running_time, best_outputs, 'red')
ax[1].set_xlabel("Running time/s", fontsize = 10)
ax[1].set_ylabel("Fitness", fontsize = 10)
ax[1].set_title("SA (Fitness vs Running time)   1 station", fontsize = 12)
plt.show()
#Visualization
optimalRoute = sol_hist[best_index].astype(int)-1
optimalRoute = optimalRoute[0]
optimalRoute
currentRoute = G[POIS[optimalRoute[0]]][POIS[optimalRoute[1]]]['route']['coords']
for i in range(1,len(optimalRoute)-1):
    currentRoute += G[POIS[optimalRoute[i]]][POIS[optimalRoute[i+1]]]['route']['coords']
drawRoute(currentRoute)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10800143523501973, 'fraction_numerical': 0.014352350197344816, 'mean_word_length': 4.619959677419355, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '542089', 'license': 'Apache-2.0', 'n_tokens_mistral': 1822, 'n_tokens_neox': 1739, 'n_words': 549, 'path': 'ridesharing_SA.ipynb', 'repo_name': 'MotasemASakr/Trajectory-based-Search-Algorithms', 'size': '5574'}