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

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

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

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

Original languageEnglish
Pages (from-to)215-227
Number of pages13
JournalNetworks : an international journal
Volume56
Issue number3
Publication statusPublished - Oct 2010
Peer-reviewedYes
Externally publishedYes

External IDs

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

Keywords

Keywords

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