search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
32 stars 15 forks source link

Exact Route Planning Algorithms (Dijkstra, A*) #1894

Open HeuristicLab-Trac-Bot opened 11 years ago

HeuristicLab-Trac-Bot commented 11 years ago

Issue migrated from trac ticket # 1894

milestone: HeuristicLab 3.3.x Backlog | component: Algorithms | priority: medium

2012-07-11 12:19:18: @spimminger created the issue

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

HeuristicLab-Trac-Bot commented 11 years ago

2012-07-11 12:21:02: @spimminger changed status from new to assigned

HeuristicLab-Trac-Bot commented 11 years ago

2012-07-11 13:10:35: @spimminger commented

r8284 initial commit for route planning branch

HeuristicLab-Trac-Bot commented 11 years ago

2012-07-11 15:54:31: @spimminger commented

r8285

  • updated references and plugin dependencies
  • initial stub version of RoutePlanningProblem implementation
HeuristicLab-Trac-Bot commented 11 years ago

2012-07-12 19:53:11: @spimminger commented

r8290 core data types for osm graphs implemented

HeuristicLab-Trac-Bot commented 11 years ago

2012-07-12 20:05:58: @spimminger commented

r8291 missed vs project file on last commit

HeuristicLab-Trac-Bot commented 11 years ago

2012-07-16 15:42:51: @spimminger commented

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
HeuristicLab-Trac-Bot commented 11 years ago

2012-07-18 12:57:04: @spimminger commented

r8300

  • graph data structures added
  • method to get the ways for a specific node
HeuristicLab-Trac-Bot commented 11 years ago

2012-07-18 16:15:41: @spimminger commented

r8301

  • graph routing algorithm plugin initial commit
  • load data in problem
HeuristicLab-Trac-Bot commented 11 years ago

2012-07-18 16:20:34: @spimminger commented

r8302 added missing references

HeuristicLab-Trac-Bot commented 11 years ago

2012-07-19 19:45:09: @spimminger commented

r8308

  • get neighbors for specific node
  • method to calculate weight between two nodes
  • interface for router
  • Dijkstra algorithm initial commit
  • Utils methods added
HeuristicLab-Trac-Bot commented 11 years ago

2012-07-20 11:20:02: @spimminger commented

r8312 worked on Dijkstra algorithm

HeuristicLab-Trac-Bot commented 11 years ago

2012-07-20 18:58:50: @spimminger commented

r8314

  • error correction on Dijkstra algorithm
  • test program adapted
  • new test graph file added
HeuristicLab-Trac-Bot commented 11 years ago

2012-07-20 22:57:28: @spimminger commented

r8315 write result in gpx file for visualization

HeuristicLab-Trac-Bot commented 11 years ago

2012-07-21 23:50:20: @spimminger commented

r8316

  • check if way has missing node references
  • check if attribute exists before using it
  • test program restructured
HeuristicLab-Trac-Bot commented 11 years ago

2012-07-24 17:41:36: @spimminger commented

r8321 initial version of astar algorithm

HeuristicLab-Trac-Bot commented 11 years ago

2012-07-27 16:35:14: @spimminger commented

r8350

  • new implementation for priority queue
  • based on heap data structure
  • allow multiple keys
  • adapted test program
HeuristicLab-Trac-Bot commented 11 years ago

2012-07-30 13:32:42: @spimminger commented

r8356 error correction on AStar algorithm

HeuristicLab-Trac-Bot commented 11 years ago

2012-07-30 17:34:07: @spimminger commented

r8362 use dictionary to check if closed list contains node

HeuristicLab-Trac-Bot commented 11 years ago

2012-07-31 12:53:16: @spimminger commented

r8369

  • consider driving directions (one way roads) and
  • check if edges (ways) can be traversed
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-03 15:04:48: @spimminger commented

r8408

  • restructured test program
  • new, faster version of AStar algorithm
  • moved method to obtain edge max speed to way
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-07 10:52:26: @spimminger commented

r8423

  • bidirectional version of Dijkstra algorithm
  • method to get neighbors of a node in reversed order
  • check for roundabouts in OneWay property
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-07 15:35:15: @spimminger commented

r8426 various error fixed

HeuristicLab-Trac-Bot commented 11 years ago

