Opened 5 years ago

Last modified 16 months 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 5 years ago by spimming

  • Status changed from new to assigned

comment:2 Changed 5 years ago by spimming

r8284 initial commit for route planning branch

comment:3 Changed 5 years ago by spimming

r8285

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

comment:4 Changed 5 years ago by spimming

r8290 core data types for osm graphs implemented

comment:5 Changed 5 years ago by spimming

r8291 missed vs project file on last commit

comment:6 Changed 5 years ago by 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

comment:7 Changed 5 years ago by spimming

r8300

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

comment:8 Changed 5 years ago by spimming

r8301

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

comment:9 Changed 5 years ago by spimming

r8302 added missing references

comment:10 Changed 5 years ago by spimming

r8308

  • 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 5 years ago by spimming

r8312 worked on Dijkstra algorithm

comment:12 Changed 5 years ago by spimming

r8314

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

comment:13 Changed 5 years ago by spimming

r8315 write result in gpx file for visualization

comment:14 Changed 5 years ago by spimming

r8316

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

comment:15 Changed 5 years ago by spimming

r8321 initial version of astar algorithm

comment:16 Changed 5 years ago by spimming

r8350

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

comment:17 Changed 5 years ago by spimming

r8356 error correction on AStar algorithm

comment:18 Changed 5 years ago by spimming

r8362 use dictionary to check if closed list contains node

comment:19 Changed 5 years ago by spimming

r8369

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

comment:20 Changed 5 years ago by spimming

r8408

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

comment:21 Changed 5 years ago by spimming

r8423

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

comment:22 Changed 5 years ago by spimming

r8426 various error fixed

comment:23 Changed 5 years ago by spimming

r8429

  • renamed Graph to OsmGraph
  • generic type in edge interface

comment:24 Changed 5 years ago by spimming

r8434

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

comment:25 Changed 5 years ago by spimming

r8438 graph interface and implementation initial commit

comment:26 Changed 5 years ago by spimming

r8461

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

comment:27 Changed 5 years ago by spimming

r8462

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

comment:28 Changed 5 years ago by spimming

r8479

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

comment:29 Changed 5 years ago by spimming

r8480

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

comment:30 Changed 5 years ago by spimming

r8481

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

comment:31 Changed 5 years ago by 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

comment:32 Changed 5 years ago by spimming

r8504 new read data method using NameTable for better performance

comment:33 Changed 5 years ago by 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

comment:34 Changed 5 years ago by spimming

r8512 tweaking of max edge speeds and heuristic cost function

comment:35 Changed 5 years ago by spimming

r8514 experimented with different settings in cost and heuristic function

comment:36 Changed 5 years ago by spimming

r8516

  • solution restructured
  • removed obsolete and outdated parts

comment:37 Changed 5 years ago by 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

comment:38 Changed 5 years ago by spimming

r8527

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

comment:39 Changed 5 years ago by spimming

r8539

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

comment:40 Changed 5 years ago by spimming

r8540 fixed assignment issue in BinaryHeap

comment:41 Changed 5 years ago by spimming

r8541 renamed heap implementations

comment:42 Changed 5 years ago by spimming

r8546

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

comment:43 Changed 5 years ago by spimming

r8572 FibonacciHeap implementation added

comment:44 Changed 5 years ago by spimming

r8640

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

comment:45 Changed 4 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 4 years ago by gkronber

Please accept this ticket.

comment:47 Changed 4 years ago by spimming

  • Status changed from assigned to accepted

comment:48 Changed 3 years ago by ascheibe

  • Owner changed from spimming to ascheibe
  • Status changed from accepted to assigned

comment:49 Changed 16 months ago by ascheibe

  • Owner changed from ascheibe to swagner
Note: See TracTickets for help on using tickets.