Create a TSP and VRP optimization library in Javascript that can be integrated into route planner applications

[mraross]

1. Use betweenPairs to get distances between stops in the route. Use same points in To and From parameters.

2. Solve TSP in the browser. This keeps it interactive instead of batch on the server.

3. To get a displayable route, an application just has to request a route from the route planner for stops in the order given by the TSP solver.

Allow user to add/remove stops, using betweenPairs to get any new distances required. This will require two requests to route/distances/betweenPairs, one for forward distances (1 x N, N x 1). For example, given an initial route of from = {1,2,3,4} and to={1,2,3,4}, to add stop 5, make the following two betweenPairs request:

from={1,2,3,4}, to={5}
from={5}, to={1,2,3,4}

[mraross]

To solve the Travelling Salesperson Problem, take a set of stops and the distances between all points then find the sequence of stops that minimizes total trip time or length. The distance between all points can be determined by a request to the route/betweenPairs resource with the same points in To and From.

Suggested algorithms for implementation:

Stochastic Fractal Search. See: https://www.researchgate.net/profile/Hamid_Salimi4/publication/265209712_Stochastic_Fractal_Search_A_powerful_metaheuristic_algorithm/links/5476a19e0cf2778985b08109.pdf https://www.mathworks.com/matlabcentral/fileexchange/47565-stochastic-fractal-search--sfs-

Encode candidate orderings using Random Keys See: https://deepblue.lib.umich.edu/bitstream/handle/2027.42/3481/ban1152.0001.001.pdf?sequence=5

[mraross]

"..., we can handle the uncapacitated vehicle routing problem. Here we create a gene for each load. Randomly generate an integer for each vehicle and add a uniform(0,1) deviate to sequence the stops. By sorting the random keys we get the loads assigned to vehicle 1, in the order they are to be delivered, followed by the loads on vehicle 2, etc."

Source: https://deepblue.lib.umich.edu/bitstream/handle/2027.42/3481/ban1152.0001.001.pdf?sequence=5

[cmhodgson]

I don't have a problem with Randomized keys; the example shows how they work with a genetic algorithm. I don't think they will work well with stochastic fractal search because small changes in the (initially random) genes will often cause no change at all in the performance of a given solution, as the numbers have to change enough to cause the ordering to be different. If you can't tell if you are getting warmer or colder at each step, you can't find what you are looking for by taking small steps in various directions. The randomized keys work with genetic algorithms because they swap entire chunks of genes, usually making significant numerical changes, very likely to change the sort order at each step.

But I will happily co-author the paper on how stochastic fractal search on randomized keys solves the TSP faster than any previous algorithm if it turns out to be so ;)

[mraross]

During developement, you can generate a random shortest distance/time matrix instead of calling betweenPairs. This defers the dependency on betweenPairs and speeds up testing when you want to generate an optimal route for many stops.

[cmhodgson]

This is an interesting approach... but it would be difficult to evaluate the solution (certainly you couldn't do it visually) - but another approach would be to just save the results of a betweenPairs call and reference the saved file instead of dynamically re-calculating each time. Once we start to need additional cases to test, we may just have to wait for the router... but we could similarly save the results if they are interesting enough to re-run in the future.

[mraross]

Here is a ballpark estimate on evolutionary TSP runtimes:

the running time of the algorithm was reasonable:
below 3 seconds for problems with up to 100 cities, below 10 seconds for the test case of 144
cities, below 40 seconds for the test case with 280 cities.

Source: https://pdfs.semanticscholar.org/9757/3990337a3a26e3947488210dddc9a8d29de2.pdf

[cmhodgson]

Alternatively this could be done on the server side using open source jsprit library.

[mraross]

Abstract Routing Models and Abstractions in the Context of Vehicle Routing https://www.ijcai.org/Proceedings/15/Papers/374.pdf

A Random-Key Genetic Algorithm for the Generalized Traveling Salesman Problem http://www.lehigh.edu/~lvs2/Papers/gtsp.pdf

A Comparative Study of Vehicles’ Routing Algorithms for Route Planning in Smart Cities http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.700.6873&rep=rep1&type=pdf

Comprehensive review of swarm optimization algorithms http://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0122827&type=printable

Opportunistic Self Organizing Migrating Algorithm for Real-Time Dynamic Traveling Salesman Problem https://arxiv.org/pdf/1709.03793.pdf

TSP by DE with local search https://www.researchgate.net/publication/224393599_Discrete_Differential_Evolution_with_local_search_to_solve_the_Traveling_Salesman_Problem_Fundamentals_and_case_studies

Orthogonal crossover in DE https://pdfs.semanticscholar.org/b9ac/f3344c6a45aa89ce5a1bc94fb322ca880dd1.pdf

A Novel Differential Evolution with Uniform Design for Continuous Global Optimization https://pdfs.semanticscholar.org/4f74/1fd9a955f23cebd2afd01e91c137aa2cbe46.pdf

Random-Key Cuckoo Search for the Travelling Salesman Problem https://arxiv.org/abs/1607.04324

Hierarchical Solution of the Traveling Salesman Problem with Random Dyadic Tilings http://www.fundatema.hu/static/uploads/dyadictilingbakbendeguz[15421].pdf

Effective Neighborhood Structures for the Generalized Traveling Salesman Problem https://www.ac.tuwien.ac.at/files/pub/hu-08.pdf

An Experimental Comparison of Biased and Unbiased Random Key Genetic Algorithms https://repositorio.inesctec.pt/bitstream/123456789/3624/1/P-009-TYV.pdf

Alternative Method for Solving Traveling Salesman Problem by Evolutionary Algorithm http://www.ef.uns.ac.rs/mis/archive-pdf/2008%20-%20No1/MIS2008_1_3.pdf

Efficient Constraint Handling in Electromagnetism-Like Algorithm for Traveling Salesman Problem with Time Windows https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3958671/pdf/TSWJ2014-871242.pdf

A New Method to Solve the Multi Traveling Salesman Problem with the Combination of Genetic Algorithm and Clustering Technique http://paper.ijcsns.org/07_book/201705/20170529.pdf

An O (log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem https://web.stanford.edu/~saberi/atsp.pdf

On the Differential Evolution for Vehicle Routing Problem http://www.softcomputing.net/socparpaper90.pdf

Pareto Local Optimum Sets in the Biobjective Traveling Salesman Problem: An Experimental Study http://www.metaheuristics.net/downloads/MOMH.TSP.pdf

Differential Evolution with Self Adaptive Local Search http://danushka.net/papers/noman_GECCO_2011.pdf

Differential Evolution using Quadratic Interpolation for Initializing the Population https://pdfs.semanticscholar.org/8a0f/722910593f974571e3f2d05ab2b8b31c18d8.pdf

Gaussian Barebones Differential Evolution with Random-type Gaussian Mutation Strategy http://www.hrpub.org/download/20161030/UJCA2-15007700.pdf

Biased random-key genetic algorithms for combinatorial optimization https://edisciplinas.usp.br/pluginfile.php/2276712/mod_resource/content/1/Biased%20random-key%20genetic%20algorithms%20for%20combinatorial%20optimization.pdf

INTEGRATED VEHICLE ROUTING AND ROSTERING FOR THE HOME HEALTH CARE SERVICES https://rtime.felk.cvut.cz/~hanzalek/publications/Hanzalek10_169603.pdf