MA7 - Machine Learning and Optimization 1

We develop NeuroPlanner, a learning–optimization framework that leverages route images to capture and enforce implicit constraints in vehicle routing problems (VRPs). In many practical settings, solutions produced by standard VRP solvers violate operational rules that are hard to encode explicitly (e.g., informal feasibility requirements or planner-specific restrictions). NeuroPlanner addresses this gap by converting each candidate solution into an image representation and generating a heatmap that highlights arcs and regions most responsible for these latent constraint violations. Building on this signal, we propose an algorithm, an iterative refinement scheme that integrates the heatmap into the optimization loop. At each iteration, the algorithm translates heatmap intensity into targeted arc-cost penalties, re-solves the VRP, and repeats the process until violations are mitigated. Computational experiments on synthetic and semi-realistic instances show that heatmap-guided Plus substantially increases the number of feasible/acceptable solutions within a small number of iterations, while maintaining solution quality. Overall, NeuroPlanner demonstrates a practical pathway to combine visual learning with classical optimization to learn, reveal, and enforce implicit VRP constraints.

Nous proposons une injection séquentielle de contraintes en apprentissage par renforcement multi-agents pour le routage ferroviaire. Inspirée de l’optimisation lagrangienne, elle améliore la stabilité, réduit le temps d’apprentissage et renforce le respect des contraintes, avec des performances équivalentes ou meilleures.

Imitation learning (IL) provides a data-driven framework for approximating policies for large-scale combinatorial optimisation problems formulated as sequential decision problems, where exact solution methods are computationally intractable. A central but underexplored aspect of IL is the role of the \emph{expert} that generates training demonstrations. Existing studies employ a wide range of expert constructions, yet lack a unifying framework to characterise their modelling assumptions, computational properties, and impact on learning performance.
This paper introduces a systematic taxonomy of experts for IL in combinatorial optimisation under uncertainty, classified along three principal dimensions: (i) treatment of uncertainty, spanning myopic, deterministic, full-information, and stochastic formulations; (ii) level of optimality, distinguishing task-optimal from approximate experts; and (iii) interaction mode, ranging from one-shot supervision to iterative schemes. Building on this taxonomy, we propose a unified DAgger framework accommodating multiple expert queries, expert aggregation, and flexible interaction strategies.

Effective management of Empty Unit Load Devices (ULDs) repositioning is crucial for optimizing efficiency and reducing costs in aviation. Repositioning empty ULDs is expensive and constrained by limited flight capacity, while high demand variance makes distribution challenging. In this study, we tackle imbalanced ULD distribution across airports by developing a data-driven approach to optimize their movement. Our approach has two stages. First, we forecast ULD demand per flight using features such as aircraft type and route characteristics. We applied regression-based models including XGBoost, and incorporated time series techniques using Prophet and foundation models such as Chronos to capture temporal dependencies at each airport. Second, we built a rolling-horizon optimization model with a recourse mechanism to determine the optimal movement of empty ULDs across the network, adaptively adjusting repositioning decisions as actual demand deviates from forecasts while ensuring cost-effective operations under operational constraints.