Document Open Access Logo

Constraint Programming to Improve Hub Utilization in Autonomous Transfer Hub Networks (Short Paper)

Authors Chungjae Lee , Wirattawut Boonbandansook , Vahid Eghbal Akhlaghi , Kevin Dalmeijer , Pascal Van Hentenryck

PDF
Thumbnail PDF

File

LIPIcs.CP.2023.46.pdf
  • Filesize: 1.11 MB
  • 11 pages

Document Identifiers

Author Details

Chungjae Lee
  • H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA
Wirattawut Boonbandansook
  • H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA
Vahid Eghbal Akhlaghi
  • H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA
Kevin Dalmeijer
  • H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA
Pascal Van Hentenryck
  • H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA

Funding

This research was partly funded through a gift from Ryder and partly supported by the NSF AI Institute for Advances in Optimization (Award 2112533).

Acknowledgements

Special thanks to the Ryder team for their invaluable support, expertise, and insights.

Cite As Get BibTex

Chungjae Lee, Wirattawut Boonbandansook, Vahid Eghbal Akhlaghi, Kevin Dalmeijer, and Pascal Van Hentenryck. Constraint Programming to Improve Hub Utilization in Autonomous Transfer Hub Networks (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 46:1-46:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CP.2023.46

Abstract

The Autonomous Transfer Hub Network (ATHN) is one of the most promising ways to adapt self-driving trucks for the freight industry. These networks use autonomous trucks for the middle mile, while human drivers perform the first and last miles. This paper extends previous work on optimizing ATHN operations by including transfer hub capacities, which are crucial for labor planning and policy design. It presents a Constraint Programming (CP) model that shifts an initial schedule produced by a Mixed Integer Program to minimize the hub capacities. The scalability of the CP model is demonstrated on a case study at the scale of the United States, based on data provided by Ryder System, Inc. The CP model efficiently finds optimal solutions and lowers the necessary total hub capacity by 42%, saving $15.2M in annual labor costs. The results also show that the reduced capacity is close to a theoretical (optimistic) lower bound.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
Keywords
  • Constraint Programming
  • Autonomous Trucking
  • Tranfer Hub Network

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Abderrahmane Aggoun and Nicolas Beldiceanu. Extending chip in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling, 17(7):57-73, 1993. URL: https://doi.org/10.1016/0895-7177(93)90068-A.
  2. Natashia Boland, Mike Hewitt, Luke Marshall, and Martin Savelsbergh. The Continuous-Time Service Network Design Problem. Operations Research, 65(5):1303-1321, 2017. URL: https://doi.org/10.1287/opre.2017.1624.
  3. Natashia Boland and Martin Savelsbergh. Perspectives on integer programming for time-dependent models. TOP, 27:147-173, 2019. URL: https://doi.org/10.1007/s11750-019-00514-4.
  4. Kevin Dalmeijer and Pascal Van Hentenryck. Optimizing Freight Operations for Autonomous Transfer Hub Networks. arXiv:2110.12327, 2021. URL: https://arxiv.org/abs/2110.12327.
  5. FleetOwner. TuSimple among autonomous truck companies to join Self-Driving Coalition. https://www.fleetowner.com/, 2021. URL: https://www.fleetowner.com/technology/autonomous-vehicles/article/21152006/tusimple-among-autonomous-truck-companies-to-join-selfdriving-coalition.
  6. Forbes. Plus Partners With IVECO To Develop Automated Trucks For Global Deployment. https://www.forbes.com/, 2021. URL: https://www.forbes.com/sites/richardbishop1/2021/04/12/plus-partners-with-iveco-to-develop-automated-trucks-for-global-deployment.
  7. FreightWaves. Gatik, Isuzu to partner on autonomous truck platform. https://www.freightwaves.com/, 2021. URL: https://www.freightwaves.com/news/gatik-isuzu-to-partner-on-autonomous-truck-platform.
  8. Glassdoor. How much does a Truck Mechanic make? https://www.glassdoor.com/Salaries/truck-mechanic-salary-SRCH_KO0,14.htm, 2023. Accessed: 2023-04-28.
  9. Sönke Hartmann and Dirk Briskorn. An updated survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 297(1):1-14, 2022. URL: https://doi.org/10.1016/j.ejor.2021.05.004.
  10. Edward He, Natashia Boland, George Nemhauser, and Martin Savelsbergh. An exact algorithm for the service network design problem with hub capacity constraints. Networks, 80(4):572-596, 2022. URL: https://doi.org/10.1002/net.22128.
  11. Heavy Duty Trucking. Daimler’s Redundant Chassis for Autonomous-Truck Operation. https://www.truckinginfo.com/, 2021. URL: https://www.truckinginfo.com/10157338/daimlers-redundant-chassis-for-autonomous-truck-operation.
  12. Willy Herroelen, Bert De Reyck, and Erik Demeulemeester. Resource-constrained project scheduling: A survey of recent developments. Computers & Operations Research, 25(4):279-302, 1998. URL: https://doi.org/10.1016/S0305-0548(97)00055-5.
  13. Chungjae Lee, Kevin Dalmeijer, and Pascal Van Hentenryck. Optimization Models for Autonomous Transfer Hub Networks. arXiv:2201.06137, 2022. URL: https://arxiv.org/abs/2201.06137.
  14. Chungjae Lee, Kevin Dalmeijer, Pascal Van Hentenryck, and Peibo Zhang. Optimizing Autonomous Transfer Hub Networks: Quantifying the Potential Impact of Self-Driving Trucks. arXiv:2305.03119, 2023. URL: https://arxiv.org/abs/2305.03119.
  15. Luke Marshall, Natashia Boland, Martin Savelsbergh, and Mike Hewitt. Interval-Based Dynamic Discretization Discovery for Solving the Continuous-Time Service Network Design Problem. Transportation Science, 55(1):29-51, 2021. URL: https://doi.org/10.1287/trsc.2020.0994.
  16. Clair E. Miller, Albert W. Tucker, and Richard A. Zemlin. Integer Programming Formulation of Traveling Salesman Problems. Journal of the ACM, 7(4):326-329, 1960. URL: https://doi.org/10.1145/321043.321046.
  17. OpenStreetMap. Planet dump retrieved from https://planet.osm.org, 2021. URL: https://www.openstreetmap.org.
  18. PACE. Partnership for an Advanced Computing Environment (PACE), 2017. URL: http://www.pace.gatech.edu.
  19. Laurent Perron and Vincent Furnon. Google OR-Tools v9.6. https://developers.google.com/optimization/, 2023.
  20. A. Alan B. Pritsker, Lawrence J. Waiters, and Wolfe Philip M. Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach. Management Science, 16(1):93-108, 1969. URL: https://doi.org/10.1287/mnsc.16.1.93.
  21. Roland Berger. Shifting up a gear - Automation, electrification and digitalization in the trucking industry. https://www.rolandberger.com/, 2018. URL: https://www.rolandberger.com/publications/publication_pdf/roland_berger_trucking_industry.pdf.
  22. Ryder System, Inc. and Socially Aware Mobility Lab. The Impact of Autonomous Trucking: A Case-Study of Ryder’s Dedicated Transportation Network. Ryder Newsroom, 2021. URL: https://newsroom.ryder.com/news/news-details/2021/Ryder-Teams-Up-with-Georgia-Tech-for-Industrys-First-Data-Driven-Study-on-Impact-of-Autonomous-Trucking/.
  23. Yannick Oskar Scherr, Mike Hewitt, Bruno Albert Neumann-Saavedra, and Dirk Christian Mattfeld. Dynamic discretization discovery for the service network design problem with mixed autonomous fleets. Transportation Research Part B: Methodological, 141:164-195, 2020. URL: https://doi.org/10.1016/j.trb.2020.09.009.
  24. Andreas Schutt, Thibaut Feydy, Peter J. Stuckey, and Mark G. Wallace. Explaining the cumulative propagator. Constraints, 16:250-282, 2011. URL: https://doi.org/10.1007/s10601-010-9103-2.
  25. Mohsen Shahandasht, Binaya Pudasaini, and Sean Logan McCauley. Autonomous Vehicles and Freight Transportation Analysis. Technical report, The University of Texas at Arlington, 2019. URL: https://doi.org/10.13140/RG.2.2.28484.78726.
  26. TechCrunch. Aurora and Volvo partner to bring autonomous long-haul trucks to North America. https://www.techcrunch.com/, 2021. URL: https://techcrunch.com/2021/03/30/aurora-and-volvo-partner-to-bring-autonomous-long-haul-trucks-to-north-america/.
  27. Transport Topics. Navistar, TuSimple Partner to Launch Self-Driving Trucks in 2024. https://www.ttnews.com/, 2020. URL: https://www.ttnews.com/articles/navistar-tusimple-partner-launch-self-driving-trucks-2024.
  28. Steve Viscelli. Driverless? Autonomous Trucks and the Future of the American Trucker. Center for Labor Research and Education, University of California, Berkeley, and Working Partnerships USA, 2018. URL: http://driverlessreport.org/.
  29. Duc Minh Vu, Mike Hewitt, Natashia Boland, and Martin Savelsbergh. Dynamic Discretization Discovery for Solving the Time-Dependent Traveling Salesman Problem with Time Windows. Transportation Science, 54(3):703-720, 2020. URL: https://doi.org/10.1287/trsc.2019.0911.
  30. Haotian Wu, Ian Herszterg, Martin Savelsbergh, and Yixiao Huang. Service Network Design for Same-Day Delivery with Hub Capacity Constraints. Transportation Science, 57(1):273-287, 2023. URL: https://doi.org/10.1287/trsc.2022.1155.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact