A machine-learning-based column generation heuristic for electric bus scheduling
Bibliographic record
Abstract
Bus scheduling in public transit consists in determining a set of bus schedules to cover a set of timetabled trips at minimum cost. This planning process has evolved recently with the advent of electric buses that introduce constraints related to vehicle autonomy and battery charging process. In particular, column-generation algorithms have regained popularity for solving problems similar to the one considered in this paper, namely, the multi-depot electric vehicle scheduling problem (MDEVSP) with a piecewise linear charging function and capacitated charging stations. To tackle large-scale MDEVSP instances, we design a column generation (CG) heuristic that relies on reduced-sized networks to generate the bus schedules. The reduction is achieved by selecting a priori a subset of the arcs. Multiple selection techniques are studied: some are based on a greedy heuristic and others exploit a supervised learning algorithm relying on a graph neural network. It turns out that combining both selection types yields the best computational results. On 405 artificial instances involving between 568 and 1474 trips and generated from real bus lines in Montreal, the network reduction technique produced an average computational time reduction of 71.6% (compared to the same CG heuristic but without network reduction), while deteriorating solution cost by an average of 2.2%. On 8 larger instances containing more than 2500 trips on average, the proposed solution method also provided an average time saving of 52.5% with an average gap of 4.2% thanks to a transfer learning approach. • Electric bus scheduling with nonlinear recharging function and capacitated stations. • We develop several heuristic arc selection procedures. • The best combines a greedy heuristic and a graph neural network. • It speeds up a column generation heuristic by an average factor of 3.5. • Solution quality deteriorates by 2.2% on average.
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.000 | 0.001 |
| Meta-epidemiology (narrow) | 0.001 | 0.000 |
| Meta-epidemiology (broad) | 0.001 | 0.001 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.001 |
| Open science | 0.001 | 0.000 |
| 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".