# Multi-Criteria Routing¶

Authors: Yalun Luan, Dongfang Cui, Lanfang Zhang and Junyuan Chen
Course: ECE1724H: Bio-inspired Algorithms for Smart Mobility - Fall 2021
Instructor: Dr. Alaa Khamis
Department: Edward S. Rogers Sr. Department of Electrical & Computer Engineering, University of Toronto

## Introduction¶

As opposed to the traditional “shortest path” route optimization problem, multi-criteria routing considers other factors in route planning, such as:

• number of intersections

• arrival/departure time gap

• danger zones

• number of left turns

• traffic scheduling estimation, etc.

These factors can be combined with other vehicular routing problems, such as capacitated vehicle routing problems (CVRP), vehicle routing problem with profits (VRPP) etc.
This example case will consider two factors, in addition to shortest path: red light intersections, and intersections with a history of fatal collisions.

import osmnx
import pandas as pd
from smart_mobility_utilities.common import Node
from collections import *
from collections import *
import numpy as np
from pymoo.core.problem import Problem
import random
from smart_mobility_utilities.common import cost
import numpy as np
from pymoo.core.duplicate import ElementwiseDuplicateElimination
from pymoo.core.mutation import Mutation
from pymoo.core.sampling import Sampling
from pymoo.core.crossover import Crossover
from pymoo.algorithms.moo.nsga2 import NSGA2
from pymoo.optimize import minimize
from matplotlib import pyplot as plt
import osmnx
import pandas as pd
import matplotlib.pyplot as plt
from smart_mobility_utilities.common import Node
from smart_mobility_utilities.viz import draw_route
from smart_mobility_utilities.viz import draw_map
from smart_mobility_utilities.common import randomized_search, cost, probability
from smart_mobility_utilities.children import get_children
from tqdm.notebook import tqdm
import random
import tabulate
import itertools
import timeit


## Dataset¶

This example considers the area surrounding the University of Toronto’s St. George campus in Downtown Toronto. A list of 567 intersections are labelled with a boolean value marking whether or not a fatal collision has occured there in the past.

df = pd.read_csv("collision_with_osmnxId.csv")

Unnamed: 0 LATITUDE LONGITUDE Collision osmnxId
0 0 43.649418 -79.371446 0 4095622247
1 1 43.650461 -79.371924 0 25768773
2 2 43.651534 -79.372360 0 29687658
3 3 43.652718 -79.372824 0 29687912
4 4 43.653704 -79.373238 0 29688544
5 5 43.655357 -79.373862 0 29688418
6 6 43.657052 -79.374531 1 25768772
7 7 43.660432 -79.375854 0 29603394
8 8 43.662420 -79.376708 1 27571559
9 9 43.666289 -79.378325 1 25628755

This can be further split into two lists; one containing all intersections, and another with the collisions only.

intersectionData = df.osmnxId.to_list()
collisionData = df.loc[df["Collision"]==1].osmnxId.to_list()


## Problem Formulation¶

### Variables¶

$$n$$ is the number of nodes in a given route
$$l_i$$ is the length of a road segment from node $$i$$ to node $$i+1$$.
$$r_i$$ is a boolean value (0 or 1) representing whether a node is also an intersection with a red light
$$s_i$$ is the speed, in km/h of the road segment between nodes $$i$$ and $$i+1$$
$$f_i$$ is a boolean value (0 or 1) representing whether or not an intersection has had a fatal collision in the past
$$X$$ represents an “average” wait time at a red light
$$Y$$ represents an “average” penalty issued for passing through a “dangerous” red light (i.e. has a history of fatal collisions)

### Objective¶

$$\sum_{i=0}^{n-1} l_i + r_i(s_iX/3.6) + f_iY$$

Essentially, the score of a given route is the sum of the lengths of the edges in the route, with penalties added for:

1. Passing through an intersection

2. Passing through an intersection that is considered “dangerous”

## Problem Setup¶

For this example, we will assume that a route is sought between the following nodes:

bbox=[43.647281, 43.669197, -79.411827, -79.374476]
G=osmnx.graph_from_bbox(*bbox, network_type='drive_service')
origin = Node(G, 82759481)
destination = Node(G, 29605000)


Both simulated annealing and a Non-dominated Sorting Genetic Algorithm (NSGA-II) will be tested.

## Simulated Annealing¶

The following schedule will be used for Simulated Annealing:

def exp_schedule(k=20, lam=0.005, limit=100):
function = lambda t: (k * np.exp(-lam*t) if t < limit else 0)
return function

schedule = exp_schedule(200,0.05,10000)
T = [schedule(k) for k in range(100)]
plt.plot(T)

[<matplotlib.lines.Line2D at 0x7f4f1e9c77c0>]


