Reformulating the traffic equilibrium problem via a smooth gap function.

*(English)*Zbl 1042.90515Summary: This paper proposes an alternate formulation of the traffic assignment problem using route flows and the shortest Origin-Destination (OD) travel times as the decision variables. This is accomplished through defining a gap function to convert the Nonlinear Complementarity Problem (NCP) formulation to an equivalent Mathematical Program (MP). This formulation has two advantages:

it can model assignment problems with general route costs which cannot be accomplished with existing formulations that use link-flow variables, the objective function is smooth, convex, and bounded, which permits efficient MP algorithms for its solution.

Two solution approaches are developed to solve the proposed formulation. The first is based on a set of working routes, which are modeled as “known a priori” based on travelers’ preferences or interviews. The second approach uses a column generation procedure to generate a new route in each iteration on a need basis. For each approach, we use a Successive Quadratic Programming (SQP) algorithm to solve for the solutions.

To show that the formulation is correct, we solve a small example with a general route cost and compare it to the classic traffic equilibrium problem which assumes an additive route cost function.

Finally, numerical results for a medium-sized network are provided to demonstrate the feasibility of the solution approach.

it can model assignment problems with general route costs which cannot be accomplished with existing formulations that use link-flow variables, the objective function is smooth, convex, and bounded, which permits efficient MP algorithms for its solution.

Two solution approaches are developed to solve the proposed formulation. The first is based on a set of working routes, which are modeled as “known a priori” based on travelers’ preferences or interviews. The second approach uses a column generation procedure to generate a new route in each iteration on a need basis. For each approach, we use a Successive Quadratic Programming (SQP) algorithm to solve for the solutions.

To show that the formulation is correct, we solve a small example with a general route cost and compare it to the classic traffic equilibrium problem which assumes an additive route cost function.

Finally, numerical results for a medium-sized network are provided to demonstrate the feasibility of the solution approach.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90B22 | Queues and service in operations research |

PDF
BibTeX
XML
Cite

\textit{H. K. Lo} and \textit{A. Chen}, Math. Comput. Modelling 31, No. 2--3, 179--195 (2000; Zbl 1042.90515)

Full Text:
DOI

##### References:

[1] | Sheffi, Y., Urban transportation networks: equilibrium analysis with mathematical programming methods, (1985), Prentice-Hall Englewood Cliffs, NJ |

[2] | Aashtiani, H., The multi-modal traffic assignment problem, () · Zbl 0967.90500 |

[3] | Dafermos, S., Traffic equilibrium and variational inequalities, Transportation science, 14, 42-54, (1980) |

[4] | Nagurney, A., Network economics: A variational inequality approach, (1993), Kluwer Academic Publishers Norwell, MA · Zbl 0873.90015 |

[5] | Friesz, T.; Bernstein, D.; Smith, T.; Tobin, R.; Wie, B., A variational inequality formulation of the dynamic network user equilibrium problem, Operations research, 41, 179-191, (1993) · Zbl 0771.90037 |

[6] | Ran, B.; Boyce, D., Modeling dynamic transportation networks, (1996), Springer Berlin · Zbl 0898.90004 |

[7] | Asmuth, R., Traffic network equilibria, () |

[8] | Patriksson, M., The traffic assignment problem: models and methods, (1994), VSP The Netherlands · Zbl 0828.90127 |

[9] | Florian, M.; Hearn, D., Network equilibrium models and algorithms, () · Zbl 0864.90042 |

[10] | LeBlanc, L.; Morlok, E.; Pierskalla, W., An efficient approach to solving the road network equilibrium traffic assignment problem, Transportation research, 9, 430-442, (1975) |

[11] | Chen, A.; Jayakrishnan, R., A path-based gradient projection algorithm: effects of equilibration with a restricted path set under two flow update policies, () |

[12] | Cascetta, E.; Russo, F.; Vitetta, A., Stochastic user equilibrium assignment with explicit path enumeration: comparison of models and algorithms, (), 1078-1084 |

[13] | Bell, M.G.; Cassir, C.; Grosso, S.; Clement, S., Path flow estimation in traffic system management, (), 1316-1321 |

[14] | Gabriel, S.; Bernstein, D., The traffic equilibrium problem with nonadditive path costs, Transportation science, 31, 4, 337-348, (1997) · Zbl 0920.90058 |

[15] | Jayakrishnan, R.; Tsai, W.K.; Prashker, J.N.; Rajadhyaksha, S., Faster path-based algorithm for traffic assignment, Transportation research record, 1443, 75-83, (1994) |

[16] | S.C. Wong, C. Yang and H. Lo, A path-based traffic assignment algorithm using the TRANSYT traffic model, Transportation Research (to appear). |

[17] | Lo, H., A dynamic traffic assignment formulation that encapsulates the cell transmission model, (), 327-350 |

[18] | H. Lo and A. Chen, Traffic equilibrium problem with route-specific costs: Formulation and algorithms, Transportation Research (to appear). |

[19] | Smith, M., The existence and calculation of traffic equilibria, Transportation research, 17B, 291-303, (1983) |

[20] | Smith, M., An algorithm for solving asymmetric equilibrium problems with a continuous cost-flow functions, Transportation research, 17B, 365-371, (1983) |

[21] | Hearn, D.; Lawphongpanich, S., A dual algorithm for traffic assignment problems, Transportation research, 24B, 6, 423-430, (1990) |

[22] | Facchinei, F.; Soares, J., Testing a new class of algorithms for nonlinear complementarity problems, () · Zbl 0849.90118 |

[23] | Hearn, D., The gap function of a convex program, Operations research letter, 1, 67-71, (1982) · Zbl 0486.90070 |

[24] | Smith, M., A new dynamic traffic model and the existence and calculation of dynamic user-equilibrium on congested capacity-constrained road networks, Transportation research, 27B, 49-63, (1993) |

[25] | Bazaraa, M.; Sherali, H.; Shetty, C., Nonlinear programming: theory and algorithms, (1993), John Wiley & Sons New York · Zbl 0774.90075 |

[26] | Schittkowski, K., On the convergence of a sequential quadratic programming method with an augmented Lagrangian line search function, Mathematische operationsforschung und statistik, series optimization, 14, 197-216, (1983) · Zbl 0523.90075 |

[27] | Schittkowski, K., More test examples for nonlinear programming codes, () · Zbl 0658.90060 |

[28] | Nguyen, S.; Dupuis, C., An efficient method for computing traffic equilibria in networks with asymmetric transportation costs, Transportation science, 18, 185-202, (1984) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.