A self-adaptive gradient projection algorithm for the nonadditive traffic equilibrium problem.

*(English)*Zbl 1251.90083Summary: Gradient projection (GP) algorithm has been shown as an efficient algorithm for solving the traditional traffic equilibrium problem with additive route costs. Recently, GP has been extended to solve the nonadditive traffic equilibrium problem (NaTEP), in which the cost incurred on each route is not just a simple sum of the link costs on that route. However, choosing an appropriate stepsize, which is not known a priori, is a critical issue in GP for solving the NaTEP. Inappropriate selection of the stepsize can significantly increase the computational burden, or even deteriorate the convergence. In this paper, a self-adaptive gradient projection (SAGP) algorithm is proposed. The self-adaptive scheme has the ability to automatically adjust the stepsize according to the information derived from previous iterations. Furthermore, the SAGP algorithm still retains the efficient flow update strategy that only requires a simple projection onto the nonnegative orthant. Numerical results are also provided to illustrate the efficiency and robustness of the proposed algorithm.

##### MSC:

90B20 | Traffic problems in operations research |

90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |

##### Keywords:

traffic equilibrium problem; nonadditive route cost; gradient projection algorithm; self-adaptive scheme
PDF
BibTeX
XML
Cite

\textit{A. Chen} et al., Comput. Oper. Res. 39, No. 2, 127--138 (2012; Zbl 1251.90083)

Full Text:
DOI

##### References:

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

[2] | Chen, A.; Lo, H.K.; Yang, H., A self-adaptive projection and contraction algorithm for the traffic assignment problem with path-specific costs, European journal of operational research, 135, 1, 27-41, (2001) · Zbl 1077.90516 |

[3] | Chen, A.; Oh, J.; Park, D.; Recker, W., Solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs, Applied mathematics and computation, 217, 7, 3020-3031, (2010) · Zbl 1202.90059 |

[4] | Zhou, Z.; Chen, A.; Behkor, S., C-logit stochastic user equilibrium model: formulations and solution algorithm, Transportmetrica, (2010) |

[5] | Yang, H.; Zhang, X.; Meng, Q., Modeling private highways in networks with entry-exit based toll charges, Transportation research part B, 38, 3, 191-213, (2004) |

[6] | Meng, Q.; Lee, D.H.; Cheu, R.L.; Yang, H., Logit-based stochastic user equilibrium problem for entry-exit toll schemes, Journal of transportation engineering, 130, 6, 805-813, (2004) |

[7] | Chien, S.; Spasovic, L.; Chhonkar, R.; Elefsiniotis, S., Evaluation of feeder bus system with probabilities time-varying demands and non-additive time costs, Transportation research record, 1760, 47-55, (2002) |

[8] | Mirchandani, P.; Soroush, H., Generalized traffic equilibrium with probabilistic travel times and perceptions, Transportation science, 21, 3, 133-152, (1987) · Zbl 0626.90026 |

[9] | Chen, A.; Ji, Z.; Recker, W., Travel time reliability with risk sensitive travelers, Transportation research record, 1783, 27-33, (2002) |

[10] | Lo, H.K.; Luo, X.W.; Siu, B.W.Y., Degradable transport network: travel time budget of travelers with heterogeneous risk aversion, Transportation research part B, 40, 9, 792-806, (2006) |

[11] | Shao, H.; Lam, W.H.K.; Meng, Q.; Tam, M.L., Demand driven travel time reliability-based traffic assignment problem, Transportation research record, 1985, 220-230, (2006) |

[12] | Chen, A.; Zhou, Z., The α-reliable Mean-excess traffic equilibrium model with stochastic travel times, Transportation research part B, 44, 4, 493-513, (2010) |

[13] | Larsson, T.; Lindberg, P.O.; Lundgren, J.; Patriksson, M.; Rydergren, C., On traffic equilibrium models with a nonlinear time/money relation, (), 19-31 · Zbl 1175.90099 |

[14] | Bernstein DH, Wynter L. 2000. Issues of uniqueness and convexity in non-additive bi-criteria equilibrium models. In: Proceedings of the EURO Working Group on Transportation, Rome, Italy. |

