Learning-Based Branch-and-Price Algorithms for the Vehicle Routing Problem with Time Windows and Two-Dimensional Loading Constraints
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
A capacitated vehicle routing problem with two-dimensional loading constraints is addressed. Associated with each customer are a set of rectangular items, the total weight of the items, and a time window. Designing exact algorithms for the problem is very challenging because the problem is a combination of two NP-hard problems. An exact branch-and-price algorithm and an approximate counterpart are proposed to solve the problem. We introduce an exact dominance rule and an approximate dominance rule. To cope with the difficulty brought by the loading constraints, a new column generation mechanism boosted by a supervised learning model is proposed. Extensive experiments demonstrate the superiority of integrating the learning model in terms of CPU time and calls of the feasibility checker. Moreover, the branch-and-price algorithms are able to significantly improve the solutions of the existing instances from literature and solve instances with up to 50 customers and 103 items. Summary of Contribution: We wish to submit an original research article entitled “Learning-based branch-and-price algorithms for a vehicle routing problem with time windows and two-dimensional loading constraints” for consideration by IJOC. We confirm that this work is original and has not been published elsewhere, nor is it currently under for publication elsewhere. In this paper, we report a study in which we develop two branch-and-price algorithms with a machine learning model injected to solve a vehicle routing problem integrated the two-dimensional packing. Due to the complexity brought by the integration, studies on exact algorithms in this field are very limited. Our study is important to the field, because we develop an effective method to significantly mitigate computational burden brought by the packing problem so that exactness turns to be achievable within reasonable time budget. The approach can be generalized to the three-dimensional case by simply replacing the packing algorithm. It can also be adapted for other VRPs when high-dimensional loading constraints are concerned. Broadly speaking, the study is a typical example of adopting supervised learning to achieve acceleration for operations research algorithms, which expands the envelop of computing and operations research. Hence, we believe this manuscript is appropriate for publication by IJOC.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.001 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.001 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it