Document Open Access Logo

Greedy Algorithms for the Freight Consolidation Problem

Authors Zuguang Gao , John R. Birge , Richard Li-Yang Chen , Maurice Cheung

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2022.4.pdf
  • Filesize: 0.6 MB
  • 19 pages

Document Identifiers

Author Details

Zuguang Gao
  • The University of Chicago Booth School of Business, Chicago, IL, USA
John R. Birge
  • The University of Chicago Booth School of Business, Chicago, IL, USA
Richard Li-Yang Chen
  • Flexport, Inc., San Francisco, CA, USA
Maurice Cheung
  • Flexport, Inc., San Francisco, CA, USA

Cite AsGet BibTex

Zuguang Gao, John R. Birge, Richard Li-Yang Chen, and Maurice Cheung. Greedy Algorithms for the Freight Consolidation Problem. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/OASIcs.ATMOS.2022.4

Abstract

We define and study the (ocean) freight consolidation problem (FCP), which plays a crucial role in solving today’s supply chain crisis. Roughly speaking, every day and every hour, a freight forwarder sees a set of shipments and a set of containers at the origin port. There is a shipment cost associated with assigning each shipment to each container. If a container is assigned any shipment, there is also a procurement cost for that container. The FCP aims to minimize the total cost of fulfilling all the shipments, subject to capacity constraints of the containers. In this paper, we show that no constant factor approximation exists for FCP, and propose a series of greedy based heuristics for solving the problem. We also test our heuristics with simulated data and show that our heuristics achieve small optimality gaps.

Subject Classification

ACM Subject Classification
  • Theory of computation → Theory and algorithms for application domains
Keywords
  • Freight consolidation
  • heuristics
  • greedy algorithm

Metrics

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

References

  1. Mohamed Abdel-Basset, Gunasekaran Manogaran, Laila Abdel-Fatah, and Seyedali Mirjalili. An improved nature inspired meta-heuristic algorithm for 1-d bin packing problems. Personal and Ubiquitous Computing, 22(5):1117-1132, 2018. Google Scholar
  2. Diaa Salama Abdul-Minaam, Wadha Mohammed Edkheel Saqar Al-Mutairi, Mohamed A Awad, and Walaa H El-Ashmawi. An adaptive fitness-dependent optimizer for the one-dimensional bin packing problem. IEEE Access, 8:97959-97974, 2020. Google Scholar
  3. Jaza Mahmood Abdullah and Tarik Ahmed. Fitness dependent optimizer: inspired by the bee swarming reproductive process. IEEE Access, 7:43473-43486, 2019. Google Scholar
  4. Shoshana Anily, Julien Bramel, and David Simchi-Levi. Worst-case analysis of heuristics for the bin packing problem with general cost structures. Operations Research, 42(2):287-298, 1994. Google Scholar
  5. Merve Aydemir and Tuncay Yigit. A review of the solutions for the container loading problem, and the use of heuristics. In The International Conference on Artificial Intelligence and Applied Mathematics in Engineering, pages 690-700. Springer, 2019. Google Scholar
  6. Mauro Maria Baldi and Maurizio Bruglieri. On the generalized bin packing problem. International Transactions in Operational Research, 24(3):425-438, 2017. Google Scholar
  7. Mauro Maria Baldi, Teodor Gabriel Crainic, Guido Perboli, and Roberto Tadei. The generalized bin packing problem. Transportation Research Part E: Logistics and Transportation Review, 48(6):1205-1220, 2012. Google Scholar
  8. Mauro Maria Baldi, Teodor Gabriel Crainic, Guido Perboli, and Roberto Tadei. Asymptotic results for the generalized bin packing problem. Procedia-Social and Behavioral Sciences, 111:663-671, 2014. Google Scholar
  9. Mauro Maria Baldi, Daniele Manerba, Guido Perboli, and Roberto Tadei. A generalized bin packing problem for parcel delivery in last-mile logistics. European Journal of Operational Research, 274(3):990-999, 2019. Google Scholar
  10. Avnish K. Bhatia, M Hazra, and SK Basu. Better-fit heuristic for one-dimensional bin-packing problem. In 2009 IEEE International Advance Computing Conference, pages 193-196. IEEE, 2009. Google Scholar
  11. Edward G Coffman, Gabor Galambos, Silvano Martello, and Daniele Vigo. Bin packing approximation algorithms: Combinatorial analysis. In Handbook of Combinatorial Optimization, pages 151-207. Springer, 1999. Google Scholar
  12. Edward G. Coffman Jr, Michael R. Garey, and David S. Johnson. Approximation algorithms for bin packing: A survey. In Dorit S. Hochbaum, editor, Approximation Algorithms for NP-hard Problems, pages 46-93. PWS Publishing Co., Boston, MA, USA, 1996. Google Scholar
  13. Leah Epstein and Asaf Levin. Bin packing with general cost structures. Mathematical Programming, 132(1):355-391, 2012. Google Scholar
  14. Juris Hartmanis. Computers and intractability: A guide to the theory of np-completeness (michael r. garey and david s. johnson). SIAM Review, 24(1):90-91, 1982. Google Scholar
  15. Mohit Jain, Vijander Singh, and Asha Rani. A novel nature-inspired algorithm for optimization: Squirrel search algorithm. Swarm and Evolutionary Computation, 44:148-175, 2019. Google Scholar
  16. David S. Johnson, Alan Demers, Jeffrey D. Ullman, Michael R Garey, and Ronald L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4):299-325, 1974. Google Scholar
  17. Seyedali Mirjalili and Andrew Lewis. The whale optimization algorithm. Advances in Engineering Software, 95:51-67, 2016. Google Scholar
  18. Chanaleä Munien and Absalom E Ezugwu. Metaheuristic algorithms for one-dimensional bin-packing problems: A survey of recent advances and applications. Journal of Intelligent Systems, 30(1):636-663, 2021. Google Scholar
  19. Ibrahim H Osman. Heuristics for the generalised assignment problem: simulated annealing and tabu search approaches. Operations-Research-Spektrum, 17(4):211-225, 1995. Google Scholar
  20. Wansoo T Rhee and Michel Talagrand. Online bin packing with items of random size. Mathematics of Operations Research, 18(2):438-445, 1993. Google Scholar
  21. Xin-She Yang and Suash Deb. Cuckoo search via Lévy flights. In 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), pages 210-214. IEEE, 2009. Google Scholar
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 Imprint Privacy Contact