Numerous algorithms have been proposed for the well-known multi-constrained shortest path (MCSP) problem, but very few have good practical performance in case of two or more constraints. In this paper, we propose a new Lagrangian relaxation algorithm to solve a generalized version of the MCSP problem where we search for multiple shortest paths subject to multiple constraints. As in some related work, our algorithm first identifies the lower and upper bounds, and then tries to close the gap with a path enumeration procedure. However, our algorithm is based on the recognition that the Lagrange multipliers found by existing methods usually do not give the best search direction for minimizing path enumerations even though they can provide near-optimized lower bounds. We provide a solution to meet both of these goals, and incorporate feasibility checks into a state-of-the-art K-shortest paths algorithm to further reduce path enumerations. Through experiments on various networks including the most challenging benchmark instances, we show that our algorithm can solve a significantly larger number of instances to optimality with less computational cost, often by one or two orders of magnitude, when compared with the best known algorithm in the literature.

Finding a multi-constrained shortest path (MCSP) between a pair of nodes arises in many important applications such as quality of service provisioning in the next-generation network. While this problem subject to a single constraint has been well studied, efficient algorithms solving this problem with two or more constraints are still quite limited. In this paper, we propose a new Lagrangian relaxation algorithm for solving a generalized version of the MCSP problem, where we search for multiple shortest paths subject to multiple constraints. As in some related work, our algorithm first identifies the lower and upper bounds, and then tries to close the gap with a path enumeration procedure. However, our algorithm is based on the recognition that the Lagrange multipliers found by existing methods usually do not give the best search direction for minimizing path enumerations even though they can provide near-optimized lower bounds. We provide a solution to meet both of these goals. Through experiments on the most challenging benchmark instances, we show that our algorithm performs significantly better than the best known algorithm in the literature.

We propose a new exact algorithm for enumerating k shortest simple paths in a directed graph with n nodes and m edges. The algorithm has a complexity of and follows the same process as Yen's deviation algorithm, but the candidate paths are computed more efficiently using a node classification technique. We first show that a candidate path can be separated by its deviation node as prefix and suffix. Our algorithm then classifies the nodes as red, yellow, and green. A node on the prefix is assigned a red color, a node that can reach t (the destination node) through a shortest path without visiting a red node is assigned a green color, and all other nodes are assigned a yellow color. We prove that when searching for the suffix of a candidate path, all green nodes can be bypassed, and we only need to apply Dijkstra's algorithm to find an all‐yellow‐node subpath. Since on average the number of yellow nodes is much smaller than n, the new algorithm has a much lower average‐case running time. Experiments on many types of networks demonstrate that the new algorithm performs significantly better than existing exact algorithms that have polynomial worst‐case complexity. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(1), 6–17 2014

Finding${\mbi {k}}$shortest simple paths in a directed graph is a fundamental problem in many engineering applications. Most existing algorithms such as Yen’s algorithm and its variants have polynomial worst-case time complexity, but their average-case running time is very high. The heuristic algorithm MPS can run significantly faster in practice. However, it requires an excessive amount of memory space. In this paper, we provide a new heuristic algorithm that achieves high space efficiency while maintaining similar average-case running time. We first propose a sidetrack representation of path, with which a path can be stored in${\mbi {O}}{\bf (1)}$space. We then show how to categorize a candidate path as either partial or complete, and restrict the number of paths added to the queue. In addition, we provide an empirical equation that can very accurately predict the${\mbi {k}}$th shortest path length, provided that a much smaller number of shortest paths have been found. Extensive experiments prove that our algorithm can achieve an${\mbi {O(n)}}$speedup in practice over Yen’s algorithm. In comparison with MPS, it runs up to three times faster and uses less space by an order of magnitude.

Delay constrained multicast routing is a typical problem in many emerging applications such as voice over IP, video on demand and teleconferencing etc. Equivalently referred to as the delay constrained minimum Steiner tree (DCMST), this problem requires to find a tree spanning a source and a set of destination nodes such that the total cost is minimized while the delay from the source to each destination node is no more than a preset upper bound. Due to its NP-complete nature, all previous work focused on developing efficient heuristics. In this paper, we study this problem from a completely different perspective by using an exact approach, which has never been done before. Preliminary experimental results demonstrate that the exact algorithm described in this paper works surprisingly well, and in certain cases it outperforms some fast heuristics. Even though the exact algorithm is not expected to be used in practice, its relative high efficiency makes it possible of creating a set of benchmark instances for evaluating the performance of a heuristic most accurately. In addition, with the help of this algorithm, we are able to gain insight into some interesting properties of this problem, which in turn may help us to design more efficient heuristics.

