nach oben

Transportation

13.05.2024

Hybrid gradient-swarm intelligence to improve quality of solutions for origin–destination matrix adjustment problem

verfasst von: Mehrdad Gholami Shahbandi, Abbas Babazadeh

Erschienen in: Transportation

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The high cost of conventional surveys has motivated researchers to develop methods for adjusting a prior Origin–destination (OD) matrix from easily available traffic counts. The gradient method is a mathematical programming approach widely used for the OD matrix adjustment problem (ODMAP). However, this method easily gets trapped in local optima due to the non-convexity of the problem. Moreover, validation of the gradient solutions against predefined target matrices shows the method has considerable difficulty with estimating the sum of the OD matrix elements. Particle swarm optimization (PSO) is a metaheuristic which is getting lots of attention for its global search ability, but is less accurate in local search. The proposed algorithm hybridizes PSO with the gradient method, considering that the combination of good local convergence properties and effective global search makes an excellent algorithm for the ODMAP. Comparison of the results for a small and a real-life network demonstrates that the hybrid algorithm provides higher convergence properties and achieves more accurate solutions than its constituent parts working alone.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Aashtiani, H.Z., Magnanti, T.L.: A linearization and decomposition algorithm for computing urban traffic equilibria. Proceeding of the IEEE Large Scale Systems Symposium 8–19 (1982)

Babazadeh, A., Javani, B., Gentile, G., Florian, M.: Reduced gradient algorithm for user equilibrium traffic assignment problem. Transportmetrica A: Transport Sci. 16(3), 1111–1135 (2020). https://doi.org/10.1080/23249935.2020.1722279CrossRef

Baek, S., Kim, H., Lim, Y.: Multiple-vehicle origin-destination matrix estimation from traffic counts using genetic algorithm. J. Transport. Eng., ASCE, May/June, 339–347 (2004). https://doi.org/10.1061/(asce)0733-947x(2004)130:3(339)

Beckmann, M.J.: On optimal tolls for highways, tunnels and bridges. In: Edie, L.C., Herman, R., Rothery, R. (eds.) Vehicular Traffic Science, pp. 331–341. American Elsevier, New York, NY (1965)

Borowska, B., Nadolski, S.: Particle swarm optimization: the gradient correction. J. Appl. Comput. Sci. 17(2), 7–15 (2009)

Caggiani, L., Ottomanelli, M., Sassanelli, D.: A fixed point approach to origin–destination matrices estimation using uncertain data and fuzzy programming on congested networks. Transportation Part C 38, 130–141 (2013). https://doi.org/10.1016/j.trc.2010.12.005CrossRef

Chen, X., Du, W., Qi, R., Qian, F., Tianfield, H.: Hybrid gradient particle swarm optimization for dynamic optimization problems for chemical processes. Asia-Pac. J. Chem. Eng. 8, 708–720 (2013). https://doi.org/10.1002/apj.1712CrossRef

De Villa, A.R., Casas, J., Breen, M., Perarnau, J.: Minimum GEH in static OD estimation. Australian Transport Research Forum Proceedings 2(4) (2013)

Doblas, J., Benitez, F.G.: An approach to estimating and updating origin-destination matrices based upon traffic counts preserving the prior structure of a survey matrix. Transp. Res. Part B 39, 565–591 (2005). https://doi.org/10.1016/j.trb.2004.06.006CrossRef

Eberhart, R.C., Kennedy, J.: A new optimizer using particle swarm theory. Proceedings of the Sixth International Symposium on Micro Machine and Human Science. IEEE Press, Piscataway, NJ, 39–43 (1995). https://doi.org/10.1109/mhs.1995.494215

Florian, M., Chen, Y.: A coordinate descent method for the bi-level O-D matrix adjustment problem. Transp. Res. Part B 22, 69–73 (1995). https://doi.org/10.1111/j.1475-3995.1995.tb00012.xCrossRef

