THE PROBABILISTIC NETWORK DESIGN PROBLEM

スポンサーリンク

概要

• 論文の詳細を見る

• We analyze the probabilistic variation of the multicommodity discrete network design problem named the probabilistic network design problem in which the commodities are generated probabilistically and the objective is to calculate the expected value of all possible network design instances. We extend the a priori strategy which has been successfully applied to the probabilistic variations of the traveling salesman and minimum spanning tree problems. We use the a priori network strategy which can be seen as an extension of the a priori strategy, to calculated the upper bounds of the expectations of the network design costs, and analyze several heuristic methods for constructing the a priori network both in the worse case model and in the probabilistic model. We also derive the lower bounding procedure using the probabilistic extensions of valid inequalities which, by combining the linear programming technique and the cutting plane procedure, induce the lower bounds of the expected network design costs.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Kubo Mikio

  Waseda University

• Kasugai Hiroshi

  Waseda University

関連論文

• HEURISTIC ALGORITHMS FOR THE SINGLE VEHICLE DIAL-A-RIDE PROBLEM
• A LAGRANGEAN APPROACH TO THE FACILITY LOCATION PROBLEM WITH CONCAVE COSTS
• THE PRECEDENCE CONSTRAINED TRAVELING SALESMAN PROBLEM
• ON THE CORE OF THE NETWORK DESIGN GAME
• THE PROBABILISTIC NETWORK DESIGN PROBLEM
• RANDOMIZED DECISION STRATEGY FOR THE HIERARCHICAL OPTIMIZATION PROBLEMS

スポンサーリンク