### Solution Class¶

def cost(G, route):
weight = 0
for u,v in zip(route, route[1:]):
weight += G[u][v][0]['length']
return round(weight,4)

def weightedCost(G, route,weight1,weight2):
weight = 0
for u, v in zip(route, route[1:]):
weight += G[u][v][0]['length']
if str(v) in intersectionData:
weight += weight1
if str(v) in collisionData:
weight += weight2
return round(weight,4)

def distanceCost(G, route):
weight = 0
for u, v in zip(route, route[1:]):
weight += G[u][v][0]['length']
return round(weight,4)

def intersectionCost(G, route):
weight = 0
for u, v in zip(route, route[1:]):
if v in intersectionData:
weight += 1
return weight

def collisionCost(G, route):
weight = 0
for u, v in zip(route, route[1:]):
if v in collisionData:
weight += 1
return weight

def SA(temperature, num_iterations, weight1, weight2):
schedule = exp_schedule(temperature,0.05,10000)

states = []
current = randomized_search(G, origin.osmid, destination.osmid)

for t in tqdm(range(num_iterations)):
#exponetially decreasing temperature
T = schedule(t)
#saved for later cost-epoch graph
states.append(weightedCost(G,current,weight1, weight2))

# Generate more paths to choose from
neighbours = get_children(G,current,num_children=5)
next_choice = random.choice(neighbours)

delta_e = weightedCost(G,next_choice,weight1, weight2) - weightedCost(G,current,weight1, weight2)
if delta_e <0 or probability(np.exp(-1 * delta_e/T)):
current = next_choice

route = current
return route, states

schedule = exp_schedule(temperature,0.05,10000)

states = []
current = randomized_search(G, origin.osmid, destination.osmid)

for t in tqdm(range(num_iterations)):
#exponetially decreasing temperature
T = schedule(t)
#generate uniform random variable in [0,1]
acceptance_P = random.uniform(0,1)
#saved for later cost-epoch graph
states.append(weightedCost(G,current,weight1, weight2))

# Generate more paths to choose from
neighbours = get_children(G,current,num_children=5)
next_choice = random.choice(neighbours)

delta_e = weightedCost(G,next_choice,weight1, weight2) - weightedCost(G,current,weight1, weight2)
if delta_e <0 or probability(np.exp(-1 * delta_e/T)) > acceptance_P:
current = next_choice

route = current
return route, states

def singleSA(temperature, num_iterations, weight1, weight2):
schedule = exp_schedule(temperature,0.05,10000)

states = []
current = randomized_search(G, origin.osmid, destination.osmid)

for t in tqdm(range(num_iterations)):
#exponetially decreasing temperature
T = schedule(t)
#saved for later cost-epoch graph
states.append(cost(G,current))

# Generate more paths to choose from
neighbours = get_children(G,current,num_children=5)
next_choice = random.choice(neighbours)

delta_e = cost(G,next_choice) - cost(G,current)
if delta_e <0 or probability(np.exp(-1 * delta_e/T)):
current = next_choice

route = current
return route, states

def getResult(resultRoute):
result = {
"len": len(resultRoute),
"route": resultRoute,
"distance": distanceCost(G,resultRoute),
"intersections": intersectionCost(G,resultRoute),
"collisions": collisionCost(G,resultRoute)
}
return result

def printResult(resultRoute):
print(len(resultRoute))
print(resultRoute)
print("distance: ", distanceCost(G, resultRoute))
print("intersections: ", intersectionCost(G, resultRoute))
print("collisions: ", collisionCost(G, resultRoute))

def printStates(resultStates):
minValue = float('inf')
minIndex = -1
for i,v in enumerate(resultStates):
if v < minValue:
minValue = v
minIndex = i

print("convergence iteration number: ", minIndex)

plt.xlabel("# iterations")
plt.ylabel("Weighted Cost (meters)")
plt.plot(resultStates)
plt.show()


### Experiment #1: Varying starting temperature¶

As can be seen below, higher start temperatures produce longer convergence times. Lower starting temperatures tend to produce better results in terms of optimality, but temperatures that are too low will get stuck at a local minimum.

temperature = 225
num_iterations = 80
weight1 = 50
weight2 = 200
route1,states1 = SA(temperature, num_iterations, weight1, weight2)

temperature = 175
route2,states2 = SA(temperature, num_iterations, weight1, weight2)

temperature = 125
route3,states3 = SA(temperature, num_iterations, weight1, weight2)

temperature = 75
route4,states4 = SA(temperature, num_iterations, weight1, weight2)

route1 = getResult(route1)
route2 = getResult(route2)
route3 = getResult(route3)
route4 = getResult(route4)

