Pathfinder- web app that shows optimal path

Published in

Coinmonks

5 min readDec 9, 2018

OUTLINE- Travelling Salesperson Problem is a very special kind of problem. In this, a salesman who must travel between N cities. The order in which he does so is something he does not care about, as long as he visits each once during his trip, and finishes where he was at first. Each city is connected to another close by cities, or nodes, by airplanes, or by road or railway. Its a kind of Hard Optimization Problem. We can see the complexity by the figure given below-

Time Complexities of Travelling Salesman Problem

As it is clearly visible that solving this problem using brute force approach takes O(n!) time and using Dynamic Programming it’s time complexity is O(n² *2^n). So it very hard to optimize that problem. For near optimization, I have used Genetic Algorithm which is a kind of approximation algorithm.

GOAL- Building the web application that shows the optimal path for set of destinations which are entered by the visitor/user. I have given the Github link for this project below-

Github- https://github.com/HACKERSHUBH/Path-Finder

Pre-requisites- HTML, CSS, Javascript

I have developed this project in two ways- Static destinations manner and Dynamic Destinations manner

Static Destinations Manner- Python script that has taken the dataset of cities/landmark places/visiting places and predicts the optimal path for covering all the cities which are included in the dataset.

Dynamic Destinations Manner- I have developed the web app that takes the destinations city in a user-friendly manner and predicts the optimal path only for the cities which user have entered.

Let's get started!

First of all, I wanted to show all of you the working demonstration of the project.

Implementation of the above problem-

Directory structure looks like this-

Genetic Algorithm- GA is great for finding solutions to complex search problems. They are used to create incredibly high-quality products, thanks to their ability to search a through a huge combination of parameters to find the best match. they can search through different combinations of materials and designs to find the perfect combination of both which could result in a stronger, lighter and overall, better final product. Genetic algorithms are based on the process of evolution by natural selection which has been observed in nature.

Basic Parameters of Genetic Algorithm-

The basic process for a genetic algorithm is:

Initialization — Create an initial population. This population is usually randomly generated and can be any desired size, from only a few individuals to thousands.
Evaluation — Each member of the population is then evaluated and we calculate a ‘fitness’ for that individual. The fitness value is calculated by how well it fits with our desired requirements. These requirements could be simple, ‘faster algorithms are better’, or more complex, ‘stronger materials are better but they shouldn’t be too heavy’.
Selection — We want to be constantly improving our population's overall fitness. Selection helps us to do this by discarding the bad designs and only keeping the best individuals in the population. There are a few different selection methods but the basic idea is the same, make it more likely that fitter individuals will be selected for our next generation.
Crossover — During crossover, we create new individuals by combining aspects of our selected individuals. We can think of this as mimicking how sex works in nature. The hope is that by combining certain traits from two or more individuals we will create an even ‘fitter’ offspring which will inherit the best traits from each of its parents.
Mutation — We need to add a little bit randomness into our populations’ genetics otherwise every combination of solutions we can create would be in our initial population. Mutation typically works by making very small changes at random to an individuals genome.
And repeat! — Now we have our next generation we can start again from step two until we reach a termination condition.

Termination

There are a few reasons why you would want to terminate your genetic algorithm from continuing its search for a solution. The most likely reason is that your algorithm has found a solution which is good enough and meets predefined minimum criteria. Offer reasons for terminating could be constraints such as time or money or we could pre-defined the number of iterations to which the algorithm run.

Solving the above problem, there are two important rules to keep in mind:

Each city needs to be visited exactly one time
We must return to the starting city, so our total distance needs to be calculated accordingly

The approach

Let’s start with a few definitions, rephrased in the context of the TSP:

Gene: a city (represented as (x, y) coordinates)
Individual (aka “chromosome”): a single route satisfying the conditions above
Population: a collection of possible routes (i.e., collection of individuals)
Parents: two routes that are combined to create a new route
Mating pool: a collection of parents that are used to create our next population (thus creating the next generation of routes)
Fitness: a function that tells us how good each route is (in our case, how short the distance is)
Mutation: a way to introduce variation in our population by randomly swapping two cities in a route
Elitism: a way to carry the best individuals into the next generation

Since users are selecting the destinations points on the google map with the help of marker so we need the distance matrix.

If a user wants their current location then they have to click on the ‘location’ button provided in the website. I am also using the different type of traveling modes like-

Car
Bicycle

I am also using whether the user has to cover highways during the trip or not, so there is also a highway enabled or disabled mode. then I am creating the duration data array for the different type of traveling modes. code for this is-

Now comes the Genetic Algorithm code with the parameters-

Now we are applying the mutation, crossover to current population and returns population of offspring. After that, we are finding the fittest individual at each iteration we are applying the tournament selection and then selects the fittest individual index.

This completes the Genetic Algorithm code for solving the travelling salesman problem. Although it is an approximation algorithm for finding the shortest route but its time complexity is very less as compared to other approaches.

References-

Get Best Software Deals Directly In Your Inbox