WB12 - Routing, Orchestration and Learning

Routing problems such as the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP) are computationally challenging due to the exponential growth of their solution spaces. Although exact algorithms and metaheuristics have achieved substantial progress, their computational effort still increases rapidly with instance size.

In this work, we propose a supervised learning framework that predicts the relevance of edges for high-quality routing solutions. The model assigns a confidence score to each edge indicating its likelihood of appearing in near-optimal solutions. These predictions are used to reduce the search space by pruning edges with low predicted relevance. The resulting reduced graphs are integrated as a preprocessing step into both mathematical optimization solvers and a state-of-the-art metaheuristic.

In a comprehensive computational study on TSP and CVRP instances with up to 1,000 nodes, the proposed approach removes a large share of candidate edges while preserving solution quality. For exact solvers, the preprocessing leads to substantial runtime reductions while maintaining optimal solutions under conservative pruning settings. For harder instances that cannot be solved to optimality within the time limit, the approach consistently improves incumbent solutions and reduces optimality gaps. When embedded in a hybrid genetic search metaheuristic, the method accelerates the discovery of solutions of equal or better quality, with performance gains increasing for larger instances.

We study the tactical planning problem of an Intelligent Decision Support Platform (IDSP) intermediating between shippers and carriers in a Many-to-One-to-Many (M1M) freight transportation system under simultaneous demand and supply uncertainty. We develop the Scheduled Service Network Design under Uncertainty in Demand and Supply (SSND-UDS), a two-stage stochastic mixed-integer program in which service selection, shipment acceptance, and tactical itinerary construction are committed before uncertainty is resolved, while second-stage recourse adapts execution to realized shipment volumes and service capacities. We show that the recourse problem admits an equivalent multidimensional knapsack reformulation enabling efficient decomposition, and adapt the decision-based scenario clustering framework of Hewitt et al. (2022) to provide tractable bounds for larger instances, achieving gaps within 2–3% of optimality. Computational experiments establish that the Value of the Stochastic Solution averages 8.29%, rising to 14.53% under high uncertainty, and that stochastic planning reduces expected recourse costs by 83–87% relative to deterministic planning.

This paper addresses the Collaborative Routing Orchestration for Organic Food Distribution Problem (CRO-FDP), a two-echelon distribution challenge inspired by a regional organic food network in Québec, Canada. The CRO-FDP integrates hub selection, vehicle routing, and synchronization decisions under strict time and perishability constraints to coordinate multiple independent producers and food banks sharing logistics resources.
To solve realistic, large-scale instances beyond the reach of standard commercial solvers, we propose an advanced decomposition framework. The problem is partitioned into two sub-problems: a Vehicle Task Sequencing Problem (VTSP), which determines routing and commodity paths, and a Vehicle Time Assignment Problem (VTAP), which ensures feasible temporal scheduling. We implement an intelligent grouping strategy that clusters physical nodes and aggregates transportation requests to enhance scalability.
Computational experiments demonstrate that the proposed decomposition approach significantly improves performance as problem complexity scales. While previous solution method remains effective for small instances, our method achieves a lower median optimality gap of 31.25% for large-scale scenarios and reduces computational time by nearly half. Managerial results reveal that collaborative orchestration can reduce fleet requirements by 60% and total travel distance by up to 28%, highlighting the strategic value of shared hub-based coordination for sustainable regional food systems

In many local and organic food networks, products generally have a shorter shelf life and are highly perishable, demanding efficient and timely delivery to maximize food quality and reduce waste. In addition, the producers are typically small, dispersed, and resource-constrained. In this context, distribution is handled collaboratively by multiple producers and organizations that share logistics resources. While this can improve efficiency, it also introduces coordination challenges, particularly when products are perishable and key factors like supply, demand, or travel times are uncertain.

This talk presents a modeling framework for collaborative routing problems in perishable food distribution networks. The focus is on how to jointly represent decisions such as hub activation, vehicle routing, and inter-vehicle transfers, while incorporating perishability constraints and stochastic elements. Rather than treating collaboration, uncertainty, and perishability as separate concerns, we discuss modeling approaches that integrate them and capture their combined effect on routing decisions and product quality.