2012-08-08 13:40:27: @spimminger commented

r8429

  • renamed Graph to OsmGraph
  • generic type in edge interface
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-08 14:13:34: @spimminger commented

r8434

  • renamed old Vertex to OsmVertex
  • added new Vertex class
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-08 16:58:13: @spimminger commented

r8438 graph interface and implementation initial commit

HeuristicLab-Trac-Bot commented 11 years ago

2012-08-09 16:17:51: @spimminger commented

r8461

  • Implemented interface IGraph in Graph
  • Equals method in vertex modified
  • Equals method in Edge implemented
  • New algorithm version for IGraph
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-09 16:20:26: @spimminger commented

r8462

  • calculate distance in kilometers for two locations
  • generate IGraph from a datasource
  • adapted test program
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-13 17:31:39: @spimminger commented

r8479

  • temporarily added weight and heuristic function to graph
  • store category information and max speed with edge
  • adapted Distance method
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-13 17:35:30: @spimminger commented

r8480

  • fixed problem with edge category in XmlDataSource
  • initial version for new DIMACS data source
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-13 17:37:17: @spimminger commented

r8481

  • adapted AStar and Dijkstra algorithms for new graph representation
  • test program modified
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-14 14:32:15: @spimminger commented

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
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-20 11:39:35: @spimminger commented

r8504 new read data method using NameTable for better performance

HeuristicLab-Trac-Bot commented 11 years ago

2012-08-20 17:33:24: @spimminger commented

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
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-21 13:41:35: @spimminger commented

r8512 tweaking of max edge speeds and heuristic cost function

HeuristicLab-Trac-Bot commented 11 years ago

2012-08-21 15:54:24: @spimminger commented

r8514 experimented with different settings in cost and heuristic function

HeuristicLab-Trac-Bot commented 11 years ago

2012-08-22 11:46:49: @spimminger commented

r8516

  • solution restructured
  • removed obsolete and outdated parts
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-22 19:15:10: @spimminger commented

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
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-27 16:38:29: @spimminger commented

r8527

  • introduced heap interface
  • various heap implementation used as priority queues
  • very simple logger added
  • various versions of Astar algorithm
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-29 18:19:35: @spimminger commented

r8539

  • Dijkstra version with no decrease key
  • used wrong index in BinHeap implementation
  • implement interface in BinaryHeap
HeuristicLab-Trac-Bot commented 11 years ago

2012-08-30 11:20:53: @spimminger commented

r8540 fixed assignment issue in BinaryHeap

HeuristicLab-Trac-Bot commented 11 years ago

2012-08-30 11:25:52: @spimminger commented

r8541 renamed heap implementations

HeuristicLab-Trac-Bot commented 11 years ago

2012-08-30 16:25:11: @spimminger commented

r8546

  • fast binary heap added
  • 4-ary heap added
  • FibonacciHeap initial commit
HeuristicLab-Trac-Bot commented 11 years ago

2012-09-04 18:26:56: @spimminger commented

r8572 FibonacciHeap implementation added

HeuristicLab-Trac-Bot commented 11 years ago

2012-09-13 10:35:18: @spimminger commented

r8640

  • Included costCalculator in a star search
  • restructured and renamed Dijkstra algorithm
  • Added code comments to FibonacciHeap
HeuristicLab-Trac-Bot commented 10 years ago

2013-07-16 19:28:21: @gkronber changed component from ### Undefined ### to Algorithms

HeuristicLab-Trac-Bot commented 10 years ago

2013-07-16 19:28:21: @gkronber changed title from Route Planning to Exact Route Planning Algorithms (Dijkstra, A)*

HeuristicLab-Trac-Bot commented 10 years ago

2013-07-22 18:54:21: @gkronber commented

Please accept this ticket.

HeuristicLab-Trac-Bot commented 10 years ago

2013-07-29 13:07:57: @spimminger changed status from assigned to accepted

HeuristicLab-Trac-Bot commented 10 years ago

2014-06-04 17:16:37: @Shabbafru changed status from accepted to assigned

HeuristicLab-Trac-Bot commented 10 years ago

2014-06-04 17:16:37: @Shabbafru changed owner from @spimminger to @Shabbafru