[15] | Agdeppa, R.; Yamashita, N.; Fukushima, M., The traffic equilibrium problem with nonadditive costs and its monotone mixed complementarity problem formulation, Transportation research part B, 41, 862-874, (2007) |

[16] | Altman, E.; Wynter, L., Equilibrium, games, and pricing in transportation and telecommunication networks, Networks and spatial economics, 4, 1, 7-21, (2004) · Zbl 1094.91003 |

[17] | Sheffi, Y., Urban transportation networks, (1985), Prentice-Hall, Incorporated Englewood Cliffs, NJ |

[18] | Bernstein, D.; Gabriel, G., Solving the nonadditive traffic equilibrium problem, (), 72-102 · Zbl 0878.90030 |

[19] | Lo, H.K.; Chen, A., Traffic equilibrium problem with route-specific costs: formulation and algorithms, Transportation research part B, 34, 6, 493-513, (2000) |

[20] | Fischer, A., A special Newton-type optimization method, Optimization, 24, 3-4, 269-284, (1992) · Zbl 0814.65063 |

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

[22] | Lo, H.K.; Chen, A., Reformulating the general traffic equilibrium problem via a smooth gap function, Mathematical and computer modeling, 31, 2-3, 179-195, (2000) · Zbl 1042.90515 |

[23] | Han, D.R.; Lo, H.K., Solving non-additive traffic assignment problems: a descent methods for co-coercive variational inequalities, European journal of operational research, 159, 3, 529-544, (2004) · Zbl 1065.90015 |

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

[25] | Chen, A.; Lee, D.-H.; Jayakrishnan, R., Computational study of state-of-the-art path-based traffic assignment algorithms, Mathematics and computers in simulation, 59, 6, 509-518, (2002) · Zbl 1030.90012 |

[26] | Scott K, Bernstein D. Solving a traffic equilibrium problem when path costs are nonadditive. Paper presented at the 78th annual meeting of the Transportation Research Board, Washington, DC, USA, 1999. |

[27] | Han, D.R.; Sun, W.Y., A new modified goldstein – levitin – polyak projection method for variational inequality problems, Computational mathematics and application, 47, 12, 1817-1825, (2004) · Zbl 1057.49011 |

[28] | Zhou, Z.; Chen, A., A self-adaptive scaling technique embedded in the projection traffic assignment algorithm, Journal of eastern Asia society for transportation studies, 5, 1647-1662, (2003) |

[29] | Wardrop, J., Some theoretical aspects of road traffic research, In: Proceedings the institution of civil engineers, 1, 325-378, (1952) |

[30] | Smith, M.J., Existence, uniqueness, and stability of traffic equilibria, Transportation research part B, 13, 4, 259-304, (1979) |

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

[32] | Bertsekas, D.P.; Gafni, E.M., Projection methods for variational inequalities with application to the traffic assignment problem, Mathematical programming study, 17, 139-159, (1982) · Zbl 0478.90071 |

[33] | Cui, Y.; He, B.S., A class of projection and contraction methods for asymmetric linear variational inequalities and their relations to Fukushima’s descent method, Computers and mathematics with applications, 38, 11-12, 151-164, (1999) · Zbl 0974.49008 |

[34] | Pang, J.S.; Chan, D., Iterative methods for variational and complementarity problems, Mathematical. programming, 24, 1, 284-313, (1982) · Zbl 0499.90074 |

[35] | Pang, J.S., Asymmetric variational inequality problems over product sets: applications and iterative methods, Mathematical programming, 31, 2, 202-219, (1985) · Zbl 0578.49006 |

[36] | Auslender, A.; Teboulle, M.; Ben-Tiba, S., Interior proximal and multiplier methods based on second order homogeneous kernels, Mathematics of operations research, 24, 3, 645-668, (1999) · Zbl 1039.90518 |

[37] | Bonnans, J.F., Local analysis of Newton-type methods for variational inequalities and nonlinear programming, Applied mathematics and optimization, 29, 2, 161-186, (1994) · Zbl 0809.90115 |

