On the Online Shortest Path Problem with Limited Arc Cost Dependencies

Abstract

This paper is concerned with the stochastic shortest path problem with recourse when limited forms of spatial and temporal arc cost dependencies are accounted for. Recourse is defined as the opportunity for a decision maker to reevaluate his or her remaining path when en-route information is available. Formulations with recourse typically provide opportunities for corrective actions when information becomes available; information here is modeled as arc cost dependencies, defined as spatial and temporal. System properties are stated and proved and solution algorithms are developed for limited cases of spatial and temporal arc cost dependencies. The numerical results verify some of the theoretical insights and demonstrate the applicability of the introduced algorithms. Show more