A mean-variance model for the minimum cost flow problem with stochastic arc costs

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

  • Stephen D. Boyles - , University of Wyoming (Autor:in)
  • S. Travis Waller - , University of Texas at Austin (Autor:in)

Abstract

This article considers a minimum cost flow problem where arc costs are uncertain, and the decision maker wishes to minimize both the expected flow cost and the variance of this cost. Two optimality conditions are given, one based on cycle marginal costs, and another based on concepts of network equilibrium. Solution methods are developed based on these conditions. The value of information is also studied, and efficient approximation techniques are developed for the specific case of learning the exact cost of one or more arcs a priori. Finally, numerical results compare the solution methods developed in this work: the minimum mean cycle canceling algorithm performs better on all of the networks tested, although the equilibrium-based algorithm is more competitive for large networks. Solution sensitivity to input parameters is also examined, as is the performance of the approximation techniques for the value of information. Approximation techniques based on arc cost distributions were found to outperform those based on properties of optimal flows.

Details

OriginalspracheEnglisch
Seiten (von - bis)215-227
Seitenumfang13
FachzeitschriftNetworks : an international journal
Jahrgang56
Ausgabenummer3
PublikationsstatusVeröffentlicht - Okt. 2010
Peer-Review-StatusJa
Extern publiziertJa

Externe IDs

ORCID /0000-0002-2939-2090/work/141543866

Schlagworte

Schlagwörter

  • bicriterion optimization, minimum cost flow, network equilibrium, stochastic costs