IDEAS home Printed from https://ideas.repec.org/a/eee/transa/v38y2004i4p305-328.html
   My bibliography  Save this article

Ferry service network design: optimal fleet size, routing, and scheduling

Author

Listed:
  • Lai, M. F.
  • Lo, Hong K.

Abstract

The study formulated a ferry network design problem by considering the optimal fleet size, routing, and scheduling for both direct and multi-stop services. The objective function combines both the operator and passengers' performance measures. Mathematically, the model is formulated as a mixed integer multiple origin-destination network flow problem with ferry capacity constraints. To solve this problem of practical size, this study developed a heuristic algorithm that exploits the polynomial-time performance of shortest path algorithms. Two scenarios of ferry services in Hong Kong were solved to demonstrate the performance of the heuristic algorithm. The results showed that the heuristic produced solutions that were within 1.3% from the CPLEX optimal solutions. The computational time is within tens of seconds even for problem size that is beyond the capability of CPLEX.

Suggested Citation

  • Lai, M. F. & Lo, Hong K., 2004. "Ferry service network design: optimal fleet size, routing, and scheduling," Transportation Research Part A: Policy and Practice, Elsevier, vol. 38(4), pages 305-328, May.
    • Handle: RePEc:eee:transa:v:38:y:2004:i:4:p:305-328
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0965-8564(03)00119-8
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Yan, Shangyao & Young, Hwei-Fwa, 1996. "A decision support framework for multi-fleet routing and multi-stop flight scheduling," Transportation Research Part A: Policy and Practice, Elsevier, vol. 30(5), pages 379-398, September.
    2. Michael Francis Gorman, 1998. "An application of genetic and tabu searches to the freight railroad operating plan problem," Annals of Operations Research, Springer, vol. 78(0), pages 51-69, January.
    3. 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.
    4. Ceder, Avishai & Wilson, Nigel H. M., 1986. "Bus network design," Transportation Research Part B: Methodological, Elsevier, vol. 20(4), pages 331-344, August.
    5. Crainic, Teodor Gabriel, 2000. "Service network design in freight transportation," European Journal of Operational Research, Elsevier, vol. 122(2), pages 272-288, April.
    6. 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.
    7. Judith M. Farvolden & Warren B. Powell, 1994. "Subgradient Methods for the Service Network Design Problem," Transportation Science, INFORMS, vol. 28(3), pages 256-272, August.
    8. 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.
    9. Crainic, Teodor Gabriel & Laporte, Gilbert, 1997. "Planning models for freight transportation," European Journal of Operational Research, Elsevier, vol. 97(3), pages 409-438, March.
    10. 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.
    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. 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.
    2. Ng, ManWo & Lo, Hong K., 2016. "Robust models for transportation service network design," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 378-386.
    3. 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.
    4. Bell, Michael G.H. & Pan, Jing-Jing & Teye, Collins & Cheung, Kam-Fung & Perera, Supun, 2020. "An entropy maximizing approach to the ferry network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 132(C), pages 15-28.
    5. 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).
    6. 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.
    7. 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.
    8. 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.
    9. Lo, Hong K. & An, Kun & Lin, Wei-hua, 2013. "Ferry service network design under demand uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 59(C), pages 48-70.
    10. Amadeu A. Coco & Christophe Duhamel & Andréa Cynthia Santos, 2020. "Modeling and solving the multi-period disruptions scheduling problem on urban networks," Annals of Operations Research, Springer, vol. 285(1), pages 427-443, February.
    11. Aslaksen, Ingvild Eide & Svanberg, Elisabeth & Fagerholt, Kjetil & Johnsen, Lennart C. & Meisel, Frank, 2021. "A combined dial-a-ride and fixed schedule ferry service for coastal cities," Transportation Research Part A: Policy and Practice, Elsevier, vol. 153(C), pages 306-325.
    12. Wang, David Z.W. & Lo, Hong K., 2008. "Multi-fleet ferry service network design with passenger preferences for differential services," Transportation Research Part B: Methodological, Elsevier, vol. 42(9), pages 798-822, November.
    13. Havre, Håkon Furnes & Lien, Ulrik & Ness, Mattias Myklebust & Fagerholt, Kjetil & Rødseth, Kenneth Løvold, 2024. "Network design with route planning for battery electric high-speed passenger vessel services," European Journal of Operational Research, Elsevier, vol. 315(1), pages 102-119.
    14. 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.
    15. 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.
    16. C E Cortés & M Gendreau & D Leng & A Weintraub, 2011. "A simulation-based approach for fleet design in a technician dispatch problem with stochastic demand," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(8), pages 1510-1523, August.
    17. 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).
    18. An, Kun & Lo, Hong K., 2015. "Robust transit network design with stochastic demand considering development density," Transportation Research Part B: Methodological, Elsevier, vol. 81(P3), pages 737-754.
    19. Škurić, Maja & Maraš, Vladislav & Davidović, Tatjana & Radonjić, Aleksandar, 2021. "Optimal allocating and sizing of passenger ferry fleet in maritime transport," Research in Transportation Economics, Elsevier, vol. 90(C).
    20. Pantuso, Giovanni & Fagerholt, Kjetil & Hvattum, Lars Magnus, 2014. "A survey on maritime fleet size and mix problems," European Journal of Operational Research, Elsevier, vol. 235(2), pages 341-349.

    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. 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.
    2. Dall'Orto, Leonardo Campo & Crainic, Teodor Gabriel & Leal, Jose Eugenio & Powell, Warren B., 2006. "The single-node dynamic service scheduling and dispatching problem," European Journal of Operational Research, Elsevier, vol. 170(1), pages 1-23, April.
    3. Wang, David Z.W. & Lo, Hong K., 2008. "Multi-fleet ferry service network design with passenger preferences for differential services," Transportation Research Part B: Methodological, Elsevier, vol. 42(9), pages 798-822, November.
    4. C S Sung & S H Song, 2003. "Integrated service network design for a cross-docking supply chain network," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(12), pages 1283-1295, December.
    5. Arnt-Gunnar Lium & Teodor Gabriel Crainic & Stein W. Wallace, 2009. "A Study of Demand Stochasticity in Service Network Design," Transportation Science, INFORMS, vol. 43(2), pages 144-157, May.
    6. Meuffels, W.J.M., 2015. "The design of road and air networks for express service providers," Other publications TiSEM d3266cb8-bc55-41be-adc7-4, Tilburg University, School of Economics and Management.
    7. Jansen, Benjamin & Swinkels, Pieter C. J. & Teeuwen, Geert J. A. & van Antwerpen de Fluiter, Babette & Fleuren, Hein A., 2004. "Operational planning of a large-scale multi-modal transportation system," European Journal of Operational Research, Elsevier, vol. 156(1), pages 41-53, July.
    8. Louwerse, I. & Mijnarends, J. & Meuffels, I. & Huisman, D. & Fleuren, H.A., 2012. "Scheduling Movements in the Network of an Express Service Provider," Econometric Institute Research Papers EI 2012-08, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    9. Naga V. C. Gudapati & Enrico Malaguti & Michele Monaci, 2022. "Network Design with Service Requirements: Scaling-up the Size of Solvable Problems," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2571-2582, September.
    10. 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.
    11. 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.
    12. Andrew P. Armacost & Cynthia Barnhart & Keith A. Ware & Alysia M. Wilson, 2004. "UPS Optimizes Its Air Network," Interfaces, INFORMS, vol. 34(1), pages 15-25, February.
    13. Quesada Pérez, José Miguel & Lange, Jean-Charles & Tancrez, Jean-Sébastien, 2018. "A multi-hub Express Shipment Service Network Design model with flexible hub assignment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 120(C), pages 116-131.
    14. Yıldız, Barış & Savelsbergh, Martin, 2022. "Optimizing package express operations in China," European Journal of Operational Research, Elsevier, vol. 300(1), pages 320-335.
    15. Jansen, B. & Swinkels, P.C.J. & Teeuwen, G.J.A. & van Antwerpen-de Fluiter, B. & Fleuren, H.A., 2004. "Operational planning of a large-scale multi-modal transportation system," Other publications TiSEM ebdccccf-58bc-4ced-91e7-f, Tilburg University, School of Economics and Management.
    16. Anantaram Balakrishnan & Gang Li & Prakash Mirchandani, 2017. "Optimal Network Design with End-to-End Service Requirements," Operations Research, INFORMS, vol. 65(3), pages 729-750, June.
    17. Ahmad I. Jarrah & Ellis Johnson & Lucas C. Neubert, 2009. "Large-Scale, Less-than-Truckload Service Network Design," Operations Research, INFORMS, vol. 57(3), pages 609-625, June.
    18. 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.
    19. 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.
    20. Grunert, Tore & Sebastian, Hans-Jurgen, 2000. "Planning models for long-haul operations of postal and express shipment companies," European Journal of Operational Research, Elsevier, vol. 122(2), pages 289-309, April.

    More about this item

    Statistics

    Access and download statistics

    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:transa:v:38:y:2004:i:4:p:305-328. 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/547/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.