- Purpose
- Overview
- Installation
- Introduction
- Examples
- Command Line Interface
- Theoretical Background
- License
pytsp aims at tackling the Travelling Salesman Problem in Python.
What is the Travelling Salesman Problem ?
- The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?"
- The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources will want to minimize the time spent moving the telescope between the sources.
If you are interested in the intricate inner workings of the different algorithms mentioned above, feel free to check out the theoretical background section.
The project consists of
-
the pytsp library, which provides various approaches in tackling the Travelling Salesman Problem (with and without Time Windows). These include
- Greedy approaches
- Geometric approaches
- Local Search approaches
- Meta-heuristic approaches
-
the tsplot command line utility, which can be used to demonstrate, compare and chain the various algorithms mentioned above.
python -m pip install virtualenv
python -m virtualenv .env
. .env/Scripts/activate
pip install git+https://github.com/billsioros/pytspWhat is a Model ?
A Model describes a set of distinctive qualities (traits) of each algorithm that can be inherited and/or assigned.
What are Traits ?
Traits provide a frictionless way of modifying the inner workings of the underlying algorithms.
Could you guess what the following python code will produce as output ?
from pytsp import Model
class Greet(Model):
class Traits:
class Greet:
def greetings(self, name):
return f'Greetings {self.title}{name}'
def hello(self, name):
return f'Hello {self.title}{name}'
def __init__(self, title, *args, **kwargs):
super().__init__(*args, **kwargs)
self.title = title
def good_evening(self, name):
return f'Good evening {self.title}{name}'
if __name__ == '__main__':
greet = Greet('Mr.', greet='hello')
print(greet.greet('Sioros'))
greet.title = 'Sir.'
greet.greet = 'greetings'
print(greet.greet('Vasileios'))
greet.title = ''
greet.greet = good_evening
print(greet.greet('Vasilis'))If you answered
Hello Mr.Sioros
Greetings Sir.Vasileios
Good evening Vasilisyou have earned yourself a cookie !
Let's now look at some examples of using pytsp. The examples are presented in least to most confusing order.
The following examples are simplified versions of a subset of the examples provided in the examples directory.
from random import uniform
from pytsp import TravellingSalesman
if __name__ == '__main__':
x_axis, y_axis = (-50, +50), (-50, +50)
cities = [
(uniform(x_axis[0], x_axis[1]), uniform(y_axis[0], y_axis[1]))
for i in range(10)
]
depot, cities = cities[0], cities[1:]
tsp = TravellingSalesman(metric='euclidean')
route, cost = tsp.nearest_neighbor(depot, cities)from random import choice, random, randrange, shuffle
from pytsp import SimulatedAnnealing
class Sort(SimulatedAnnealing):
class Traits:
class Mutate:
def shift_1(self, elements):
neighbor = elements[:]
i = randrange(0, len(elements))
j = randrange(0, len(elements))
neighbor.insert(j, neighbor.pop(i))
return neighbor
class Cost:
def ordered(self, individual):
mispositioned = 0
for i in range(0, len(individual) - 1):
for j in range(i + 1, len(individual)):
mispositioned += individual[i] > individual[j]
return mispositioned
if __name__ == '__main__':
sorter = Sort(mutate='shift_1', cost='ordered')
individual = list(range(10))
shuffle(individual)
best, cost = sorter.fit(individual)from random import choice, random, randrange
from string import printable
from pytsp import GeneticAlgorithm
class GuessString(GeneticAlgorithm):
class Traits:
class Mutate:
def randomize(self, individual):
return ''.join([
choice(printable)
if random() < self.per_character_mutation_probability
else individual[i]
for i in range(len(individual))
])
class Crossover:
def cut_and_stitch(self, individual_a, individual_b):
left = individual_a[:len(individual_a) // 2]
right = individual_b[len(individual_b) // 2:]
return left + right
class Select:
def random_top_half(self, population):
return population[randrange(0, len(population) // 2)]
class Fitness:
def least_squares(self, individual):
squared_sum = 0
for i in range(len(self.target)):
squared_sum += (ord(individual[i]) - ord(self.target[i])) ** 2
return 1 / (squared_sum + 1)
def __init__(self, target, *args, per_character_mutation_probability=0.1, **kwargs):
super().__init__(*args, **kwargs)
self.target = target
self.per_character_mutation_probability = per_character_mutation_probability
if __name__ == '__main__':
target = 'Hello World!'
string_guesser = GuessString(
target,
mutate='randomize',
crossover='cut_and_stitch',
select='random_top_half',
fitness='least_squares',
max_iterations=10000
)
individual = ''.join([choice(printable)for _ in range(len(target))])
fittest = string_guesser.fit(individual)tsplot provides a means of demonstrating, comparing and chaining different algorithms.
Apart from the main options showcased above, each sub-command has its own sub-options, which can be viewed with the --help flag, as such
We are going to focus on chaining different algorithms, as simpler cases are demonstrated in the theoretical background section anyway.
Chaining refers to passing the solution produced by the algorithm at hand as input to the algorithm following, so that it can be further improved.
tsplot -n 20 -s 2 -g tsp nearest-neighbor simulated-annealing opt-2tsplot -n 20 -s 0 -g tsp convex-hull genetic-algorithm opt-2
tsplot is a Click based application, which means that enabling the autocompletion of its' sub-commands and options can be achieved as simply as adding a line to your .*rc file. To be more specific, when it comes to bash adding the following line to your .bashrc file will do exactly that.
eval "$(_TSPLOT_COMPLETE=source_bash tsplot)"For more information, on enabling tab completion on different shells, please refer here.
Special thanks to Andrinopoulou Christina for her major contribution in the theoretical research of the problem.
In the following sections the terms path, tour, route are used interchangeably
- Initialize all vertices as unvisited.
- Select an arbitrary vertex, set it as the current vertex and mark as visited.
- Find out the shortest edge connecting the current vertex and an unvisited vertex.
- Set the unvisited vertex as the current vertex and mark it as visited.
- If all the vertices in the domain are visited, then terminate. Otherwise, go to step 3.
The sequence of the visited vertices is the output of the algorithm.
tsplot -n 20 -s 2 -g tsptw nearest-neighbor- Given a set of vertices, construct a partial tour consisting of the convex hull of the set and set the vertices that the convex hull is consisting of as visited.
- While there are unvisited vertices do the following
- Given triplets of the form (a, b, c), where a and c correspond to consecutive vertices of the partial tour and b to an unvisited vertex, calculate every angle that is formed by such a triplet.
- Find the triplet, corresponding to the maximal angle value, and insert the unvisited vertex belonging to the triplet between the consecutive vertices of the partial tour that belong in the triplet.
Yet again, the sequence of the visited vertices is the output of the algorithm.
tsplot-n 20 -s 2 -g tsptw convex-hull -c angleThis algorithm is quite similar to the angle comparison method mentioned above.
In fact, the only difference is that, we use the notion of ellipses. To be more specific, triplets of the aforementioned structure are formed, in each iteration of the algorithm, such that vertices a and c are the focal points of the ellipse and vertex b intersects with the ellipse at hand.
Now the vertices are not inserted into the partial tour in maximal angle order. Instead, they are inserted in maximal ellipse eccentricity order, which is calculated as such
tsplot -n 20 -s 2 -g tsptw convex-hull -c eccentricityThe main idea behind it is to take a route that crosses over itself and reorder it so that it does not.
Given a route of length n, i.e. an ordering of the vertices, the 2-opt swapping mechanism performs the following
- Initialize new_route to be a new empty route.
- Take the elements from index
0to indexi - 1and add them in order to new_route. - Take the elements from index
ito indexkand add them in reverse order to new_route. - Take the elements from index
k + 1tonand add them in order to new_route - Return new_route as a new candidate route
The actual algorithm utilizing the mechanism explained above performs the following
- Assign the initially provided route as the best found route
- Until no better solution can be found
- Calculate the cost of the best found route
- For every possible pair
(i, k)- Find a new candidate route, using the 2-opt swapping mechanism
- Calculate the candidate route's cost
- If the candidate route' cost is smaller than the cost of the best route thus far, restart the whole procedure, with the candidate route as the initially provided route.
- If the set of possible
(i, k)pairs is exhausted, return the best found route.
tsplot-n 20 -s 2 -g tsptw opt-2In this section, only a high level overview of the algorithms is going to be provided, as the exact steps of each algorithm are of miniscule importance, when compared to the mechanisms performing the mutatation, selection, crossover, fitness assessment, e.t.c of individuals.
The mechanisms concerning the Travelling Salesman Problem are self explanatory and provide a solid start in tackling other combinatorial optimization problems
Given an individual, the genetic algorithm performs the following
- Generate the initial generation of
nindividuals, by means of mutation on the provided individual - While the maximum number of iterations has not been reached
- Calculate the fitness of all individuals belonging to the current generation
- If an individual with a fitness value higher than the one of the fittest individual thus far exists, assign it as the fittest individual
- If the fitness of the fittest individual thus far exceeds the fitness threshold, return it.
- Otherwise, until the next generation contains
nindividuals- Select 2 individuals belonging to the current generation
- Cross them over in order to produce an offspring
- Probabilistically mutate the offspring
- Add the offspring to the next generation
- Return the fittest individual
tsplot -n 20 -s 2 -g tsptw genetic-algorithmGiven an initial solution, a cooling rate and an initial temperature, the simulated annealing heuristic performs the following
- Let the current solution be the initial solution as well as the best solution so far
- While the maximum number of iterations has not been reached and the current temperature is greater than 0
- Generate a new candidate solution and calculate its cost
- Probabilistically decide to accept the candidate solution as the current solution whilst taking into consideration the temperature, the current solution's cost as well as the candidate solution's cost
- If the candidate solution's cost is smaller than the best so far solution's cost, assign the candidate as the best found solution thus far
- Increase the number of iteration by 1
- Reduce the temperature by a factor of 1 - cooling rate
- Return the best found solution
tsplot -n 20 -s 2 -g tsptw simulated-annealingA variant of Simulated Annealing incorporating a variable penalty method to solve the Travelling Salesman Problem with Time Windows. Augmenting temperature from traditional Simulated Annealing with the concept of pressure (analogous to the value of the penalty multiplier), compressed annealing relaxes the time-window constraints by integrating a penalty method within a stochastic search procedure.
Sadly, Compressed Annealing can not be presented in the context of a brief theoretical overview, as it is indeed quite complex.
For anyone interested in achieving a greater theoretical understanding of the algorithm, I advise you to study the original paper by Jeffrey W. Ohlmann and Barrett W. Thomas (Department of Management Sciences, University of Iowa).
tsplot -n 20 -s 2 -g tsptw compressed-annealingFor a more exhaustive analysis of the problem and the algorithms presented, feel free to check out our paper.
The project is licensed under the MIT License:
Copyright © 2020 Vasileios Sioros
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.