headers = ['starting_temp'] + list(route1.keys())
t1 = [225] + list(route1.values())
t2 = [175] + list(route2.values())
t3 = [125] + list(route3.values())
t4 = [75] + list(route4.values())
routes = [x[2] for x in table[1:]]
table = [[x[0]]+x[3:] for x in table]
print(tabulate.tabulate(table, tablefmt='fancy_grid'))

╒═══════════════╤══════════╤═══════════════╤════════════╕
│ starting_temp │ distance │ intersections │ collisions │
├───────────────┼──────────┼───────────────┼────────────┤
│ 225           │ 1551.518 │ 5             │ 0          │
├───────────────┼──────────┼───────────────┼────────────┤
│ 175           │ 1964.216 │ 2             │ 0          │
├───────────────┼──────────┼───────────────┼────────────┤
│ 125           │ 1689.718 │ 1             │ 0          │
├───────────────┼──────────┼───────────────┼────────────┤
│ 75            │ 1916.85  │ 4             │ 0          │
╘═══════════════╧══════════╧═══════════════╧════════════╛

route_map = osmnx.plot_route_folium(G,routes[0], color="green",opacity="0.5")
route_map = osmnx.plot_route_folium(G,routes[1], route_map = route_map, color="blue",opacity="0.5")
route_map = osmnx.plot_route_folium(G,routes[2], route_map = route_map, color="orange",opacity="0.5")
route_map = osmnx.plot_route_folium(G,routes[3], route_map = route_map, color="purple",opacity="0.5")
route_map

Make this Notebook Trusted to load map: File -> Trust Notebook
fig, axs = plt.subplots(2,2)
fig.set_figheight(10)
fig.set_figwidth(10)
axs[0,0].plot(states1)
axs[0,0].title.set_text("Starting Temp: 225")
axs[0,1].plot(states2)
axs[0,1].title.set_text("Starting Temp: 175")
axs[1,0].plot(states3)
axs[1,0].title.set_text("Starting Temp: 125")
axs[1,1].plot(states4)
axs[1,1].title.set_text("Starting Temp: 75")
for ax in axs.flat:
ax.set(xlabel='# iterations', ylabel="Weighted Cost (meters)")


### Experiment #2: Varying starting temperature with Adaptive SA¶

The same experiment can be performed using an adaptive version of the previous algorithm. This adaptive version holds higher temperatures for a longer time through the use of an “acceptance” distribution.

temperature = 225
route5,states5 = adaptiveSA(temperature, num_iterations, weight1, weight2)

temperature = 175
route6,states6 = adaptiveSA(temperature, num_iterations, weight1, weight2)

temperature = 125
route7,states7 = adaptiveSA(temperature, num_iterations, weight1, weight2)

temperature = 75
route8,states8 = adaptiveSA(temperature, num_iterations, weight1, weight2)

route5 = getResult(route5)
route6 = getResult(route6)
route7 = getResult(route7)
route8 = getResult(route8)

t5 = [225] + list(route5.values())
t6 = [175] + list(route6.values())
t7 = [125] + list(route7.values())
t8 = [75] + list(route8.values())
routes2 = [x[2] for x in table2[1:]]
table2 = [[x[0]]+x[3:] for x in table2]
print(tabulate.tabulate(table2, tablefmt='fancy_grid'))

╒═══════════════╤══════════╤═══════════════╤════════════╕
│ starting_temp │ distance │ intersections │ collisions │
├───────────────┼──────────┼───────────────┼────────────┤
│ 225           │ 1810.306 │ 4             │ 0          │
├───────────────┼──────────┼───────────────┼────────────┤
│ 175           │ 1692.581 │ 1             │ 0          │
├───────────────┼──────────┼───────────────┼────────────┤
│ 125           │ 1694.372 │ 1             │ 0          │
├───────────────┼──────────┼───────────────┼────────────┤
│ 75            │ 1802.766 │ 3             │ 0          │
╘═══════════════╧══════════╧═══════════════╧════════════╛

route_map = osmnx.plot_route_folium(G,routes2[0], color="green",opacity="0.5")
route_map = osmnx.plot_route_folium(G,routes2[1], route_map = route_map, color="blue",opacity="0.5")
route_map = osmnx.plot_route_folium(G,routes2[2], route_map = route_map, color="orange",opacity="0.5")
route_map = osmnx.plot_route_folium(G,routes2[3], route_map = route_map, color="purple",opacity="0.5")
route_map

Make this Notebook Trusted to load map: File -> Trust Notebook
fig, axs = plt.subplots(2,2)
fig.set_figheight(10)
fig.set_figwidth(10)
axs[0,0].plot(states5)
axs[0,0].title.set_text("Starting Temp: 225")
axs[0,1].plot(states6)
axs[0,1].title.set_text("Starting Temp: 175")
axs[1,0].plot(states7)
axs[1,0].title.set_text("Starting Temp: 125")
axs[1,1].plot(states8)
axs[1,1].title.set_text("Starting Temp: 75")
for ax in axs.flat:
ax.set(xlabel='# iterations', ylabel="Weighted Cost (meters)")


