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

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.