search

torressa / cspy

A collection of algorithms for the (Resource) Constrained Shortest Path problem in Python / C++ / C#
https://torressa.github.io/cspy/
MIT License
77 stars 24 forks source link

Speed ups: Heuristics (Tabu and GreedyElim) #40

Closed torressa closed 3 years ago

torressa commented 4 years ago

The shortest path heuristic (used in both Tabu and GreedyElim) that deals with negative cycles is really slow.

Defined in https://github.com/torressa/cspy/blob/6ad0650e5baa27882594a0e4fe6a0c5835fb0504/cspy/algorithms/path_base.py#L88 Currently uses networkx.shortest_simple_paths function to filter the paths with negative reduced cost (if any) and returns the max_depth'th shortest path from this reduced set of paths.

Here are some ideas:

Preprocessing

Every time the function is called, some sort of preprocessing can be applied to remove the negative cycles and solve the problem using a standard algorithm. Not sure how this would work or if it would remove most of the good paths.

A* star based algorithm

  1. Remove negative edge weights
  2. Run the A* algorithm
  3. evaluate the path and stop if negative reduced cost or maximum number of iterations is exceeded.
  4. Remove current path, and return to step 2.

However, this seems pretty similar to the existing version and is probably going to be slower.

torressa commented 3 years ago

Faster in the latest release

torressa commented 3 years ago

Open discussion in #63

stale[bot] commented 3 years ago

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.