1.5. The Vehicle Routing Problem (VRP)#
The Vehicle Routing Problem (VRP) is an combinatorial optimization problem of finding a set of routes for a fleet of vehicles that minimizes travel time. The Vehicle Routing Problem can be thought of as multiple Travelling Salesman Problems (TSP) combined together.
INPUT
List of Locations that needs to be visited
Number of Vehicles
Location of the Depot. Which is used as the starting adn ending point for all the vehicles.
SCORING:
Fig. 1.1 Example VRP with three vehicles Source: https://commons.wikimedia.org/wiki/File:Figure_illustrating_the_vehicle_routing_problem.png Image by PierreSelim. Released to public domain#
Determine the longest route of all the vehicles -> The larger the route the worse the score
1.5.1. 1. Build a Basic VRP Solver#
Starter Code: You may use the following implementation of tsp to ge you started.
It should pass the following:
When called like:
# create a problem instance:
vrp = VehicleRoutingProblem("bayg29", 3, 12)
# generate random solution and evaluate it:
randomSolution = random.sample(range(len(vrp)), len(vrp))
print("random solution = ", randomSolution)
print("route breakdown = ", vrp.getRoutes(randomSolution))
print("max distance = ", vrp.getMaxDistance(randomSolution))
# plot the solution:
plot = vrp.plotData(randomSolution)
plot.show()
It should output:
>python vrp.py
https://raw.githubusercontent.com/mastqe/tsplib/master/bayg29.tsp
length = 29, locations = [array([1150., 1760.], dtype=float32), array([ 630., 1660.], dtype=float32), array([ 40., 2090.], dtype=float32), array([ 750., 1100.], dtype=float32), array([ 750., 2030.], dtype=float32), array([1030., 2070.], dtype=float32), array([1650., 650.], dtype=float32), array([1490., 1630.], dtype=float32), array([ 790., 2260.], dtype=float32), array([ 710., 1310.], dtype=float32), array([840., 550.], dtype=float32), array([1170., 2300.], dtype=float32), array([ 970., 1340.], dtype=float32), array([510., 700.], dtype=float32), array([750., 900.], dtype=float32), array([1280., 1200.], dtype=float32), array([230., 590.], dtype=float32), array([460., 860.], dtype=float32), array([1040., 950.], dtype=float32), array([ 590., 1390.], dtype=float32), array([ 830., 1770.], dtype=float32), array([490., 500.], dtype=float32), array([1840., 1240.], dtype=float32), array([1260., 1500.], dtype=float32), array([1280., 790.], dtype=float32), array([ 490., 2130.], dtype=float32), array([1460., 1420.], dtype=float32), array([1260., 1910.], dtype=float32), array([ 360., 1980.], dtype=float32)]
0, 1: location1 = [1150. 1760.], location2 = [ 630. 1660.] => distance = 529.528076171875
0, 2: location1 = [1150. 1760.], location2 = [ 40. 2090.] => distance = 1158.0155029296875
0, 3: location1 = [1150. 1760.], location2 = [ 750. 1100.] => distance = 771.7512817382812
...
0, 4: location1 = [1150. 1760.], location2 = [ 750. 2030.] => distance = 482.5971374511719
0, 5: location1 = [1150. 1760.], location2 = [1030. 2070.] => distance = 332.4154052734375
0, 6: location1 = [1150. 1760.], location2 = [1650. 650.] => distance = 1217.415283203125
random solution = [13, 25, 17, 16, 14, 23, 28, 7, 12, 0, 1, 10, 29, 26, 2, 27, 19, 11, 21, 8, 24, 22, 15, 4, 5, 6, 30, 20, 9, 3, 18]
route breakdown = [[13, 25, 17, 16, 14, 23, 28, 7, 0, 1, 10], [26, 2, 27, 19, 11, 21, 8, 24, 22, 15, 4, 5, 6], [20, 9, 3, 18]]
Fig. 1.2 Should print something like this.#
1.5.1.1. Base Code#
import csv
import pickle
import os
import codecs
import numpy as np
from urllib.request import urlopen
import matplotlib.pyplot as plt
class TravelingSalesmanProblem:
"""This class encapsulates the Traveling Salesman Problem.
City coordinates are read from an online file and distance matrix is calculated.
The data is serialized to disk.
The total distance can be calculated for a path represented by a list of city indices.
A plot can be created for a path represented by a list of city indices.
:param name: The name of the corresponding TSPLIB problem, e.g. 'burma14' or 'bayg29'.
"""
def __init__(self, name):
"""
Creates an instance of a TSP
:param name: name of the TSP problem
"""
# initialize instance variables:
self.name = name
self.locations = []
self.distances = []
self.tspSize = 0
# initialize the data:
self.__initData()
def __len__(self):
"""
returns the length of the underlying TSP
:return: the length of the underlying TSP (number of cities)
"""
return self.tspSize
def __initData(self):
"""Reads the serialized data, and if not available - calls __create_data() to prepare it
"""
# attempt to read serialized data:
try:
self.locations = pickle.load(open(os.path.join("tsp-data", self.name + "-loc.pickle"), "rb"))
self.distances = pickle.load(open(os.path.join("tsp-data", self.name + "-dist.pickle"), "rb"))
except (OSError, IOError):
pass
# serailized data not found - create the data from scratch:
if not self.locations or not self.distances:
self.__createData()
# set the problem 'size':
self.tspSize = len(self.locations)
def __createData(self):
"""Reads the desired TSP file from the Internet, extracts the city coordinates, calculates the distances
between every two cities and uses them to populate a distance matrix (two-dimensional array).
It then serializes the city locations and the calculated distances to disk using the pickle utility.
"""
self.locations = []
# print("http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/" + self.name + ".tsp")
# Use the following instead: https://raw.githubusercontent.com/mastqe/tsplib/master/a280.tsp
URL = "https://raw.githubusercontent.com/mastqe/tsplib/master/"
print(URL + self.name + ".tsp")
# open whitespace-delimited file from url and read lines from it:
with urlopen(URL + self.name + ".tsp") as f:
reader = csv.reader(codecs.iterdecode(f, 'utf-8'), delimiter=" ", skipinitialspace=True)
# skip lines until one of these lines is found:
for row in reader:
if row[0] in ('DISPLAY_DATA_SECTION', 'NODE_COORD_SECTION'):
break
# read data lines until 'EOF' found:
for row in reader:
if row[0] != 'EOF':
# remove index at beginning of line:
del row[0]
# convert x,y coordinates to ndarray:
self.locations.append(np.asarray(row, dtype=np.float32))
else:
break
# set the problem 'size':
self.tspSize = len(self.locations)
# print data:
print("length = {}, locations = {}".format(self.tspSize, self.locations))
# initialize distance matrix by filling it with 0's:
self.distances = [[0] * self.tspSize for _ in range(self.tspSize)]
# populate the distance matrix with calculated distances:
for i in range(self.tspSize):
for j in range(i + 1, self.tspSize):
# calculate euclidean distance between two ndarrays:
distance = np.linalg.norm(self.locations[j] - self.locations[i])
self.distances[i][j] = distance
self.distances[j][i] = distance
print("{}, {}: location1 = {}, location2 = {} => distance = {}".format(i, j, self.locations[i], self.locations[j], distance))
# serialize locations and distances:
if not os.path.exists("tsp-data"):
os.makedirs("tsp-data")
pickle.dump(self.locations, open(os.path.join("tsp-data", self.name + "-loc.pickle"), "wb"))
pickle.dump(self.distances, open(os.path.join("tsp-data", self.name + "-dist.pickle"), "wb"))
def getTotalDistance(self, indices):
"""Calculates the total distance of the path described by the given indices of the cities
:param indices: A list of ordered city indices describing the given path.
:return: total distance of the path described by the given indices
"""
# distance between th elast and first city:
distance = self.distances[indices[-1]][indices[0]]
# add the distance between each pair of consequtive cities:
for i in range(len(indices) - 1):
distance += self.distances[indices[i]][indices[i + 1]]
return distance
def plotData(self, indices, label=None):
"""plots the path described by the given indices of the cities
:param indices: A list of ordered city indices describing the given path.
:return: the resulting plot
"""
# plot the dots representing the cities:
plt.scatter(*zip(*self.locations), marker='.', color='red')
# create a list of the corresponding city locations:
locs = [self.locations[i] for i in indices]
locs.append(locs[0])
# plot a line between each pair of consequtive cities:
plt.plot(*zip(*locs), linestyle='-', color='blue')
if label:
plt.title(label)
return plt
# Starter Code
class VehicleRoutingProblem:
def __init__(self, tspName, numOfVehicles, depotIndex):
"""
Creates an instance of a VRP
:param tspName: name of the underlying TSP
:param numOfVehicles: number of vehicles used
:param depotIndex: the index of the TSP city that will be used as the depot location
"""
self.tsp = TravelingSalesmanProblem(tspName)
self.numOfVehicles = numOfVehicles
self.depotIndex = depotIndex
def __len__(self):
"""
returns the number of indices used to internally represent the VRP
:return: the number of indices used to internally represent the VRP
"""
return len(self.tsp) + self.numOfVehicles - 1
def getRoutes(self, indices):
"""
breaks the list of given indices into separate routes,
by detecting the 'separator' indices
:param indices: list of indices, including 'separator' indices
:return: a list of routes, each route being a list of location indices from the tsp problem
"""
# initialize lists:
routes = []
route = []
# loop over all indices in the list:
for i in indices:
# skip depot index:
if i == self.depotIndex:
continue
# index is part of the current route:
if not self.isSeparatorIndex(i):
route.append(i)
# separator index - route is complete:
else:
routes.append(route)
route = [] # reset route
# append the last route:
if route or self.isSeparatorIndex(i):
routes.append(route)
return routes
def isSeparatorIndex(self, index):
"""
Finds if curent index is a separator index
:param index: denotes the index of the location
:return: True if the given index is a separator
"""
# check if the index is larger than the number of the participating locations:
return index >= len(self) - (self.numOfVehicles - 1)
def getRouteDistance(self, indices):
"""Calculates total the distance of the path that starts at the depo location and goes through
the cities described by the given indices
:param indices: a list of ordered city indices describing the given path.
:return: total distance of the path described by the given indices
"""
if not indices:
return 0
# find the distance between the depo location and the city:
distance = self.tsp.distances[self.depotIndex][indices[0]]
# add the distance between the last city and the depot location:
distance += self.tsp.distances[indices[-1]][self.depotIndex]
# add the distances between the cities along the route:
for i in range(len(indices) - 1):
distance += self.tsp.distances[indices[i]][indices[i + 1]]
return distance
def getTotalDistance(self, indices):
"""Calculates the combined distance of the various paths described by the given indices
:param indices: a list of ordered city indices and separator indices describing one or more paths.
:return: combined distance of the various paths described by the given indices
"""
totalDistance = 0
for route in self.getRoutes(indices):
routeDistance = self.getRouteDistance(route)
#print("- route distance = ", routeDistance)
totalDistance += routeDistance
return totalDistance
def getMaxDistance(self, indices)-> float:
"""Calculates the max distance among the distances of the various paths described by the given indices
:param indices: a list of ordered city indices and separator indices describing one or more paths.
:return: max distance among the distances of the various paths described by the given indices
"""
maxDistance = 0
for route in self.getRoutes(indices):
# TODO get the distance of the current route:
# TODO update the max distance if the current route distance is larger
pass
return maxDistance
def getAvgDistance(self, indices) -> float:
"""Calculates the average distance among the distances of the various paths described by the given indices
Does not consider empty paths
:param indices: a list of ordered city indices and separator indices describing one or more paths.
:return: max distance among the distances of the various paths described by the given indices
"""
# TODO Get routes, for each route if the route is not empty. Calculate the distance and add it to the total distance
# TODO Return the average distance
pass
def plotData(self, indices) -> plt:
"""breaks the list of indices into separate routes and plot each route in a different color
:param indices: A list of ordered indices describing the combined routes
:return: the resulting plot
"""
# TODO plot the dots representing the cities:
# TODO mark the depot with a large 'x'
# TODO break the indices into separate routes and plot each route in a different color
pass
1.5.1.2. Solution#
Check the solution.
class VehicleRoutingProblem:
def __init__(self, tspName, numOfVehicles, depotIndex):
"""
Creates an instance of a VRP
:param tspName: name of the underlying TSP
:param numOfVehicles: number of vehicles used
:param depotIndex: the index of the TSP city that will be used as the depot location
"""
self.tsp = TravelingSalesmanProblem(tspName)
self.numOfVehicles = numOfVehicles
self.depotIndex = depotIndex
def __len__(self):
"""
returns the number of indices used to internally represent the VRP
:return: the number of indices used to internally represent the VRP
"""
return len(self.tsp) + self.numOfVehicles - 1
def getRoutes(self, indices):
"""
breaks the list of given indices into separate routes,
by detecting the 'separator' indices
:param indices: list of indices, including 'separator' indices
:return: a list of routes, each route being a list of location indices from the tsp problem
"""
# initialize lists:
routes = []
route = []
# loop over all indices in the list:
for i in indices:
# skip depot index:
if i == self.depotIndex:
continue
# index is part of the current route:
if not self.isSeparatorIndex(i):
route.append(i)
# separator index - route is complete:
else:
routes.append(route)
route = [] # reset route
# append the last route:
if route or self.isSeparatorIndex(i):
routes.append(route)
return routes
def isSeparatorIndex(self, index):
"""
Finds if curent index is a separator index
:param index: denotes the index of the location
:return: True if the given index is a separator
"""
# check if the index is larger than the number of the participating locations:
return index >= len(self) - (self.numOfVehicles - 1)
def getRouteDistance(self, indices):
"""Calculates total the distance of the path that starts at the depo location and goes through
the cities described by the given indices
:param indices: a list of ordered city indices describing the given path.
:return: total distance of the path described by the given indices
"""
if not indices:
return 0
# find the distance between the depo location and the city:
distance = self.tsp.distances[self.depotIndex][indices[0]]
# add the distance between the last city and the depot location:
distance += self.tsp.distances[indices[-1]][self.depotIndex]
# add the distances between the cities along the route:
for i in range(len(indices) - 1):
distance += self.tsp.distances[indices[i]][indices[i + 1]]
return distance
def getTotalDistance(self, indices):
"""Calculates the combined distance of the various paths described by the given indices
:param indices: a list of ordered city indices and separator indices describing one or more paths.
:return: combined distance of the various paths described by the given indices
"""
totalDistance = 0
for route in self.getRoutes(indices):
routeDistance = self.getRouteDistance(route)
#print("- route distance = ", routeDistance)
totalDistance += routeDistance
return totalDistance
def getMaxDistance(self, indices):
"""Calculates the max distance among the distances of the various paths described by the given indices
:param indices: a list of ordered city indices and separator indices describing one or more paths.
:return: max distance among the distances of the various paths described by the given indices
"""
maxDistance = 0
for route in self.getRoutes(indices):
routeDistance = self.getRouteDistance(route)
#print("- route distance = ", routeDistance)
maxDistance = max(routeDistance, maxDistance)
return maxDistance
def getAvgDistance(self, indices):
"""Calculates the average distance among the distances of the various paths described by the given indices
Does not consider empty paths
:param indices: a list of ordered city indices and separator indices describing one or more paths.
:return: max distance among the distances of the various paths described by the given indices
"""
routes = self.getRoutes(indices)
totalDistance = 0
counter = 0
for route in routes:
if route: # consider only routes that are not empty
routeDistance = self.getRouteDistance(route)
# print("- route distance = ", routeDistance)
totalDistance += routeDistance
counter += 1
return totalDistance/counter
def plotData(self, indices):
"""breaks the list of indices into separate routes and plot each route in a different color
:param indices: A list of ordered indices describing the combined routes
:return: the resulting plot
"""
# plot th ecities of the underlying TSP:
plt.scatter(*zip(*self.tsp.locations), marker='.', color='red')
# mark the depot location with a large 'X':
d = self.tsp.locations[self.depotIndex]
plt.plot(d[0], d[1], marker='x', markersize=10, color='green')
# break the indices to separate routes and plot each route in a different color:
routes = self.getRoutes(indices)
color = iter(plt.cm.rainbow(np.linspace(0, 1, self.numOfVehicles)))
for route in routes:
route = [self.depotIndex] + route + [self.depotIndex]
stops = [self.tsp.locations[i] for i in route]
plt.plot(*zip(*stops), linestyle='-', color=next(color))
return plt
import random
# create a problem instance:
vrp = VehicleRoutingProblem("bayg29", 3, 12)
# generate random solution and evaluate it:
randomSolution = random.sample(range(len(vrp)), len(vrp))
print("random solution = ", randomSolution)
print("route breakdown = ", vrp.getRoutes(randomSolution))
print("max distance = ", vrp.getMaxDistance(randomSolution))
# plot the solution:
plot = vrp.plotData(randomSolution)
plot.show()
random solution = [19, 6, 10, 22, 11, 21, 23, 25, 17, 4, 9, 15, 12, 7, 13, 30, 28, 5, 1, 3, 24, 14, 29, 8, 16, 18, 20, 26, 0, 2, 27]
route breakdown = [[19, 6, 10, 22, 11, 21, 23, 25, 17, 4, 9, 15, 7, 13], [28, 5, 1, 3, 24, 14], [8, 16, 18, 20, 26, 0, 2, 27]]
max distance = 15537.391
1.5.2. Implemente a Genetic Algorithm for VRP#
Using DEAP framework implement a Genetic Algorithm for VRP.
set the random seed:
RANDOM_SEED = 42
random.seed(RANDOM_SEED)
create the desired vehicle routing problem using a traveling salesman problem instance:
TSP_NAME = “bayg29”
NUM_OF_VEHICLES = 3
DEPOT_LOCATION = 12
Genetic Algorithm constants:
POPULATION_SIZE = 500
P_CROSSOVER = 0.9 # probability for crossover
P_MUTATION = 0.2 # probability for mutating an individual
MAX_GENERATIONS = 1000
HALL_OF_FAME_SIZE = 30
Toolbox Setttings
Fitness Min with base weight of -1.[1]
Register Individual [2] using array of integers. That uses
fitnessMinas the fitness function.Register an operator
randomOrderthat generates a random shuffle of indices used to internally represent the VRPRegister an operator
evaluatethat calculates the total distance of the VRP solutionIndividual Creator operator named
individualCreatorthat: [3]Takes as container the individual class
uses
randomOrderto generate the individual
Population Creator operator named
populationCreatorthat: [4]Takes as container the list class
Uses
individualCreatorto generate the population
toolbox Genetic Algorithm Settings
use vrp.getMaxDistance(individual) to calculate the fitness of the individual [5]
Use Tournament selection of tournament size 2. [6]
mutateusing strategymutShuffleIndexesthat shuffles the indexes of the individual ussing indenpendt probability for each attribute to be exchaged as the inverse of the number of attributes.mateusing strategy: cxUniformPartiallyMatched[7] that uses indenpendt probability for each attribute to be exchaged as the inverse of the number of attributes * 2.Which is similar to a combination of the Uniform [8] and Partially Matched [9] crossover operators.
1.5.2.1. Base Code#
from deap import tools
from deap import algorithms
def eaSimpleWithElitism(population, toolbox, cxpb, mutpb, ngen, stats=None,
halloffame=None, verbose=__debug__):
"""This algorithm is similar to DEAP eaSimple() algorithm, with the modification that
halloffame is used to implement an elitism mechanism. The individuals contained in the
halloffame are directly injected into the next generation and are not subject to the
genetic operators of selection, crossover and mutation.
"""
logbook = tools.Logbook()
logbook.header = ['gen', 'nevals'] + (stats.fields if stats else [])
# Evaluate the individuals with an invalid fitness
invalid_ind = [ind for ind in population if not ind.fitness.valid]
fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
ind.fitness.values = fit
if halloffame is None:
raise ValueError("halloffame parameter must not be empty!")
halloffame.update(population)
hof_size = len(halloffame.items) if halloffame.items else 0
record = stats.compile(population) if stats else {}
logbook.record(gen=0, nevals=len(invalid_ind), **record)
if verbose:
print(logbook.stream)
# Begin the generational process
for gen in range(1, ngen + 1):
# Select the next generation individuals
offspring = toolbox.select(population, len(population) - hof_size)
# Vary the pool of individuals
offspring = algorithms.varAnd(offspring, toolbox, cxpb, mutpb)
# Evaluate the individuals with an invalid fitness
invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
ind.fitness.values = fit
# add the best back to population:
offspring.extend(halloffame.items)
# Update the hall of fame with the generated individuals
halloffame.update(offspring)
# Replace the current population by the offspring
population[:] = offspring
# Append the current generation statistics to the logbook
record = stats.compile(population) if stats else {}
logbook.record(gen=gen, nevals=len(invalid_ind), **record)
if verbose:
print(logbook.stream)
return population, logbook
from deap import base
from deap import creator
from deap import tools
import random
import array
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
# set the random seed:
RANDOM_SEED = 42
random.seed(RANDOM_SEED)
# create the desired vehicle routing problem using a traveling salesman problem instance:
TSP_NAME = "bayg29"
NUM_OF_VEHICLES = 3
DEPOT_LOCATION = 12
vrp = VehicleRoutingProblem(TSP_NAME, NUM_OF_VEHICLES, DEPOT_LOCATION)
# Genetic Algorithm constants:
POPULATION_SIZE = 500
P_CROSSOVER = 0.9 # probability for crossover
P_MUTATION = 0.2 # probability for mutating an individual
MAX_GENERATIONS = 1000
HALL_OF_FAME_SIZE = 30
1.5.2.2. Solution#
toolbox = base.Toolbox()
# define a single objective, minimizing fitness strategy:
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
# create the Individual class based on list of integers:
creator.create("Individual", array.array, typecode='i', fitness=creator.FitnessMin)
# create an operator that generates randomly shuffled indices:
toolbox.register("randomOrder", random.sample, range(len(vrp)), len(vrp))
# create the individual creation operator to fill up an Individual instance with shuffled indices:
toolbox.register("individualCreator", tools.initIterate, creator.Individual, toolbox.randomOrder)
# create the population creation operator to generate a list of individuals:
toolbox.register("populationCreator", tools.initRepeat, list, toolbox.individualCreator)
# fitness calculation - compute the max distance that the vehicles covered
# for the given list of cities represented by indices:
def vrpDistance(individual):
return vrp.getMaxDistance(individual), # return a tuple
toolbox.register("evaluate", vrpDistance)
# Genetic operators:
toolbox.register("select", tools.selTournament, tournsize=2)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=1.0/len(vrp))
toolbox.register("mate", tools.cxUniformPartialyMatched, indpb=2.0/len(vrp))
# create initial population (generation 0):
population = toolbox.populationCreator(n=POPULATION_SIZE)
# prepare the statistics object:
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("min", np.min)
stats.register("avg", np.mean)
# define the hall-of-fame object:
hof = tools.HallOfFame(HALL_OF_FAME_SIZE)
# perform the Genetic Algorithm flow with hof feature added:
population, logbook = eaSimpleWithElitism(population, toolbox, cxpb=P_CROSSOVER, mutpb=P_MUTATION,
ngen=MAX_GENERATIONS, stats=stats, halloffame=hof, verbose=True)
# print best individual info:
best = hof.items[0]
print("-- Best Ever Individual = ", best)
print("-- Best Ever Fitness = ", best.fitness.values[0])
print("best ever fitness found at =", logbook.select("gen")[np.argmin(logbook.select("min"))])
print("-- Route Breakdown = ", vrp.getRoutes(best))
print("-- total distance = ", vrp.getTotalDistance(best))
print("-- max distance = ", vrp.getMaxDistance(best))
# plot best solution:
plt.figure(1)
vrp.plotData(best)
# plot statistics:
minFitnessValues, meanFitnessValues = logbook.select("min", "avg")
plt.figure(2)
sns.set_style("whitegrid")
plt.plot(minFitnessValues, color='red')
plt.plot(meanFitnessValues, color='green')
plt.xlabel('Generation')
plt.ylabel('Min / Average Fitness')
plt.title('Min and Average fitness over Generations')
# show both plots:
plt.show()
gen nevals min avg
0 500 8732.15 16903.6
1 437 8732.15 14680.1
2 437 8445.67 13151.6
3 429 7249.19 12458.5
4 447 7249.19 11984.6
5 417 7249.19 11329.2
6 426 7249.19 11156
7 437 7249.19 10676.3
8 421 7249.19 10421.8
9 446 7249.19 9873.39
10 424 7059.04 9647.56
11 421 6409.66 9133.03
12 447 6409.66 9152.62
13 432 6409.66 9017.36
14 437 6409.66 9073.68
15 420 6409.66 8825.44
16 427 6347.89 8674.57
17 433 6347.89 8622.92
18 435 6217.87 8609.6
19 436 6217.87 8573.16
20 436 6217.87 8592.75
21 434 6217.87 8328.55
22 434 6112.11 8209.46
23 430 6093.48 7891
24 432 5995.94 7543.89
25 439 5866.95 7190.49
26 420 5837.97 6951.21
27 433 5837.97 6696.05
28 449 5598.72 6593.52
29 424 5598.72 6449.88
30 433 5598.72 6412.2
31 431 5598.72 6246.35
32 434 5598.72 6259.06
33 425 5598.72 6180.36
34 428 5431.48 6111.86
35 429 5431.48 6096.18
36 430 5404.87 6162.62
37 412 5404.87 6039.49
38 442 5404.87 5998.8
39 430 5312.18 5926.3
40 432 5312.18 5872.72
41 434 5312.18 5975.1
42 439 5312.18 5996.42
43 428 5312.18 5937.5
44 432 5246.8 5964.55
45 434 5246.8 5881.08
46 426 5246.8 5778.79
47 435 5246.8 5784.27
48 436 5148.37 5740.14
49 424 5148.37 5638.72
50 428 5148.37 5730.06
51 424 5069.45 5634.26
52 417 5069.45 5626.17
53 433 5067.78 5570.83
54 435 5067.78 5585.94
55 435 5017.24 5595.59
56 442 5017.24 5556.52
57 437 5017.24 5544.15
58 424 5017.24 5578.6
59 430 4960.22 5506.9
60 423 4960.22 5420.8
61 428 4921.73 5435.54
62 437 4921.73 5354.55
63 432 4921.73 5357.3
64 420 4921.73 5377.46
65 441 4921.73 5333.5
66 421 4921.73 5293.9
67 430 4921.73 5330.3
68 437 4907.42 5231.74
69 429 4907.42 5136.18
70 431 4907.42 5270.3
71 427 4907.42 5237.64
72 425 4894.1 5270
73 422 4894.1 5257.84
74 437 4894.1 5231.29
75 433 4894.1 5224.02
76 441 4894.1 5207.8
77 436 4873.15 5230.98
78 439 4839.34 5157.38
79 418 4839.34 5193.89
80 431 4839.34 5235.75
81 443 4839.34 5160.06
82 436 4839.34 5196.89
83 453 4836.35 5220.81
84 439 4836.35 5226.93
85 437 4836.35 5222.21
86 430 4836.35 5212.78
87 435 4836.35 5271.77
88 429 4836.35 5257.82
89 441 4836.35 5127.96
90 428 4821.97 5162.02
91 441 4821.97 5127.92
92 430 4781.55 5103.41
93 432 4781.55 5112.41
94 453 4781.55 5115.98
95 435 4781.55 5144.52
96 433 4781.55 5121.73
97 428 4781.55 5060.48
98 423 4781.55 5183.87
99 431 4778.13 5088.69
100 435 4773.17 5030.75
101 433 4769.83 5053.51
102 430 4769.83 4998.64
103 442 4769.83 5036.2
104 438 4769.83 5129.39
105 432 4769.83 5062.86
106 424 4769.83 5061.04
107 436 4769.83 5033.83
108 407 4769.83 5124.14
109 442 4769.83 5060.93
110 434 4769.83 5089.93
111 446 4689.67 5122.26
112 434 4688.69 5051.02
113 428 4688.69 5090.36
114 431 4688.69 5089.28
115 442 4687.55 5047.71
116 437 4687.55 4976.47
117 429 4687.55 5098.15
118 419 4687.55 5024.47
119 437 4687.55 5054.89
120 433 4687.55 4971.56
121 434 4687.55 4914.45
122 429 4687.55 4980.6
123 426 4687.55 4997.63
124 448 4687.55 5015.91
125 431 4687.55 4955.74
126 419 4687.55 4941.03
127 437 4687.55 4996.69
128 421 4687.55 4955.8
129 427 4687.55 4927.69
130 422 4680.73 4942.11
131 410 4680.73 5015.56
132 448 4680.73 4931
133 433 4540.27 5024.64
134 426 4540.27 4972.65
135 444 4540.27 4873.06
136 432 4540.27 4940.42
137 431 4530.27 4982.42
138 420 4530.27 4935.06
139 431 4419.96 4979.15
140 428 4419.96 4998.03
141 437 4419.96 4916.44
142 427 4419.96 4998.03
143 429 4419.96 4925.9
144 426 4419.96 4869.06
145 426 4419.96 4799.79
146 432 4419.96 4798.57
147 429 4419.96 4794.23
148 436 4419.96 4778.52
149 428 4419.96 4701.62
150 434 4419.96 4691.1
151 431 4419.96 4703.91
152 433 4419.96 4649.01
153 446 4419.96 4718.66
154 432 4419.96 4655.71
155 440 4419.96 4766.03
156 432 4419.96 4699.99
157 421 4419.96 4648.44
158 430 4419.96 4698.29
159 437 4419.96 4706.05
160 442 4419.96 4832.77
161 433 4419.96 4728.37
162 431 4419.96 4663.35
163 424 4419.96 4721.71
164 428 4419.96 4745.47
165 432 4419.96 4748.42
166 431 4419.96 4668.2
167 443 4419.96 4735.73
168 446 4419.96 4662.54
169 430 4419.96 4699.03
170 410 4419.96 4755.73
171 444 4419.96 4741.26
172 433 4419.96 4686.86
173 441 4419.96 4664.86
174 426 4419.96 4798.1
175 437 4419.96 4669.2
176 435 4419.96 4704.93
177 432 4419.96 4657.6
178 432 4419.96 4700.82
179 449 4404.26 4686.76
180 428 4404.26 4606.3
181 436 4404.26 4740.56
182 432 4404.26 4649.53
183 428 4404.26 4675.23
184 432 4404.26 4702.35
185 436 4404.26 4659
186 433 4404.26 4656.07
187 432 4404.26 4684.21
188 439 4404.26 4737.96
189 437 4404.26 4683.84
190 439 4404.26 4675.15
191 416 4404.26 4642.43
192 435 4404.26 4662.28
193 432 4404.26 4751.05
194 423 4404.26 4582.23
195 435 4404.26 4669.5
196 442 4404.26 4714.43
197 436 4404.26 4708.36
198 437 4404.26 4636
199 444 4324.16 4621.45
200 431 4324.16 4638.81
201 434 4324.16 4753.43
202 420 4324.16 4647.6
203 428 4324.16 4687.13
204 437 4324.16 4732.72
205 423 4287 4701.01
206 431 4287 4713.02
207 409 4286.83 4640.56
208 428 4286.83 4683.24
209 428 4253.15 4606.37
210 431 4253.15 4617.59
211 447 4253.15 4662.82
212 435 4252.2 4629.34
213 416 4252.2 4531.76
214 427 4246.38 4592.55
215 437 4244.63 4584.77
216 431 4244.63 4637.48
217 430 4244.63 4556.44
218 441 4244.63 4515.41
219 444 4244.63 4590.87
220 434 4244.63 4540.89
221 450 4244.63 4575.08
222 436 4244.63 4532.9
223 431 4244.63 4518.15
224 430 4244.63 4555.58
225 440 4231.3 4567.98
226 435 4231.3 4619.83
227 430 4231.3 4576.96
228 428 4231.3 4486.18
229 432 4231.3 4473.65
230 451 4231.3 4513.04
231 428 4120.02 4559.71
232 437 4120.02 4491.54
233 429 4118.27 4554.34
234 438 4118.27 4560.06
235 429 4118.27 4511.09
236 422 4118.27 4497.9
237 431 4118.27 4441.6
238 423 4118.27 4547.26
239 450 4118.27 4562.07
240 426 4118.27 4415.31
241 425 4118.27 4436.55
242 442 4118.27 4482.2
243 425 4118.27 4373.57
244 425 4118.27 4439.64
245 428 4118.27 4463.81
246 435 4118.27 4460.72
247 421 4118.27 4448.43
248 421 4118.27 4360.16
249 427 4118.27 4371.55
250 434 4118.27 4424.26
251 431 4118.27 4448.85
252 441 4118.27 4466.24
253 432 4118.27 4326.25
254 427 4118.27 4415.48
255 433 4118.27 4422.4
256 425 4118.27 4431.48
257 413 4118.27 4372.32
258 427 4118.27 4419.16
259 428 4118.27 4458.48
260 418 4118.27 4431.49
261 438 4118.27 4531.67
262 431 4118.27 4409.56
263 443 4118.27 4379.58
264 431 4118.27 4496.18
265 425 4118.27 4453.37
266 435 4118.27 4364.46
267 434 4118.27 4420.35
268 433 4118.27 4432.86
269 420 4118.27 4325.52
270 432 4118.27 4356.97
271 431 4118.27 4481.23
272 437 4118.27 4459.87
273 437 4118.27 4418.47
274 443 4118.27 4370.33
275 434 4118.27 4478.1
276 427 4118.27 4402.62
277 433 4118.27 4401.2
278 432 4118.27 4415.06
279 433 4118.27 4358.73
280 422 4118.27 4375.62
281 422 4118.27 4338.48
282 430 4118.27 4416.84
283 434 4118.27 4389.33
284 427 4118.27 4405.02
285 425 4118.27 4434.52
286 450 4118.27 4432.12
287 420 4118.27 4471.02
288 434 4118.27 4459.57
289 428 4118.27 4384.53
290 427 4118.27 4406.27
291 430 4118.27 4426.23
292 430 4118.27 4426.19
293 432 4118.27 4531.04
294 427 4118.27 4434.46
295 440 4118.27 4461.02
296 426 4118.27 4556.38
297 427 4118.27 4484.51
298 426 4117.34 4496.69
299 441 4117.34 4400.59
300 442 4117.34 4402.04
301 428 4117.34 4499.38
302 430 4101.64 4486.16
303 429 4101.64 4479.85
304 438 4101.64 4477.46
305 425 4101.64 4444.37
306 423 4086.17 4392.85
307 429 4086.17 4459.34
308 442 4064.32 4525.08
309 424 4064.32 4436.95
310 422 4064.32 4335.93
311 435 4064.32 4372.11
312 431 4064.32 4439.18
313 444 4064.32 4370.79
314 439 4064.32 4316.58
315 421 4064.32 4347.23
316 425 4064.32 4370.26
317 436 4064.32 4382.06
318 432 4064.32 4360.28
319 447 4064.32 4367.35
320 440 4064.32 4357.46
321 428 4064.32 4349.61
322 444 4064.32 4246.86
323 433 4064.32 4253.11
324 440 4064.32 4339.42
325 424 4064.32 4351.69
326 435 4064.32 4347.57
327 436 4064.32 4394.79
328 430 4064.32 4346.19
329 422 4064.32 4412.24
330 437 4064.32 4413.85
331 431 4064.32 4296.36
332 442 4064.32 4352.91
333 429 4064.32 4364.63
334 432 4064.32 4458.57
335 446 4064.32 4387.43
336 447 4064.32 4381.45
337 417 4064.32 4373.46
338 416 4064.32 4356.43
339 423 4064.32 4399.81
340 424 4064.32 4325.73
341 428 4064.32 4351.61
342 437 4064.32 4292.89
343 425 4064.32 4371.43
344 432 4064.32 4411.86
345 434 4064.32 4242.47
346 425 4064.32 4318.46
347 435 4064.32 4332.22
348 427 4064.32 4348.1
349 426 4064.32 4346.34
350 448 4064.32 4322.13
351 444 4064.32 4407.04
352 451 4064.32 4294.01
353 439 4064.32 4278.14
354 440 4064.32 4351.43
355 434 4064.32 4314.43
356 442 4064.32 4324.41
357 437 4064.32 4328.27
358 429 4064.32 4302.51
359 428 4064.32 4369.17
360 431 4064.32 4305.06
361 438 4064.32 4349.37
362 435 4064.32 4317.1
363 417 4064.32 4381.23
364 422 4064.32 4354.89
365 433 4064.32 4446.77
366 434 4064.32 4366.21
367 443 4064.32 4382.53
368 419 4064.32 4368.88
369 412 4064.32 4337.5
370 446 4064.32 4283.16
371 441 4064.32 4301.51
372 437 4064.32 4373.96
373 427 4064.32 4407.3
374 436 4064.32 4391.84
375 433 4064.32 4350.29
376 436 4064.32 4375.39
377 427 4064.32 4277.74
378 423 4064.32 4401.23
379 420 4064.32 4365.26
380 435 4064.32 4323.88
381 443 4064.32 4326.45
382 439 4064.32 4342.03
383 436 4064.32 4404.53
384 421 4064.32 4362.99
385 449 4064.32 4359.2
386 441 4064.32 4349.84
387 410 4064.32 4380.07
388 437 4064.32 4320.85
389 429 4064.32 4299.36
390 444 4064.32 4399.21
391 440 4064.32 4309.97
392 435 4064.32 4278.02
393 431 4064.32 4290.31
394 430 4064.32 4272.13
395 430 4064.32 4358.24
396 434 4064.32 4374.28
397 443 4064.32 4346.62
398 438 4064.32 4365.1
399 440 4064.32 4331.65
400 427 4064.32 4294.97
401 429 4064.32 4344.93
402 425 4064.32 4287.5
403 425 4064.32 4366.42
404 436 4064.32 4296.06
405 429 4064.32 4319.62
406 433 4064.32 4390.97
407 426 4064.32 4332.95
408 434 4064.32 4372.38
409 420 4064.32 4345.68
410 448 4064.32 4322.35
411 440 4064.32 4296.48
412 434 4064.32 4361.8
413 447 4064.32 4333.38
414 433 4064.32 4340.33
415 436 4064.32 4350.92
416 436 4064.32 4369.68
417 429 4064.32 4348.68
418 442 4064.32 4399.21
419 433 4064.32 4343.32
420 424 4064.32 4381.85
421 431 4064.32 4398.82
422 430 4064.32 4395.96
423 440 4064.32 4342.77
424 429 4064.32 4383.14
425 435 4064.32 4375.26
426 433 4064.32 4370.9
427 427 4064.32 4381.4
428 422 4064.32 4294.05
429 438 4064.32 4276.27
430 422 4064.32 4386.93
431 424 4064.32 4361.57
432 434 4064.32 4376.97
433 439 4064.32 4332.98
434 434 4064.32 4405.28
435 446 4064.32 4282.5
436 434 4064.32 4327.24
437 423 4064.32 4286.97
438 419 4064.32 4284.69
439 430 4064.32 4319.12
440 426 4064.32 4324.33
441 428 4064.32 4318.46
442 428 4064.32 4359.63
443 430 4064.32 4340.54
444 442 4064.32 4340.92
445 440 4064.32 4348.78
446 440 4064.32 4352.72
447 441 4064.32 4384.41
448 419 4064.32 4377.6
449 444 4064.32 4352.02
450 440 4064.32 4335.81
451 424 4064.32 4381.29
452 426 4064.32 4376.8
453 443 4064.32 4447.04
454 435 4064.32 4386.53
455 432 4064.32 4362.17
456 435 4064.32 4349.7
457 435 4064.32 4318.82
458 433 4064.32 4377.94
459 432 4064.32 4305.95
460 441 4064.32 4293.62
461 429 4064.32 4385.68
462 428 4064.32 4326.49
463 446 4064.32 4369
464 425 4064.32 4373.32
465 428 4064.32 4318.15
466 430 4064.32 4331.17
467 431 4064.32 4344.43
468 432 4064.32 4380.37
469 429 4064.32 4321.6
470 430 4064.32 4323.14
471 437 4064.32 4320.25
472 422 4064.32 4330.11
473 430 4064.32 4368.16
474 428 4064.32 4362.64
475 428 4064.32 4336.04
476 440 4064.32 4357.39
477 446 4064.32 4357.43
478 436 4064.32 4298.4
479 437 4064.32 4389.34
480 436 4064.32 4398.17
481 440 4064.32 4363.78
482 442 4064.32 4415.75
483 423 4064.32 4304.4
484 431 4064.32 4336.65
485 438 4064.32 4364.41
486 426 4064.32 4395.09
487 426 4064.32 4434.3
488 430 4064.32 4336.17
489 432 4064.32 4294.61
490 410 4064.32 4346.38
491 431 4064.32 4291.92
492 429 4064.32 4389.26
493 431 4064.32 4334.93
494 433 4064.32 4390.33
495 442 4064.32 4394.24
496 428 4064.32 4354.13
497 441 4064.32 4400.02
498 423 4064.32 4343.2
499 434 4064.32 4333.52
500 431 4064.32 4413.96
501 423 4064.32 4324.92
502 420 4064.32 4324.6
503 428 4064.32 4396.38
504 435 4064.32 4443.11
505 436 4064.32 4391.98
506 428 4064.32 4390.55
507 429 4064.32 4360.91
508 436 4064.32 4387.01
509 435 4064.32 4356.8
510 426 4064.32 4350.9
511 442 4064.32 4359.15
512 431 4064.32 4356.83
513 426 4064.32 4327.63
514 429 4064.32 4309.07
515 438 4064.32 4443.82
516 414 4064.32 4408.64
517 429 4064.32 4356.37
518 432 4064.32 4270.89
519 423 4064.32 4359.9
520 431 4064.32 4404.86
521 429 4064.32 4281.79
522 440 4064.32 4360.83
523 439 4064.32 4363.68
524 428 4064.32 4283.58
525 429 4064.32 4347.94
526 426 4064.32 4347.24
527 435 4064.32 4347.66
528 428 4064.32 4376.21
529 430 4064.32 4404.8
530 432 4064.32 4341.69
531 431 4064.32 4382.37
532 423 4064.32 4354.6
533 436 4064.32 4442
534 408 4064.32 4351.94
535 430 4064.32 4338.98
536 436 4064.32 4363.9
537 444 4064.32 4394.05
538 439 4064.32 4359.35
539 415 4064.32 4312.1
540 433 4064.32 4355.35
541 419 4064.32 4280.83
542 420 4064.32 4327.19
543 442 4064.32 4383.47
544 432 4064.32 4394.05
545 433 4064.32 4327.62
546 421 4064.32 4318.7
547 421 4064.32 4419.55
548 445 4064.32 4329.03
549 428 4064.32 4382.08
550 434 4064.32 4440.71
551 435 4064.32 4354.56
552 428 3992.41 4325.4
553 426 3992.41 4293.77
554 427 3992.41 4305.43
555 424 3992.41 4400.39
556 439 3992.41 4349.78
557 425 3992.41 4380.94
558 427 3992.41 4409.59
559 426 3992.41 4388.54
560 437 3992.41 4376.08
561 437 3992.41 4394.08
562 439 3992.41 4451.57
563 414 3992.41 4367
564 446 3992.41 4445.26
565 442 3992.41 4348.17
566 429 3992.41 4316.14
567 422 3992.41 4324.26
568 419 3972.96 4293.03
569 451 3972.96 4311.15
570 428 3972.96 4301.02
571 433 3972.96 4221.4
572 440 3972.96 4361.16
573 437 3972.96 4267.35
574 440 3972.96 4277.69
575 436 3972.96 4243.95
576 426 3972.96 4311.25
577 437 3972.96 4265.27
578 430 3972.96 4204.48
579 431 3972.96 4233.46
580 439 3972.96 4224.16
581 420 3972.96 4306.05
582 429 3972.96 4307.13
583 447 3972.96 4371.75
584 438 3972.96 4225.93
585 430 3972.96 4279.86
586 434 3972.96 4300.81
587 439 3972.96 4301.16
588 424 3972.96 4284.34
589 427 3972.96 4218.8
590 433 3972.03 4212.88
591 439 3972.03 4206.37
592 431 3972.03 4313.06
593 432 3972.03 4262.58
594 444 3972.03 4240.96
595 435 3972.03 4256.95
596 425 3972.03 4298.08
597 425 3972.03 4313.92
598 423 3972.03 4332.4
599 427 3972.03 4291.24
600 439 3972.03 4320.28
601 423 3972.03 4299.07
602 421 3972.03 4276.42
603 426 3972.03 4230.18
604 430 3972.03 4293.6
605 422 3972.03 4287.68
606 424 3972.03 4258.53
607 420 3972.03 4252.89
608 441 3972.03 4259.36
609 423 3943.72 4346.11
610 435 3943.72 4286.9
611 440 3943.72 4326.86
612 429 3943.72 4284.64
613 436 3943.72 4311.26
614 430 3943.72 4202.8
615 418 3943.72 4284.01
616 422 3943.72 4276.8
617 435 3943.72 4283.57
618 422 3943.72 4219.7
619 426 3943.72 4244.11
620 428 3943.72 4223.04
621 438 3943.72 4304.38
622 427 3943.72 4372.07
623 431 3943.72 4302.85
624 439 3943.72 4300.35
625 425 3943.72 4228.01
626 436 3943.72 4234.19
627 438 3943.72 4213.64
628 439 3943.72 4293.32
629 432 3943.72 4278.08
630 437 3943.72 4329.17
631 435 3943.72 4299.29
632 429 3943.72 4239.81
633 431 3943.72 4201.53
634 433 3943.72 4193.62
635 428 3943.72 4205.74
636 445 3943.72 4230.34
637 432 3943.72 4209.25
638 428 3943.72 4317.6
639 438 3943.72 4209.87
640 436 3943.72 4235.79
641 427 3943.72 4302.45
642 432 3943.72 4273.7
643 441 3943.72 4229.9
644 429 3943.72 4209.09
645 437 3943.72 4242.9
646 427 3943.72 4164.31
647 434 3943.72 4226.3
648 430 3943.72 4258.07
649 433 3943.72 4248.88
650 425 3943.72 4239.02
651 442 3943.72 4307.02
652 423 3943.72 4209.54
653 437 3943.72 4270.5
654 442 3943.72 4265.76
655 449 3943.72 4298.9
656 434 3943.72 4215.38
657 431 3943.72 4298.59
658 441 3943.72 4298.98
659 433 3943.72 4216.12
660 439 3943.72 4208.24
661 441 3943.72 4280.17
662 435 3943.72 4336.18
663 434 3943.72 4316.63
664 437 3943.72 4284.06
665 427 3943.72 4226.8
666 431 3943.72 4216.95
667 438 3943.72 4224.23
668 450 3943.72 4175.68
669 416 3943.72 4201.51
670 431 3943.72 4278.52
671 435 3943.72 4242.33
672 438 3943.72 4268.18
673 424 3943.72 4204.37
674 443 3943.72 4243.03
675 421 3943.72 4247.56
676 441 3943.72 4260.36
677 432 3943.72 4222.24
678 431 3943.72 4114.39
679 429 3943.72 4208.29
680 433 3943.72 4146.85
681 440 3943.72 4266.54
682 422 3943.72 4232.85
683 436 3943.72 4278.93
684 429 3943.72 4264.18
685 434 3943.72 4216.55
686 433 3943.72 4246.1
687 435 3943.72 4242.27
688 447 3943.72 4242.09
689 446 3943.72 4271.86
690 429 3943.72 4224.87
691 441 3943.72 4180.82
692 436 3943.72 4202.81
693 424 3943.72 4258.98
694 428 3943.72 4136.99
695 428 3943.72 4270.59
696 427 3943.72 4242.13
697 422 3943.72 4282.16
698 442 3943.72 4205.65
699 423 3943.72 4254.74
700 447 3943.72 4168.36
701 424 3943.72 4132.18
702 418 3943.72 4267.57
703 435 3943.72 4212.44
704 437 3943.72 4351.58
705 431 3943.72 4251.19
706 413 3943.72 4220.79
707 442 3943.72 4224.95
708 437 3943.72 4282.75
709 440 3943.72 4306.21
710 433 3943.72 4280.61
711 440 3943.72 4267.83
712 444 3943.72 4219.89
713 440 3943.72 4262.06
714 425 3943.72 4276.51
715 440 3943.72 4269
716 438 3943.72 4277.86
717 447 3943.72 4286.79
718 434 3943.72 4324.77
719 430 3943.72 4236.3
720 429 3943.72 4263.45
721 424 3943.72 4324.5
722 441 3943.72 4250.7
723 431 3943.72 4224.12
724 439 3943.72 4263.71
725 435 3943.72 4282.01
726 429 3943.72 4254.02
727 423 3943.72 4272.75
728 432 3943.72 4343.81
729 439 3943.72 4212.59
730 437 3943.72 4261.76
731 436 3943.72 4196.21
732 430 3943.72 4220.32
733 432 3943.72 4176.19
734 427 3943.72 4134.2
735 426 3943.72 4265.84
736 438 3943.72 4200.03
737 430 3943.72 4286.23
738 439 3943.72 4251.21
739 437 3943.72 4175.7
740 432 3943.72 4211.73
741 441 3943.72 4237.61
742 431 3943.72 4248.62
743 428 3943.72 4200.3
744 436 3943.72 4267.98
745 443 3943.72 4291.7
746 428 3943.72 4316.45
747 422 3943.72 4253.5
748 418 3943.72 4205.88
749 426 3943.72 4263.96
750 435 3943.72 4191.7
751 428 3943.72 4333.53
752 446 3943.72 4236.35
753 447 3943.72 4322.15
754 431 3943.72 4282.08
755 438 3943.72 4261.27
756 427 3943.72 4231.75
757 446 3943.72 4271.6
758 427 3943.72 4191.13
759 432 3943.72 4195.51
760 436 3943.72 4257.32
761 423 3943.72 4199.39
762 429 3943.72 4159.22
763 420 3943.72 4215.8
764 435 3943.72 4208.72
765 436 3943.72 4213.46
766 420 3943.72 4324.91
767 433 3943.72 4216.65
768 431 3943.72 4259.25
769 423 3943.72 4219.03
770 449 3943.72 4266.8
771 441 3943.72 4277.32
772 430 3943.72 4313.14
773 434 3943.72 4228.43
774 431 3943.72 4215.88
775 436 3943.72 4247.01
776 425 3943.72 4230.16
777 443 3943.72 4224.57
778 439 3943.72 4321.28
779 430 3943.72 4189.65
780 450 3943.72 4183.9
781 430 3943.72 4292.79
782 452 3943.72 4175.57
783 440 3943.72 4207.13
784 427 3943.72 4210.56
785 436 3943.72 4208.53
786 430 3943.72 4270.26
787 433 3943.72 4289.8
788 424 3943.72 4228.87
789 433 3943.72 4182.21
790 438 3943.72 4191
791 435 3943.72 4231.69
792 429 3943.72 4297.33
793 454 3943.72 4163.35
794 422 3943.72 4273.94
795 438 3943.72 4360.91
796 428 3943.72 4211.96
797 427 3943.72 4219.65
798 435 3943.72 4194.46
799 430 3943.72 4248.02
800 428 3943.72 4273.65
801 433 3943.72 4274.57
802 435 3943.72 4228.57
803 425 3943.72 4124.43
804 440 3943.72 4152.31
805 431 3943.72 4228.25
806 416 3943.72 4161.09
807 429 3943.72 4263.26
808 439 3943.72 4239.34
809 438 3943.72 4218.56
810 434 3943.72 4214.69
811 435 3943.72 4192.95
812 438 3943.72 4244.87
813 431 3943.72 4213.47
814 429 3943.72 4276.01
815 442 3943.72 4166.08
816 433 3943.72 4204.49
817 436 3943.72 4221.93
818 450 3943.72 4230.5
819 418 3943.72 4237.76
820 449 3943.72 4231.91
821 425 3943.72 4273.43
822 425 3943.72 4186.9
823 441 3943.72 4203.92
824 433 3943.72 4221.54
825 429 3943.72 4199.81
826 431 3943.72 4173.76
827 431 3943.72 4188.76
828 449 3943.72 4173.39
829 430 3943.72 4175.98
830 431 3943.72 4145.57
831 442 3943.72 4245.28
832 428 3943.72 4214.8
833 437 3943.72 4220.59
834 420 3943.72 4161.84
835 429 3943.72 4218.22
836 426 3943.72 4177.12
837 426 3943.72 4293.85
838 429 3943.72 4200.01
839 427 3912.12 4200.59
840 436 3912.12 4256.17
841 419 3912.12 4301.19
842 427 3912.12 4317.75
843 431 3912.12 4164.42
844 422 3912.12 4136.57
845 439 3912.12 4263.03
846 444 3912.12 4246.22
847 440 3912.12 4242.79
848 436 3912.12 4250.08
849 434 3890.55 4256.7
850 435 3890.55 4199.39
851 429 3890.55 4237.64
852 446 3890.55 4223.51
853 423 3890.55 4159.15
854 440 3890.55 4140.47
855 435 3890.55 4180.4
856 420 3890.55 4167.66
857 427 3890.55 4204.77
858 447 3890.55 4190.47
859 432 3890.55 4213.79
860 430 3890.55 4184.92
861 444 3890.55 4136.55
862 432 3890.55 4150.71
863 427 3890.55 4203.43
864 442 3890.55 4151.47
865 437 3890.55 4241.85
866 437 3890.55 4153.01
867 430 3890.55 4216.53
868 419 3890.55 4282.27
869 439 3890.55 4205.21
870 440 3890.55 4188.88
871 434 3890.55 4129.55
872 436 3890.55 4166.06
873 436 3890.55 4202.7
874 432 3890.55 4186.62
875 443 3890.55 4203.36
876 430 3890.55 4125.26
877 432 3890.55 4199.77
878 435 3890.55 4221.51
879 440 3890.55 4245.77
880 435 3890.55 4200.41
881 436 3890.55 4261.97
882 440 3890.55 4245.75
883 435 3890.55 4176.88
884 428 3890.55 4209.98
885 439 3890.55 4167.86
886 430 3886.14 4238.44
887 428 3886.14 4247.26
888 425 3857.36 4173.35
889 432 3857.36 4106.33
890 432 3857.36 4177.14
891 431 3857.36 4154.03
892 433 3857.36 4219.53
893 429 3857.36 4133.15
894 425 3857.36 4150.06
895 433 3857.36 4199.53
896 419 3857.36 4193.73
897 434 3857.36 4124.05
898 424 3857.36 4133.93
899 437 3857.36 4132.2
900 416 3857.36 4238.39
901 431 3857.36 4121.17
902 425 3857.36 4184.47
903 446 3857.36 4180
904 438 3857.36 4239.58
905 432 3857.36 4138.29
906 434 3857.36 4110.96
907 434 3857.36 4156.09
908 427 3857.36 4135.15
909 423 3857.36 4130.28
910 429 3857.36 4137.26
911 428 3857.36 4159.18
912 435 3857.36 4125.9
913 434 3857.36 4130.68
914 437 3857.36 4142.55
915 442 3857.36 4176.42
916 432 3857.36 4161.68
917 434 3857.36 4127.69
918 432 3857.36 4264.94
919 428 3857.36 4164.41
920 417 3857.36 4237.3
921 435 3857.36 4259.91
922 421 3857.36 4240.53
923 428 3857.36 4182.08
924 438 3857.36 4123.75
925 439 3857.36 4169.93
926 428 3857.36 4196.88
927 434 3857.36 4133.28
928 446 3857.36 4142.82
929 427 3857.36 4172.54
930 429 3857.36 4221.45
931 445 3857.36 4160.95
932 429 3857.36 4205.41
933 426 3857.36 4198.3
934 441 3857.36 4122.22
935 426 3857.36 4116.99
936 430 3857.36 4088.06
937 424 3857.36 4071.19
938 427 3857.36 4121.27
939 426 3857.36 4230.8
940 436 3857.36 4152.78
941 434 3857.36 4182.56
942 442 3857.36 4135.26
943 437 3857.36 4162.45
944 438 3857.36 4211.09
945 441 3857.36 4157.37
946 435 3857.36 4189.01
947 418 3857.36 4198.6
948 435 3857.36 4163.09
949 434 3857.36 4153.49
950 430 3857.36 4137.02
951 437 3857.36 4169.32
952 432 3857.36 4186.61
953 436 3857.36 4141.21
954 431 3857.36 4107.2
955 441 3857.36 4261.95
956 434 3857.36 4165.38
957 426 3857.36 4178.18
958 430 3857.36 4170.48
959 439 3857.36 4152.26
960 446 3857.36 4201.6
961 438 3857.36 4197.6
962 438 3857.36 4159.73
963 440 3857.36 4126.43
964 422 3857.36 4142.62
965 444 3857.36 4109.51
966 439 3857.36 4127.55
967 429 3857.36 4169.34
968 436 3857.36 4198.57
969 443 3857.36 4166.65
970 432 3857.36 4054.18
971 427 3857.36 4115.53
972 423 3857.36 4162.82
973 426 3857.36 4251.55
974 438 3857.36 4108.7
975 448 3857.36 4108.29
976 438 3857.36 4140.95
977 425 3857.36 4160.81
978 434 3857.36 4181.41
979 443 3857.36 4213.74
980 427 3857.36 4184.36
981 441 3857.36 4132.69
982 420 3857.36 4096.02
983 444 3857.36 4132.34
984 446 3857.36 4193.19
985 439 3857.36 4134.83
986 443 3857.36 4223.77
987 434 3857.36 4185.27
988 424 3857.36 4179.24
989 426 3857.36 4119.15
990 443 3857.36 4142.64
991 436 3857.36 4101.94
992 429 3857.36 4148.98
993 432 3857.36 4146.12
994 432 3857.36 4127.26
995 426 3857.36 4116.32
996 419 3857.36 4172.79
997 419 3857.36 4125.39
998 430 3857.36 4072.89
999 441 3857.36 4205.53
1000 438 3857.36 4188.69
-- Best Ever Individual = Individual('i', [0, 20, 17, 16, 13, 21, 10, 14, 3, 29, 15, 23, 7, 26, 12, 22, 6, 24, 18, 9, 19, 30, 27, 11, 5, 4, 8, 25, 2, 28, 1])
-- Best Ever Fitness = 3857.36376953125
best ever fitness found at = 888
-- Route Breakdown = [[0, 20, 17, 16, 13, 21, 10, 14, 3], [15, 23, 7, 26, 22, 6, 24, 18, 9, 19], [27, 11, 5, 4, 8, 25, 2, 28, 1]]
-- total distance = 11541.875
-- max distance = 3857.3638
1.5.3. Use 4 Vehicles Instead.#
[ ] Check the previous solution, how long does it take to reach the most optimal solution?
[ ] Change the number of vehicles to 4 and run the Genetic Algorithm again.
[ ] Check now how long does it take to reach the most optimal solution?
[ ] Why do you think it took less/longer to react the most optimal solution?
from deap import base
from deap import creator
from deap import tools
import random
import array
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
# set the random seed:
RANDOM_SEED = 42
random.seed(RANDOM_SEED)
# create the desired vehicle routing problem using a traveling salesman problem instance:
TSP_NAME = "bayg29"
NUM_OF_VEHICLES = 4
DEPOT_LOCATION = 12
vrp = VehicleRoutingProblem(TSP_NAME, NUM_OF_VEHICLES, DEPOT_LOCATION)
# Genetic Algorithm constants:
POPULATION_SIZE = 500
P_CROSSOVER = 0.9 # probability for crossover
P_MUTATION = 0.2 # probability for mutating an individual
MAX_GENERATIONS = 1000
HALL_OF_FAME_SIZE = 30
toolbox = base.Toolbox()
# define a single objective, minimizing fitness strategy:
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
# create the Individual class based on list of integers:
creator.create("Individual", array.array, typecode='i', fitness=creator.FitnessMin)
# create an operator that generates randomly shuffled indices:
toolbox.register("randomOrder", random.sample, range(len(vrp)), len(vrp))
# create the individual creation operator to fill up an Individual instance with shuffled indices:
toolbox.register("individualCreator", tools.initIterate, creator.Individual, toolbox.randomOrder)
# create the population creation operator to generate a list of individuals:
toolbox.register("populationCreator", tools.initRepeat, list, toolbox.individualCreator)
# fitness calculation - compute the max distance that the vehicles covered
# for the given list of cities represented by indices:
def vrpDistance(individual):
return vrp.getMaxDistance(individual), # return a tuple
toolbox.register("evaluate", vrpDistance)
# Genetic operators:
toolbox.register("select", tools.selTournament, tournsize=2)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=1.0/len(vrp))
toolbox.register("mate", tools.cxUniformPartialyMatched, indpb=2.0/len(vrp))
# create initial population (generation 0):
population = toolbox.populationCreator(n=POPULATION_SIZE)
# prepare the statistics object:
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("min", np.min)
stats.register("avg", np.mean)
# define the hall-of-fame object:
hof = tools.HallOfFame(HALL_OF_FAME_SIZE)
# perform the Genetic Algorithm flow with hof feature added:
population, logbook = eaSimpleWithElitism(population, toolbox, cxpb=P_CROSSOVER, mutpb=P_MUTATION,
ngen=MAX_GENERATIONS, stats=stats, halloffame=hof, verbose=True)
# print best individual info:
best = hof.items[0]
print("-- Best Ever Individual = ", best)
print("-- Best Ever Fitness = ", best.fitness.values[0])
print('Best Ever Fintess Found at =', logbook.select("gen")[np.argmin(logbook.select("min"))])
print("-- Route Breakdown = ", vrp.getRoutes(best))
print("-- total distance = ", vrp.getTotalDistance(best))
print("-- max distance = ", vrp.getMaxDistance(best))
# plot best solution:
plt.figure(1)
vrp.plotData(best)
# plot statistics:
minFitnessValues, meanFitnessValues = logbook.select("min", "avg")
plt.figure(2)
sns.set_style("whitegrid")
plt.plot(minFitnessValues, color='red')
plt.plot(meanFitnessValues, color='green')
plt.xlabel('Generation')
plt.ylabel('Min / Average Fitness')
plt.title('Min and Average fitness over Generations')
# show both plots:
plt.show()
gen nevals min avg
0 500 7837.46 14242.2
1 448 7237.95 12314.5
2 438 7237.95 11137.5
3 433 6731.61 10441.4
4 431 6731.61 9968.3
5 440 6731.61 9800.87
6 431 6088.3 9610.91
7 437 6088.3 9116.61
8 442 6088.3 8956.79
9 443 5911.07 8822.75
10 442 5911.07 8911.82
11 423 5911.07 8676.48
12 433 5911.07 8471.87
13 430 5904.08 8295.78
14 427 5792.08 8154.6
15 436 5616.79 8025.53
16 440 5616.79 8116.42
17 440 5616.79 8023.71
18 436 5616.79 7836.25
19 432 5429.51 7800.96
20 432 5429.51 7695.47
21 426 5429.51 7646.61
22 434 5429.51 7529.57
23 440 5429.51 7469.3
24 430 5429.51 7541.31
25 422 5429.51 7362.24
26 422 5429.51 7221.79
27 445 5429.51 7275.91
28 443 5353.37 7261.57
29 429 5353.37 7275.52
30 437 5353.37 7134.43
31 446 5353.37 7143.44
32 436 5274.98 7056.61
33 417 5216.23 6948.34
34 435 4972.62 6846.72
35 425 4972.62 6846
36 417 4972.62 6658.23
37 430 4884.29 6199.3
38 442 4884.29 6013.63
39 429 4869.56 5874.75
40 421 4806.65 5705.16
41 443 4747.06 5639.1
42 424 4747.06 5452.27
43 434 4728.57 5441.82
44 427 4728.57 5352.84
45 434 4728.57 5286.8
46 427 4728.57 5299.68
47 447 4665.06 5147.49
48 435 4589.51 5141.27
49 430 4514.56 5061.4
50 437 4514.56 5067.27
51 442 4514.56 5026.25
52 440 4514.56 5040.37
53 442 4514.56 4898.38
54 442 4427.98 4959.87
55 426 4235.43 4966.25
56 434 4235.43 4903.22
57 430 4235.43 4798.32
58 423 4235.43 4913.38
59 431 4125.64 4821.38
60 430 4125.64 4827.48
61 426 4125.64 4768.88
62 425 4125.64 4585.83
63 423 4125.64 4632.81
64 430 4125.64 4518.82
65 439 4125.64 4517.47
66 437 3986.36 4463.31
67 433 3986.36 4413.28
68 444 3986.36 4411.81
69 428 3986.36 4393.22
70 436 3986.36 4367.04
71 434 3830.63 4339.99
72 447 3830.63 4305.35
73 443 3830.63 4285.52
74 432 3830.63 4306.49
75 440 3830.63 4295.54
76 428 3830.63 4232.62
77 429 3815.24 4164.23
78 427 3815.24 4159.25
79 446 3815.24 4188.21
80 424 3815.24 4079.14
81 434 3815.24 4119.99
82 436 3815.24 4141.41
83 441 3815.24 4116.62
84 440 3815.24 4089.08
85 426 3815.24 4192
86 438 3815.24 4056.99
87 433 3815.24 4078.08
88 435 3815.24 4077.16
89 443 3815.24 4127.73
90 428 3815.24 4146.89
91 430 3623.25 4106.83
92 415 3623.25 4137.37
93 432 3586.84 4068.11
94 414 3586.84 4096.73
95 421 3586.84 4060.25
96 427 3585.05 4078.27
97 429 3585.05 4058.69
98 445 3585.05 4048.62
99 444 3585.05 4062.99
100 431 3585.05 4026.55
101 419 3572.76 3986.68
102 431 3572.76 3971.69
103 443 3572.76 3897.26
104 427 3572.76 3877.69
105 421 3572.76 3952.78
106 424 3572.76 3932.4
107 438 3572.76 3936.35
108 428 3572.76 3917.27
109 421 3572.76 3870.07
110 423 3572.76 3881.65
111 428 3572.76 3857.75
112 418 3572.76 3914.11
113 435 3572.76 3938.73
114 422 3572.76 3782.22
115 442 3572.76 3832.87
116 443 3572.76 3848.99
117 428 3572.76 3927.79
118 438 3572.76 3827.44
119 440 3572.76 3892.37
120 431 3572.76 3830.94
121 429 3572.76 3822.14
122 438 3572.76 3826.77
123 437 3572.76 3912.38
124 428 3572.76 3759.11
125 428 3572.76 3832.26
126 433 3572.76 3850.53
127 430 3572.76 3843.12
128 424 3572.76 3812.84
129 428 3572.76 3812.98
130 434 3572.76 3799.45
131 437 3572.76 3765.25
132 428 3572.76 3913.48
133 442 3572.76 3909.23
134 443 3572.76 3867.96
135 427 3572.76 3818.33
136 440 3572.76 3823.22
137 430 3572.76 3792.51
138 428 3572.76 3813.76
139 445 3572.76 3897.5
140 421 3572.76 3863.79
141 424 3572.76 3878.47
142 423 3572.76 3822.11
143 428 3572.76 3871.28
144 434 3572.76 3870.21
145 420 3572.76 3841.24
146 432 3572.76 3860.82
147 433 3572.76 3879.33
148 413 3572.76 3860.64
149 436 3572.76 3819.43
150 433 3572.76 3910.48
151 437 3572.76 3816.56
152 437 3572.76 3856.58
153 438 3572.76 3831.04
154 422 3572.76 3892.05
155 444 3572.76 3821.62
156 426 3572.76 3880.1
157 436 3572.76 3840.79
158 423 3572.76 3839.98
159 438 3572.76 3763.6
160 433 3572.76 3865.36
161 429 3572.76 3832.72
162 429 3572.76 3882.3
163 426 3572.76 3861.45
164 440 3572.76 3904.99
165 431 3572.76 3863.64
166 439 3572.76 3915.63
167 442 3572.76 3822.67
168 428 3572.76 3785.66
169 432 3572.76 3858.09
170 436 3572.76 3827.49
171 436 3572.76 3858.5
172 436 3572.76 3877.23
173 438 3572.76 3838.65
174 441 3572.76 3870.86
175 441 3572.76 3822.73
176 421 3572.76 3785.79
177 422 3572.76 3863.44
178 419 3572.76 3823.39
179 436 3572.76 3883.79
180 435 3572.76 3799.64
181 430 3572.76 3840.42
182 431 3572.76 3804.64
183 442 3572.76 3797.32
184 443 3572.76 3840.56
185 423 3572.76 3870.55
186 429 3572.76 3855.45
187 429 3572.76 3847.13
188 431 3572.76 3794.26
189 436 3572.76 3870.5
190 445 3572.76 3862.77
191 438 3572.76 3849.2
192 442 3572.76 3808.65
193 421 3572.76 3864.23
194 434 3572.76 3845.83
195 429 3572.76 3859.82
196 438 3572.76 3913.73
197 429 3572.76 3906.66
198 431 3572.76 3885.86
199 434 3572.76 3921.21
200 432 3572.76 3902.43
201 415 3572.76 3800.52
202 427 3572.76 3796.22
203 435 3572.76 3842.08
204 438 3572.76 3851.39
205 426 3572.76 3908.62
206 427 3572.76 3818.98
207 434 3572.76 3914.53
208 416 3572.76 3863.56
209 422 3572.76 3785.88
210 439 3572.76 3803.27
211 432 3572.76 3832.46
212 432 3572.76 3939.97
213 439 3572.76 3873.11
214 429 3572.76 3815.01
215 440 3572.76 3869.18
216 434 3572.76 3929.91
217 419 3572.76 3870.59
218 444 3572.76 3861.7
219 432 3572.76 3831.4
220 436 3572.76 3801.56
221 417 3572.76 3864.97
222 442 3572.76 3828.29
223 426 3572.76 3887.94
224 436 3572.76 3841.49
225 441 3572.76 3795.5
226 432 3572.76 3776.37
227 436 3572.76 3858
228 432 3572.76 3921.9
229 442 3572.76 3862.34
230 425 3572.76 3768.48
231 429 3572.76 3860.08
232 432 3572.76 3941.06
233 418 3572.76 3786.19
234 440 3572.76 3852.47
235 429 3572.76 3852.47
236 432 3572.76 3858.97
237 423 3572.76 3909.44
238 441 3572.76 3893.83
239 435 3572.76 3896.31
240 428 3572.76 3856.25
241 431 3572.76 3775.85
242 445 3572.76 3825.51
243 438 3572.76 3925.62
244 424 3572.76 3854.06
245 438 3572.76 3884
246 431 3572.76 3848.63
247 434 3572.76 3917.12
248 437 3572.76 3895.76
249 436 3572.76 3909.44
250 437 3572.76 3835.01
251 426 3572.76 3906.47
252 424 3572.76 3846.6
253 428 3572.76 3886.07
254 447 3572.76 3871.95
255 423 3572.76 3883.54
256 442 3572.76 3886.96
257 425 3572.76 3858.28
258 435 3572.76 3782.56
259 433 3572.76 3844.32
260 426 3572.76 3822.58
261 428 3572.76 3769.98
262 441 3572.76 3797.78
263 424 3572.76 3888.4
264 445 3572.76 3875.37
265 424 3572.76 3793.06
266 441 3572.76 3840.58
267 432 3572.76 3851.62
268 424 3572.76 3815.02
269 421 3572.76 3873.68
270 443 3572.76 3880.2
271 434 3572.76 3856.94
272 439 3572.76 3844.15
273 446 3572.76 3883.24
274 429 3572.76 3792.98
275 430 3572.76 3857.12
276 430 3572.76 3852.99
277 431 3572.76 3808.53
278 425 3572.76 3772.38
279 437 3572.76 3841.27
280 431 3572.76 3881.48
281 431 3572.76 3818.9
282 440 3572.76 3873.32
283 433 3572.76 3836.42
284 425 3572.76 3851.93
285 438 3572.76 3875.17
286 436 3572.76 3880.58
287 425 3572.76 3860.58
288 432 3572.76 3884.95
289 425 3572.76 3865.26
290 428 3572.76 3865.52
291 443 3572.76 3819.95
292 435 3572.76 3945.3
293 427 3572.76 3943.39
294 446 3572.76 3911.53
295 433 3572.76 3886.09
296 420 3572.76 3884.21
297 425 3572.76 3910.55
298 428 3572.76 3869.36
299 424 3572.76 3869.86
300 430 3572.76 3852
301 417 3572.76 3907.52
302 432 3572.76 3928.32
303 428 3572.76 3854.76
304 441 3572.76 3899.31
305 436 3572.76 3836.26
306 425 3572.76 3884.65
307 422 3572.76 3872.26
308 427 3572.76 3856.98
309 434 3572.76 3851.25
310 432 3572.76 3780.45
311 438 3572.76 3889.28
312 434 3572.76 3842.25
313 430 3572.76 3859.65
314 427 3572.76 3860.92
315 430 3572.76 3832.51
316 446 3572.76 3874.08
317 439 3572.76 3858.59
318 438 3572.76 3859.9
319 443 3572.76 4010.62
320 432 3572.76 3959.19
321 428 3572.76 3869.26
322 422 3572.76 3896.7
323 428 3572.76 3833.51
324 431 3572.76 3855.17
325 432 3572.76 3861.63
326 436 3572.76 3844.42
327 425 3572.76 3836.96
328 424 3572.76 3881.53
329 433 3572.76 3892
330 438 3572.76 3827.47
331 433 3572.76 3880.88
332 429 3572.76 3832.06
333 422 3572.76 3802.44
334 437 3572.76 3893.29
335 425 3572.76 3844.89
336 440 3572.76 3828.15
337 417 3572.76 3839.74
338 439 3572.76 3805.52
339 437 3572.76 3834.87
340 420 3572.76 3840.18
341 435 3572.76 3818.69
342 427 3572.76 3898.69
343 437 3572.76 3845.35
344 439 3572.76 3856.64
345 430 3572.76 3844.31
346 433 3572.76 3791.98
347 446 3572.76 3847.32
348 439 3572.76 3869.06
349 429 3572.76 3866.73
350 423 3572.76 3873.65
351 428 3572.76 3891.78
352 426 3572.76 3797.41
353 423 3572.76 3880.07
354 441 3572.76 3929.43
355 427 3572.76 3851.45
356 446 3572.76 3844.56
357 436 3572.76 3800.91
358 427 3572.76 3856.47
359 430 3572.76 3879.23
360 448 3572.76 3895.9
361 439 3572.76 3881.29
362 440 3572.76 3878.61
363 434 3572.76 3792.23
364 424 3572.76 3836.41
365 432 3572.76 3796.68
366 435 3572.76 3874.22
367 428 3572.76 3830.32
368 430 3572.76 3842.73
369 426 3572.76 3777.98
370 440 3572.76 3822.94
371 425 3572.76 3835.18
372 434 3572.76 3785.43
373 447 3572.76 3844.64
374 431 3572.76 3857.1
375 430 3572.76 3914.91
376 429 3572.76 3865.51
377 435 3572.76 3852
378 425 3572.76 3875.15
379 432 3572.76 3852.47
380 447 3572.76 3966.05
381 433 3572.76 3844.16
382 421 3572.76 3890.6
383 443 3572.76 3895.09
384 430 3572.76 3898.58
385 430 3572.76 3850.74
386 428 3572.76 3798.36
387 433 3572.76 3780.41
388 440 3572.76 3866.63
389 422 3572.76 3854.3
390 436 3572.76 3797.44
391 431 3572.76 3744.21
392 423 3572.76 3818.02
393 427 3572.76 3853.59
394 423 3572.76 3921.68
395 434 3572.76 3816.41
396 444 3572.76 3913.6
397 437 3572.76 3844.19
398 431 3572.76 3759.41
399 434 3572.76 3806.23
400 430 3572.76 3860.93
401 434 3572.76 3872.8
402 437 3572.76 3859.32
403 433 3572.76 3831.32
404 433 3572.76 3785.4
405 438 3572.76 3858.82
406 436 3572.76 3919.38
407 436 3572.76 3915.48
408 435 3572.76 3878.39
409 417 3572.76 3871.26
410 431 3572.76 3819.95
411 439 3572.76 3953.3
412 437 3572.76 3874.11
413 437 3572.76 3853.09
414 433 3572.76 3801.14
415 436 3572.76 3819.25
416 439 3572.76 3901.06
417 432 3572.76 3816.96
418 435 3572.76 3887.57
419 439 3572.76 3868.63
420 432 3572.76 3866.25
421 435 3572.76 3784.31
422 447 3572.76 3881.91
423 435 3572.76 3829.53
424 433 3572.76 3856.14
425 434 3572.76 3861.59
426 428 3572.76 3883.57
427 433 3572.76 3803.79
428 447 3572.76 3786.39
429 441 3572.76 3865.59
430 435 3572.76 3916.43
431 433 3572.76 3784.99
432 425 3572.76 3827.39
433 422 3572.76 3867.11
434 442 3572.76 3789.69
435 434 3572.76 3891.56
436 432 3572.76 3881.94
437 428 3572.76 3791.38
438 446 3572.76 3902.35
439 410 3572.76 3916.57
440 442 3572.76 3914
441 438 3572.76 3838.08
442 431 3572.76 3815.16
443 432 3572.76 3824.08
444 420 3572.76 3907.57
445 436 3572.76 3914.93
446 422 3572.76 3874.26
447 432 3572.76 3868.68
448 429 3572.76 3906.87
449 452 3572.76 3906.13
450 438 3572.76 3859.63
451 403 3572.76 3775.2
452 447 3572.76 3830.6
453 442 3572.76 3854.69
454 445 3572.76 3914.73
455 418 3572.76 3850.03
456 437 3572.76 3935.48
457 441 3572.76 3867.5
458 435 3572.76 3855.19
459 424 3572.76 3865.25
460 429 3572.76 3951.16
461 433 3572.76 3893.71
462 442 3572.76 3871.18
463 435 3572.76 3877.68
464 432 3572.76 3854.6
465 441 3572.76 3856.84
466 441 3572.76 3845.08
467 424 3572.76 3894.3
468 427 3572.76 3852.93
469 428 3572.76 3937.37
470 430 3572.76 3896.87
471 434 3572.76 3902.79
472 436 3572.76 3879.83
473 416 3572.76 3832.66
474 439 3572.76 3890.92
475 433 3572.76 3830.77
476 426 3572.76 3894.43
477 433 3572.76 3861.96
478 418 3572.76 3807.36
479 424 3572.76 3884.08
480 423 3572.76 3850.39
481 437 3572.76 3850.66
482 431 3572.76 3765.63
483 412 3572.76 3777.87
484 436 3572.76 3896.71
485 427 3572.76 3849.95
486 442 3572.76 3814.45
487 425 3572.76 3866.1
488 436 3572.76 3912.25
489 437 3572.76 3901.51
490 429 3572.76 3813.19
491 424 3572.76 3763.47
492 431 3572.76 3819.47
493 430 3572.76 3819.36
494 432 3572.76 3784.53
495 427 3572.76 3859.52
496 439 3572.76 3823.23
497 426 3572.76 3853.12
498 427 3572.76 3840.84
499 443 3572.76 3865.04
500 423 3572.76 3882.02
501 418 3572.76 3941
502 434 3572.76 3868.69
503 440 3572.76 3953.26
504 422 3572.76 3843.27
505 434 3572.76 3954.93
506 425 3572.76 3862.03
507 436 3572.76 3866.49
508 454 3572.76 3874.2
509 434 3572.76 3884.21
510 406 3572.76 3843.69
511 442 3572.76 3873.93
512 435 3572.76 3866.57
513 426 3572.76 3805.57
514 439 3572.76 3905.3
515 424 3572.76 3967.01
516 430 3572.76 3893.11
517 428 3572.76 3843.57
518 426 3572.76 3867.34
519 427 3572.76 3829.72
520 431 3572.76 3847.65
521 435 3572.76 3873.87
522 429 3572.76 3897.21
523 437 3572.76 3904.83
524 421 3572.76 3890.99
525 398 3572.76 3808.4
526 417 3572.76 3802.86
527 435 3572.76 3837.33
528 435 3572.76 3804.69
529 438 3572.76 3783.13
530 433 3572.76 3846.22
531 424 3572.76 3870.94
532 432 3572.76 3863.03
533 438 3572.76 3852.7
534 442 3572.76 3881.46
535 418 3572.76 3854.12
536 420 3572.76 3805.7
537 433 3572.76 3786.89
538 432 3572.76 3856.71
539 446 3572.76 3873.02
540 436 3572.76 3847.74
541 424 3572.76 3779.06
542 439 3572.76 3843.85
543 433 3572.76 3927.72
544 441 3572.76 3883.98
545 435 3572.76 3917.73
546 442 3572.76 3858.7
547 397 3572.76 3839.69
548 438 3572.76 3855.04
549 424 3572.76 3880.4
550 421 3572.76 3842.82
551 437 3572.76 3851.11
552 431 3572.76 3788.07
553 426 3572.76 3835.94
554 426 3572.76 3884.51
555 437 3572.76 3852.87
556 435 3572.76 3837.2
557 425 3572.76 3859.04
558 438 3572.76 3846.5
559 432 3572.76 3877.78
560 435 3572.76 3913.94
561 433 3572.76 3889.96
562 437 3572.76 3854.68
563 428 3572.76 3841.32
564 434 3572.76 3929.99
565 427 3572.76 3881.99
566 437 3572.76 3875.38
567 435 3572.76 3860.96
568 445 3572.76 3852.97
569 431 3572.76 3853.15
570 420 3572.76 3813.21
571 439 3572.76 3828.95
572 426 3572.76 3758.83
573 434 3572.76 3816.6
574 431 3572.76 3868.31
575 429 3572.76 3875.8
576 423 3572.76 3924.42
577 432 3572.76 3857.2
578 427 3572.76 3788.19
579 444 3572.76 3865.2
580 438 3572.76 3828.93
581 428 3572.76 3743.65
582 438 3572.76 3827.97
583 446 3572.76 3802.6
584 441 3572.76 3836.89
585 441 3572.76 3864.87
586 433 3572.76 3817.66
587 443 3572.76 3831.82
588 435 3572.76 3837.74
589 433 3572.76 3842.18
590 439 3572.76 3879.18
591 431 3572.76 3952.76
592 433 3572.76 3848.5
593 438 3572.76 3805.65
594 450 3572.76 3826.86
595 426 3572.76 3808.26
596 450 3572.76 3882.42
597 429 3572.76 3880.7
598 442 3572.76 3921.47
599 439 3572.76 3868.23
600 444 3572.76 3857.41
601 439 3572.76 3803.8
602 438 3572.76 3755.53
603 434 3572.76 3834.75
604 440 3572.76 3870.8
605 424 3572.76 3926.45
606 430 3572.76 3768.36
607 420 3572.76 3864.87
608 450 3572.76 3908.32
609 440 3572.76 3841.47
610 420 3572.76 3833.82
611 439 3572.76 3865.95
612 436 3572.76 3909.09
613 434 3572.76 3907.97
614 421 3572.76 3869.58
615 451 3572.76 3826.79
616 442 3572.76 3887.44
617 425 3572.76 3813.06
618 430 3572.76 3869.09
619 427 3572.76 3823.77
620 428 3572.76 3906.68
621 444 3572.76 3869.07
622 447 3572.76 3918.24
623 434 3572.76 3850.79
624 430 3572.76 3869.06
625 427 3572.76 3827.75
626 444 3572.76 3865.27
627 429 3572.76 3854.7
628 439 3572.76 3865.34
629 434 3572.76 3838.53
630 445 3572.76 3842.82
631 428 3572.76 3817.6
632 439 3572.76 3854.64
633 429 3572.76 3864.92
634 431 3572.76 3907.04
635 428 3572.76 3835.36
636 437 3572.76 3883.05
637 424 3572.76 3837.68
638 449 3572.76 3846.44
639 429 3572.76 3800.05
640 426 3572.76 3836.69
641 427 3572.76 3940.91
642 431 3572.76 3831.38
643 435 3572.76 3862.46
644 431 3572.76 3803.48
645 442 3572.76 3880.21
646 435 3572.76 3860.67
647 431 3572.76 3803.56
648 443 3572.76 3866.57
649 429 3572.76 3848.1
650 425 3572.76 3835.21
651 428 3572.76 3835.71
652 432 3572.76 3899.46
653 427 3572.76 3819.14
654 433 3572.76 3893.32
655 432 3572.76 3868.6
656 414 3572.76 3908.83
657 442 3572.76 3843.07
658 430 3572.76 3822.3
659 446 3572.76 3775.47
660 440 3572.76 3852.03
661 448 3572.76 3868.63
662 427 3572.76 3869.57
663 452 3572.76 3842.24
664 415 3572.76 3870.82
665 434 3572.76 3873.56
666 429 3572.76 3841.96
667 432 3572.76 3889.37
668 426 3572.76 3911.55
669 432 3572.76 3940.85
670 436 3572.76 3878.1
671 432 3572.76 3832.84
672 426 3572.76 3789.37
673 430 3572.76 3830.06
674 439 3572.76 3804.36
675 439 3572.76 3860.79
676 438 3572.76 3786.59
677 430 3572.76 3914.53
678 424 3572.76 3827.55
679 430 3572.76 3855
680 430 3572.76 3910.17
681 409 3572.76 3884.86
682 436 3572.76 3879.41
683 443 3572.76 3859
684 433 3572.76 3974.58
685 436 3572.76 3886.81
686 437 3572.76 3827.09
687 431 3572.76 3786.95
688 428 3572.76 3894.02
689 428 3572.76 3917.83
690 434 3572.76 3874.21
691 434 3572.76 3903.88
692 433 3572.76 3823.1
693 433 3572.76 3897.65
694 435 3572.76 3881.06
695 440 3572.76 3906.64
696 436 3572.76 3920.7
697 442 3572.76 3860.01
698 436 3572.76 3846.5
699 448 3572.76 3831.42
700 437 3572.76 3914.29
701 429 3572.76 3881.06
702 447 3572.76 3934.44
703 429 3572.76 3906.95
704 420 3572.76 3830.8
705 432 3572.76 3930.59
706 429 3572.76 3880.69
707 437 3572.76 3792.51
708 442 3572.76 3876.28
709 449 3572.76 3950.6
710 427 3572.76 3802.15
711 437 3572.76 3836.85
712 434 3572.76 3857.8
713 432 3572.76 3868.99
714 425 3572.76 3785.23
715 429 3572.76 3917.93
716 437 3572.76 3797.97
717 420 3572.76 3794.8
718 424 3572.76 3808.5
719 444 3572.76 3940.53
720 420 3572.76 3896.72
721 439 3572.76 3890.63
722 436 3572.76 3837.24
723 430 3572.76 3897.39
724 429 3572.76 3914.44
725 422 3572.76 3906.38
726 415 3572.76 3772.76
727 439 3572.76 3849.85
728 427 3572.76 3813.9
729 422 3572.76 3843.1
730 442 3572.76 3853.54
731 417 3572.76 3901.33
732 446 3572.76 3876.26
733 434 3572.76 3775.72
734 435 3572.76 3896.66
735 433 3572.76 3906.82
736 437 3572.76 3832.08
737 432 3572.76 3844.63
738 437 3572.76 3839.53
739 441 3572.76 3950.66
740 432 3572.76 3916.14
741 440 3572.76 3921.94
742 437 3572.76 3877.48
743 431 3572.76 3834.43
744 442 3572.76 3862.83
745 436 3572.76 3817.35
746 431 3572.76 3908.47
747 437 3572.76 3813.27
748 433 3572.76 3887.51
749 423 3572.76 3880.92
750 443 3572.76 3888.89
751 423 3572.76 3845.28
752 433 3572.76 3914.05
753 424 3572.76 3824.2
754 437 3572.76 3754.56
755 433 3572.76 3874.23
756 432 3572.76 3836.72
757 417 3572.76 3808.6
758 429 3572.76 3882.78
759 422 3572.76 3841.96
760 427 3572.76 3820.02
761 436 3572.76 3837.93
762 427 3572.76 3829.37
763 424 3572.76 3802.92
764 423 3572.76 3840
765 431 3572.76 3877.46
766 443 3572.76 3813.28
767 426 3572.76 3891.65
768 427 3572.76 3864.91
769 436 3572.76 3870.19
770 432 3572.76 3854.01
771 433 3572.76 3831.33
772 434 3572.76 3924.04
773 435 3572.76 3880.43
774 434 3572.76 3818.02
775 429 3572.76 3834.59
776 430 3572.76 3844.49
777 434 3572.76 3854.29
778 441 3572.76 3874.03
779 438 3572.76 3887.88
780 416 3572.76 3885.61
781 436 3572.76 3895
782 436 3572.76 3897.8
783 426 3572.76 3829.02
784 427 3572.76 3832.26
785 428 3572.76 3798.35
786 431 3572.76 3830.66
787 422 3572.76 3873.04
788 433 3572.76 3785.5
789 437 3572.76 3880.01
790 443 3572.76 3814.88
791 441 3572.76 3839.52
792 444 3572.76 3746.49
793 438 3572.76 3790.87
794 427 3572.76 3828.12
795 429 3572.76 3870.9
796 429 3572.76 3887.4
797 423 3572.76 3853.97
798 415 3572.76 3838
799 413 3572.76 3752.04
800 446 3572.76 3911.23
801 426 3572.76 3826.54
802 438 3572.76 3875.61
803 440 3572.76 3827.27
804 440 3572.76 3978.65
805 440 3572.76 3810.53
806 428 3572.76 3874.05
807 440 3572.76 3919
808 441 3572.76 3877.48
809 428 3572.76 3873.27
810 437 3572.76 3788.64
811 418 3572.76 3849.46
812 448 3572.76 3829.66
813 420 3572.76 3851.32
814 438 3572.76 3832.89
815 434 3572.76 3852.61
816 432 3572.76 3828.74
817 442 3572.76 3852.88
818 438 3572.76 3867.91
819 431 3572.76 3822.54
820 418 3572.76 3881.61
821 437 3572.76 3893.25
822 431 3572.76 3790.63
823 428 3572.76 3832.01
824 423 3572.76 3842.77
825 431 3572.76 3822.03
826 423 3572.76 3822.56
827 435 3572.76 3850.91
828 430 3572.76 3858.14
829 433 3572.76 3900.26
830 435 3572.76 3882.22
831 423 3572.76 3866.03
832 433 3572.76 3787.06
833 436 3572.76 3828.36
834 443 3572.76 3818.53
835 419 3572.76 3854.36
836 437 3572.76 3852.07
837 416 3572.76 3839.83
838 440 3572.76 3861.78
839 429 3572.76 3845.78
840 435 3572.76 3834.47
841 430 3572.76 3806.61
842 429 3572.76 3810.62
843 428 3572.76 3830.22
844 429 3572.76 3801.95
845 436 3572.76 3786.02
846 439 3572.76 3845.26
847 444 3572.76 3871.54
848 437 3572.76 3844.39
849 444 3572.76 3782.54
850 434 3572.76 3837.34
851 434 3572.76 3877.29
852 443 3572.76 3827.56
853 434 3572.76 3922.66
854 437 3572.76 3913.77
855 429 3572.76 3889.36
856 437 3572.76 3822.18
857 434 3572.76 3847.11
858 422 3572.76 3878.72
859 434 3572.76 3896.72
860 427 3572.76 3907.75
861 422 3572.76 3900.85
862 432 3572.76 3850.61
863 428 3572.76 3825.58
864 424 3572.76 3858.42
865 443 3572.76 3851.55
866 434 3572.76 3873.72
867 440 3572.76 3821.29
868 431 3572.76 3860.45
869 433 3572.76 3799.39
870 429 3572.76 3871.47
871 434 3572.76 3830.35
872 441 3572.76 3868.35
873 441 3572.76 3861.99
874 436 3572.76 3849.61
875 421 3572.76 3910.13
876 424 3572.76 3800.88
877 427 3572.76 3810.83
878 433 3572.76 3848.61
879 429 3572.76 3869.83
880 436 3572.76 3874.32
881 426 3572.76 3822.49
882 425 3572.76 3889.86
883 445 3572.76 3838.36
884 439 3572.76 3863.16
885 427 3572.76 3840.82
886 435 3572.76 3854.76
887 431 3572.76 3896.82
888 409 3572.76 3875.07
889 429 3572.76 3817.34
890 435 3572.76 3750.22
891 442 3572.76 3804.89
892 445 3572.76 3878.93
893 437 3572.76 3857.1
894 438 3572.76 3934.68
895 440 3572.76 3924.18
896 434 3572.76 3947.06
897 429 3572.76 3922.88
898 433 3572.76 3843.4
899 443 3572.76 3813.66
900 439 3572.76 3828.76
901 434 3572.76 3823.07
902 422 3572.76 3785.96
903 431 3572.76 3823.06
904 437 3572.76 3804.63
905 429 3572.76 3885
906 437 3572.76 3907.58
907 438 3572.76 3840.15
908 438 3572.76 3818.92
909 421 3572.76 3845.94
910 428 3572.76 3767.14
911 432 3572.76 3792.63
912 429 3572.76 3810.06
913 429 3572.76 3839.49
914 431 3572.76 3830.92
915 431 3572.76 3928.66
916 433 3572.76 3807.83
917 429 3572.76 3844.42
918 444 3572.76 3817.45
919 428 3572.76 3873.7
920 441 3572.76 3889.7
921 431 3572.76 3900.58
922 429 3572.76 3812.89
923 437 3572.76 3842.65
924 441 3572.76 3824.63
925 429 3572.76 3943.48
926 424 3572.76 3839.47
927 428 3572.76 3810.9
928 435 3572.76 3886.22
929 435 3572.76 3824.05
930 432 3572.76 3850.5
931 435 3572.76 3832.03
932 444 3572.76 3857.26
933 437 3572.76 3809.15
934 446 3572.76 3868.69
935 429 3572.76 3817.84
936 407 3572.76 3855.69
937 432 3572.76 3784.28
938 437 3572.76 3890.52
939 436 3572.76 3867.27
940 431 3572.76 3939.91
941 431 3572.76 3848.66
942 442 3572.76 3874.02
943 439 3572.76 3779.66
944 426 3572.76 3859.58
945 431 3572.76 3916.39
946 435 3572.76 3875.92
947 428 3572.76 3927.16
948 424 3572.76 3836.87
949 445 3572.76 3837.9
950 428 3572.76 3916.06
951 430 3572.76 3856.06
952 433 3572.76 3855.97
953 441 3572.76 3802.77
954 442 3572.76 3803.62
955 430 3572.76 3812.46
956 439 3572.76 3924.32
957 439 3572.76 3808
958 443 3572.76 3871.84
959 418 3572.76 3915.37
960 432 3572.76 3849.31
961 434 3572.76 3819.35
962 428 3572.76 3846
963 429 3572.76 3886.08
964 442 3572.76 3844.9
965 439 3572.76 3744.13
966 438 3572.76 3881.9
967 430 3572.76 3846.73
968 427 3572.76 3897.36
969 430 3572.76 3895.18
970 432 3572.76 3889.07
971 430 3572.76 3841.06
972 436 3572.76 3818.02
973 427 3572.76 3810.96
974 432 3572.76 3822.18
975 427 3572.76 3884.7
976 440 3572.76 3893.35
977 435 3572.76 3915.26
978 428 3572.76 3914.85
979 441 3572.76 3843.16
980 436 3572.76 3844.58
981 424 3572.76 3825.78
982 437 3572.76 3808.64
983 426 3572.76 3849.83
984 431 3572.76 3789.43
985 428 3572.76 3939.74
986 434 3572.76 3883.72
987 435 3572.76 3881.27
988 438 3572.76 3817.34
989 435 3572.76 3845.81
990 433 3572.76 3885.02
991 426 3572.76 3850.84
992 436 3572.76 3897.65
993 429 3572.76 3883.21
994 431 3572.76 3850.51
995 432 3572.76 3920.71
996 428 3572.76 3871.97
997 426 3572.76 3788.18
998 434 3572.76 3772.19
999 443 3572.76 3845.4
1000 439 3572.76 3818.27
-- Best Ever Individual = Individual('i', [3, 13, 10, 24, 12, 6, 22, 15, 30, 7, 26, 18, 21, 16, 17, 14, 31, 0, 27, 25, 2, 20, 29, 23, 11, 5, 4, 8, 28, 1, 19, 9])
-- Best Ever Fitness = 3572.755615234375
Best Ever Fintess Found at = 101
-- Route Breakdown = [[3, 13, 10, 24, 6, 22, 15], [7, 26, 18, 21, 16, 17, 14], [0, 27, 25, 2, 20], [23, 11, 5, 4, 8, 28, 1, 19, 9]]
-- total distance = 13868.3671875
-- max distance = 3572.7556