## NSGA-II¶

### Solution Class¶

def cross_over(route_1, route_2):
origin = route_1[0]
destination = route_1[-1]
intersection = [*itertools.filterfalse(\
lambda element : element in [origin, destination] ,\
list(set(route_1) & set(route_2)))]

if len(intersection) == 0:
return route_1, route_2 # if there is not common node, just return the first route

cross_over_point = random.choice(intersection)
first_point = route_1.index(cross_over_point)
second_point = route_2.index(cross_over_point)

res_1 = route_1[:first_point] + route_2[second_point:]
res_2 = route_2[:second_point] + route_1[first_point:]

return res_1, res_2

def dijkstra(G, origin, destination):

# Using a set here avoids the problem with self loops
seen = set()
shortest_dist = {osmid: math.inf for osmid in G.nodes()}
unrelaxed_nodes = [Node(graph = G, osmid = osmid) for osmid in G.nodes()]

shortest_dist[origin] = 0
found = False

node = min(unrelaxed_nodes, key = lambda node : shortest_dist[node.osmid])

# relaxing the node
unrelaxed_nodes.remove(node)

# if the destination node has been relaxed then that is the route we want
if node == destination:
route = node.path()
found = True
continue

# otherwise, let's relax edges of its neighbours
for child in node.expand():
# skip self-loops

if child.osmid in seen: continue

child_obj = next((node for node in unrelaxed_nodes if node.osmid == child.osmid), None)
child_obj.distance = child.distance

distance = shortest_dist[node.osmid] + child.distance
if distance < shortest_dist[child_obj.osmid]:
shortest_dist[child_obj.osmid] = distance
child_obj.parent = node

return route

def mutate(route, G):
source = route[0]
destination = route[-1]

path = route.copy()
size = len(route)
for i in range(1, size):
end = random.randint(i+1,size-2)
#subpath = dijkstra(G, route[i-1], route[end+1])
#subpath = osmnx.distance.shortest_path(G, route[i-1], route[end+1])
subpath = randomized_search(G, route[i-1], route[end+1])
newPath = route[:i-1]+subpath+route[end+2:]
if len(newPath) == len(set(newPath)):
return newPath

return path

class NSGA_II(Problem):

def __init__(self, n_characters=10):
super().__init__(n_var=1, n_obj=3, n_constr=0)
self.state = []
self.G = self.generateMap()
self.df =  df
self.ids = self.df['osmnxId'].tolist()
self.source = 82759481
self.destination = 29605000

def generateMap(self):
bbox=[43.647281, 43.669197, -79.411827, -79.374476]
return osmnx.graph_from_bbox(*bbox, network_type='drive_service')

def calculateDistance(self, G,route):
return cost(G, route)

def calculateSafety(self, df, route, ids):
safety = 0
for i in range(len(route)):
if route[i] in ids:
if df.loc[df['osmnxId'] == route[i], 'Collision'].iloc[0] > 0:
safety += 1000
return safety

def calculateIntersections(self, df, route, ids):
intersection = 0
for i in range(len(route)):
if route[i] in ids:
intersection += 1000
return intersection

def _evaluate(self, X, out, *args, **kwargs):
costs = []
for x in X:
costs.append(self.calculateDistance(self.G, x[0]))
safety_list = []
for x in X:
safety_list.append(self.calculateSafety(self.df, x[0], self.ids))
intersections = []
for x in X:
intersections.append(self.calculateIntersections(self.df, x[0], self.ids))
out["F"] = np.column_stack([costs, safety_list, intersections])
self.state.append(out["F"])
#out["F"] = np.array([- n_a, - n_b], dtype=float)

from pymoo.core.sampling import Sampling

class MySampling1(Sampling):

def _do(self, problem, n_samples, **kwargs):
#X = np.full((n_samples, 1), None, dtype=object)
X = []
for i in range(n_samples):
X.append([randomized_search(problem.G, problem.source, problem.destination)])
#X[i, 0] = randomized_search(problem.G, problem.source, problem.destination)#"".join([np.random.choice(problem.ALPHABET) for _ in range(problem.n_characters)])
return X
from pymoo.core.crossover import Crossover

class MyCrossover1(Crossover):
def __init__(self, prob=0.7):

# define the crossover: number of parents and number of offsprings
super().__init__(2, 2)
self.prob = prob

def _do(self, problem, X, **kwargs):

