IDEAS home Printed from https://ideas.repec.org/a/kap/netspa/v12y2012i3p441-480.html
   My bibliography  Save this article

Hybrid Evolutionary Metaheuristics for Concurrent Multi-Objective Design of Urban Road and Public Transit Networks

Author

Listed:
  • Elnaz Miandoabchi
  • Reza Farahani
  • Wout Dullaert
  • W. Szeto

Abstract

This paper addresses a bi-modal multi-objective discrete urban road network design problem with automobile and bus flow interaction. The problem considers the concurrent urban road and bus network design in which the authorities play a major role in designing bus network topology. The road network design deals with the decision making for new street constructions, lane additions to existing streets, lane allocations for two-way streets, and the orientations and locations of one-way streets. The bus network design is performed by keeping the terminal stations of the existing bus lines unchanged and redesigning the forth and back routes of each line. Four measures, namely user benefit, the demand coverage of the bus network, the demand share of the bus mode, and the average travel generalized cost of bus passengers, are used to evaluate the network design scenarios. The problem is formulated as a multi-objective optimization model in which a modal-split/assignment model is included to depict the mode and route choice behaviors of travelers. The model is solved by the hybrid genetic algorithm and the hybrid clonal selection algorithm. The performance of these algorithms is presented and investigated by solving a number of test networks. Copyright Springer Science+Business Media, LLC 2012

