IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v276y2019i2p483-494.html
   My bibliography  Save this article

A hybrid algorithm for large-scale service network design considering a heterogeneous fleet

Author

Listed:
  • Wang, Zujian
  • Qi, Mingyao
  • Cheng, Chun
  • Zhang, Canrong

Abstract

Service network design addresses decisions related to transportation services operation and origin-to-destination commodity flow distribution. In this paper, we consider the usage of a heterogeneous fleet to provide services for a very large transportation network. Apart from decisions on transportation services and commodity flow, the problem also determines the number of vehicles of different types that facilitated on each service link, to better reflect real applications. We propose both arc-based and cycle-path models to formulate the problem. A hybrid algorithm is presented to solve large-scale instances. The method includes pricing and cutting techniques to achieve tight lower bounds, as well as a local search algorithm to obtain high-quality solutions. Computational study indicates the effectiveness and efficiency of the proposed algorithm when compared to the state-of-the-art solver CPLEX. The proposed methodology is applied to a real-world network, which shows the necessity of considering a heterogeneous fleet.

Suggested Citation

  • Wang, Zujian & Qi, Mingyao & Cheng, Chun & Zhang, Canrong, 2019. "A hybrid algorithm for large-scale service network design considering a heterogeneous fleet," European Journal of Operational Research, Elsevier, vol. 276(2), pages 483-494.
    • Handle: RePEc:eee:ejores:v:276:y:2019:i:2:p:483-494
    DOI: 10.1016/j.ejor.2019.01.022
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719300414
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.01.022?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. Andersen, Jardar & Crainic, Teodor Gabriel & Christiansen, Marielle, 2009. "Service network design with management and coordination of multiple fleets," European Journal of Operational Research, Elsevier, vol. 193(2), pages 377-389, March.
    2. Teodor Gabriel Crainic & Mike Hewitt & Michel Toulouse & Duc Minh Vu, 2018. "Scheduled service network design with resource acquisition and management," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 277-309, September.
    3. Richa Agarwal & Özlem Ergun, 2008. "Ship Scheduling and Network Design for Cargo Routing in Liner Shipping," Transportation Science, INFORMS, vol. 42(2), pages 175-196, May.
    4. Ilfat Ghamlouche & Teodor Crainic & Michel Gendreau, 2004. "Path Relinking, Cycle-Based Neighbourhoods and Capacitated Multicommodity Network Design," Annals of Operations Research, Springer, vol. 131(1), pages 109-133, October.
    5. 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.
    6. Tang, Ching-Hui & Yan, Shangyao & Chen, Yu-Hsuan, 2008. "An integrated model and solution algorithms for passenger, cargo, and combi flight scheduling," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(6), pages 1004-1024, November.
    7. Natashia Boland & Mike Hewitt & Luke Marshall & Martin Savelsbergh, 2017. "The Continuous-Time Service Network Design Problem," Operations Research, INFORMS, vol. 65(5), pages 1303-1321, October.
    8. Teypaz, Nicolas & Schrenk, Susann & Cung, Van-Dat, 2010. "A decomposition scheme for large-scale Service Network Design with asset management," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(1), pages 156-170, January.
    9. An, Kun & Lo, Hong K., 2014. "Ferry service network design with stochastic demand under user equilibrium flows," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 70-89.
    10. Daeki Kim & Cynthia Barnhart & Keith Ware & Gregory Reinhardt, 1999. "Multimodal Express Package Delivery: A Service Network Design Application," Transportation Science, INFORMS, vol. 33(4), pages 391-407, November.
    11. Michael Berliner Pedersen & Teodor Gabriel Crainic & Oli B. G. Madsen, 2009. "Models and Tabu Search Metaheuristics for Service Network Design with Asset-Balance Requirements," Transportation Science, INFORMS, vol. 43(2), pages 158-177, May.
    12. Jardar Andersen & Marielle Christiansen & Teodor Gabriel Crainic & Roar Grønhaug, 2011. "Branch and Price for Service Network Design with Asset Management Constraints," Transportation Science, INFORMS, vol. 45(1), pages 33-49, February.
    13. Yan, Shangyao & Chen, Hao-Lei, 2002. "A scheduling model and a solution algorithm for inter-city bus carriers," Transportation Research Part A: Policy and Practice, Elsevier, vol. 36(9), pages 805-825, November.
    14. J Andersen & M Christiansen, 2009. "Designing new European rail freight services," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(3), pages 348-360, March.
    15. Xiao Ruan & Xuehao Feng & Kelvin Pang, 2018. "Development of port service network in OBOR via capacity sharing: an idea from Zhejiang province in China," Maritime Policy & Management, Taylor & Francis Journals, vol. 45(1), pages 105-124, January.
    16. Li, Xiangyong & Wei, Kai & Aneja, Y.P. & Tian, Peng, 2017. "Design-balanced capacitated multicommodity network design with heterogeneous assets," Omega, Elsevier, vol. 67(C), pages 145-159.
    17. Smilowitz, Karen R. & Atamtürk, Alper & Daganzo, Carlos F., 2003. "Deferred item and vehicle routing within integrated networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 39(4), pages 305-323, July.
    18. Daniela Ambrosino & Claudio Ferrari & Anna Sciomachen & Alessio Tei, 2018. "Ports, external costs, and Northern Italian transport network design: effects for the planned transformation," Maritime Policy & Management, Taylor & Francis Journals, vol. 45(6), pages 803-818, August.
    19. Andrew P. Armacost & Cynthia Barnhart & Keith A. Ware, 2002. "Composite Variable Formulations for Express Shipment Service Network Design," Transportation Science, INFORMS, vol. 36(1), pages 1-20, February.
    20. SteadieSeifi, M. & Dellaert, N.P. & Nuijten, W. & Van Woensel, T. & Raoufi, R., 2014. "Multimodal freight transportation planning: A literature review," European Journal of Operational Research, Elsevier, vol. 233(1), pages 1-15.
    21. Lin, Cheng-Chang & Chen, Yin-Chieh, 2003. "The integration of Taiwanese and Chinese air networks for direct air cargo services," Transportation Research Part A: Policy and Practice, Elsevier, vol. 37(7), pages 629-647, August.
    22. Ilfat Ghamlouche & Teodor Gabriel Crainic & Michel Gendreau, 2003. "Cycle-Based Neighbourhoods for Fixed-Charge Capacitated Multicommodity Network Design," Operations Research, INFORMS, vol. 51(4), pages 655-667, August.
    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. Wang, Zujian & Qi, Mingyao, 2019. "Service network design considering multiple types of services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 1-14.
    2. Belieres, Simon & Hewitt, Mike & Jozefowiez, Nicolas & Semet, Frédéric & Van Woensel, Tom, 2020. "A Benders decomposition-based approach for logistics service network design," European Journal of Operational Research, Elsevier, vol. 286(2), pages 523-537.
    3. Rajabighamchi, Farzaneh & van Hoesel, Stan & Defryn, Christof, 2023. "Bus service for cargo," Research Memorandum 005, Maastricht University, Graduate School of Business and Economics (GSBE).
    4. Xudong Diao & Ai Gao & Xin Jin & Hui Chen, 2022. "A Layer-Based Relaxation Approach for Service Network Design," Sustainability, MDPI, vol. 14(20), pages 1-13, October.
    5. Liu, Chuanju & Lin, Shaochong & Shen, Zuo-Jun Max & Zhang, Junlong, 2023. "Stochastic service network design: The value of fixed routes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 174(C).
    6. Zhang, X. & Liu, X., 2022. "A two-stage robust model for express service network design with surging demand," European Journal of Operational Research, Elsevier, vol. 299(1), pages 154-167.
    7. Liu, Chuanju & Zhang, Junlong & Lin, Shaochong & Shen, Zuo-Jun Max, 2023. "Service network design with consistent multiple trips," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 171(C).
    8. Fan, Qiaochu & van Essen, J. Theresia & Correia, Gonçalo H.A., 2024. "A bi-level framework for heterogeneous fleet sizing of ride-hailing services considering an approximated mixed equilibrium between automated and non-automated traffic," European Journal of Operational Research, Elsevier, vol. 315(3), pages 879-898.

    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, Zujian & Qi, Mingyao, 2019. "Service network design considering multiple types of services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 1-14.
    2. Bilegan, Ioana C. & Crainic, Teodor Gabriel & Wang, Yunfei, 2022. "Scheduled service network design with revenue management considerations and an intermodal barge transportation illustration," European Journal of Operational Research, Elsevier, vol. 300(1), pages 164-177.
    3. Liu, Chuanju & Zhang, Junlong & Lin, Shaochong & Shen, Zuo-Jun Max, 2023. "Service network design with consistent multiple trips," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 171(C).
    4. SteadieSeifi, M. & Dellaert, N.P. & Nuijten, W. & Van Woensel, T. & Raoufi, R., 2014. "Multimodal freight transportation planning: A literature review," European Journal of Operational Research, Elsevier, vol. 233(1), pages 1-15.
    5. Mervat Chouman & Teodor Gabriel Crainic, 2015. "Cutting-Plane Matheuristic for Service Network Design with Design-Balanced Requirements," Transportation Science, INFORMS, vol. 49(1), pages 99-113, February.
    6. Li, Xiangyong & Ding, Yi & Pan, Kai & Jiang, Dapei & Aneja, Y.P., 2020. "Single-path service network design problem with resource constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    7. Li, Xiangyong & Wei, Kai & Aneja, Y.P. & Tian, Peng, 2017. "Design-balanced capacitated multicommodity network design with heterogeneous assets," Omega, Elsevier, vol. 67(C), pages 145-159.
    8. Bai, Ruibin & Wallace, Stein W. & Li, Jingpeng & Chong, Alain Yee-Loong, 2014. "Stochastic service network design with rerouting," Transportation Research Part B: Methodological, Elsevier, vol. 60(C), pages 50-65.
    9. SteadieSeifi, M. & Dellaert, N.P. & Nuijten, W. & Van Woensel, T., 2017. "A metaheuristic for the multimodal network flow problem with product quality preservation and empty repositioning," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 321-344.
    10. Xin Wang & Teodor Gabriel Crainic & Stein W. Wallace, 2019. "Stochastic Network Design for Planning Scheduled Transportation Services: The Value of Deterministic Solutions," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 153-170, February.
    11. Crainic, Teodor Gabriel & Gendron, Bernard & Akhavan Kazemzadeh, Mohammad Rahim, 2022. "A taxonomy of multilayer network design and a survey of transportation and telecommunication applications," European Journal of Operational Research, Elsevier, vol. 303(1), pages 1-13.
    12. Teodor Gabriel Crainic & Nicoletta Ricciardi & Giovanni Storchi, 2009. "Models for Evaluating and Planning City Logistics Systems," Transportation Science, INFORMS, vol. 43(4), pages 432-454, November.
    13. Jardar Andersen & Marielle Christiansen & Teodor Gabriel Crainic & Roar Grønhaug, 2011. "Branch and Price for Service Network Design with Asset Management Constraints," Transportation Science, INFORMS, vol. 45(1), pages 33-49, February.
    14. Ahmad Baubaid & Natashia Boland & Martin Savelsbergh, 2021. "The Value of Limited Flexibility in Service Network Designs," Transportation Science, INFORMS, vol. 55(1), pages 52-74, 1-2.
    15. Zhang, X. & Liu, X., 2022. "A two-stage robust model for express service network design with surging demand," European Journal of Operational Research, Elsevier, vol. 299(1), pages 154-167.
    16. Naoto Katayama, 2020. "MIP neighborhood search heuristics for a service network design problem with design-balanced requirements," Journal of Heuristics, Springer, vol. 26(4), pages 475-502, August.
    17. Liu, Chuanju & Lin, Shaochong & Shen, Zuo-Jun Max & Zhang, Junlong, 2023. "Stochastic service network design: The value of fixed routes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 174(C).
    18. Li, Xiangyong & Wei, Kai & Guo, Zhaoxia & Wang, Wei & Aneja, Y.P., 2021. "An exact approach for the service network design problem with heterogeneous resource constraints," Omega, Elsevier, vol. 102(C).
    19. Dayarian, Iman & Rocco, Adolfo & Erera, Alan & Savelsbergh, Martin, 2022. "Operations design for high-velocity intra-city package service," Transportation Research Part B: Methodological, Elsevier, vol. 161(C), pages 150-168.
    20. Hewitt, Mike & Crainic, Teodor Gabriel & Nowak, Maciek & Rei, Walter, 2019. "Scheduled service network design with resource acquisition and management under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 324-343.

    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:ejores:v:276:y:2019:i:2:p:483-494. 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/locate/eor .

    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.