Consider the node–arc formulation of the ‘‘traffic-assignment’’ model. Define a ‘‘commodity’’ as…
Consider the node–arc formulation of the ‘‘traffic-assignment’’ model. Define a ‘‘commodity’’ as the flow from an origin to a destination. Let
The conservation-of-flow equations for each commodity are:
The capacity restrictions on the arcs can be formulated as follows:
assuming that ti j the travel time on arc i − j. To minimize total travel time on the network, we have the following objective function:
a) Let the conservation-of-flow constraints for a commodity correspond to a subproblem, and the capacity restrictions on the arcs correspond to the master constraints in a decomposition approach. Formulate the restricted master, and the subproblem for the kth commodity. What is the objective function of this subproblem?
b) What is the relationship between solving the subproblems of the node–arc formulation and finding the minimum reduced cost for each commodity in the arc–chain formulation discussed in the previous exercise?
c) Show that the solution of the node–arc formulation by decomposition is identical to solving the arc–chain formulation discussed in the previous exercise. [Hint. In the arc–chain formulation, define new variables