Contextual bandits learning-based branch-and-price-and-cut algorithm for the two-dimensional vector packing problem with conflicts and time windows

A two-dimensional vector packing problem with conflicts and time windows (2DVPPCTW) is investigated in this study. It consists of packing items into the minimum number of bins, and items are characterized by different weights, volumes, and time windows. Items also have conflicts and cannot be packed in the same bin. The authors formulate the 2DVPPCTW as an integer programming model and reformulate it to the master problem and the subproblem based on the Danzig–Wolfe decomposition. An exact algorithm, contextual bandits learning-based branch-and-price-and-cut algorithm (CBL-BPC), is proposed for the 2DVPPCTW with reinforcement learning technique. In particular, they provide a CBL framework for the subproblem, which usually poses considerable computational challenges. Five heuristic algorithms, namely, adaptive large neighborhood search (ALNS), ant colony optimization heuristic (ACO), heuristic dynamic programming (DP), a combination of ALNS and heuristic DP, and a combination of ACO and heuristic DP, are developed as bandit arms in the CBL framework. The CBL framework adaptively chooses one of five heuristics algorithms to solve the subproblem by learning from previous experiences. An exact dynamic programming algorithm is invoked to guarantee optimality once the CBL fails to find a better solution to the subproblem. Rounded capacity inequalities and accelerating strategies are introduced to accelerate the solution. An extensive computational study shows that the CBL-BPC can solve all 800 instances optimally within a reasonable time frame and is highly competitive with state-of-the-art exact and heuristics methods.

• Record URL:
  • https://doi.org/10.1016/j.tre.2024.103866
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S1366554524004575
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/13665545
• Supplemental Notes:
  • © 2024 Elsevier Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies. Abstract reprinted with permission of Elsevier.
• Authors:
  • Chen, Yanru
  • Gao, Mujin
  • Zhang, Zongcheng
  • Li, Junheng
  • Wahab, M I M
  • Jiang, Yangsheng
• Publication Date: 2025-1

Language

• English

Media Info

• Media Type: Web
• Features: Appendices; Figures; References; Tables;
• Pagination: 103866
• Serial:
  • Transportation Research Part E: Logistics and Transportation Review
  • Volume: 193
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 1366-5545
  • Serial URL: http://www.sciencedirect.com/science/journal/13665545

Subject/Index Terms

• TRT Terms: Algorithms; Containerization; Costs; Machine learning; Stuffing; Terminal operations; Time windows
• Subject Areas: Data and Information Technology; Finance; Freight Transportation; Terminals and Facilities;

Filing Info

• Accession Number: 01941365
• Record Type: Publication
• Files: TRIS
• Created Date: Dec 30 2024 11:16AM