A new heuristics for finding the delay constrained least cost path
Gang Cheng, Nirwan Ansari · 2004
We investigate the problem of finding the delay constrained least cost path (DCLC) in a network, which is NP-complete and has been extensively studied. Many proposed algorithms tackle this problem by transforming it into the shortest path selection problem or the k-shortest paths selection problem, which are NP-complete, with an integrated weight function that maps the delay and cost for each link into a single weight. However, they suffer from either high computational complexity or low success ratio in finding the optimal paths (the least cost path satisfying a given delay constraint). Based on the extended Bellman-Ford (EB) algorithm, we propose a high performance algorithm, dual extended Bellman-Ford (DEB) algorithm, which achieves a high success ratio in finding the least cost path subject to a delay constraint with low computational complexity. Extensive simulations show that DEB outperforms its contender on: the worst-case computational complexity; average cost of the solutions; the success ratio in finding the delay constrained least cost path.