Decomposition Strategies for Vehicle Routing Heuristics
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
Decomposition techniques are an important component of modern heuristics for large instances of vehicle routing problems. The current literature lacks a characterization of decomposition strategies and a systematic investigation of their impact when integrated into state-of-the-art heuristics. This paper fills this gap: We discuss the main characteristics of decomposition techniques in vehicle routing heuristics, highlight their strengths and weaknesses, and derive a set of desirable properties. Through an extensive numerical campaign, we investigate the impact of decompositions within two algorithms for the capacitated vehicle routing problem: the Adaptive Large Neighborhood Search of Pisinger and Ropke (2007 ) and the Hybrid Genetic Search of Vidal et al. (2012 ). We evaluate the quality of popular decomposition techniques from the literature and propose new strategies. We find that route-based decomposition methods, which define subproblems by means of the customers contained in selected subsets of the routes of a given solution, generally appear superior to path-based methods, which merge groups of customers to obtain smaller subproblems. The newly proposed decomposition barycenter clustering achieves the overall best performance and leads to significant gains compared with using the algorithms without decomposition. History: Erwin Pesch, Area Editor for Heuristic Search and Approximation Algorithms. Funding: This work was supported by the U.S. Air Force [Grant FA9550-17-1-0234], the Ministerio de Ciencia e Innovación (Juan de la Cierva Formación), H2020 Marie Skłodowska-Curie Actions [Grant 945380], the Ministero dell’Università e della Ricerca [Grant 2015JJLC3E_002], the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grant 308528/2018-2], and the Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro [Grant E-26/202.790/2019]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.1288 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0048 ) at ( http://dx.doi.org/10.5281/zenodo.7613129 ).
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.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| 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