Travelling Salesman Problem system, made in functional programming Javascript with Ramda.
- Description
- Installation
- Start the App
- Output Example
- Project Architecture
- Developer Tools
- Git Actions
- Authors
- Special Thanks
- Links
The Travelling Salesman Problem also known as TSP is an NP-hard problem in combinatorial optimization.
Imagine a set of city disposed on a map, you have a set of salesman (population) and they must all
go to every city in the least amount of time/distance.
The optimization solution is the one where a salesman goes through all the cities with the least
distance or/and time.
In the schema below you can see an example with some cities in Europe (Paris, Marseille, Berlin, Hamburg). Going from a city to another take more or less time than other depending on the distance.
The Travelling Salesman Problem can find the most optimized path to join all cities.
WARNING This code below shows how it works, it will be well printed by seeing this GitHub Repository
flowchart LR
subgraph France
Paris --- |775,2 km| Marseille
end
subgraph Germany
Hamburg --- |289,4 km| Berlin
end
Paris --- |1054,3 km| Berlin
Paris --- |913,4 km| Hamburg
Marseille --- |1542,2 km| Berlin
Marseille --- |1460,5 km| Hamburg
style Paris fill:#002654,color:white,stroke:white
style Marseille fill:#ED2939,color:white,stroke:white
style Hamburg fill:black,color:white,stroke:white
style Berlin fill:#FFCC00,color:black,stroke:white
style France fill:black,color:white,stroke:black
style Germany fill:black,color:white,stroke:black
linkStyle 0 stroke:white,stroke-width:5
linkStyle 1 stroke:#DD0000,stroke-width:5
To implement the travelling salesman problem we use genetic algorithm.
Step order:
-
Generate a population where every salesman (individual) has a list of city he goes through.
-
Mutate the population (20% chance of happening on every individual).
-
Crossover the population to create 40% of new individuals that will replace 40% of the old one. An offspring inherits all cities from its first parent and a chance of 20% to inherits a city from its second parent.
-
Repair all individuals which pass through a city more than one time.
-
Calculate the score of all individuals. The score is calculated by the addition of all values of all cities. All individuals have a different score because the calculation is limited by a max distance. If the max distance is greater than the sum of all cities, all individuals would have the same score.
-
Show the best score among all the population.
-
Reiterates all the previous steps N times with the new mutated population.
To run the app, you need to install NodeJS
Once installed, with your terminal go to the folder to the root of the project and run the following commande:
If you're using npm: npm install
Or if you're using Yarn: yarn install
It will install all the needed libraries to start the project.
After just start the program by typing: npm start or yarn start
all Cities :
{
'0': { x: 32, y: 12, value: 7 },
'1': { x: 31, y: 47, value: 28 },
'2': { x: 21, y: 47, value: 46 },
'3': { x: 6, y: 33, value: 48 },
'4': { x: 4, y: 29, value: 5 },
'5': { x: 5, y: 0, value: 6 },
'6': { x: 11, y: 28, value: 23 },
'7': { x: 9, y: 39, value: 28 },
'8': { x: 12, y: 37, value: 9 },
'9': { x: 47, y: 24, value: 4 },
'10': { x: 16, y: 10, value: 0 },
'11': { x: 23, y: 4, value: 43 },
'12': { x: 27, y: 17, value: 8 },
'13': { x: 11, y: 33, value: 16 },
'14': { x: 4, y: 43, value: 36 },
'15': { x: 46, y: 40, value: 38 },
'16': { x: 12, y: 42, value: 46 },
'17': { x: 28, y: 0, value: 21 },
'18': { x: 41, y: 36, value: 6 },
'19': { x: 4, y: 9, value: 17 },
'20': { x: 31, y: 23, value: 2 },
'21': { x: 47, y: 49, value: 8 },
'22': { x: 4, y: 26, value: 15 },
'23': { x: 20, y: 27, value: 35 },
'24': { x: 49, y: 17, value: 4 },
'25': { x: 19, y: 38, value: 42 },
'26': { x: 18, y: 10, value: 49 },
'27': { x: 48, y: 49, value: 45 },
'28': { x: 21, y: 16, value: 24 },
'29': { x: 19, y: 6, value: 8 },
'30': { x: 15, y: 13, value: 22 },
'31': { x: 8, y: 41, value: 39 },
'32': { x: 39, y: 19, value: 33 },
'33': { x: 6, y: 25, value: 2 },
'34': { x: 47, y: 37, value: 17 },
'35': { x: 25, y: 20, value: 10 },
'36': { x: 22, y: 39, value: 38 },
'37': { x: 49, y: 36, value: 20 },
'38': { x: 1, y: 39, value: 43 },
'39': { x: 26, y: 21, value: 2 },
'40': { x: 36, y: 6, value: 40 },
'41': { x: 25, y: 41, value: 44 },
'42': { x: 11, y: 30, value: 27 },
'43': { x: 20, y: 22, value: 43 },
'44': { x: 44, y: 17, value: 44 },
'45': { x: 34, y: 20, value: 15 },
'46': { x: 35, y: 44, value: 37 },
'47': { x: 39, y: 23, value: 48 },
'48': { x: 32, y: 40, value: 48 },
'49': { x: 26, y: 12, value: 31 },
max: 50
}
Best result 1st iteration : {
path: [
10, 35, 46, 23, 34, 1, 15, 8, 32, 22, 40,
9, 3, 7, 36, 28, 13, 38, 26, 11, 16, 48,
5, 37, 49, 0, 27, 42, 4, 14, 43, 47, 6,
39, 45, 44, 20, 25, 17, 18, 41, 21, 2, 24,
19, 12, 31, 33, 30, 29
],
score: 649
}
Best result after 100 iterations {
path: [
8, 46, 25, 7, 14, 38, 0, 40, 37, 44, 19,
30, 22, 3, 36, 43, 6, 45, 28, 23, 41, 47,
31, 16, 2, 42, 13, 11, 49, 26, 17, 35, 33,
21, 10, 15, 34, 20, 48, 24, 12, 39, 32, 27,
5, 18, 1, 4, 29, 9
],
score: 996
}
| Location | |
|---|---|
| Source code | root |
| Gulpfile | root |
| Unit test scripts | test folder |
The Source code is at the root folder and contains the TSP.
The gulpfile is an auto-run script to run the TSP.
The unit test scripts are a set of scripts to verify the good behaviour of some functions.
The project is set with some tools like auto run (gulp), unit test (Chai, Mocha), code formatter (Xo/Prettier).
The project has a gulpfile to autorun the script while programming.
To install gulp type the following command:
npm install --global gulp-cli or yarn add gulp-cli
To start it types in the root folder the command: gulp
Each time a js script is modified and save, it will run the example.js file.
The gulp file is written in js.
To run the unit test scripts, you can type the command: npm test or yarn test
It will start Mocha that will look for test scripts.
The test scripts are written in js with Chai.
Take note that GitHub verify the correct work of the tests.
You can test the format code of the project by typing the following command:
npm run code-style or yarn run code-style
Warning To easily achieve the code format test, you should use Prettier for Xo (code formater wraper) code-formatting that is already set with some parameters in the project
The project is set with GitHub Actions that will test:
If one of those test failed a mail is sent to the person who tried to merge its code from the staging to main branch.
- Node and npm (runtime environment and software packaging system)
- Yarn (software packaging system)
- Ramda (functional programming library in JS)
- Gulp (auto script starter)
- Chai (assertion library)
- Mocha (test framework)
- Xo (code formater wraper)
- Prettier (code formatter)
- Editor config (normalize the IDE for the project)
- Mermaid (Graph shown in Readme)