Suggested Citation

  • Elnaz Miandoabchi & Reza Farahani & Wout Dullaert & W. Szeto, 2012. "Hybrid Evolutionary Metaheuristics for Concurrent Multi-Objective Design of Urban Road and Public Transit Networks," Networks and Spatial Economics, Springer, vol. 12(3), pages 441-480, September.
    • Handle: RePEc:kap:netspa:v:12:y:2012:i:3:p:441-480
    DOI: 10.1007/s11067-011-9163-x
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s11067-011-9163-x
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11067-011-9163-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Cantarella, G.E. & Pavone, G. & Vitetta, A., 2006. "Heuristics for urban road network design: Lane layout and signal settings," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1682-1695, December.
    2. Szeto, W.Y. & Lo, Hong K., 2008. "Time-dependent transport network improvement and tolling strategies," Transportation Research Part A: Policy and Practice, Elsevier, vol. 42(2), pages 376-391, February.
    3. Poorzahedy, Hossain & Turnquist, Mark A., 1982. "Approximate algorithms for the discrete network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 16(1), pages 45-55, February.
    4. Lo, Hong K. & Yip, C. W. & Wan, K. H., 2003. "Modeling transfer and non-linear fare structure in multi-modal network," Transportation Research Part B: Methodological, Elsevier, vol. 37(2), pages 149-170, February.
    5. Ampol Karoonsoontawong & Steven Waller, 2010. "Integrated Network Capacity Expansion and Traffic Signal Optimization Problem: Robust Bi-level Dynamic Formulation," Networks and Spatial Economics, Springer, vol. 10(4), pages 525-550, December.
    6. Zhi-Chun Li & William Lam & S. Wong, 2009. "The Optimal Transit Fare Structure under Different Market Regimes with Uncertainty in the Network," Networks and Spatial Economics, Springer, vol. 9(2), pages 191-216, June.
    7. Spiess, Heinz & Florian, Michael, 1989. "Optimal strategies: A new assignment model for transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 23(2), pages 83-102, April.
    8. Kenetsu Uchida & Agachai Sumalee & David Watling & Richard Connors, 2007. "A Study on Network Design Problems for Multi-modal Networks by Probit-based Stochastic User Equilibrium," Networks and Spatial Economics, Springer, vol. 7(3), pages 213-240, September.
    9. Florian, Michael & Spiess, Heinz, 1982. "The convergence of diagonalization algorithms for asymmetric network equilibrium problems," Transportation Research Part B: Methodological, Elsevier, vol. 16(6), pages 477-483, December.
    10. Satish Ukkusuri & S. Waller, 2008. "Linear Programming Models for the User and System Optimal Dynamic Network Design Problem: Formulations, Comparisons and Extensions," Networks and Spatial Economics, Springer, vol. 8(4), pages 383-406, December.
    11. Szeto, W.Y. & Wu, Yongzhong, 2011. "A simultaneous bus route design and frequency setting problem for Tin Shui Wai, Hong Kong," European Journal of Operational Research, Elsevier, vol. 209(2), pages 141-155, March.
    12. Drezner, Zvi & Wesolowsky, George O., 2003. "Network design: selection and design of links and facility location," Transportation Research Part A: Policy and Practice, Elsevier, vol. 37(3), pages 241-256, March.
    13. Nagurney, Anna B., 1984. "Comparative tests of multimodal traffic equilibrium methods," Transportation Research Part B: Methodological, Elsevier, vol. 18(6), pages 469-485, December.
    14. Dung-Ying Lin & Ampol Karoonsoontawong & S. Waller, 2011. "A Dantzig-Wolfe Decomposition Based Heuristic Scheme for Bi-level Dynamic Network Design Problem," Networks and Spatial Economics, Springer, vol. 11(1), pages 101-126, March.
    15. T. L. Magnanti & R. T. Wong, 1984. "Network Design and Transportation Planning: Models and Algorithms," Transportation Science, INFORMS, vol. 18(1), pages 1-55, February.
    16. Gallo, Mariano & D'Acierno, Luca & Montella, Bruno, 2010. "A meta-heuristic approach for solving the Urban Network Design Problem," European Journal of Operational Research, Elsevier, vol. 201(1), pages 144-157, February.
    17. Giulio Cantarella & Antonino Vitetta, 2006. "The multi-criteria road network design problem in an urban area," Transportation, Springer, vol. 33(6), pages 567-588, November.
    18. Ceder, Avishai & Wilson, Nigel H. M., 1986. "Bus network design," Transportation Research Part B: Methodological, Elsevier, vol. 20(4), pages 331-344, August.
    19. Lo, Hong K. & Szeto, W.Y., 2009. "Time-dependent transport network design under cost-recovery," Transportation Research Part B: Methodological, Elsevier, vol. 43(1), pages 142-158, January.
    20. Larry J. Leblanc, 1975. "An Algorithm for the Discrete Network Design Problem," Transportation Science, INFORMS, vol. 9(3), pages 183-199, August.
    21. Sang Nguyen & Stefano Pallottino & Michel Gendreau, 1998. "Implicit Enumeration of Hyperpaths in a Logit Model for Transit Networks," Transportation Science, INFORMS, vol. 32(1), pages 54-64, February.
    22. Clegg, Janet & Smith, Mike & Xiang, Yanling & Yarrow, Robert, 2001. "Bilevel programming applied to optimising urban transportation," Transportation Research Part B: Methodological, Elsevier, vol. 35(1), pages 41-70, January.
    23. Bellei, Giuseppe & Gentile, Guido & Papola, Natale, 2002. "Network pricing optimization in multi-user and multimodal context with elastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 36(9), pages 779-798, November.
    24. Byung Chung & Tao Yao & Chi Xie & Andreas Thorsen, 2011. "Robust Optimization Model for a Dynamic Network Design Problem Under Demand Uncertainty," Networks and Spatial Economics, Springer, vol. 11(2), pages 371-389, June.
    25. Poorzahedy, Hossain & Rouhani, Omid M., 2007. "Hybrid meta-heuristic algorithms for solving network design problem," European Journal of Operational Research, Elsevier, vol. 182(2), pages 578-596, October.
    26. Ferrari, Paolo, 1999. "A model of urban transport management," Transportation Research Part B: Methodological, Elsevier, vol. 33(1), pages 43-61, February.
    27. Zvi Drezner & George O. Wesolowsky, 1997. "Selecting an Optimum Configuration of One-Way and Two-Way Routes," Transportation Science, INFORMS, vol. 31(4), pages 386-394, November.
    28. Joaquín de Cea & Enrique Fernández, 1993. "Transit Assignment for Congested Public Transport Systems: An Equilibrium Model," Transportation Science, INFORMS, vol. 27(2), pages 133-147, May.
    29. Agostino Nuzzolo & Francesco Russo & Umberto Crisalli, 2001. "A Doubly Dynamic Schedule-based Assignment Model for Transit Networks," Transportation Science, INFORMS, vol. 35(3), pages 268-285, August.
    30. Hossain Poorzahedy & Farhad Abulghasemi, 2005. "Application of Ant System to network design problem," Transportation, Springer, vol. 32(3), pages 251-273, May.
    31. Ben-Ayed, Omar & Boyce, David E. & Blair, Charles E., 1988. "A general bilevel linear programming formulation of the network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 22(4), pages 311-318, August.
    32. Stella Dafermos, 1982. "Relaxation Algorithms for the General Asymmetric Traffic Equilibrium Problem," Transportation Science, INFORMS, vol. 16(2), pages 231-240, May.
    33. Ying, Jiang Qian & Yang, Hai, 2005. "Sensitivity analysis of stochastic user equilibrium flows in a bi-modal network with application to optimal pricing," Transportation Research Part B: Methodological, Elsevier, vol. 39(9), pages 769-795, November.
    34. Hamdouch, Younes & Florian, Michael & Hearn, Donald W. & Lawphongpanich, Siriphong, 2007. "Congestion pricing for multi-modal transportation systems," Transportation Research Part B: Methodological, Elsevier, vol. 41(3), pages 275-291, March.
    35. Sang Nguyen & Clermont Dupuis, 1984. "An Efficient Method for Computing Traffic Equilibria in Networks with Asymmetric Transportation Costs," Transportation Science, INFORMS, vol. 18(2), pages 185-202, May.
    36. Szeto, W.Y. & Lo, Hong K., 2006. "Transportation network improvement and tolling strategies: The issue of intergeneration equity," Transportation Research Part A: Policy and Practice, Elsevier, vol. 40(3), pages 227-243, March.
    37. Gao, Ziyou & Sun, Huijun & Shan, Lian Long, 2004. "A continuous equilibrium network design model and algorithm for transit systems," Transportation Research Part B: Methodological, Elsevier, vol. 38(3), pages 235-250, March.
    38. Stella C. Dafermos, 1972. "The Traffic Assignment Problem for Multiclass-User Transportation Networks," Transportation Science, INFORMS, vol. 6(1), pages 73-87, February.
    39. Long, Jiancheng & Gao, Ziyou & Zhang, Haozhi & Szeto, W.Y., 2010. "A turning restriction design problem in urban road networks," European Journal of Operational Research, Elsevier, vol. 206(3), pages 569-578, November.
    40. D'Acierno, Luca & Gallo, Mariano & Montella, Bruno, 2006. "Optimisation models for the urban parking pricing problem," Transport Policy, Elsevier, vol. 13(1), pages 34-48, January.
    41. Mustafa Abdulaal & Larry J. LeBlanc, 1979. "Methods for Combining Modal Split and Equilibrium Assignment Models," Transportation Science, INFORMS, vol. 13(4), pages 292-314, November.
    42. Friesz, Terry L. & Anandalingam, G. & Mehta, Nihal J. & Nam, Keesung & Shah, Samir J. & Tobin, Roger L., 1993. "The multiobjective equilibrium network design problem revisited: A simulated annealing approach," European Journal of Operational Research, Elsevier, vol. 65(1), pages 44-57, February.
    43. Fitsum Teklu, 2008. "A Stochastic Process Approach for Frequency-based Transit Assignment with Strict Capacity Constraints," Networks and Spatial Economics, Springer, vol. 8(2), pages 225-240, September.
    44. Guihaire, Valérie & Hao, Jin-Kao, 2008. "Transit network design and scheduling: A global review," Transportation Research Part A: Policy and Practice, Elsevier, vol. 42(10), pages 1251-1273, December.
    45. Dantzig, George B. & Harvey, Roy P. & Lansdowne, Zachary F. & Robinson, David W. & Maier, Steven F., 1979. "Formulating and solving the network design problem by decomposition," Transportation Research Part B: Methodological, Elsevier, vol. 13(1), pages 5-17, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. David Eichler & Hillel Bar-Gera & Meir Blachman, 2013. "Vortex-Based Zero-Conflict Design of Urban Road Networks," Networks and Spatial Economics, Springer, vol. 13(3), pages 229-254, September.
    2. Rashidi, Eghbal & Parsafard, Mohsen & Medal, Hugh & Li, Xiaopeng, 2016. "Optimal traffic calming: A mixed-integer bi-level programming model for locating sidewalks and crosswalks in a multimodal transportation network to maximize pedestrians’ safety and network usability," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 91(C), pages 33-50.
    3. Farahani, Reza Zanjirani & Miandoabchi, Elnaz & Szeto, W.Y. & Rashidi, Hannaneh, 2013. "A review of urban transportation network design problems," European Journal of Operational Research, Elsevier, vol. 229(2), pages 281-302.
    4. Rahimi-Golkhandan, Armin & Garvin, Michael J. & Brown, Bryan L., 2019. "Characterizing and measuring transportation infrastructure diversity through linkages with ecological stability theory," Transportation Research Part A: Policy and Practice, Elsevier, vol. 128(C), pages 114-130.
    5. Wang, Shuaian & Meng, Qiang & Yang, Hai, 2013. "Global optimization methods for the discrete network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 50(C), pages 42-60.
    6. Arash Kaviani & Russell G. Thompson & Abbas Rajabifard & Majid Sarvi, 2020. "A model for multi-class road network recovery scheduling of regional road networks," Transportation, Springer, vol. 47(1), pages 109-143, February.
    7. Judith Y. T. Wang & Richard D. Connors, 2018. "Urban Growth, Transport Planning, Air Quality and Health: A Multi-Objective Spatial Analysis Framework for a Linear Monocentric City," Networks and Spatial Economics, Springer, vol. 18(4), pages 839-874, December.
    8. Amirali Zarrinmehr & Mahmoud Saffarzadeh & Seyedehsan Seyedabrishami & Yu Marco Nie, 2016. "A path-based greedy algorithm for multi-objective transit routes design with elastic demand," Public Transport, Springer, vol. 8(2), pages 261-293, September.
    9. Barahimi, Amir Hossein & Eydi, Alireza & Aghaie, Abdolah, 2021. "Multi-modal urban transit network design considering reliability: multi-objective bi-level optimization," Reliability Engineering and System Safety, Elsevier, vol. 216(C).
    10. Loder, Allister & Bliemer, Michiel C.J. & Axhausen, Kay W., 2022. "Optimal pricing and investment in a multi-modal city — Introducing a macroscopic network design problem based on the MFD," Transportation Research Part A: Policy and Practice, Elsevier, vol. 156(C), pages 113-132.
    11. Khooban, Zohreh & Farahani, Reza Zanjirani & Miandoabchi, Elnaz & Szeto, W.Y., 2015. "Mixed network design using hybrid scatter search," European Journal of Operational Research, Elsevier, vol. 247(3), pages 699-710.
    12. Hadi Karimi & Bahador Ghadirifaraz & Seyed Nader Shetab Boushehri & Seyyed-Mohammadreza Hosseininasab & Narges Rafiei, 2022. "Reducing traffic congestion and increasing sustainability in special urban areas through one-way traffic reconfiguration," Transportation, Springer, vol. 49(1), pages 37-60, February.
    13. Long, Jiancheng & Szeto, W.Y. & Huang, Hai-Jun, 2014. "A bi-objective turning restriction design problem in urban road networks," European Journal of Operational Research, Elsevier, vol. 237(2), pages 426-439.
    14. Liu, Haoxiang & Szeto, W.Y. & Long, Jiancheng, 2019. "Bike network design problem with a path-size logit-based equilibrium constraint: Formulation, global optimization, and matheuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 127(C), pages 284-307.
    15. Javier Durán-Micco & Pieter Vansteenwegen, 2022. "A survey on the transit network design and frequency setting problem," Public Transport, Springer, vol. 14(1), pages 155-190, March.
    16. Javier Duran & Lorena Pradenas & Victor Parada, 2019. "Transit network design with pollution minimization," Public Transport, Springer, vol. 11(1), pages 189-210, June.
    17. Inbal Haas & Shlomo Bekhor, 2017. "An Alternative Approach for Solving the Environmentally-Oriented Discrete Network Design Problem," Networks and Spatial Economics, Springer, vol. 17(3), pages 963-988, September.
    18. Long, Jiancheng & Szeto, W.Y. & Huang, Hai-Jun & Gao, Ziyou, 2015. "An intersection-movement-based stochastic dynamic user optimal route choice model for assessing network performance," Transportation Research Part B: Methodological, Elsevier, vol. 74(C), pages 182-217.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Elnaz Miandoabchi & Reza Farahani & W. Szeto, 2012. "Bi-objective bimodal urban road network design using hybrid metaheuristics," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 20(4), pages 583-621, December.
    2. Farahani, Reza Zanjirani & Miandoabchi, Elnaz & Szeto, W.Y. & Rashidi, Hannaneh, 2013. "A review of urban transportation network design problems," European Journal of Operational Research, Elsevier, vol. 229(2), pages 281-302.
    3. Khooban, Zohreh & Farahani, Reza Zanjirani & Miandoabchi, Elnaz & Szeto, W.Y., 2015. "Mixed network design using hybrid scatter search," European Journal of Operational Research, Elsevier, vol. 247(3), pages 699-710.
    4. Szeto, W.Y. & Jiang, Y., 2014. "Transit route and frequency design: Bi-level modeling and hybrid artificial bee colony algorithm approach," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 235-263.
    5. Hosseininasab, Seyyed-Mohammadreza & Shetab-Boushehri, Seyyed-Nader & Hejazi, Seyed Reza & Karimi, Hadi, 2018. "A multi-objective integrated model for selecting, scheduling, and budgeting road construction projects," European Journal of Operational Research, Elsevier, vol. 271(1), pages 262-277.
    6. Gallo, Mariano & D'Acierno, Luca & Montella, Bruno, 2010. "A meta-heuristic approach for solving the Urban Network Design Problem," European Journal of Operational Research, Elsevier, vol. 201(1), pages 144-157, February.
    7. W. Szeto & Y. Jiang & D. Wang & A. Sumalee, 2015. "A Sustainable Road Network Design Problem with Land Use Transportation Interaction over Time," Networks and Spatial Economics, Springer, vol. 15(3), pages 791-822, September.
    8. Hamdouch, Younes & Szeto, W.Y. & Jiang, Y., 2014. "A new schedule-based transit assignment model with travel strategies and supply uncertainties," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 35-67.
    9. Hosseininasab, Seyyed-Mohammadreza & Shetab-Boushehri, Seyyed-Nader, 2015. "Integration of selecting and scheduling urban road construction projects as a time-dependent discrete network design problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 762-771.
    10. Luathep, Paramet & Sumalee, Agachai & Lam, William H.K. & Li, Zhi-Chun & Lo, Hong K., 2011. "Global optimization method for mixed transportation network design problem: A mixed-integer linear programming approach," Transportation Research Part B: Methodological, Elsevier, vol. 45(5), pages 808-827, June.
    11. Wang, Shuaian & Meng, Qiang & Yang, Hai, 2013. "Global optimization methods for the discrete network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 50(C), pages 42-60.
    12. Hamid Farvaresh & Mohammad Sepehri, 2013. "A Branch and Bound Algorithm for Bi-level Discrete Network Design Problem," Networks and Spatial Economics, Springer, vol. 13(1), pages 67-106, March.
    13. Cantarella, Giulio Erberto & Cartenì, Armando & de Luca, Stefano, 2015. "Stochastic equilibrium assignment with variable demand: Theoretical and implementation issues," European Journal of Operational Research, Elsevier, vol. 241(2), pages 330-347.
    14. Liu, Jiangtao & Zhou, Xuesong, 2016. "Capacitated transit service network design with boundedly rational agents," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 225-250.
    15. Amirali Zarrinmehr & Mahmoud Saffarzadeh & Seyedehsan Seyedabrishami & Yu Marco Nie, 2016. "A path-based greedy algorithm for multi-objective transit routes design with elastic demand," Public Transport, Springer, vol. 8(2), pages 261-293, September.
    16. Di, Xuan & Ma, Rui & Liu, Henry X. & Ban, Xuegang (Jeff), 2018. "A link-node reformulation of ridesharing user equilibrium with network design," Transportation Research Part B: Methodological, Elsevier, vol. 112(C), pages 230-255.
    17. D E Boyce, 1984. "Urban Transportation Network-Equilibrium and Design Models: Recent Achievements and Future Prospects," Environment and Planning A, , vol. 16(11), pages 1445-1474, November.
    18. Cancela, Héctor & Mauttone, Antonio & Urquhart, María E., 2015. "Mathematical programming formulations for transit network design," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 17-37.
    19. Xiang Zhang & S. Travis Waller, 2019. "Implications of link-based equity objectives on transportation network design problem," Transportation, Springer, vol. 46(5), pages 1559-1589, October.
    20. Du, Muqing & Chen, Anthony, 2022. "Sensitivity analysis for transit equilibrium assignment and applications to uncertainty analysis," Transportation Research Part B: Methodological, Elsevier, vol. 157(C), pages 175-202.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:kap:netspa:v:12:y:2012:i:3:p:441-480. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.