Computational experiments with a lazy version of a K quickest simple path ranking algorithm

作     者：Pascoal, M. Captivo, M. E. Climaco, J. C. 

作者机构：Univ Coimbra Fac Ciencias & Tecnol CIS Dept Matemat P-3001454 Coimbra Portugal Univ Lisbon Fac Ciencias DEIO CIO P-1749016 Lisbon Portugal Univ Coimbra Fac Econ P-3004512 Coimbra Portugal Inst Engn Sistemas & Computadores Coimbra P-3000033 Coimbra Portugal 

出 版 物：《TOP》 (TOP：西班牙统计学与运筹学学会杂志)

年 卷 期：2007年第15卷第2期

页      面：372-382页

核心收录：

学科分类：0202[经济学-应用经济学] 02[经济学] 020208[经济学-统计学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 0714[理学-统计学（可授理学、经济学学位）] 

主　　题：graph algorithms networks quickest path ranking 

摘      要：The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time. Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509-520, 2005;Rosen et al. in Comput. Oper. Res. 18(6):571-584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen in Inf. Process. Lett. 50:89-92, 1994), and afterwards selecting the K quickest ones. After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper. Res. 147(l):5-21, 2006). This is a lazy version of Chen s algorithm, able to interchange the calculation of new simple paths and the output of each k-quickest simple path. Finally, the described algorithm is computationally compared to its former version, as well as to deviation algorithms.