[38] | Harker, P.T.; Pang, J.S., A damped-Newton method for the linear complementarity problem, Lectures in applied mathematics, 26, 265-284, (1990) |

[39] | Goldstein, A.A., Convex programming in Hilbert space, Bulletin of the American mathematical society, 70, 5, 709-710, (1964) · Zbl 0142.17101 |

[40] | Levitin, E.S.; Polyak, B.T., Constrained minimization methods, USSR, computational mathematics and mathematical physics, 6, 787-823, (1965) · Zbl 0184.38902 |

[41] | Nagurney, A.; Zhang, D., Projected dynamical systems and variational inequality with applications, (1996), Kluwer Academic Publishers Dordrecht, Boston, MA |

[42] | Bertsekas, D.R., On the goldstein – levitin – polyak gradient projection method, IEEE transactions on automatic control, 21, 2, 174-184, (1976) · Zbl 0326.49025 |

[43] | Armijo, L., Minimization of functions having continuous partial derivatives, Pacific journal of mathematics, 16, 1, 1-3, (1966) · Zbl 0202.46105 |

[44] | Gafni EM, Bertsekas DP. Convergence of a gradient projection method. LIDS-P 1201, 1982 |

[45] | He, B.S.; Yang, H.; Meng, Q.; Han, D.R., Modified goldstein – levitin – polyak projection method for asymmetric strongly monotone variational inequalities, Journal of optimization, theory and applications, 112, 1, 129-143, (2002) · Zbl 0998.65066 |

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

[47] | INRO Consultants. Emme/2 user’s manual: Release 9.2. Montréal, 1999. |

[48] | Bekhor S, Toledo T, Prashker JN. Implementation issues of route choice models in path-based algorithms. Paper presented at the 11th international conference on travel behaviour research, Kyoto, Japan, 2006. |

[49] | Bekhor, S.; Toledo, T.; Prashker, J.N., Effects of choice set size and route choice models on path-based traffic assignment, Transportmetrica, 4, 2, 117-133, (2008) |

[50] | Azevedo, J.A.; Santos Costa, M.E.O.; Silvestre Madera, J.J.E.R.; Vieira Martins, E.Q., An algorithm for the ranking of shortest paths, European journal of operational research, 69, 1, 97-106, (1993) · Zbl 0782.90091 |

[51] | De La Barra T, Perez B, Anez J. Multidimensional path search and assignment. In: Proceedings of the 21st PTRC summer annual meeting, Manchester, England, 1993, p. 307-19. |

[52] | Boyce, D.; Ralevic-Deki, B; Bar-Gera, H., Convergence of traffic assignments: how much is enough?, Journal of transportation engineering, 130, 1, 49-55, (2004) |

[53] | Ben-Akiva, M.; Bergman, M.J.; Daly, A.J.; Ramaswamy, R., Modeling inter urban route choice behaviour, (), 299-330 |

[54] | Bekhor S, Ben-Akiva M, Ramming S. Route choice: choice set generation and route choice models. Paper presented at the IV Tristan conference, Azores, Portugal, 2001. · Zbl 1156.90314 |

[55] | Gabriel, S.; Bernstein, D., Nonadditive shortest paths: subproblems in multi-agent competitive network model, Computational and mathematical organization theory, 6, 1, 29-45, (2000) |

[56] | Tsaggouris, G.; Zaroliagis, C., Non-additive shortest paths, Lecture notes in computer science, 3221, 822-834, (2004) · Zbl 1111.90365 |

[57] | Reinhardt, L.B.; Pisinger, D., Multi-objective and multi-constrained non-additive shortest path problems, Computers & operations research, 38, 3, 605-616, (2011) · Zbl 1201.90035 |

[58] | Chen A, Jayakrishnan R. A path-based gradient projection algorithm: effects of equilibration with a restricted path set under two flow update policies. Paper presented at the 77th Transportation Research Board annual meeting, Washington, DC, USA, 1998. |

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.