# The input of has the following shape (n_parents, n_matings, n_var)
_, n_matings, n_var = X.shape
# The output owith the shape (n_offsprings, n_matings, n_var)
# Because there the number of parents and offsprings are equal it keeps the shape of X
Y = np.full_like(X, None, dtype=object)
if np.random.uniform(0, 1) < self.prob:
return X
# for each mating provided
for k in range(n_matings):
# get the first and the second parent
a, b = X[0, k, 0], X[1, k, 0]
# prepare the offsprings
if a == b and np.random.uniform(0, 1) < 0.1:
off_a = a
off_b = randomized_search(problem.G, a[0], a[-1])
else:
off_a, off_b = cross_over(a,b)

Y[0, k, 0], Y[1, k, 0] = off_a, off_b
return Y
from pymoo.core.mutation import Mutation

class MyMutation1(Mutation):
def __init__(self, prob =0.4):
super().__init__()
self.prob  = prob

def _do(self, problem, X, **kwargs):
offspring=[]
# loop over individuals in population
for i in X:
# performe mutation with certain probability
if np.random.uniform(0, 1) < self.prob:
mutated_individual = mutate(i[0], problem.G)
offspring.append([mutated_individual])
# if no mutation
else:
offspring.append([i[0]])
#for i in range(len(X)):
#    r = np.random.random()

# with a probabilty of 40% - change the order of characters
#   if r < self.prob:
#       mutated_individual = mutate(X[i][0], problem.G)
#       offspring.append([mutated_individual])
# also with a probabilty of 40% - change a character randomly
#elif:
#offspring.append([X[i]])

return offspring
from pymoo.core.duplicate import ElementwiseDuplicateElimination

class MyDuplicateElimination1(ElementwiseDuplicateElimination):

def is_equal(self, a, b):
return a.X[0] == b.X[0]


### Parameters¶

pop_size = 20
n_offSpring = 10
n_gen = 200
mutation_prob = 0.4
crossover_prob = 1.0


### Experiment #3: Solution using NSGA-II¶

problem = NSGA_II()
random.seed(10)
start = timeit.default_timer()
algorithm = NSGA2(pop_size=pop_size,
sampling=MySampling1(),
crossover=MyCrossover1(),
n_offspring = n_offSpring,
mutation=MyMutation1(),
eliminate_duplicates=False)
from pymoo.factory import get_termination
termination = get_termination("n_gen", n_gen)

res = minimize(problem,
algorithm,
termination,
save_history=True,
verbose=True)
stop = timeit.default_timer()

/home/yinan/book-env/lib/python3.8/site-packages/pymoo/core/population.py:84: VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray.
res = [np.array(e) for e in res]

=======================================================
n_gen |  n_eval |  n_nds  |     eps      |  indicator
=======================================================
1 |      20 |       2 |            - |            -
2 |      40 |       2 |  0.074123989 |        nadir

    3 |      60 |       6 |  0.00000E+00 |            f
4 |      80 |      12 |  0.00000E+00 |            f

    5 |     100 |      20 |  0.00000E+00 |            f
6 |     120 |      20 |  0.926266976 |        ideal

    7 |     140 |      20 |  0.00000E+00 |            f
8 |     160 |      20 |  0.00000E+00 |            f

    9 |     180 |      20 |  0.00000E+00 |            f
10 |     200 |      20 |  0.00000E+00 |            f

   11 |     220 |      20 |  0.00000E+00 |            f
12 |     240 |      20 |  0.00000E+00 |            f

   13 |     260 |      20 |  0.00000E+00 |            f
14 |     280 |      20 |  0.00000E+00 |            f

   15 |     300 |      20 |  0.00000E+00 |            f
16 |     320 |      20 |  0.00000E+00 |            f

   17 |     340 |      14 |  0.713284455 |        ideal
18 |     360 |      20 |  0.00000E+00 |            f

   19 |     380 |      20 |  0.00000E+00 |            f
20 |     400 |      20 |  0.00000E+00 |            f

   21 |     420 |      20 |  0.00000E+00 |            f
22 |     440 |      20 |  0.00000E+00 |            f

   23 |     460 |      20 |  0.00000E+00 |            f
24 |     480 |      20 |  0.00000E+00 |            f

   25 |     500 |      20 |  0.00000E+00 |            f
26 |     520 |      20 |  0.00000E+00 |            f

   27 |     540 |      20 |  0.00000E+00 |            f
28 |     560 |      20 |  0.00000E+00 |            f
29 |     580 |      20 |  0.00000E+00 |            f

   30 |     600 |      20 |  0.00000E+00 |            f

   31 |     620 |      20 |  0.00000E+00 |            f
32 |     640 |      20 |  0.00000E+00 |            f

   33 |     660 |      20 |  0.00000E+00 |            f
