K短路徑（k-shortest paths）問題應用非常廣泛，包含實際路線應用、排程的問題、最佳化問題等…。考慮禁止路徑（forbidden path）的最短路徑問題（SPPFP, shortest path problem with forbidden paths）即是一個具有限制的最短路徑問題，這些限制來自有一禁止路徑的集合，我們所找出的最短路徑裡不能有任何路徑包含禁止路徑集合中的任一路徑作為子路徑。SPPFP可以被用來解決難以被模組化的路徑限制、實作精確的分支結構等…。
Villeneuve和Desaulniers所提出的論文[18]是第一篇將SPPFP歸併到K短路徑問題的論文。本篇論文主要是提出了一個增進效能的演算法去改進Villeneuve和Desaulniers所提出的禁止路徑演算法，經由節點的合併可降低後續步驟所需的執行時間。同時Villeneuve和Desaulniers的演算法在某種特定的情況下其實無法完整地禁止掉所有路徑，但本論文可在不增加時間複雜度的情況下修正這個錯誤。

The applications of k-shortest paths are very wide, including choosing an actual path in our life, scheduling problems, optimization problems, and so on. The shortest path problem with forbidden paths (SPPFP) considers diverse constrained shortest problems to which a finite set of forbidden paths are attached. The solution of the problem cannot include any path in the set of forbidden paths as a portion. SPPFP may be used to solve the problems with hard-to-modeled path constraints or to implement exact branching scheme.
The method proposed by Villeneuve and Desaulniers [18] is the first accomplishment that reduces SPPFP to a k-shortest paths problem. This paper presents an algorithm which reduces execution time of solving the SPPFP problem via combination of nodes. Therefore, it improves the approach proposed by Villeneuve and Desaulniers. Moreover, in some cases, Villeneuve and Desaulniers`s approach cannot provide the forbidden paths completely. However, the proposed method can fix it without increasing time complexity.

[1]　Aho, A. V., and Corasick, M. J., “Efficient string matching: An aid to bibliographic search”, Journal of the ACM, 18 (6), 333-340, 1975.
[2]　Arunapuram S., Mathur K., and Solow D., “Vehicle routing and scheduling with full truck loads”, Transportation Science, 37, 170-182, 2003.
[3]　Azevedo J. A., Costa M. E. O. S., Madeira J. J. E. S., and Martins E. Q. V., “An algorithm for the ranking of shortest paths”, European Journal of Operational Research, 69, 97-106, 1993.
[4]　Chauny F., Ratsirahonana L., and Savard G., “A model and column generation algorithm for the aircraft loading problem”, Les Cahiers du GERAD G-2000-68, Ecole des Hautes Etudes Commerciales, Montreal, 2000.
[5]　Chen Y. L., and Yang H. H., “Finding the first k shortest paths in a time-window network”, Computers and Operations Research, 31, 499-513, 2004.
[6]　Coutinho-Rodrigues J. M., Climaco J. C. N., and Current J. R., “An interactive bi-objective shortest path approach: searching for unsupported nondominated solutions”, Computers and Operations Research, 26, 789-798, 1999.
[7]　Desaulniers G., Langevin A., Riopel D., and Villeneuve B., “Dispatching and conflict-free routing of automated guided vehicles: An exact approach”, Les Cahiers du GERAD G-2002-31, Ecole des Hautes Etudes Commerciales, Montreal. International Journal of Flexible Manufacturing Systems, in press, 2002.
[8]　Eppstein D., “Finding the k shortest paths”, SIAM Journal on Computing, 18(2), 652-673, 1999.
[9]　Gustafsson T., “A heuristic approach to column generation for airline crew scheduling”, Licentiate thesis, Chalmers University of Technology and Goteborg University, S-412 96 Goteborg, Sweden, 1999.
[10]　Handler G. Y., and Zang I. A., “A dual algorithm for the constrained shortest path problem”, Networks, 10, 293-310, 1980.
[11]　Hansen P., and Jaumard B., de Aragao M. P., “Un algorithme primal de programmation lineaire generalisee pourles programmes mixtes”, Comptes Rendus de 1`Academie des Sciences, 313, 557-560, 1991 (in French).
[12]　Hoffman W., and Pavley R., “A method for the solution of the N`th best path problem”, Journal of the Association for Computing Machinery, 6, 506-5014, 1959.
[13]　Jimenez V. M., and Marzal A., “Computing the k shortest paths: a new algorithm and an experimental comparison”, Lecture notes in computer Science, 1688, 15-29, 1999.
[14]　Katoh N., Ibaraki T., and Mine H., “An efficient algorithm for k shortest simple paths”, Networks, 12, 411-427, 1982.
[15]　Lawler E. L., “Aprocedure for computing the k best solutions to discrete optimization problems and its application to the shortest path”, Management Science, 18(7), 401-405, 1972.
[17]　Martins E.Q.V., “An algorithm for ranking paths that may contain cycles”, European Journal of Operational Research, 18, 123-130, 1984.
[18] Villeneuve D., and Desaulniers G., “The shortest path problem with forbidden paths”, European Journal of Operational Research, 165, 97-107, 2005.
[19]　Yang H. H., and Chen Y. L., “Finding k shortest looping paths in a traffic-light network”, Computers and Operations Research, 32, 571-581, 2005.
[20]　Yang H. H., and Chen Y. L., “Finding K shortest looping paths with waiting time in a time-windows network”, Applied Mathematical Modelling, 30, 458-465, 2006.
[21]　Yen Y. J., “Finding the k shortest loopless paths in a network”, Management Science, 17(11), 712-716, 1971.
[22]　Zijpp N. J., and Catalano S. F., “Path enumeration by finding the constrained k-shortest paths”, Transport Research B, 39, 545-563, 2005.