IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v35y2001i6p525-547.html
   My bibliography  Save this article

The freight routing problem of time-definite freight delivery common carriers

Author

Listed:
  • Lin, Cheng-Chang

Abstract

The freight routing problem of time-definite common carriers is to minimize the sum of handling and transportation costs, while meeting service commitments and operational restrictions. There are two types of operational restrictions, capacity and directed in-tree rooted at each destination. Directed in-tree implicitly implies that there is a singular path for each origin-destination pair. The routing problem is an integrality constrained multi-commodity problem with side constraints. In this research, we study two approaches, the Lagrangian relaxation (LR) and implicit enumeration algorithm with [var epsilon]-optimality (IE-[var epsilon]). We use the third largest time-definite freight delivery common carrier in Taiwan for our numerical test. The result shows that the IE-[var epsilon] outperforms the LR, both quantitatively and qualitatively. In addition, two major shortcomings of the LR approach are shown: it may fail to find any feasible solutions even though they exist, and it cannot determine whether the feasible set is empty or not.

Suggested Citation

  • Lin, Cheng-Chang, 2001. "The freight routing problem of time-definite freight delivery common carriers," Transportation Research Part B: Methodological, Elsevier, vol. 35(6), pages 525-547, July.
    • Handle: RePEc:eee:transb:v:35:y:2001:i:6:p:525-547
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191-2615(00)00008-4
    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. Warren B. Powell & Ioannis A. Koskosidis, 1992. "Shipment Routing Algorithms with Tree Constraints," Transportation Science, INFORMS, vol. 26(3), pages 230-245, August.
    2. Cynthia Barnhart & Yosef Sheffi, 1993. "A Network-Based Primal-Dual Heuristic for the Solution of Multicommodity Network Flow Problems," Transportation Science, INFORMS, vol. 27(2), pages 102-117, May.
    3. J. A. Tomlin, 1966. "Minimum-Cost Multicommodity Network Flows," Operations Research, INFORMS, vol. 14(1), pages 45-51, February.
    4. Warren B. Powell & Yosef Sheffi, 1989. "OR Practice—Design and Implementation of an Interactive Optimization System for Network Design in the Motor Carrier Industry," Operations Research, INFORMS, vol. 37(1), pages 12-29, February.
    5. Janny M. Y. Leung & Thomas L. Magnanti & Vijay Singhal, 1990. "Routing in Point-to-Point Delivery Systems: Formulations and Solution Heuristics," Transportation Science, INFORMS, vol. 24(4), pages 245-260, 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. Theo Arentze & Tao Feng & Harry Timmermans & Jops Robroeks, 2012. "Context-dependent influence of road attributes and pricing policies on route choice behavior of truck drivers: results of a conjoint choice experiment," Transportation, Springer, vol. 39(6), pages 1173-1188, November.
    2. Omar Ben-Ayed, 2012. "Redesigning the inter-facility network of a parcel distribution company in a developing country," International Journal of Services, Economics and Management, Inderscience Enterprises Ltd, vol. 4(1), pages 27-42.
    3. Lin, Cheng-Chang & Lee, Shwu-Chiou, 2018. "Hub network design problem with profit optimization for time-definite LTL freight transportation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 104-120.
    4. Sheu Chen, 2010. "A Heuristic Algorithm for Hierarchical Hub-and-spoke Network of Time-definite Common Carrier Operation Planning Problem," Networks and Spatial Economics, Springer, vol. 10(4), pages 509-523, December.
    5. G. Guastaroba & M. G. Speranza & D. Vigo, 2016. "Intermediate Facilities in Freight Transportation Planning: A Survey," Transportation Science, INFORMS, vol. 50(3), pages 763-789, August.
    6. Lin, Cheng-Chang & Chen, Sheu-Hua, 2004. "The hierarchical network design problem for time-definite express common carriers," Transportation Research Part B: Methodological, Elsevier, vol. 38(3), pages 271-283, March.
    7. Estrada-Romeu, Miquel & Robusté, Francesc, 2015. "Stopover and hub-and-spoke shipment strategies in less-than-truckload carriers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 76(C), pages 108-121.
    8. Lin, Cheng-Chang & Lin, Yu-Jen & Lin, Dung-Ying, 2003. "The economic effects of center-to-center directs on hub-and-spoke networks for air express common carriers," Journal of Air Transport Management, Elsevier, vol. 9(4), pages 255-265.
    9. Lin, Cheng-Chang, 2010. "The integrated secondary route network design model in the hierarchical hub-and-spoke network for dual express services," International Journal of Production Economics, Elsevier, vol. 123(1), pages 20-30, January.
    10. 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.
    11. Meuffels, W.J.M. & Fleuren, H.A. & Cruijssen, F. & van Dam, E.R., 2009. "Enriching the Tactical Network Design of Express Service Carriers with Fleet Scheduling Characteristics," Discussion Paper 2009-79, Tilburg University, Center for Economic Research.
    12. Greening, Lacy M. & Dahan, Mathieu & Erera, Alan L., 2023. "Lead-Time-Constrained Middle-Mile Consolidation Network Design with Fixed Origins and Destinations," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    13. Campbell, James F., 2013. "A continuous approximation model for time definite many-to-many transportation," Transportation Research Part B: Methodological, Elsevier, vol. 54(C), pages 100-112.
    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. Sarah Root & Amy Cohn, 2008. "A novel modeling approach for express package carrier planning," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(7), pages 670-683, October.
    16. Hande Yaman & Oya Ekin Karasan & Bahar Y. Kara, 2012. "Release Time Scheduling and Hub Location for Next-Day Delivery," Operations Research, INFORMS, vol. 60(4), pages 906-917, August.
    17. Lin, Cheng-Chang & Lee, Shwu-Chiou, 2010. "The competition game on hub network design," Transportation Research Part B: Methodological, Elsevier, vol. 44(4), pages 618-629, May.
    18. Meuffels, W.J.M. & Fleuren, H.A. & Cruijssen, F. & van Dam, E.R., 2009. "Enriching the Tactical Network Design of Express Service Carriers with Fleet Scheduling Characteristics," Other publications TiSEM e146d914-9638-4ae0-9587-b, Tilburg University, School of Economics and Management.

    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. Tamvada, Srinivas Subramanya & Mansouri, Bahareh & Hassini, Elkafi & Pribytkov, Theodore, 2021. "An integer programming model and directed Steiner-forest based heuristic for routing less-than-truckload freight," International Journal of Production Economics, Elsevier, vol. 232(C).
    2. Raymond K. Cheung & B. Muralidharan, 2000. "Dynamic Routing for Priority Shipments in LTL Service Networks," Transportation Science, INFORMS, vol. 34(1), pages 86-98, February.
    3. Crainic, Teodor Gabriel, 2000. "Service network design in freight transportation," European Journal of Operational Research, Elsevier, vol. 122(2), pages 272-288, April.
    4. 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.
    5. Kaj Holmberg & Di Yuan, 2003. "A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 42-57, February.
    6. Alan Erera & Michael Hewitt & Martin Savelsbergh & Yang Zhang, 2013. "Improved Load Plan Design Through Integer Programming Based Local Search," Transportation Science, INFORMS, vol. 47(3), pages 412-427, August.
    7. G. Guastaroba & M. G. Speranza & D. Vigo, 2016. "Intermediate Facilities in Freight Transportation Planning: A Survey," Transportation Science, INFORMS, vol. 50(3), pages 763-789, August.
    8. J. F. Campbell & A. T. Ernst & M. Krishnamoorthy, 2005. "Hub Arc Location Problems: Part I---Introduction and Results," Management Science, INFORMS, vol. 51(10), pages 1540-1555, October.
    9. Klaus Büdenbender & Tore Grünert & Hans-Jürgen Sebastian, 2000. "A Hybrid Tabu Search/Branch-and-Bound Algorithm for the Direct Flight Network Design Problem," Transportation Science, INFORMS, vol. 34(4), pages 364-380, November.
    10. 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.
    11. Rina R. Schneur & James B. Orlin, 1998. "A Scaling Algorithm for Multicommodity Flow Problems," Operations Research, INFORMS, vol. 46(2), pages 231-246, April.
    12. Michael F. Gorman & John-Paul Clarke & Amir Hossein Gharehgozli & Michael Hewitt & René de Koster & Debjit Roy, 2014. "State of the Practice: A Review of the Application of OR/MS in Freight Transportation," Interfaces, INFORMS, vol. 44(6), pages 535-554, December.
    13. 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.
    14. C S Sung & W Yang, 2008. "An exact algorithm for a cross-docking supply chain network design problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(1), pages 119-136, January.
    15. Christina N. Burt & Lou Caccetta, 2014. "Equipment Selection for Surface Mining: A Review," Interfaces, INFORMS, vol. 44(2), pages 143-162, April.
    16. Dewil, R. & Vansteenwegen, P. & Cattrysse, D. & Van Oudheusden, D., 2015. "A minimum cost network flow model for the maximum covering and patrol routing problem," European Journal of Operational Research, Elsevier, vol. 247(1), pages 27-36.
    17. Mehdy Roayaei & Mohammadreza Razzazi, 2017. "Augmenting weighted graphs to establish directed point-to-point connectivity," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 1030-1056, April.
    18. Garg, Manish & Smith, J. Cole, 2008. "Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios," Omega, Elsevier, vol. 36(6), pages 1057-1071, December.
    19. 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.
    20. Rémy Dupas & Eiichi Taniguchi & Jean-Christophe Deschamps & Ali G. Qureshi, 2020. "A Multi-commodity Network Flow Model for Sustainable Performance Evaluation in City Logistics: Application to the Distribution of Multi-tenant Buildings in Tokyo," Sustainability, MDPI, vol. 12(6), pages 1-18, March.

    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:transb:v:35:y:2001:i:6:p:525-547. 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/548/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.