Opened 6 years ago
Last modified 2 years ago
#1894 assigned feature request
Exact Route Planning Algorithms (Dijkstra, A*)
Reported by: | spimming | Owned by: | swagner |
---|---|---|---|
Priority: | medium | Milestone: | HeuristicLab 3.3.x Backlog |
Component: | Algorithms | Version: | branch |
Keywords: | Cc: |
Description
Solve route planning problems (point-to-point) using algorithms like Dykstra and A*. Use the OSM data format to import graphs.
Change History (49)
comment:1 Changed 6 years ago by spimming
- Status changed from new to assigned
comment:2 Changed 6 years ago by spimming
comment:3 Changed 6 years ago by spimming
- updated references and plugin dependencies
- initial stub version of RoutePlanningProblem implementation
comment:4 Changed 6 years ago by spimming
r8290 core data types for osm graphs implemented
comment:5 Changed 6 years ago by spimming
r8291 missed vs project file on last commit
comment:6 Changed 6 years ago by spimming
- new default constructor for osm base types
- defined common interface for data sources
- implemented xml data source
- added test project with osm test files
comment:7 Changed 6 years ago by spimming
- graph data structures added
- method to get the ways for a specific node
comment:8 Changed 6 years ago by spimming
- graph routing algorithm plugin initial commit
- load data in problem
comment:9 Changed 6 years ago by spimming
r8302 added missing references
comment:10 Changed 6 years ago by spimming
- get neighbors for specific node
- method to calculate weight between two nodes
- interface for router
- Dijkstra algorithm initial commit
- Utils methods added
comment:11 Changed 6 years ago by spimming
r8312 worked on Dijkstra algorithm
comment:12 Changed 6 years ago by spimming
- error correction on Dijkstra algorithm
- test program adapted
- new test graph file added
comment:13 Changed 6 years ago by spimming
r8315 write result in gpx file for visualization
comment:14 Changed 6 years ago by spimming
- check if way has missing node references
- check if attribute exists before using it
- test program restructured
comment:15 Changed 6 years ago by spimming
r8321 initial version of astar algorithm
comment:16 Changed 6 years ago by spimming
- new implementation for priority queue
- based on heap data structure
- allow multiple keys
- adapted test program
comment:17 Changed 6 years ago by spimming
r8356 error correction on AStar algorithm
comment:18 Changed 6 years ago by spimming
r8362 use dictionary to check if closed list contains node
comment:19 Changed 6 years ago by spimming
- consider driving directions (one way roads) and
- check if edges (ways) can be traversed
comment:20 Changed 6 years ago by spimming
- restructured test program
- new, faster version of AStar algorithm
- moved method to obtain edge max speed to way
comment:21 Changed 6 years ago by spimming
- bidirectional version of Dijkstra algorithm
- method to get neighbors of a node in reversed order
- check for roundabouts in OneWay property
comment:22 Changed 6 years ago by spimming
r8426 various error fixed
comment:23 Changed 6 years ago by spimming
- renamed Graph to OsmGraph
- generic type in edge interface
comment:24 Changed 6 years ago by spimming
- renamed old Vertex<T> to OsmVertex<T>
- added new Vertex class
comment:25 Changed 6 years ago by spimming
r8438 graph interface and implementation initial commit
comment:26 Changed 6 years ago by spimming
- Implemented interface IGraph in Graph
- Equals method in vertex modified
- Equals method in Edge implemented
- New algorithm version for IGraph
comment:27 Changed 6 years ago by spimming
- calculate distance in kilometers for two locations
- generate IGraph from a datasource
- adapted test program
comment:28 Changed 6 years ago by spimming
- temporarily added weight and heuristic function to graph
- store category information and max speed with edge
- adapted Distance method
comment:29 Changed 6 years ago by spimming
- fixed problem with edge category in XmlDataSource
- initial version for new DIMACS data source
comment:30 Changed 6 years ago by spimming
- adapted AStar and Dijkstra algorithms for new graph representation
- test program modified
comment:31 Changed 6 years ago by spimming
- 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
comment:32 Changed 6 years ago by spimming
r8504 new read data method using NameTable for better performance
comment:33 Changed 6 years ago by spimming
- 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
comment:34 Changed 6 years ago by spimming
r8512 tweaking of max edge speeds and heuristic cost function
comment:35 Changed 6 years ago by spimming
r8514 experimented with different settings in cost and heuristic function
comment:36 Changed 6 years ago by spimming
- solution restructured
- removed obsolete and outdated parts
comment:37 Changed 6 years ago by spimming
- 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
comment:38 Changed 6 years ago by spimming
- introduced heap interface
- various heap implementation used as priority queues
- very simple logger added
- various versions of Astar algorithm
comment:39 Changed 6 years ago by spimming
- Dijkstra version with no decrease key
- used wrong index in BinHeap implementation
- implement interface in BinaryHeap
comment:40 Changed 6 years ago by spimming
r8540 fixed assignment issue in BinaryHeap
comment:41 Changed 6 years ago by spimming
r8541 renamed heap implementations
comment:42 Changed 6 years ago by spimming
- fast binary heap added
- 4-ary heap added
- FibonacciHeap initial commit
comment:43 Changed 6 years ago by spimming
r8572 FibonacciHeap implementation added
comment:44 Changed 6 years ago by spimming
- Included costCalculator in a star search
- restructured and renamed Dijkstra algorithm
- Added code comments to FibonacciHeap
comment:45 Changed 5 years ago by gkronber
- Component changed from ### Undefined ### to Algorithms
- Summary changed from Route Planning to Exact Route Planning Algorithms (Dijkstra, A*)
comment:46 Changed 5 years ago by gkronber
Please accept this ticket.
comment:47 Changed 5 years ago by spimming
- Status changed from assigned to accepted
comment:48 Changed 5 years ago by ascheibe
- Owner changed from spimming to ascheibe
- Status changed from accepted to assigned
comment:49 Changed 2 years ago by ascheibe
- Owner changed from ascheibe to swagner
r8284 initial commit for route planning branch