A note on detecting unbounded instances of the online shortest path problem. Issue 4 (18th January 2016)

• Record Type: Journal Article
• Authors: Boyles, Stephen D.; Rambha, Tarun
• Is Part Of: Networks. Volume 67:Issue 4(2016)
• Page Start: 270
• Page End: 276
• Publication Date: 2016-01-18
• Subjects: online routing -- recourse -- stochastic shortest paths -- policy iteration -- label correcting -- absorbing Markov chains -- negative arc costs; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21670
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : The online shortest path problem is a type of stochastic shortest path problem in which certain arc costs are revealed en route, and the path is updated accordingly to minimize expected cost. This note addresses the open problem of determining whether a problem instance admits a finite optimal solution in the presence of negative arc costs. We formulate the problem as a Markov decision process and show ways to detect such instances in the course of solving the problem using standard algorithms such as value and policy iteration. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(4), 270–276 2016