Foulds, L., do Nascimento, H., Calixto, I., Hall, B., Longo, H.: A fuzzy set-based approach to origin–destination matrix estimation in urban traffic networks with imprecise data. Eur. J. Operation. Res. 231, 190–201 (2013). https://doi.org/10.1016/j.ejor.2013.05.012CrossRef

Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logist. Quart. 3, 95–110 (1956). https://doi.org/10.1007/springerreference_6330CrossRef

Ghaffari-Miab, M., Farmahini-Farahani, A., Faraji-Dana, R., Lucas, C.: An efficient hybrid swarm intelligence-Gradient optimization method for complex time green’s functions of multilayer media. Progress in Electromagnetics Research, PIER 77, 181–192 (2007). https://doi.org/10.2528/pier07072504CrossRef

Gholami Shabandi, M., Babazadeh., A.: A PSO metaheuristic for origin-destination matrix estimation problem. 10^th international congress on advances in civil engineering, Middle East Technical University, Ankara, Turkey 1–9 (2012)

Gong, Z.: Estimating the urban OD matrix: A neural network approach. Eur. J. Oper. Res. 106, 108–115 (1998). https://doi.org/10.1016/s0377-2217(97)00162-8CrossRef

Gur Y., Turnquist M., Schneider M., Leblanc L., Kurth D.: Estimation of an origin-destination trip table based on observed link volumes and turning movements. Final Report, No. DOT-FH-11–9292, U.S. Federal Highway Administration, Washington D.C. 1–119 (1979)

Hoberg, P.: Estimation of parameters in models for traffic prediction: a non-linear approach. Transp. Res. Part B 10, 263–265 (1976). https://doi.org/10.1016/0041-1647(76)90059-9CrossRef

Javani, B., Babazadeh, A.: Origin-destination-based truncated quadratic programming algorithm for traffic assignment problem. Transport. Lett. 9, 166–176 (2016). https://doi.org/10.1080/19427867.2016.1227531CrossRef

Jayakrishnan, R., Tsai, W.T., Prasker, J.: Rajadhyaksha, S: A faster path-based algorithm for traffic assignment. Transport. Res. Record: J. Transport. Res. Board 1443, 75–83 (1994)

Kawakami, K., Meng, A.: Improvement of particle swarm optimization. Piers Online 5(3), 261–266 (2009)CrossRef

Kennedy, J., Eberhart, R.C.: Particle swarm optimization 1942–1948. Proceedings of the IEEE International Conference on Neural Networks. IEEE Press, Piscataway, NJ (1995)

Kim, D., Chang, Y.: Neural network-based O-D matrix estimation from link traffic counts. Int. J. Urban Sci. 12(2), 146–157 (2008). https://doi.org/10.1080/12265934.2008.9693637CrossRef

Kim, H., Beak, S., Lim, Y.: Origin-destination matrices estimated with a genetic algorithm from link traffic counts. Transp. Res. Rec. Transp. Res. Board 1771, 156–163 (2001). https://doi.org/10.3141/1771-20

Leblanc, L., Farhangian, K.: Selection of a trip table which reproduces observed link flows. Transp. Res. Part B 16, 83–88 (1982). https://doi.org/10.1016/0191-2615(82)90029-7CrossRef

Low, D.: A new approach to transportation systems modelling. Traffic Quart. 26, 391–404 (1972)

Lundgren, J., Peterson, A.: A heuristic for the bi-level origin-destination matrix estimation problem. Transp. Res. Part B 42, 339–359 (2008). https://doi.org/10.1016/j.trb.2007.09.005CrossRef

Maher, M., Zang, X., Van Vilet, D.: A bi-level programming approach for trip matrix estimation and traffic control problems with stochastic user equilibrium link flows. Transp. Res. Part B 35, 23–40 (2001). https://doi.org/10.1016/s0191-2615(00)00017-5CrossRef

Marler, R.T., Arora, J.S.: The weighted sum method for multi-objective optimization: new insights. Struct. Multidisc. Optim. 41, 853–862 (2010). https://doi.org/10.1007/s00158-009-0460-7CrossRef

Mussone, L., Matteucci, M.: OD matrices network estimation from link counts by neural networks. J. Transp. Syst. Eng. Inf. Technol. 13(4), 84–93 (2013). https://doi.org/10.1016/s1570-6672(13)60117-8CrossRef

