A lagrange relaxation method for the network design problem considering facility location

Ming Zhe Chen*, Naoto Katayama, Hiroaki Mohri


研究成果: Article査読


The network design problem, which attempts to simultaneously take into account facility location and network topology, has a number of applications in transportation network design, distribution systems, telecommunication network planning, and other areas. In this paper, we investigate a new model that simultaneously optimizes facility locations for distribution centers and concentrators, network topology for line-haul trucks and fiber-optic communication lines, and routes of commodity flow for freight and communication data. Our model consists of uncapacitated facility location, uncapaci-tated arc design, general network design, an unlimited number of freight transshipment at facilities, and multi-commodity flow routing that has a large number of origin-destination pairs. It has been noted that this model is not suitable for solving problems that exist in the real world with current OR software on the market. We present a new formulation of this problem that minimizes the sum of flow costs, arc design costs, and facility location costs, and a new Lagrange relaxation problem with relaxed flow conservation constraints and some forcing constraints. We present an exact solution method for this Lagrange relaxation problem, and a subgradient method for Lagrange multipliers. In addition, we present an approximate solution method for obtaining good upper bound using solutions of a Lagrange relaxation problem, which is called Lagrange heuristics. Numerical examples up to 100 nodes are given to show the effectiveness of our formulation and solution methods for lower and upper bound.

ジャーナルJournal of Japan Industrial Management Association
出版ステータスPublished - 2005 12月 1

ASJC Scopus subject areas

  • 戦略と経営
  • 経営科学およびオペレーションズ リサーチ
  • 産業および生産工学
  • 応用数学


「A lagrange relaxation method for the network design problem considering facility location」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。