Exact Route Planning Algorithms (Dijkstra, A*)

[spimming]

Solve route planning problems (point-to-point) using algorithms like Dykstra and A*. Use the OSM data format to import graphs.

[spimming]

r8284 initial commit for route planning branch

[spimming]

r8285

• updated references and plugin dependencies
• initial stub version of RoutePlanningProblem implementation

[spimming]

r8290 core data types for osm graphs implemented

[spimming]

r8291 missed vs project file on last commit

[spimming]

r8293

• new default constructor for osm base types
• defined common interface for data sources
• implemented xml data source
• added test project with osm test files

[spimming]

r8300

• graph data structures added
• method to get the ways for a specific node

[spimming]

r8301

• graph routing algorithm plugin initial commit
• load data in problem

[spimming]

r8302 added missing references

[spimming]

r8308

• get neighbors for specific node
• method to calculate weight between two nodes
• interface for router
• Dijkstra algorithm initial commit
• Utils methods added

[spimming]

r8312 worked on Dijkstra algorithm

[spimming]

r8314

• error correction on Dijkstra algorithm
• test program adapted
• new test graph file added

[spimming]

r8315 write result in gpx file for visualization

[spimming]

r8316

• check if way has missing node references
• check if attribute exists before using it
• test program restructured

[spimming]

r8321 initial version of astar algorithm

[spimming]

r8350

• new implementation for priority queue
• based on heap data structure
• allow multiple keys
• adapted test program

[spimming]

r8356 error correction on AStar algorithm

[spimming]

r8362 use dictionary to check if closed list contains node

[spimming]

r8369

• consider driving directions (one way roads) and
• check if edges (ways) can be traversed

[spimming]

r8408

• restructured test program
• new, faster version of AStar algorithm
• moved method to obtain edge max speed to way

[spimming]

r8423

• bidirectional version of Dijkstra algorithm
• method to get neighbors of a node in reversed order
• check for roundabouts in OneWay property

[spimming]

r8426 various error fixed

[spimming]

r8429

• renamed Graph to OsmGraph
• generic type in edge interface

[spimming]

r8434

• renamed old Vertex<T> to OsmVertex<T>
• added new Vertex class

[spimming]

r8438 graph interface and implementation initial commit

[spimming]

r8461

• Implemented interface IGraph in Graph
• Equals method in vertex modified
• Equals method in Edge implemented
• New algorithm version for IGraph

[spimming]

r8462

• calculate distance in kilometers for two locations
• generate IGraph from a datasource
• adapted test program

[spimming]

r8479

• temporarily added weight and heuristic function to graph
• store category information and max speed with edge
• adapted Distance method

[spimming]

r8480

• fixed problem with edge category in XmlDataSource
• initial version for new DIMACS data source

[spimming]

r8481

• adapted AStar and Dijkstra algorithms for new graph representation
• test program modified

[spimming]

r8488

• introduced weight property in Edge
• new data source implementation for DIMACS graphs
• lightweight data source implementation for osm graphs
• cost calculator interface and implementations added

[spimming]

r8504 new read data method using NameTable for better performance

[spimming]

r8509

• Dijkstra: get node with a specific rank
• graph interface extended: get vertices
• fixed bug in ReadData method
• methods to perform routing algorithm benchmark added to test program

[spimming]

r8512 tweaking of max edge speeds and heuristic cost function

[spimming]

r8514 experimented with different settings in cost and heuristic function

[spimming]

r8516

• solution restructured
• removed obsolete and outdated parts

[spimming]

r8520

• extended datasource interface to get routing graph for a specific vehicle type
• use ICostCalculator to calculate edge weights
• moved common enums in own file
• removed method to estimate cost from graph; use ICostCalculator

[spimming]

r8527

• introduced heap interface
• various heap implementation used as priority queues
• very simple logger added
• various versions of Astar algorithm

[spimming]

r8539

• Dijkstra version with no decrease key
• used wrong index in BinHeap implementation
• implement interface in BinaryHeap

[spimming]

r8540 fixed assignment issue in BinaryHeap

[spimming]

r8541 renamed heap implementations

[spimming]

r8546

• fast binary heap added
• 4-ary heap added
• FibonacciHeap initial commit

[spimming]

r8572 FibonacciHeap implementation added

[spimming]

r8640

• Included costCalculator in a star search
• restructured and renamed Dijkstra algorithm
• Added code comments to FibonacciHeap

[gkronber]

Please accept this ticket.