A Dual Approach for Solving the Combined Distribution and Assignment Problem with Link Capacity Constraints

Seungkyu Ryu, Anthony Chen, Xiangdong Xu, Keechoo Choi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

23 Citations (Scopus)

Abstract

In this paper, we consider the combined distribution and assignment (CDA) problem with link capacity constraints modeled as a hierarchical logit choice problem based on random utility theory. The destination and route choices are calculated based on the multi-nominal logit probability function, which forms the basis for constructing the side constrained CDA (SC-CDA) problem as an equivalent mathematical programming (MP) formulation. A dual MP formulation of the SC-CDA problem is developed as a solution algorithm, which consists of an iterative balancing scheme and a column generation scheme, for solving the SC-CDA problem. Due to the entropy-type objective function, the dual formulation has a simple nonlinear constrained optimization structure, where the feasible set only consists of nonnegative orthants. The iterative balancing scheme explicitly makes use of the optimality conditions of the dual formulation to analytically adjust the dual variables and update the primal variables, while a column generation scheme is used to iteratively generate routes to the working route set as needed to satisfy the side constraints. Two numerical experiments are conducted to demonstrate the features of the SC-CDA model and the computational performance of the solution algorithm. The results reveal that imposing link capacity constraints can have a significant impact on the network equilibrium flow allocations, and the dual approach is a practical solution algorithm for solving the complex SC-CDA problem.
Original languageEnglish
Pages (from-to)245-270
Number of pages26
JournalNetworks and Spatial Economics
Volume14
Issue number2
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes

Keywords

  • Capacity constraints
  • Combined distribution and assignment problem
  • Dual approach
  • Iterative balancing
  • Side constraints

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this