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

Yanru Chen, Mujin Gao, Zongcheng Zhang, Junheng Li, M.I.M. Wahab and Yangsheng Jiang

Transportation Research Part E: Logistics and Transportation Review, 2025, vol. 193, issue C

Abstract: 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. We 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, we 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.

Keywords: Two-dimensional vector packing problem; Conflict graph; Time window; Branch-and-price-and-cut; Contextual bandits (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554524004575
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:193:y:2025:i:c:s1366554524004575

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2024.103866

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().