Nguyen, S.: Estimation an OD matrix from network data: A network equilibrium approach. University of Montreal Publication, 60 (1977)

Noel, M., Jannett, T.: Simulation of a new hybrid particle swarm optimization algorithm. In Proceedings of the thirty-sixth southeastern symposium on system theory, 150–153 (2004). https://doi.org/10.1109/ssst.2004.1295638

Noriega, Y., Florian, M.: Some enhancement of the gradient method for OD matrix adjustment. Interuniversity research center of enterprise networks, Logistics and Transportations (CIRRELT) (2009)

Plevris, V., Papadrakakis, M.: A hybrid particle swarm-gradient algorithm for global structural optimization. Computer-Aided Civil and Infrastructure Engineering 26, 48–68 (2011). https://doi.org/10.1111/j.1467-8667.2010.00664.xCrossRef

Qteish, A., Hamdan, M.: Hybrid particle swarm and conjugate gradient optimization algorithm. Proceeding of the First Conference on Advances in Swarm Intelligence, Part I, 582–588 (2010). https://doi.org/10.1007/978-3-642-13495-1_71CrossRef

Robillard, P.: Estimation an O-D matrix from observed link volumes. Transp. Res. Part B 9, 53–65 (1975). https://doi.org/10.1016/0041-1647(75)90049-0CrossRef

Rodenas, R., Rayo, D.: A column generation algorithm for the estimation of origin-destination matrices in congested traffic networks. Eur. J. Oper. Res. 184, 860–878 (2006). https://doi.org/10.1016/j.ejor.2006.11.037CrossRef

Shafahi, Y., Faturechi, R.: A new fuzzy approach to estimate the O-D matrix from link volumes. Transp. Plan. Technol. 32(6), 499–526 (2009). https://doi.org/10.1080/03081060903374700CrossRef

Sherali, H., Narayanan, A., Sivanandan, R.: Estimation of origin-destination trip-tables based on a partial set of traffic link counts. Transp. Res. Part B 37, 815–836 (2002). https://doi.org/10.1016/s0191-2615(02)00073-5CrossRef

Shi, YH., Eberhart, RC.: Empirical study of particle swarm optimization. Proceedings of the Congress on Evolutionary Computation, 1945–1950 (1999). https://doi.org/10.1109/cec.1999.785511

Spiess, H.: A gradient approach for the OD matrix adjustment problem. University of Montreal Publication, No. 693 (1990)

Walpen, J., Mancinelli, E., Lotito, A.: A heuristic for the OD matrix adjustment problem in a congested transport network. Eur. J. Oper. Res. 242, 807–819 (2015). https://doi.org/10.1016/j.ejor.2014.11.009CrossRef

Wardrop, J.: Some theoretical aspects of road traffic research. Proceedings of the Institute of Civil Engineers 1(2), 325–378 (1952). https://doi.org/10.1680/ipeds.1952.11259CrossRef

Yang, H., Sasaki, T., Lida, Y., Asakura, Y.: Estimation of origin-destination matrices from link traffic counts on congested networks. Transp. Res. Part B 26, 417–434 (1992). https://doi.org/10.1016/0191-2615(92)90008-kCrossRef

Zhang, R., Zhang W., Zhang, X.: A new hybrid gradient-based particle swarm optimization algorithm and its applications to control of polarization mode dispersion compensation in optical fiber communications systems. The international joint conference computational sciences and optimization, 1031–1033 (2009). https://doi.org/10.1109/cso.2009.68

Titel: Hybrid gradient-swarm intelligence to improve quality of solutions for origin–destination matrix adjustment problem
verfasst von: Mehrdad Gholami Shahbandi
Abbas Babazadeh
Publikationsdatum: 13.05.2024
Verlag: Springer US
Erschienen in: Transportation
Print ISSN: 0049-4488
Elektronische ISSN: 1572-9435
DOI: https://doi.org/10.1007/s11116-024-10493-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Premium Partner