search

Xavier-MaYiMing / The-labeling-algorithm-for-the-shortest-path-problem-with-time-windows

The labeling algorithm for the shortest path problem with time windows.
7 stars 0 forks source link

Computational Capacity #1

Open AGMA71997 opened 2 months ago

AGMA71997 commented 2 months ago

Hey,

Thanks for the implementation, but what is the maximum instance size (no. of nodes) for which this implementation is capable of delivering solutions within a short time (lets say a few seconds)?

Kind regards, Abdo

Xavier-MaYiMing commented 2 months ago

Dear Abdo,

The CPU time is influenced by instance characteristics, such as the degree, graph structure, and time-window constraints. In my tests with randomly generated instances, including up to 10,000 vertices and 50,000 edges, the average CPU time was 24.29 seconds on a computer equipped with 32 GB of RAM and an Apple M2 Pro CPU. However, since SPPTW is NP-hard, solving larger instances efficiently may require heuristics or reinforcement learning approaches to produce good solutions within a reasonable time frame.

Additionally, I've refined the code for SPPTW.

Best regards, Xavier