IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v37y2003i2p170-182.html
   My bibliography  Save this article

Vehicle Routing and Scheduling with Full Truckloads

Author

Listed:
  • Sundararajan Arunapuram

    (Manugistics Inc., Wayne, Pennsylvania 19087)

  • Kamlesh Mathur

    (Department of Operations, Weatherhead School of Management, Case Western Reserve University, Cleveland, Ohio 44106)

  • Daniel Solow

    (Department of Operations, Weatherhead School of Management, Case Western Reserve University, Cleveland, Ohio 44106)

Abstract

Truckload carriers are constantly faced with the problem of shipping full truckloads of goods at minimum cost between pairs of cities or customers, using a fleet of trucks located at one or more depots. In this paper, a new branch-and-bound algorithm for solving an integer-programming formulation of this vehicle-routing problem (VRP) with full truckloads is developed. The algorithm also takes into consideration the time-window constraints and waiting costs. The resulting efficiency, validated by computational tests on random problems, is due to a column-generation scheme that exploits the special structure of the problem to solve the linear-programming relaxation problems that arise at the nodes.

Suggested Citation

  • Sundararajan Arunapuram & Kamlesh Mathur & Daniel Solow, 2003. "Vehicle Routing and Scheduling with Full Truckloads," Transportation Science, INFORMS, vol. 37(2), pages 170-182, May.
    • Handle: RePEc:inm:ortrsc:v:37:y:2003:i:2:p:170-182
    DOI: 10.1287/trsc.37.2.170.15248
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.37.2.170.15248
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.37.2.170.15248?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
    ---><---

    References listed on IDEAS

    as
    1. Mauro Dell'Amico & Matteo Fischetti & Paolo Toth, 1993. "Heuristic Algorithms for the Multiple Depot Vehicle Scheduling Problem," Management Science, INFORMS, vol. 39(1), pages 115-125, January.
    2. Desrochers, Martin & Soumis, Francois, 1988. "A reoptimization algorithm for the shortest path problem with time windows," European Journal of Operational Research, Elsevier, vol. 35(2), pages 242-254, May.
    3. Giorgio Carpaneto & Paolo Toth, 1980. "Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem," Management Science, INFORMS, vol. 26(7), pages 736-743, July.
    4. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    5. Celso C. Ribeiro & François Soumis, 1994. "A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem," Operations Research, INFORMS, vol. 42(1), pages 41-52, February.
    6. Skitt, Robin A. & Levary, Reuven R., 1985. "Vehicle routing via column generation," European Journal of Operational Research, Elsevier, vol. 21(1), pages 65-76, July.
    7. Desaulniers, Guy & Lavigne, June & Soumis, Francois, 1998. "Multi-depot vehicle scheduling problems with time windows and waiting costs," European Journal of Operational Research, Elsevier, vol. 111(3), pages 479-494, December.
    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. Martin Bichler & Hans Ulrich Buhl & Johannes Knörr & Felipe Maldonado & Paul Schott & Stefan Waldherr & Martin Weibelzahl, 2022. "Electricity Markets in a Time of Change: A Call to Arms for Business Research," Schmalenbach Journal of Business Research, Springer, vol. 74(1), pages 77-102, March.
    2. Escudero-Santana, Alejandro & Muñuzuri, Jesús & Cortés, Pablo & Onieva, Luis, 2021. "The one container drayage problem with soft time windows," Research in Transportation Economics, Elsevier, vol. 90(C).
    3. Iris F. A. Vis & Kees Jan Roodbergen, 2009. "Scheduling of Container Storage and Retrieval," Operations Research, INFORMS, vol. 57(2), pages 456-467, April.
    4. Mohammad M. Fazel-Zarandi & J. Christopher Beck, 2012. "Using Logic-Based Benders Decomposition to Solve the Capacity- and Distance-Constrained Plant Location Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 387-398, August.
    5. Nils Boysen & Dirk Briskorn & Stefan Schwerdfeger, 2023. "How to charge while driving: scheduling point-to-point deliveries of an electric vehicle under overhead wiring," Journal of Scheduling, Springer, vol. 26(1), pages 19-41, February.
    6. Taha Hossein Rashidi & Matthew J. Roorda, 2018. "A business establishment fleet ownership and composition model," Transportation, Springer, vol. 45(3), pages 971-987, May.
    7. V M Miori, 2011. "A multiple objective goal programming approach to the truckload routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(8), pages 1524-1532, August.
    8. Zolfagharinia, Hossein & Haughton, Michael, 2018. "The importance of considering non-linear layover and delay costs for local truckers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 331-355.
    9. Neves-Moreira, F. & Amorim, P. & Guimarães, L. & Almada-Lobo, B., 2016. "A long-haul freight transportation problem: Synchronizing resources to deliver requests passing through multiple transshipment locations," European Journal of Operational Research, Elsevier, vol. 248(2), pages 487-506.
    10. Jennifer A. Pazour & Lucas C. Neubert, 2013. "Routing and Scheduling of Cross-Town Drayage Operations at J.B. Hunt Transport," Interfaces, INFORMS, vol. 43(2), pages 117-129, April.

    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. Alberto Ceselli & Giovanni Righini & Matteo Salani, 2009. "A Column Generation Algorithm for a Rich Vehicle-Routing Problem," Transportation Science, INFORMS, vol. 43(1), pages 56-69, February.
    2. Desaulniers, Guy & Lavigne, June & Soumis, Francois, 1998. "Multi-depot vehicle scheduling problems with time windows and waiting costs," European Journal of Operational Research, Elsevier, vol. 111(3), pages 479-494, December.
    3. Hang Xu & Zhi-Long Chen & Srinivas Rajagopal & Sundar Arunapuram, 2003. "Solving a Practical Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 37(3), pages 347-364, August.
    4. Stefan Irnich & Guy Desaulniers & Jacques Desrosiers & Ahmed Hadjar, 2010. "Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 297-313, May.
    5. Niu, Huimin & Zhou, Xuesong & Tian, Xiaopeng, 2018. "Coordinating assignment and routing decisions in transit vehicle schedules: A variable-splitting Lagrangian decomposition approach for solution symmetry breaking," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 70-101.
    6. Hernandez, Florent & Feillet, Dominique & Giroudeau, Rodolphe & Naud, Olivier, 2016. "Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 249(2), pages 551-559.
    7. Kulkarni, Sarang & Krishnamoorthy, Mohan & Ranade, Abhiram & Ernst, Andreas T. & Patil, Rahul, 2018. "A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 457-487.
    8. Timo Gschwind & Stefan Irnich, 2012. "Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing," Working Papers 1211, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    9. Timo Gschwind & Stefan Irnich & Simon Emde & Christian Tilk, 2018. "Branch-Cut-and-Price for the Scheduling Deliveries with Time Windows in a Direct Shipping Network," Working Papers 1805, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    10. Perumal, Shyam S.G. & Lusby, Richard M. & Larsen, Jesper, 2022. "Electric bus planning & scheduling: A review of related problems and methodologies," European Journal of Operational Research, Elsevier, vol. 301(2), pages 395-413.
    11. Ahmed Hadjar & Odile Marcotte & François Soumis, 2006. "A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem," Operations Research, INFORMS, vol. 54(1), pages 130-149, February.
    12. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    13. Vis, Iris F.A., 2006. "Survey of research in the design and control of automated guided vehicle systems," European Journal of Operational Research, Elsevier, vol. 170(3), pages 677-709, May.
    14. Keng Hoo Chuah & Jon C. Yingling, 2005. "Routing for a Just-in-Time Supply Pickup and Delivery System," Transportation Science, INFORMS, vol. 39(3), pages 328-339, August.
    15. Dayarian, Iman & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2015. "A column generation approach for a multi-attribute vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 241(3), pages 888-906.
    16. Timo Gschwind & Stefan Irnich & Christian Tilk & Simon Emde, 2020. "Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network," Journal of Scheduling, Springer, vol. 23(3), pages 363-377, June.
    17. Chris Martin & David Jones & Pinar Keskinocak, 2003. "Optimizing On-Demand Aircraft Schedules for Fractional Aircraft Operators," Interfaces, INFORMS, vol. 33(5), pages 22-35, October.
    18. Sarac, Abdulkadir & Batta, Rajan & Rump, Christopher M., 2006. "A branch-and-price approach for operational aircraft maintenance routing," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1850-1869, December.
    19. Range, Troels Martin, 2013. "Exploiting Set-Based Structures to Accelerate Dynamic Programming Algorithms for the Elementary Shortest Path Problem with Resource Constraints," Discussion Papers on Economics 17/2013, University of Southern Denmark, Department of Economics.
    20. Taş, D. & Gendreau, M. & Dellaert, N. & van Woensel, T. & de Kok, A.G., 2014. "Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach," European Journal of Operational Research, Elsevier, vol. 236(3), pages 789-799.

    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:inm:ortrsc:v:37:y:2003:i:2:p:170-182. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.