34 |     680 |      20 |  0.00000E+00 |            f

   35 |     700 |      20 |  0.00000E+00 |            f
36 |     720 |      20 |  0.00000E+00 |            f

   37 |     740 |      20 |  0.00000E+00 |            f
38 |     760 |      20 |  0.00000E+00 |            f

   39 |     780 |      20 |  0.00000E+00 |            f
40 |     800 |      20 |  0.00000E+00 |            f

   41 |     820 |      20 |  0.00000E+00 |            f
42 |     840 |      20 |  0.00000E+00 |            f

   43 |     860 |      20 |  0.00000E+00 |            f

   44 |     880 |      20 |  0.00000E+00 |            f
45 |     900 |      20 |  0.00000E+00 |            f

   46 |     920 |      20 |  0.00000E+00 |            f
47 |     940 |      20 |  0.00000E+00 |            f

   48 |     960 |      20 |  0.00000E+00 |            f
49 |     980 |      20 |  0.00000E+00 |            f

   50 |    1000 |      20 |  0.00000E+00 |            f
51 |    1020 |      20 |  0.00000E+00 |            f

   52 |    1040 |      20 |  0.00000E+00 |            f
53 |    1060 |      20 |  0.00000E+00 |            f

   54 |    1080 |      20 |  0.00000E+00 |            f
55 |    1100 |      20 |  0.00000E+00 |            f

   56 |    1120 |      20 |  0.00000E+00 |            f
57 |    1140 |      20 |  0.00000E+00 |            f

   58 |    1160 |      20 |  0.00000E+00 |            f

   59 |    1180 |      20 |  0.00000E+00 |            f
60 |    1200 |      20 |  0.00000E+00 |            f

   61 |    1220 |      20 |  0.00000E+00 |            f
62 |    1240 |      10 |  0.290281471 |        nadir

   63 |    1260 |      19 |  0.282481206 |        ideal
64 |    1280 |      20 |  0.00000E+00 |            f

   65 |    1300 |      20 |  0.00000E+00 |            f
66 |    1320 |      20 |  0.00000E+00 |            f

   67 |    1340 |      20 |  0.00000E+00 |            f
68 |    1360 |      20 |  0.00000E+00 |            f

   69 |    1380 |      18 |  0.009479150 |            f
70 |    1400 |      20 |  0.00000E+00 |            f

   71 |    1420 |      20 |  0.00000E+00 |            f
72 |    1440 |      20 |  0.00000E+00 |            f

   73 |    1460 |      20 |  0.00000E+00 |            f
74 |    1480 |      20 |  0.00000E+00 |            f

   75 |    1500 |      20 |  0.00000E+00 |            f
76 |    1520 |      20 |  0.00000E+00 |            f

   77 |    1540 |      20 |  0.00000E+00 |            f
78 |    1560 |      20 |  0.00000E+00 |            f

   79 |    1580 |      20 |  0.00000E+00 |            f
80 |    1600 |      20 |  0.00000E+00 |            f

   81 |    1620 |      20 |  0.00000E+00 |            f
82 |    1640 |      20 |  0.00000E+00 |            f

   83 |    1660 |      20 |  0.00000E+00 |            f
84 |    1680 |      20 |  0.00000E+00 |            f

   85 |    1700 |      20 |  0.00000E+00 |            f
86 |    1720 |      20 |  0.00000E+00 |            f

   87 |    1740 |      20 |  0.012825895 |            f
88 |    1760 |      20 |  0.00000E+00 |            f

   89 |    1780 |      20 |  0.00000E+00 |            f
90 |    1800 |      20 |  0.00000E+00 |            f

   91 |    1820 |      20 |  0.00000E+00 |            f
92 |    1840 |      20 |  0.00000E+00 |            f

   93 |    1860 |      20 |  0.00000E+00 |            f
94 |    1880 |      20 |  0.00000E+00 |            f

   95 |    1900 |      16 |  0.054336077 |        ideal
96 |    1920 |      20 |  0.00000E+00 |            f

   97 |    1940 |      20 |  0.00000E+00 |            f
98 |    1960 |      20 |  0.00000E+00 |            f

   99 |    1980 |      20 |  0.00000E+00 |            f
100 |    2000 |      20 |  0.00000E+00 |            f

  101 |    2020 |      20 |  0.00000E+00 |            f

  102 |    2040 |      20 |  0.00000E+00 |            f
103 |    2060 |      20 |  0.00000E+00 |            f

  104 |    2080 |      20 |  0.00000E+00 |            f
105 |    2100 |      20 |  0.00000E+00 |            f

  106 |    2120 |      20 |  0.00000E+00 |            f
107 |    2140 |      20 |  0.00000E+00 |            f

  108 |    2160 |      20 |  0.00000E+00 |            f
