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

A Heuristic Algorithm for the Auto-Carrier Transportation Problem

Author

Listed:
  • R. Tadei

    (D.A.I., Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129, Torino, Italy)

  • G. Perboli

    (D.A.I., Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129, Torino, Italy)

  • F. Della Croce

    (D.A.I., Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129, Torino, Italy)

Abstract

The delivery of vehicles to dealers is one of the major tasks in the vehicle production industry. It has relied on transportation companies that use special tractor-trailer trucks called auto-carriers. One of the main problems these companies have to solve is the optimal loading and routing of the auto-carriers, referred to as the Auto-Carrier Transportation (ACT) problem. In this paper we provide an integer programming formulation of the ACT problem and show that the problem is NP -hard in the strong sense. A three-step heuristic procedure stronglybased on the IP formulation, which considers loading, vehicle selection, and routing aspects, is proposed. An application to a real case studyof a vehicle transportation company located in northern Italyis given, with an average deviation lower than 3% from an upper bound on the optimal solution value.

Suggested Citation

  • R. Tadei & G. Perboli & F. Della Croce, 2002. "A Heuristic Algorithm for the Auto-Carrier Transportation Problem," Transportation Science, INFORMS, vol. 36(1), pages 55-62, February.
    • Handle: RePEc:inm:ortrsc:v:36:y:2002:i:1:p:55-62
    DOI: 10.1287/trsc.36.1.55.567
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.36.1.55.567
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.36.1.55.567?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. Irnich, Stefan, 2000. "A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles," European Journal of Operational Research, Elsevier, vol. 122(2), pages 310-328, April.
    2. K Fagerholt & M Christiansen, 2000. "A combined ship scheduling and allocation problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 51(7), pages 834-842, July.
    3. M. W. P. Savelsbergh & M. Sol, 1995. "The General Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 29(1), pages 17-29, February.
    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. Perboli, Guido & Tadei, Roberto & Gobbato, Luca, 2014. "The Multi-Handler Knapsack Problem under Uncertainty," European Journal of Operational Research, Elsevier, vol. 236(3), pages 1000-1007.
    2. Sun, Yanshuo & Kirtonia, Sajeeb & Chen, Zhi-Long, 2021. "A survey of finished vehicle distribution and related problems from an optimization perspective," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    3. Christian Billing & Florian Jaehn & Thomas Wensing, 2018. "A multiperiod auto-carrier transportation problem with probabilistic future demands," Journal of Business Economics, Springer, vol. 88(7), pages 1009-1028, September.
    4. Manuel Iori & Silvano Martello, 2010. "Routing problems with loading constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 4-27, July.
    5. Cordeau, Jean-François & Dell’Amico, Mauro & Falavigna, Simone & Iori, Manuel, 2015. "A rolling horizon algorithm for auto-carrier transportation," Transportation Research Part B: Methodological, Elsevier, vol. 76(C), pages 68-80.
    6. Mauro Dell’Amico & Simone Falavigna & Manuel Iori, 2015. "Optimization of a Real-World Auto-Carrier Transportation Problem," Transportation Science, INFORMS, vol. 49(2), pages 402-419, May.
    7. Chen, Feng & Wang, Yu, 2020. "Downward compatible loading optimization with inter-set cost in automobile outbound logistics," European Journal of Operational Research, Elsevier, vol. 287(1), pages 106-118.
    8. Jäck, Christian & Gönsch, Jochen, 2024. "How to load your auto carrier. A hybrid packing approach for the auto-carrier loading problem," European Journal of Operational Research, Elsevier, vol. 315(3), pages 1167-1181.
    9. Kim, Jindae & Ok, Chang-Soo & Kumara, Soundar & Yee, Shang-Tae, 2010. "A market-based approach for dynamic vehicle deployment planning using radio frequency identification (RFID) information," International Journal of Production Economics, Elsevier, vol. 128(1), pages 235-247, November.
    10. Bonassa, Antonio Carlos & Cunha, Claudio Barbieri da & Isler, Cassiano Augusto, 2023. "A multi-start local search heuristic for the multi-period auto-carrier loading and transportation problem in Brazil," European Journal of Operational Research, Elsevier, vol. 307(1), pages 193-211.
    11. Wang, Yu & Chen, Feng & Chen, Zhi-Long, 2018. "Pickup and delivery of automobiles from warehouses to dealers," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 412-430.
    12. Mingzhou Jin & Sandra Eksioglu & Burak Eksioglu & Haiyuan Wang, 2010. "Mode Selection for Automotive Distribution with Quantity Discounts," Networks and Spatial Economics, Springer, vol. 10(1), pages 1-13, March.

    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. Pang, King-Wah & Xu, Zhou & Li, Chung-Lun, 2011. "Ship routing problem with berthing time clash avoidance constraints," International Journal of Production Economics, Elsevier, vol. 131(2), pages 752-762, June.
    2. Tino Henke & M. Grazia Speranza & Gerhard Wäscher, 2019. "A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes," Annals of Operations Research, Springer, vol. 275(2), pages 321-338, April.
    3. Hassan S. Hayajneh & Xuewei Zhang, 2020. "Logistics Design for Mobile Battery Energy Storage Systems," Energies, MDPI, vol. 13(5), pages 1-14, March.
    4. Ostermeier, Manuel & Henke, Tino & Hübner, Alexander & Wäscher, Gerhard, 2021. "Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions," European Journal of Operational Research, Elsevier, vol. 292(3), pages 799-817.
    5. Lu, Quan & Dessouky, Maged M., 2006. "A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 175(2), pages 672-687, December.
    6. Gronalt, Manfred & Hartl, Richard F. & Reimann, Marc, 2003. "New savings based algorithms for time constrained pickup and delivery of full truckloads," European Journal of Operational Research, Elsevier, vol. 151(3), pages 520-535, December.
    7. Y H Lee & J I Kim & K H Kang & K H Kim, 2008. "A heuristic for vehicle fleet mix problem using tabu search and set partitioning," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(6), pages 833-841, June.
    8. Qin, Hu & Moriakin, Anton & Xu, Gangyan & Li, Jiliu, 2024. "The generator distribution problem for base stations during emergency power outage: A branch-and-price-and-cut approach," European Journal of Operational Research, Elsevier, vol. 318(3), pages 752-767.
    9. Heßler, Katrin, 2021. "Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes," European Journal of Operational Research, Elsevier, vol. 294(1), pages 188-205.
    10. Albert H. Schrotenboer & Evrim Ursavas & Iris F. A. Vis, 2019. "A Branch-and-Price-and-Cut Algorithm for Resource-Constrained Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 53(4), pages 1001-1022, July.
    11. Capelle, Thomas & Cortés, Cristián E. & Gendreau, Michel & Rey, Pablo A. & Rousseau, Louis-Martin, 2019. "A column generation approach for location-routing problems with pickup and delivery," European Journal of Operational Research, Elsevier, vol. 272(1), pages 121-131.
    12. Ricardo Gatica & Pablo Miranda, 2011. "Special Issue on Latin-American Research: A Time Based Discretization Approach for Ship Routing and Scheduling with Variable Speed," Networks and Spatial Economics, Springer, vol. 11(3), pages 465-485, September.
    13. Tino Henke & M. Grazia Speranza & Gerhard Wäscher, 2014. "The Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes," FEMM Working Papers 140006, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    14. Shaza Hanif & Shahab Ud Din & Ning Gui & Tom Holvoet, 2023. "Multiagent Coordination and Teamwork: A Case Study for Large-Scale Dynamic Ready-Mixed Concrete Delivery Problem," Mathematics, MDPI, vol. 11(19), pages 1-25, September.
    15. Hatzenbühler, Jonas & Jenelius, Erik & Gidófalvi, Gyözö & Cats, Oded, 2023. "Modular vehicle routing for combined passenger and freight transport," Transportation Research Part A: Policy and Practice, Elsevier, vol. 173(C).
    16. Agatz, Niels & Erera, Alan & Savelsbergh, Martin & Wang, Xing, 2012. "Optimization for dynamic ride-sharing: A review," European Journal of Operational Research, Elsevier, vol. 223(2), pages 295-303.
    17. le Blanc, H.M. & Cruijssen, F. & Fleuren, H.A. & de Koster, M.B.M., 2006. "Factory gate pricing: An analysis of the Dutch retail distribution," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1950-1967, November.
    18. Jesus Gonzalez-Feliu, 2013. "Vehicle Routing in Multi-Echelon Distribution Systems with Cross-Docking: A Systematic Lexical-Metanarrative Analysis," Post-Print halshs-00834573, HAL.
    19. Bhoopalam, Anirudh Kishore & Agatz, Niels & Zuidwijk, Rob, 2018. "Planning of truck platoons: A literature review and directions for future research," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 212-228.
    20. Diana, Marco & Dessouky, Maged M., 2004. "A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(6), pages 539-557, July.

    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:36:y:2002:i:1:p:55-62. 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.