Global optimization method for mixed transportation network design problem: A mixed-integer linear programming approach

Paramet Luathep, Agachai Sumalee, Hing Keung William Lam, Zhi Chun Li, Hong K. Lo

Research output: Journal article publicationJournal articleAcademic researchpeer-review

138 Citations (Scopus)

Abstract

This paper proposes a global optimization algorithm for solving a mixed (continuous/discrete) transportation network design problem (MNDP), which is generally expressed as a mathematical programming with equilibrium constraint (MPEC). The upper level of the MNDP aims to optimize the network performance via both expansion of existing links and addition of new candidate links, whereas the lower level is a traditional Wardrop user equilibrium (UE) problem. In this paper, we first formulate the UE condition as a variational inequality (VI) problem, which is defined from a finite number of extreme points of a link-flow feasible region. The MNDP is approximated as a piecewise-linear programming (P-LP) problem, which is then transformed into a mixed-integer linear programming (MILP) problem. A global optimization algorithm based on a cutting constraint method is developed for solving the MILP problem. Numerical examples are given to demonstrate the efficiency of the proposed method and to compare the results with alternative algorithms reported in the literature.
Original languageEnglish
Pages (from-to)808-827
Number of pages20
JournalTransportation Research Part B: Methodological
Volume45
Issue number5
DOIs
Publication statusPublished - 1 Jan 2011

Keywords

  • Discrete network design
  • Global optimization
  • Mixed network design
  • Mixed-integer linear programming
  • Network design problem

ASJC Scopus subject areas

  • Transportation
  • Management Science and Operations Research

Cite this