IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v101y2017icp13-29.html
   My bibliography  Save this article

The multi-criteria constrained shortest path problem

Author

Listed:
  • Shi, Ning
  • Zhou, Shaorui
  • Wang, Fan
  • Tao, Yi
  • Liu, Liming

Abstract

In this study, we propose an exact method for finding all the Pareto-optimal paths for a multi-criteria constrained shortest path problem. We show that solving the special bi-criteria problem is equivalent to generating at most |P| constrained shortest paths with successive tightened constraints, where |P| is the total number of all Pareto-optimal paths. For the general multi-criteria case, we propose a decomposition procedure and theoretically prove that this method can identify all the Pareto-optimal paths from at most (u-1)!|P| candidate paths, where u is the number of criteria. Numerical studies demonstrate that our algorithm is highly efficient and robust.

Suggested Citation

  • Shi, Ning & Zhou, Shaorui & Wang, Fan & Tao, Yi & Liu, Liming, 2017. "The multi-criteria constrained shortest path problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 101(C), pages 13-29.
    • Handle: RePEc:eee:transe:v:101:y:2017:i:c:p:13-29
    DOI: 10.1016/j.tre.2017.02.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554516304884
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2017.02.002?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. van der Zijpp, N.J. & Fiorenzo Catalano, S., 2005. "Path enumeration by finding the constrained K-shortest paths," Transportation Research Part B: Methodological, Elsevier, vol. 39(6), pages 545-563, July.
    2. Bektas, Tolga & Laporte, Gilbert, 2011. "The Pollution-Routing Problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1232-1250, September.
    3. Tsung-Sheng Chang & Linda K. Nozick & Mark A. Turnquist, 2005. "Multiobjective Path Finding in Stochastic Dynamic Networks, with Application to Routing Hazardous Materials Shipments," Transportation Science, INFORMS, vol. 39(3), pages 383-399, August.
    4. Di Puglia Pugliese, Luigi & Guerriero, Francesca, 2013. "Shortest path problem with forbidden paths: The elementary version," European Journal of Operational Research, Elsevier, vol. 227(2), pages 254-267.
    5. Liu, Ming & Lee, Chung-Yee & Zhang, Zizhen & Chu, Chengbin, 2016. "Bi-objective optimization for the container terminal integrated planning," Transportation Research Part B: Methodological, Elsevier, vol. 93(PB), pages 720-749.
    6. Guo, Xiaolei & Yang, Hai, 2009. "User heterogeneity and bi-criteria system optimum," Transportation Research Part B: Methodological, Elsevier, vol. 43(4), pages 379-390, May.
    7. Rivera, Juan Carlos & Murat Afsar, H. & Prins, Christian, 2016. "Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 249(1), pages 93-104.
    8. Karsten, Christian Vad & Pisinger, David & Ropke, Stefan & Brouer, Berit Dangaard, 2015. "The time constrained multi-commodity network flow problem and its application to liner shipping network design," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 76(C), pages 122-138.
    9. Verma, Manish & Verter, Vedat & Zufferey, Nicolas, 2012. "A bi-objective model for planning and managing rail-truck intermodal transportation of hazardous materials," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 132-149.
    10. Song, Dong-Ping & Li, Dong & Drake, Paul, 2015. "Multi-objective optimization for planning liner shipping service with uncertain port times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 84(C), pages 1-22.
    11. Wang, Li & Yang, Lixing & Gao, Ziyou, 2016. "The constrained shortest path problem with stochastic correlated link travel times," European Journal of Operational Research, Elsevier, vol. 255(1), pages 43-57.
    12. Gabrel, Virginie & Vanderpooten, Daniel, 2002. "Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite," European Journal of Operational Research, Elsevier, vol. 139(3), pages 533-542, June.
    13. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2014. "The bi-objective Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 464-478.
    14. F. Guerriero & R. Musmanno, 2001. "Label Correcting Methods to Solve Multicriteria Shortest Path Problems," Journal of Optimization Theory and Applications, Springer, vol. 111(3), pages 589-613, December.
    15. Santos, Luis & Coutinho-Rodrigues, João & Current, John R., 2007. "An improved solution algorithm for the constrained shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 41(7), pages 756-771, August.
    16. Matthias Ehrgott & Xavier Gandibleux, 2004. "Approximative solution methods for multiobjective combinatorial optimization," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 12(1), pages 1-63, June.
    17. Chen, Bi Yu & Li, Qingquan & Lam, William H.K., 2016. "Finding the k reliable shortest paths under travel time uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 189-203.
    18. Baykasoğlu, Adil & Subulan, Kemal, 2016. "A multi-objective sustainable load planning model for intermodal transportation networks with a real-life application," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 207-247.
    19. Wang, Shuaian & Meng, Qiang & Sun, Zhuo, 2013. "Container routing in liner shipping," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 49(1), pages 1-7.
    20. Wang, Haijun & Du, Lijing & Ma, Shihua, 2014. "Multi-objective open location-routing model with split delivery for optimized relief distribution in post-earthquake," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 160-179.
    21. Martins, Ernesto Queiros Vieira, 1984. "On a multicriteria shortest path problem," European Journal of Operational Research, Elsevier, vol. 16(2), pages 236-245, May.
    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. Shen, Liang & Shao, Hu & Wu, Ting & Fainman, Emily Zhu & Lam, William H.K., 2020. "Finding the reliable shortest path with correlated link travel times in signalized traffic networks under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 144(C).
    2. Elías Escobar-Gómez & J.L. Camas-Anzueto & Sabino Velázquez-Trujillo & Héctor Hernández-de-León & Rubén Grajales-Coutiño & Eduardo Chandomí-Castellanos & Héctor Guerra-Crespo, 2019. "A Linear Programming Model with Fuzzy Arc for Route Optimization in the Urban Road Network," Sustainability, MDPI, vol. 11(23), pages 1-18, November.
    3. P. Festa & F. Guerriero & A. Napoletano, 2019. "An auction-based approach for the re-optimization shortest path tree problem," Computational Optimization and Applications, Springer, vol. 74(3), pages 851-893, December.
    4. Qian Ye & Hyun Kim, 2019. "Partial Node Failure in Shortest Path Network Problems," Sustainability, MDPI, vol. 11(22), pages 1-21, November.

    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. Wang, Li & Yang, Lixing & Gao, Ziyou, 2016. "The constrained shortest path problem with stochastic correlated link travel times," European Journal of Operational Research, Elsevier, vol. 255(1), pages 43-57.
    2. Zajac, Sandra & Huber, Sandra, 2021. "Objectives and methods in multi-objective routing problems: a survey and classification scheme," European Journal of Operational Research, Elsevier, vol. 290(1), pages 1-25.
    3. Xie, Chi & Travis Waller, S., 2012. "Parametric search and problem decomposition for approximating Pareto-optimal paths," Transportation Research Part B: Methodological, Elsevier, vol. 46(8), pages 1043-1067.
    4. Shijin Wang & Xiaodong Wang & Xin Liu & Jianbo Yu, 2018. "A Bi-Objective Vehicle-Routing Problem with Soft Time Windows and Multiple Depots to Minimize the Total Energy Consumption and Customer Dissatisfaction," Sustainability, MDPI, vol. 10(11), pages 1-21, November.
    5. Shen, Liang & Shao, Hu & Wu, Ting & Fainman, Emily Zhu & Lam, William H.K., 2020. "Finding the reliable shortest path with correlated link travel times in signalized traffic networks under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 144(C).
    6. Babagolzadeh, Mahla & Zhang, Yahua & Abbasi, Babak & Shrestha, Anup & Zhang, Anming, 2022. "Promoting Australian regional airports with subsidy schemes: Optimised downstream logistics using vehicle routing problem," Transport Policy, Elsevier, vol. 128(C), pages 38-51.
    7. Mohri, Seyed Sina & Mohammadi, Mehrdad & Gendreau, Michel & Pirayesh, Amir & Ghasemaghaei, Ali & Salehi, Vahid, 2022. "Hazardous material transportation problems: A comprehensive overview of models and solution approaches," European Journal of Operational Research, Elsevier, vol. 302(1), pages 1-38.
    8. Ehmke, Jan Fabian & Campbell, Ann M. & Thomas, Barrett W., 2018. "Optimizing for total costs in vehicle routing in urban areas," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 242-265.
    9. Yagcitekin, Bunyamin & Uzunoglu, Mehmet, 2016. "A double-layer smart charging strategy of electric vehicles taking routing and charge scheduling into account," Applied Energy, Elsevier, vol. 167(C), pages 407-419.
    10. Duque, Daniel & Lozano, Leonardo & Medaglia, Andrés L., 2015. "An exact method for the biobjective shortest path problem for large-scale road networks," European Journal of Operational Research, Elsevier, vol. 242(3), pages 788-797.
    11. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    12. Elifcan Göçmen & Rızvan Erol, 2018. "The Problem of Sustainable Intermodal Transportation: A Case Study of an International Logistics Company, Turkey," Sustainability, MDPI, vol. 10(11), pages 1-16, November.
    13. Yu, Yang & Wu, Yuting & Wang, Junwei, 2019. "Bi-objective green ride-sharing problem: Model and exact method," International Journal of Production Economics, Elsevier, vol. 208(C), pages 472-482.
    14. Dukkanci, Okan & Karsu, Özlem & Kara, Bahar Y., 2022. "Planning sustainable routes: Economic, environmental and welfare concerns," European Journal of Operational Research, Elsevier, vol. 301(1), pages 110-123.
    15. Hamed Farrokhi-Asl & Ahmad Makui & Armin Jabbarzadeh & Farnaz Barzinpour, 2020. "Solving a multi-objective sustainable waste collection problem considering a new collection network," Operational Research, Springer, vol. 20(4), pages 1977-2015, December.
    16. Koyuncu, Işıl & Yavuz, Mesut, 2019. "Duplicating nodes or arcs in green vehicle routing: A computational comparison of two formulations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 122(C), pages 605-623.
    17. Brunner, Carlos & Giesen, Ricardo & Klapp, Mathias A. & Flórez-Calderón, Luz, 2021. "Vehicle routing problem with steep roads," Transportation Research Part A: Policy and Practice, Elsevier, vol. 151(C), pages 1-17.
    18. Goeke, Dominik & Schneider, Michael, 2015. "Routing a mixed fleet of electric and conventional vehicles," European Journal of Operational Research, Elsevier, vol. 245(1), pages 81-99.
    19. Suzuki, Yoshinori & Lan, Bo, 2018. "Cutting fuel consumption of truckload carriers by using new enhanced refueling policies," International Journal of Production Economics, Elsevier, vol. 202(C), pages 69-80.
    20. Wen, Liang & Çatay, Bülent & Eglese, Richard, 2014. "Finding a minimum cost path between a pair of nodes in a time-varying road network with a congestion charge," European Journal of Operational Research, Elsevier, vol. 236(3), pages 915-923.

    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:eee:transe:v:101:y:2017:i:c:p:13-29. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    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.