Reem Khir

Ritesh Ojha, Wenbo Chen, Hanyu Zhang et al.

The load planning problem is a critical challenge in service network design for parcel carriers: it decides how many trailers to assign for dispatch over time between pairs of terminals. Another key challenge is to determine a flow plan, which specifies how parcel volumes are assigned to planned loads. This paper considers the Outbound Load Planning Problem (OLPP) that considers flow and load planning challenges jointly in order to adjust loads and flows as the demand forecast changes over time before the day of operations in a terminal. The paper aims at developing a decision-support tool to inform planners making these decisions at terminals across the network. The paper formulates the OLPP as a mixed-integer programming model and shows that it admits a large number of symmetries in a network where each commodity can be routed through primary and alternate terminals. As a result, an optimization solver may return fundamentally different solutions to closely related problems, confusing planners and reducing trust in optimization. To remedy this limitation, this paper proposes a lexicographical optimization approach that eliminates those symmetries by generating optimal solutions staying close to a reference plan. Moreover, this paper designs an optimization proxy that addresses the computational challenges of the optimization model. The optimization proxy combines a machine-learning model and a repair procedure to find near-optimal solutions that satisfy real-time constraints imposed by planners in the loop. An extensive computational study on industrial instances shows that the optimization proxy is orders of magnitude faster for generating solutions that are consistent with each other. The proposed approach also demonstrates the benefits of the OLPP for load consolidation and the significant savings obtained from combining machine learning and optimization.

Wenbo Chen, Reem Khir, Pascal Van Hentenryck

The Flexible Job-shop Scheduling Problem (FJSP) is an important combinatorial optimization problem that arises in manufacturing and service settings. FJSP is composed of two subproblems, an assignment problem that assigns tasks to machines, and a scheduling problem that determines the starting times of tasks on their chosen machines. Solving FJSP instances of realistic size and composition is an ongoing challenge even under simplified, deterministic assumptions. Motivated by the inevitable randomness and uncertainties in supply chains, manufacturing, and service operations, this paper investigates the potential of using a deep learning framework to generate fast and accurate approximations for FJSP. In particular, this paper proposes a two-stage learning framework 2SLFJSP that explicitly models the hierarchical nature of FJSP decisions, uses a confidence-aware branching scheme to generate appropriate instances for the scheduling stage from the assignment predictions and leverages a novel symmetry-breaking formulation to improve learnability. 2SL-FJSP is evaluated on instances from the FJSP benchmark library. Results show that 2SL-FJSP can generate high-quality solutions in milliseconds, outperforming a state-of-the-art reinforcement learning approach recently proposed in the literature, and other heuristics commonly used in practice.

Zhuoli Yin, Yi Ding, Reem Khir et al.

Solving Traveling Salesman Problem (TSP) is NP-hard yet fundamental for wide real-world applications. Classical exact methods face challenges in scaling, and heuristic methods often require domain-specific parameter calibration. While learning-based approaches have shown promise, they suffer from poor generalization and limited scalability due to fixed training data. This work proposes ViTSP, a novel framework that leverages pre-trained vision language models (VLMs) to visually guide the solution process for large-scale TSPs. The VLMs function to identify promising small-scale subproblems from a visualized TSP instance, which are then efficiently optimized using an off-the-shelf solver to improve the global solution. ViTSP bypasses the dedicated model training at the user end while maintaining effectiveness across diverse instances. Experiments on real-world TSP instances ranging from 1k to 88k nodes demonstrate that ViTSP consistently achieves solutions with average optimality gaps below 0.2%, outperforming existing learning-based methods. Under the same runtime budget, it surpasses the best-performing heuristic solver, LKH-3, by reducing its gaps by 12% to 100%, particularly on very-large-scale instances with more than 10k nodes. Our framework offers a new perspective in hybridizing pre-trained generative models and operations research solvers in solving combinatorial optimization problems, with practical implications for integration into more complex logistics systems. The code is available at https://anonymous.4open.science/r/ViTSP_codes-6683.