109 |    2180 |      20 |  0.00000E+00 |            f

  110 |    2200 |      20 |  0.00000E+00 |            f
111 |    2220 |      20 |  0.00000E+00 |            f

  112 |    2240 |      20 |  0.00000E+00 |            f
113 |    2260 |      20 |  0.00000E+00 |            f

  114 |    2280 |      20 |  0.00000E+00 |            f
115 |    2300 |      20 |  0.00000E+00 |            f

  116 |    2320 |      20 |  0.00000E+00 |            f
117 |    2340 |      20 |  0.00000E+00 |            f

  118 |    2360 |      20 |  0.00000E+00 |            f
119 |    2380 |      20 |  0.00000E+00 |            f

  120 |    2400 |      20 |  0.00000E+00 |            f
121 |    2420 |      20 |  0.00000E+00 |            f

  122 |    2440 |      20 |  0.00000E+00 |            f
123 |    2460 |      20 |  0.00000E+00 |            f

  124 |    2480 |      20 |  0.00000E+00 |            f
125 |    2500 |      20 |  0.00000E+00 |            f

  126 |    2520 |      20 |  0.00000E+00 |            f
127 |    2540 |      20 |  0.00000E+00 |            f

  128 |    2560 |      20 |  0.00000E+00 |            f
129 |    2580 |      20 |  0.00000E+00 |            f

  130 |    2600 |      20 |  0.00000E+00 |            f
131 |    2620 |      20 |  0.00000E+00 |            f

  132 |    2640 |      20 |  0.00000E+00 |            f
133 |    2660 |      20 |  0.00000E+00 |            f

  134 |    2680 |      20 |  0.00000E+00 |            f
135 |    2700 |      20 |  0.00000E+00 |            f

  136 |    2720 |      20 |  0.00000E+00 |            f
137 |    2740 |      20 |  0.00000E+00 |            f

  138 |    2760 |      20 |  0.00000E+00 |            f
139 |    2780 |      20 |  0.00000E+00 |            f

  140 |    2800 |      20 |  0.00000E+00 |            f
141 |    2820 |      20 |  0.00000E+00 |            f

  142 |    2840 |      20 |  0.00000E+00 |            f
143 |    2860 |      20 |  0.00000E+00 |            f

  144 |    2880 |      20 |  0.00000E+00 |            f
145 |    2900 |      20 |  0.00000E+00 |            f

  146 |    2920 |      20 |  0.00000E+00 |            f
147 |    2940 |      20 |  0.00000E+00 |            f

  148 |    2960 |      20 |  0.00000E+00 |            f
149 |    2980 |      16 |  0.020838641 |            f

  150 |    3000 |      20 |  0.00000E+00 |            f
151 |    3020 |      20 |  0.00000E+00 |            f

  152 |    3040 |      20 |  0.00000E+00 |            f
153 |    3060 |      20 |  0.00000E+00 |            f

  154 |    3080 |      20 |  0.00000E+00 |            f
155 |    3100 |      20 |  0.00000E+00 |            f

  156 |    3120 |      20 |  0.00000E+00 |            f
157 |    3140 |      20 |  0.00000E+00 |            f

  158 |    3160 |      20 |  0.00000E+00 |            f
159 |    3180 |      20 |  0.00000E+00 |            f

  160 |    3200 |      20 |  0.00000E+00 |            f
161 |    3220 |      20 |  0.00000E+00 |            f

  162 |    3240 |      20 |  0.00000E+00 |            f
163 |    3260 |      20 |  0.00000E+00 |            f

  164 |    3280 |      20 |  0.00000E+00 |            f
165 |    3300 |      20 |  0.00000E+00 |            f

  166 |    3320 |      20 |  0.00000E+00 |            f
167 |    3340 |      20 |  0.00000E+00 |            f

  168 |    3360 |      20 |  0.00000E+00 |            f
169 |    3380 |      20 |  0.00000E+00 |            f

  170 |    3400 |      20 |  0.00000E+00 |            f
171 |    3420 |      20 |  0.007468537 |        ideal

  172 |    3440 |      20 |  0.00000E+00 |            f
173 |    3460 |      20 |  0.00000E+00 |            f

  174 |    3480 |      20 |  0.00000E+00 |            f
175 |    3500 |      20 |  0.00000E+00 |            f

  176 |    3520 |      20 |  0.00000E+00 |            f
177 |    3540 |      20 |  0.00000E+00 |            f

  178 |    3560 |      20 |  0.00000E+00 |            f
179 |    3580 |      20 |  0.00000E+00 |            f

  180 |    3600 |      20 |  0.00000E+00 |            f
181 |    3620 |      20 |  0.00000E+00 |            f

  182 |    3640 |      20 |  0.00000E+00 |            f
