search

orientechnologies / orientdb

OrientDB is the most versatile DBMS supporting Graph, Document, Reactive, Full-Text and Geospatial models in one Multi-Model product. OrientDB can run distributed (Multi-Master), supports SQL, ACID Transactions, Full-Text indexing and Reactive Queries.
https://orientdb.dev
Apache License 2.0
4.74k stars 871 forks source link

Traveling salesman function in OrientDB #5005

Closed jmdavid closed 3 years ago

jmdavid commented 9 years ago

As OrientDB has already a dijkstra function, it would be nice to have a traveling salesman function in complement, using nearest neighbour algorithm: (see http://www.sanfoundry.com/java-program-implement-traveling-salesman-problem-using-nearest-neighbour-algorithm/) or, ideally, using a genetic algorithm (see http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5 and http://jgap.sourceforge.net/doc/salesman/TravellingSalesman.html).

Signature would be: travelingSalesman(sourceVertex, weightEdgeFieldName, maxNumberOfMutations, [toBeVisitedVertex1, toBeVisitedVertex2, ...])

Calculating the distance between every vertex could be done by calling dijkstra.

The return would be given toBeVisitedVertex in optimized order.

There are plenty of potential applications in the field (optimizing working routes, optimizing pick-ups, etc.).

lvca commented 9 years ago

:+1. Anybody would like to provide the first impl starting by cloning OSQLFunctionShortestPath?