search

bcgov / ols-router

BC Advanced Route Planner
https://bcgov.github.io/ols-router/
Apache License 2.0
24 stars 11 forks source link

Select and implement most promising advanced routing algorithms #24

Closed mraross closed 1 year ago

mraross commented 6 years ago

@mraross commented on Mon Mar 26 2018

  1. Evaluate existing algorithms that support dynamic and time-dependent route planning with user preferences and make a recommendation.

  2. Evaluate existing timetable-based routing algorithms to support ferry routing and make a recommendation.

  3. Determine how to best integrate recommended algorithms.

  4. Write up findings and recommendations in an Advanced Routing Algorithm Evaluation document

  5. Implement recommended algorithms

@mraross commented on Fri Jun 01 2018

Issue moved to bcgov/ols-router #2 via ZenHub

@mraross commented on Fri Jun 01 2018

Issue moved to bcgov/ols-router #4 via ZenHub

cmhodgson commented 6 years ago

Promising implementation approaches include:

Dynamic Time-Dependent Routing in Road Networks Through Sampling (TD-S+P) http://drops.dagstuhl.de/opus/volltexte/2017/7897/pdf/OASIcs-ATMOS-2017-3.pdf

Dynamic, time-dependent route planning in road networks with user preferences (TDCRP) https://arxiv.org/pdf/1512.09132

Fast Exact Shortest Path and Distance Queries on Road Networks with Parameterized Costs (Generalized PRP) https://arxiv.org/pdf/1509.03165.pdf

Hierarchical Time-Dependent Shortest Path Algorithms for Vehicle Routing under ITS https://www.eecis.udel.edu/lena/files/iie16_lena.pdf

Each of these approaches has a deep set of cited references which cover the other algorithms at the root of the complete approaches, many of which are linked to from #25 .

mraross commented 3 years ago

Route planner uses the jsprit open source library for solving the TSP (e.g. optimal ordering of stops in a single route). jSprit uses the Ruin and recreate algorithm. Here's a discussion of Ruin and recreate algorithm in jSprit repo: https://github.com/graphhopper/jsprit/blob/master/docs/Meta-Heuristic.md

Original paper on Ruin and recreate algorithm (2000) http://polymorphe.free.fr/cours/ia/tsp/schrimpf-record_breaking_opt_ruin_recreate.pdf

Slack induction by string removal for VRP (2018). Recent improved implementation of Ruin and Recreate. https://lirias.kuleuven.be/retrieve/545845

A general heuristic for VRP problems https://backend.orbit.dtu.dk/ws/portalfiles/portal/3154462/A+general+heuristic+for+vehicle+routing+problems_TechRep_Pisinger_Ropke.pdf