183 |    3660 |      20 |  0.00000E+00 |            f

  184 |    3680 |      20 |  0.00000E+00 |            f
185 |    3700 |      20 |  0.00000E+00 |            f

  186 |    3720 |      20 |  0.00000E+00 |            f
187 |    3740 |      20 |  0.00000E+00 |            f

  188 |    3760 |      20 |  0.00000E+00 |            f
189 |    3780 |      20 |  0.00000E+00 |            f

  190 |    3800 |      20 |  0.00000E+00 |            f
191 |    3820 |      20 |  0.00000E+00 |            f

  192 |    3840 |      20 |  0.00000E+00 |            f
193 |    3860 |      20 |  0.00000E+00 |            f

  194 |    3880 |      20 |  0.00000E+00 |            f
195 |    3900 |      20 |  0.00000E+00 |            f

  196 |    3920 |      20 |  0.00000E+00 |            f
197 |    3940 |      20 |  0.00000E+00 |            f

  198 |    3960 |      20 |  0.00000E+00 |            f
199 |    3980 |      20 |  0.00000E+00 |            f

  200 |    4000 |      20 |  0.00000E+00 |            f


### Visualizing the Results¶

print('Time: ', stop - start)

f = []
# iterate over the generations
for generation in res.history:
# retrieve the optimal for all objectives from the generation
opt = generation.opt
this_f = opt.get("F")
f.append(this_f)

fNumpy = np.asarray(f)
history = fNumpy

weights = [0.5,0.2,0.3]
mins = []
converg_iter = n_gen
for generation in fNumpy:
min_score = 100000000000
for f in generation:
#print(f[0])
score = weights[0]*f[0]+weights[1]*f[1]+weights[2]*f[2]
min_score = min(score, min_score)
mins.append(min_score)
min_score = mins[-1]
for i in range(len(mins)-1,0, -1):
if(mins[i] == min_score):
converg_iter -= 1

plt.plot(mins)
plt.xlabel("generations")
plt.ylabel("score")
plt.title("population=20, generation=100")

decisions = []
for f in res.F:
score = weights[0]*f[0]+weights[1]*f[1]+weights[2]*f[2]
decisions.append(score)
val, idx = min((val, idx) for (idx, val) in enumerate(decisions))
print("final score: ", val)
print("distance: ", res.F[idx][0])
print("collisions: ", res.F[idx][1]/1000)
print("intersections: ", res.F[idx][2]/1000)
print("convergence iteration number: ", converg_iter)

Time:  25.436917803999677
final score:  1132.6264999999999
distance:  1665.253
collisions:  0.0
intersections:  1.0
convergence iteration number:  61

/home/yinan/book-env/lib/python3.8/site-packages/numpy/core/_asarray.py:102: VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray.
return array(a, dtype, copy=False, order=order)

X=res.X
pool = []
for element in X:
pool.append(element[0])

random_hexa = lambda: random.randint(0,255) # generate random hexadecimal color
rc = ['#%02X%02X%02X' % (random_hexa(),random_hexa(),random_hexa()) for _ in range(len(pool))]
route_map = osmnx.plot_route_folium(G,pool.pop(), color=rc.pop(), opacity=0.5)
for x in pool:
route_map = osmnx.plot_route_folium(G,x, opacity=0.5, color=rc.pop(), route_map=route_map)
route_map

Make this Notebook Trusted to load map: File -> Trust Notebook

The NSGA-II algorithm generates a set of solutions, depending on the balance between the various constraints.

We can define a custom weighting of the constraints to select a solution. Below you can see the differences in solutions when different weights are used:

def getRouteByWeight(weights):
decisions = []
for f in res.F:
score = weights[0]*f[0]+weights[1]*f[1]+weights[2]*f[2]
decisions.append(score)
val, idx = min((val, idx) for (idx, val) in enumerate(decisions))
print("final score: ", val)
print("distance: ", res.F[idx][0])
print("collision: ", res.F[idx][1])
print("intersections: ", res.F[idx][2]/1000)
return res.X[idx][0]

# Test Weight 1
weight1 = [0.5,0.2,0.3]
test1 = getRouteByWeight(weight1)
print("---")

# Shortest Path
weight2 = [1.0,0.0,0.0]
test2 = getRouteByWeight(weight2)
print("---")

final score:  1132.6264999999999
distance:  1665.253
collision:  0.0
intersections:  1.0
---
final score:  1544.078
distance:  1544.078
collision:  0.0
intersections:  3.0
---

route_map = osmnx.plot_route_folium(G,test1, color='green', opacity=0.5)
route_map = osmnx.plot_route_folium(G,test2, color='red', route_map=route_map,opacity=0.5)
route_map

Make this Notebook Trusted to load map: File -> Trust Notebook