This paperc onsidersS tochasticS hortestP ath( SSP)p roblemsi n probabilisticn etworks.A variety of approaches have already been proposed in the literature. However, unlike in the deterministic case, they are related to distinct models, interpretationsa nd applications.W e have chosent o look at the case where detours from the original path must be taken whenever the "first-choice" arc fails. The main results obtained include the proof of some counterintuitive facts (e.g., the SSP may contain a cycle), the proof of the validity of applying stochasticp rogrammingt o this problem and the proof that the computational complexity of a particular SSP problem is polynomial.

Stochastic Shortest Paths with Recourse

ANDREATTA, GIOVANNI;
1988

Abstract

This paperc onsidersS tochasticS hortestP ath( SSP)p roblemsi n probabilisticn etworks.A variety of approaches have already been proposed in the literature. However, unlike in the deterministic case, they are related to distinct models, interpretationsa nd applications.W e have chosent o look at the case where detours from the original path must be taken whenever the "first-choice" arc fails. The main results obtained include the proof of some counterintuitive facts (e.g., the SSP may contain a cycle), the proof of the validity of applying stochasticp rogrammingt o this problem and the proof that the computational complexity of a particular SSP problem is polynomial.
1988
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/111242
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 59
  • ???jsp.display-item.citation.isi??? 52
social impact