Car-Sharing Service#
Let’s imagine a car-sharing service using Shared Autonomous Vehicles (SAVs) operating in Toronto.
Under this SAV model, The car-sharing platform would dispatch its autonomous vehicles from depots to pickup locations, driving the passenger to a dropoff location, and then proceeding either to the next passenger, or returning to the depot.
import pandas as pd
from smart_mobility_utilities.poi import poi
from smart_mobility_utilities.poi import drawRouteOrder
from smart_mobility_utilities.problem import ordOne_crossover, swap_mutation
from copy import deepcopy
import random
from heapq import nlargest
import matplotlib.pyplot as plt
---------------------------------------------------------------------------
ModuleNotFoundError Traceback (most recent call last)
Input In [1], in <cell line: 2>()
1 import pandas as pd
----> 2 from smart_mobility_utilities.poi import poi
3 from smart_mobility_utilities.poi import drawRouteOrder
4 from smart_mobility_utilities.problem import ordOne_crossover, swap_mutation
ModuleNotFoundError: No module named 'smart_mobility_utilities'
Introduction#
Let’s define the following parameters to our example problem:
Let’s assume there are 10 vehicle depots scattered around the city of Toronto.
There are also 10 passengers at different locations all waiting for an SAV.
The goal is to assign vehicles to passengers in such a way to optmize for some constraints.
Additionally, let’s consider the following:
For now, each SAV should only hold a maximum of one passenger at a time.
Each depot can only accomodate one SAV at a time.
Gas costs 0.3 per unit of distance.
SAVs earn 0.8 per unit of distance.
Fitness Function#
We can define the fitness of a solution in terms of its real world cost. Since the only cost provided above is the cost of gas, which is directly related to distance travelled, we can consider total fleet distance as a variable to minimize. It may also be interesting to minimize overall mileage on the fleet for the purposes of maintenance, but this too is essentially a minimization of total fleet distance.
Let’s assume that the number of vehicles is not a cost driver. That is to say, driving 4 km on one vehicle is more costly than driving 1 km on two vehicles, and equivalent to driving 2 km on two vehicles. This favours using more vehicles whenever convenient, which is the end goal of this problem.
To that end, the cost of driving is as follows:
\( C = g \times \sum_{n=1}^{N} \sum_{j=1}^{S_n} \sum_{k=1}^{len(S_n)-1} distance(S_n^k,S_n^{k+1})\)
Where
\(N=\) total number of vehicles being used
\(S_n=\) list of stops for vehicle \(n\), where \(S_n^k\) is the \(k\) th stop for vehicle \(n\)
\(g=\) the cost of fuel per distance
However, we also earn money from driving, as long as we have a passenger in the vehicle. This means:
\( R = r \times \sum_{n=1}^{N} \sum_{j=1}^{S_n} \sum_{k=1}^{len(S_n)-1} distance(S_n^k,S_n^{k+1})\)
Where
\(N=\) total number of vehicles being used
\(S_n=\) list of stops for vehicle \(n\), where \(S_n^k\) is the \(k\) th stop for vehicle \(n\) AND \(S_n^k\) is a pickup, and \(S_n^{k+1}\) is a dropoff. This means we don’t make money when the car is going from dropoff to the next pickup, and we don’t make money to and from the depots.
\(g=\) the cost of fuel per distance
Profit is then calculated as being \(P=R-C\)
Data#
# Import location data
depots = pd.read_csv("carshare_depot.csv")
depot_nodes = [poi(row['address'],'canada',row['lat'],row['lng']) for index, row in depots.iterrows()]
pickups = pd.read_csv("carshare_origin.csv")
pickup_nodes = [poi(row['address'],'canada',row['lat'],row['lng']) for index, row in pickups.iterrows()]
dropoffs = pd.read_csv("carshare_dest.csv")
dropoff_nodes = [poi(row['address'],'canada',row['lat'],row['lng']) for index, row in dropoffs.iterrows()]
# Import a pre-calculated trip distance matrix
# These distances are based off of an osrm routing
tm = pd.read_csv("trip_matrix.csv").values
trip_matrix = {}
all_points = depot_nodes + pickup_nodes + dropoff_nodes
for point in all_points:
i = all_points.index(point)
trip_matrix[point] = {}
for point2 in all_points:
j = all_points.index(point2)
trip_matrix[point][point2] = tm[i][j+1]
Solution Class#
class CarSharingSolver:
def __init__(
self,
depot_nodes,
pickup_nodes,
dropoff_nodes,
trip_matrix,
pop_size,
iterations,
num_parents,
mutation_prob,
crossover_prob,
pre_avoid = [],
post_avoid = []
):
self.pickups = pickup_nodes
self.depots = depot_nodes
self.dropoffs = dropoff_nodes
self.trip_matrix = trip_matrix
self.pop_size = pop_size
self.iterations = iterations
self.num_parents = num_parents
self.mutation_prob = mutation_prob
self.crossover_prob = crossover_prob
self.population = None
self.costs = None
self.states = []
self.solution = None
self.solution_cost = None
self.pre_avoid = pre_avoid
self.post_avoid = post_avoid
def crossover(parent1, parent2):
return ordOne_crossover(parent1, parent2)
def mutation(permutation):
return swap_mutation(permutation)
# Find the closest depots for start and end, avoiding ones that are already filled
def find_depots(self, route):
start = route[0]
end = route[-1]
depots = deepcopy(self.depots)
tmp_depots = deepcopy(depots)
[depots.pop(depots.index(x)) for x in self.pre_avoid if x in depots]
distances_to_start = [self.trip_matrix[x][start] for x in depots]
[depots.pop(depots.index(x)) for x in self.post_avoid if x in depots]
distances_from_end = [self.trip_matrix[end][x] for x in depots]
start_depot = tmp_depots[distances_to_start.index(min(distances_to_start))]
end_depot = tmp_depots[distances_from_end.index(min(distances_from_end))]
route = [start_depot] + route + [end_depot]
return route
def random_solution(self):
route = []
can_visit = deepcopy(self.pickups)
for i in range(len(self.pickups)):
# select a random pickup location
random_pickup = random.choice(can_visit)
route.append(random_pickup)
can_visit.pop(can_visit.index(random_pickup))
# now we can choose the depot closest to starting and ending locations
route = self.find_depots(route)
return route
def expand_route(self, route):
actual_route = []
for stop in route:
if stop not in self.pickups:
# It is a depot
actual_route.append(stop)
continue
actual_route.append(stop)
drop = self.dropoffs[self.pickups.index(stop)]
actual_route.append(drop)
return actual_route
def fitness(self, solutions):
result = []
for vehicle_route in solutions:
# We need to expand the routes into pickup-dropoffs to calculate actual cost
expanded_route = self.expand_route(vehicle_route)
total = 0
for stop, next_stop in zip(expanded_route[:-1], expanded_route[1:]):
if stop in self.pickups and next_stop in self.dropoffs:
cost_factor = 0.5
else:
cost_factor = -0.3
total += cost_factor * self.trip_matrix[stop][next_stop]
result.append(round(total,2))
return result
def initial_population(self):
self.population = [
self.random_solution()
for _ in range(self.pop_size)
]
self.costs = self.fitness(self.population)
# Single vehicle, genetic algorithm
def run(self):
# Check that initial population exists:
if self.population:
# Show some information
print("Initial Population costs:")
print(self.costs)
else:
raise Exception("Population not initialized.")
for _ in range(self.iterations):
self.costs = self.fitness(self.population)
self.states.append(max(self.costs))
# Select the parents, we want to maximize the profit
parents = nlargest(self.num_parents,self.population, key=lambda x: self.costs[self.population.index(x)])
# Need to remove depots from the routes
parents = [x[1:-1] for x in parents]
offspring = []
new_population = []
for p1, p2 in zip(parents[:len(parents)//2],parents[len(parents)//2:]):
# Crossover probability
if random.random() < self.crossover_prob:
offspring.append(CarSharingSolver.crossover(p1,p2))
offspring.append(CarSharingSolver.crossover(p2,p1))
else:
offspring.append(p1)
offspring.append(p2)
for child in offspring:
if random.random() < self.mutation_prob:
new_population.append(CarSharingSolver.mutation(child))
else:
new_population.append(child)
new_population.extend(parents)
self.population = [self.find_depots(route) for route in new_population]
# Show best solution
self.costs = self.fitness(self.population)
self.states.append(max(self.costs))
self.solution = max(self.population,key= lambda x: self.costs[self.population.index(x)])
self.solution_cost = self.costs[self.population.index(self.solution)]
self.solution = self.expand_route(self.solution)
print("Best Solution:", self.solution)
print("Best Solution Profits:", self.solution_cost)
def visualize_solution(self, m=None, route_color="red", prefix=""):
# define marker colors
colors = []
for stop in self.solution:
if stop in self.depots:
colors.append('blue')
if stop in self.pickups:
colors.append('green')
if stop in self.dropoffs:
colors.append('red')
return drawRouteOrder(
[x.coordinates[::-1] for x in self.solution],
self.solution,
range(1,len(self.solution)+1),
colors=colors, route_color=route_color, m=m, prefix=prefix)
def visualize_graph(self):
plt.plot(self.states)
plt.xlabel("Iterations")
plt.ylabel("Profit")
plt.show()
Solution using Genetic Algorithm (Single Vehicle)#
The problem can be further defined as a problem of passenger allocation. For a one-vehicle solution, all 10 passengers are allocated to the lone vehicle. In this case, the vehicle must find the shortest route from the first depot, through all 10 pickup and dropoff locations, and finally back to a depot.
Parameters#
pop_size = 16
iterations = 1000
num_parents = 8
mutation_prob = 0.3
crossover_prob = 0.7
Run the Solver#
solver = CarSharingSolver(
depot_nodes,
pickup_nodes,
dropoff_nodes,
trip_matrix,
pop_size,
iterations,
num_parents,
mutation_prob,
crossover_prob)
# Initialize the population
solver.initial_population()
solver.run()
Initial Population costs:
[13436.51, 2845.91, 396.92, 1266.29, 6367.61, 5174.6, 8291.99, 3089.69, 1940.99, 12003.11, 232.97, 7730.93, 1341.8, 7872.38, 2475.65, -807.7]
Best Solution: [Name: Loblaws ID: 31582988, Name: 90 ID: 66412375, Name: Continental Tower ID: 103953736, Name: 444 ID: 401029480, Name: 32 ID: 66412324, Name: St. Barnabas Anglican Church ID: 43811604, Name: Royal Bank Plaza North Tower ID: 27767624, Name: Bloor Street West ID: 2286883372, Name: 40 ID: 72376319, Name: The Squire and Firkin ID: 2287594369, Name: 51 ID: 67739858, Name: October Convenience ID: 588647080, Name: 35 ID: 67737319, Name: 565 ID: 66224003, Name: 31 ID: 66228528, Name: Toronto Transit Commission ID: 32052212, Name: 2575 ID: 43805702, Name: Bayview Avenue ID: 2525612330, Name: 15 ID: 66227910, Name: 799 ID: 401062600, Name: 49 ID: 66412700, Name: 93 ID: 401029490]
Best Solution Profits: 18088.64
Visualize the results#
solver.visualize_graph()
solver.visualize_solution()
As you can see, this solution prioritizes finding pickup locations that are close to previous dropoff locations, thus minimizing time driving without a passenger.
Solution using Genetic Algorithm (Two vehicle, pre-assigned allocation)#
As a second example, we can consider the use of two active vehicles, where we can pre-allocate the pickups by “district”. Consider the following plot of the pickup locations, with Bathurst Street highlighted as a dividing line:
from folium import Map, Marker, PolyLine, Icon
m = Map(location=pickup_nodes[0].coordinates[::-1], zoom_start=11)
bathurst_start = [43.82720773214452, -79.45379689449601]
bathurst_end = [43.636628218276, -79.3998242335392]
first_vehicle_index = [0,4,7,8,9]
second_vehicle_index = [1,2,3,5,6]
for x in pickup_nodes:
if pickup_nodes.index(x) in second_vehicle_index:
c = "green"
if pickup_nodes.index(x) in first_vehicle_index:
c = "purple"
Marker(location=x.coordinates[::-1], popup=x.coordinates, icon=Icon(color=c)).add_to(m)
PolyLine([bathurst_start, bathurst_end], color="red").add_to(m)
m
We can assign all the pickups to the west (left) of the line to the first vehicle, and assign the pickups to the east (right) of the line to the second vehicle.
The steps to do this are as follows:
Generate the best solution for the first vehicle and its subset of pickups.
Remove the first vehicle’s used depots as viable depots for the second vehicle.
Generate the best solution for the second vehicle and its subset of pickups.
first_vehicle_index = [0,4,7,8,9]
second_vehicle_index = [1,2,3,5,6]
first_pickups = [x for x in pickup_nodes if pickup_nodes.index(x) in first_vehicle_index]
first_dropoffs = [x for x in dropoff_nodes if dropoff_nodes.index(x) in first_vehicle_index]
second_pickups = [x for x in pickup_nodes if pickup_nodes.index(x) in second_vehicle_index]
second_dropoffs = [x for x in dropoff_nodes if dropoff_nodes.index(x) in second_vehicle_index]
# First vehicle best solution
first_solver = CarSharingSolver(
depot_nodes,
first_pickups,
first_dropoffs,
trip_matrix,
pop_size,
iterations,
num_parents,
mutation_prob,
crossover_prob)
# Initialize the population
first_solver.initial_population()
first_solver.run()
Initial Population costs:
[713.51, 1348.04, -1228.57, 567.2, -823.6, 3591.74, -356.14, -1262.32, 3111.23, 5771.18, 4984.16, 1127.33, 1360.64, -75.28, 1810.7, -1038.04]
Best Solution: [Name: Kitchen Stuff Plus ID: 899348830, Name: Bloor Street West ID: 2286883372, Name: 40 ID: 72376319, Name: The Squire and Firkin ID: 2287594369, Name: 51 ID: 67739858, Name: October Convenience ID: 588647080, Name: 35 ID: 67737319, Name: 565 ID: 66224003, Name: 31 ID: 66228528, Name: 799 ID: 401062600, Name: 49 ID: 66412700, Name: 93 ID: 401029490]
Best Solution Profits: 7153.55
# Second vehicle best solution, with depots removed
second_solver = CarSharingSolver(
depot_nodes,
second_pickups,
second_dropoffs,
trip_matrix,
pop_size,
iterations,
num_parents,
mutation_prob,
crossover_prob,
pre_avoid = [first_solver.solution[0]],
post_avoid = [first_solver.solution[-1]])
# Initialize the population
second_solver.initial_population()
second_solver.run()
Initial Population costs:
[3711.6, 3406.86, 5359.89, 5567.82, 5484.21, 5669.61, 3595.62, 8565.51, 5113.08, 4636.8, 5567.82, 4888.86, 5365.11, 6670.65, 6014.88, 4923.0]
Best Solution: [Name: 93 ID: 401029490, Name: Toronto Transit Commission ID: 32052212, Name: 2575 ID: 43805702, Name: Bayview Avenue ID: 2525612330, Name: 15 ID: 66227910, Name: 90 ID: 66412375, Name: Continental Tower ID: 103953736, Name: 444 ID: 401029480, Name: 32 ID: 66412324, Name: St. Barnabas Anglican Church ID: 43811604, Name: Royal Bank Plaza North Tower ID: 27767624, Name: Kitchen Stuff Plus ID: 899348830]
Best Solution Profits: 9184.23
print("Total profit: ",round(first_solver.solution_cost+second_solver.solution_cost,2))
Total profit: 16337.78
first_map = first_solver.visualize_solution(prefix="A")
second_map = second_solver.visualize_solution(route_color="blue", m=first_map, prefix="B")
second_map
Profit vs Time#
As you can see from the two vehicle implementation, the overall profits have been reduced. However, if our passengers have time constraints (i.e. they must be picked up before a certain time), using multiple vehicles allows us to satisfy those constraints.
Going Further#
You can try to implement a solution that uses even more vehicles, or perhaps a different set of constraints. Alternatively, you can also try to solve the same problem but using a different algorithm (such as particle swarm or Tabu search).