Managing Large Fixed Costs in Vehicle Routing and Crew Scheduling Problems Solved by Column Generation
Bibliographic record
Abstract
Abstract We consider vehicle routing and crew scheduling problems that involve a lexicographic bi-level objective function (for instance, minimizing first the number of vehicles and second the operational costs) and can be solved by column generation where the subproblem is a resource constrained shortest path problem. Such problems are often modeled using a single-level objective function with a large fixed cost (weight) for ensuring the minimization of the primary objective. In this paper, we study the impact on the solution time of the fixed cost value. First, we present computational results which show that the solution time increases as the fixed cost value gets larger. Then, we develop an exact dynamic fixed cost procedure compatible with column generation that starts with a relatively small fixed cost value and increases it iteratively until optimality is reached. To prove optimality, a shortest path problem with resource constraints needs to be solved. Through a series of computational experiments on two types of problems, we show that this procedure can reduce solution times by up to 50% when compared to an approach relying on one very large fixed cost value. Column generation is a widely used solution method for addressing several types of vehicle routing and crew scheduling problems. In these problems, the objective has often two levels. For instance, at the first level, the number of resources required (e.g., vehicles) is minimized while the second level aims at minimizing the operational costs. Typically, for modeling a two-level objective, one uses a single objective function that is defined as the first objective value multiplied by a very large fixed cost plus the second objective value. Doing so, two difficulties can arise. Firstly, the hierarchy between the objectives might not be respected when the fixed cost is not large enough. Secondly, when this cost is too large, solution times required by a column generation method increase. In this paper, we address these two possible drawbacks by developing a simple procedure that is compatible with column generation. The proposed procedure guarantees optimality with regards to the hierarchy between the objectives and substantially reduces solution times when compared to a model using a very large fixed cost.
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.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.003 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.001 | 0.001 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.001 | 0.001 |
| Open science | 0.001 | 0.001 |
| Research integrity | 0.001 | 0.001 |
| Insufficient payload (model declined to judge) | 0.003 | 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 itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".