Constrained minimum Steiner tree (CMST) problem is a key issue in multicast routing with quality of service (QoS) support. Many heuristics have been developed to solve this NP-complete problem. In recent years, some interesting work has been done to use the greedy randomized adaptive search procedure (GRASP) to solve this problem. While it helps to achieve very high success ratios of finding optimal solutions on networks of small or medium sizes (less than 100 nodes), a high computation time is also required, usually in the range of tens of seconds. Considering a normal call admission time is expected to be in the range of tens or hundreds of milliseconds and network sizes may become much larger, it is worth developing algorithms that can run faster while keeping the tree cost at an acceptable level. In this paper, an algorithm called GRASP-BSMA is proposed for such purpose. By using an efficient procedure to construct the initial feasible solution, together with the best implementation of the bounded shortest multicast algorithm (BSMA), the proposed algorithm well meets the expectations.

The development of efficient quality of service (QoS) routing algorithms in a high-speed networking or the next generation IP networking environment is a very important and at the same time very difficult task due to the need to provide divergent services with multiple QoS requirements. Recently, a heuristic algorithm H/spl I.bar/MCOP, which is based on a nonlinear Lagrange relaxation (NLR) technique, has been proposed to resolve the contradiction between the time complexity and the quality of solution. Even though H/spl I.bar/MCOP has demonstrated outstanding capability for finding feasible solutions to the multi-path constrained (MCP) problem, it has not exploited the full capability that an NLR-based technique could offer. In this paper, we propose a new NLR-based heuristic, in which the search process is interpreted from a probability perspective. Simulation results indicate that, in comparison with H/spl I.bar/MCOP, the proposed heuristic can achieve a significant performance improvement when it is used as a basic step for solving more complicated QoS routing problems.

The development of efficient quality of service (QoS) routing algorithms in a high-speed networking or the next generation IP networking environment is a very important and at the same time very difficult task due to the need to provide divergent services with multiple QoS requirements. Recently, a heuristic algorithm, H/spl I.bar/MCOP, which is based on a nonlinear Lagrange relaxation (NLR) technique, has been proposed to resolve the contradiction between the time complexity and the quality of solution. Even though H/spl I.bar/MCOP has demonstrated an outstanding capability of finding feasible solutions to the multipath constrained (MCP) problem, it has not exploited the full capability that an NLR-based technique could offer. We propose a new NLR-based heuristic, called NLR/spl I.bar/MCP, in which the search process is interpreted from a probability perspective. Simulation results indicate that NLR/spl I.bar/MCP can achieve a higher probability of finding feasible solutions than H/spl I.bar/MCOP. We also verify that the performance improvement of an MCP heuristic has a tremendous impact on the performance of a higher level heuristic that uses an MCP heuristic as the basic step.

Delay-constrained least cost (DCLC) path problem is a typical delay sensitive quality of service (QoS) routing problem. In this paper, we provide an explicit expression of the time complexity of a previously proposed heuristic NR-DCLC when delay and cost are integers. The expression indicates it compares favorably with other heuristics. We further describe a heuristic NR-DCLC-1toN to compute the DCLC paths from one source to all destinations satisfying the delay constraint. Simulations demonstrate that NR-DCLC-1toN can always find delay constrained paths with lower costs than the delay scaling algorithm (DSA), which is so far the best heuristic for such problem. Even though NR-DCLC-1toN needs higher execution time than DSA in some cases, it runs much faster than DSA in many other cases such as when the delay constraint has to be strictly guaranteed or when the delay and cost are distributed on large intervals.

Network services for finding a feasible or an optimal path subject to multiple constraints on performance metrics such as delay, jitter, loss probability, etc. give rise to multipath-constrained (MCP) or multiconstrained optimal-path (MCOP) quality of service (QoS) routing problems, which are NP-complete. Heuristic algorithm H/spl I.bar/MCOP proposed by Korkmaz et al. has been widely recognized for its low time complexity and high probability of finding feasible solutions. The performance of this heuristic is reinvestigated under several special cases. Simulation results indicate that in some cases its probability of finding feasible solutions is unexpectedly low. Such observation, which is further used to explain the performance of a heuristic based on H-MCOP, is of extreme importance when designing any higher-level QoS routing algorithms that need to use H/spl I.bar/MCOP to find feasible solutions.