💻 computer science

A Joint Learning and Optimization Approach for the Two-Stage Stochastic Service Network Design Problem

This paper proposes a neural network-augmented optimization framework for the computationally intractable two-stage Stochastic Service Network Design problem, demonstrating that a novel perturbation-based data generation strategy enables the model to achieve solution quality comparable to Sample Average Approximation while offering improved scalability for freight consolidation carriers.

Original authors: Ahmad Baubaid

Published 2026-10-29

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ahmad Baubaid

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Freight companies that move goods by truck, train, or ship face a constant, high-stakes gamble. They must decide today how many vehicles to schedule and which routes to open for the coming season, long before they know exactly how much cargo will actually arrive. If they plan too few vehicles, they miss shipments and pay heavy penalties; if they plan too many, they waste money on empty trucks. This is the core of the service network design problem: creating a map of connections that balances cost and capacity. In the real world, the future is never certain. Demand fluctuates, traffic jams appear, and fuel prices shift. To handle this, planners use a method called a two-stage stochastic program. In the first stage, they lock in their network design. In the second stage, once the actual demand is revealed, they adjust by paying for extra, more expensive spot-market services if their initial plan falls short. The goal is to find the initial design that minimizes the total expected cost, accounting for all possible future scenarios. However, calculating this for a realistic network with thousands of possible outcomes is so computationally heavy that it often becomes impossible to solve with standard tools.

Researchers at King Fahd University of Petroleum and Minerals have developed a new way to tackle this impossible calculation by teaching a computer to guess the cost of the second stage. Instead of trying to solve the complex math for every single possible future scenario, the team trained a type of artificial intelligence, known as a neural network, to act as a shortcut. This network learns to predict the extra cost a company would face if they chose a specific network design, based on thousands of examples it studied beforehand. Once trained, this neural network is embedded directly into the planning software. The software then asks the network, "If we build this specific network, what will the future cost look like?" and uses that answer to find the best overall plan. This turns a problem that usually takes forever to solve into one that can be handled quickly, offering a practical tool for logistics managers.

The critical challenge in this approach was figuring out how to teach the neural network effectively. Because the number of possible vehicle schedules is vast and unbounded, simply feeding the computer random examples of schedules would not work well. The researchers tested three different ways to generate the training data. The first was a random approach, where they created thousands of random vehicle schedules. The second was a perturbation-based approach, which started with realistic schedules derived from solving smaller, simpler versions of the problem and then made small, local adjustments to them. The third was a hybrid mix of the two. When they tested these methods on eighteen different network scenarios, the results were clear. The random approach produced poor predictions and led to suboptimal plans. In contrast, the perturbation-based method and the hybrid method, which relied on realistic starting points, generated highly accurate predictions. These methods allowed the system to find network designs that were significantly cheaper and more reliable than those found using the random data.

To see if this new learning-based method could compete with existing solutions, the researchers compared it against a standard industry technique called Sample Average Approximation. This traditional method works by solving the problem repeatedly with different sets of random scenarios to find a good answer. The study found that the learning-based approach, particularly when using the perturbation or hybrid data generation methods, produced designs of comparable quality to the traditional method. In many cases, the new approach found solutions that were just as good, but it did so by solving a single, streamlined model rather than running dozens of complex calculations. The researchers noted that while the new method requires an upfront investment of time to generate the training data and train the network, it offers a powerful alternative for companies that need to make these decisions quickly or face networks too large for traditional solvers. The study concludes that by learning from realistic examples rather than random guesses, artificial intelligence can successfully navigate the uncertainty of freight planning, providing a viable and efficient path forward for service network design.

Technical Summary: A Joint Learning and Optimization Approach for the Two-Stage Stochastic Service Network Design Problem

Problem Definition
The paper addresses the Two-Stage Stochastic Service Network Design (SSND) problem, a critical tactical planning challenge for freight consolidation carriers (e.g., LTL, parcel, and intermodal carriers). In this context, carriers must determine the capacity of services (number of vehicles) to operate between terminals for an upcoming season under uncertain demand. The problem is formulated as a two-stage stochastic program:

First Stage: Decisions involve selecting the number of vehicles to operate on network arcs (design variables) before demand is realized. These are general integer variables.
Second Stage: Once demand is revealed, the carrier routes commodities through the selected network. If the planned capacity is insufficient, additional "spot market" vehicles are acquired at a higher cost (recourse decisions).
The objective is to minimize the sum of first-stage design costs and the expected second-stage recourse costs. The problem is computationally intractable for realistic network sizes due to the large-scale mixed-integer nature of the model and the exponential growth of scenarios required to represent uncertainty.

Methodology
The author proposes a neural network-augmented optimization framework that replaces the computationally expensive second-stage recourse cost subproblem with a learned surrogate model. The core methodology involves:

Surrogate Modeling: A feedforward neural network (NN) with Rectified Linear Unit (ReLU) activation functions is trained to approximate the expected recourse cost $E_\omega[Q(r, \omega)]$ given a first-stage design vector $r$ .
Embedding into MIP: Because ReLU functions can be exactly represented using mixed-integer linear constraints, the trained NN is embedded directly into a Mixed-Integer Programming (MIP) formulation. This creates a "surrogate MIP" where the second-stage subproblem constraints and objective are replaced by the NN's mathematical representation, allowing the entire problem to be solved as a single deterministic MIP.
Data Generation Strategies: A significant portion of the methodology focuses on generating labeled training data (pairs of design vectors $r$ $r$ and their true expected recourse costs). Since the first-stage variables are general integers (unbounded), random sampling is insufficient. The author introduces and compares three strategies:
- Random: Generates vehicle counts uniformly across arcs, scaled to meet a global capacity limit.
- Perturbation: Seeds training samples from exact solutions of single-scenario deterministic subproblems. It then generates additional samples by applying small integer perturbations to these base solutions to explore local neighborhoods of high-quality designs.
- Hybrid: A combination of the Perturbation and Random approaches, controlled by a parameter $\alpha$ (the fraction of samples generated via perturbation).
Benchmarking: The proposed approach is benchmarked against the Sample Average Approximation (SAA) method, a standard technique for solving two-stage stochastic programs that relies on sampling a finite set of scenarios to approximate the expected cost.

Key Contributions
The paper makes four primary contributions to the literature:

Novel Framework for General Integers: It presents the first learning-based approach for the SSND problem specifically handling general integer first-stage variables, extending previous work that was limited to binary variables.
Advanced Data Generation: It proposes and validates novel data generation techniques (Perturbation and Hybrid) specifically designed to cover the unbounded feasible solution space of integer design variables more effectively than random sampling.
Empirical Validation: Through experiments on 18 distinct network instances, the study demonstrates that the choice of data generation method significantly impacts solution quality. The Perturbation and Hybrid approaches consistently outperform the Random approach in both prediction accuracy (MAE, MSE) and the realized cost of the resulting network designs.
Comparative Analysis with SAA: The study benchmarks the learning-based approach against SAA. Results indicate that the Perturbation and Hybrid methods yield solution qualities comparable to SAA (with average gaps to the best solution of 0.94% and 1.02%, respectively) while offering different trade-offs regarding computational effort and scalability.

Results

Prediction Accuracy: The Perturbation-based approach achieved the lowest Mean Absolute Error (MAE = 9.11) and Mean Squared Error (MSE = 161.95) on the test set, outperforming both Random and Hybrid methods in absolute error metrics.
Solution Quality: Designs generated using the Perturbation and Hybrid data strategies resulted in lower actual total costs compared to those generated using the Random strategy. The Perturbation approach showed the closest agreement between estimated and actual costs (average deviation of 1.33%), whereas the Random approach showed significantly higher deviations (10.81%).
Dataset Size Sensitivity: Increasing the training dataset size generally reduced error metrics, with performance stabilizing after approximately 4,000 samples.
Hybrid Parameter ( $\alpha$ ): Varying the hybrid parameter $\alpha$ (the ratio of perturbation to random samples) showed that $\alpha = 0.75$ provided the best balance, yielding the lowest actual costs on the majority of instances, particularly for larger network configurations.
SAA Comparison: While SAA occasionally found slightly better solutions on larger instances, the learning-based approaches achieved competitive results by solving a single surrogate model, contrasting with SAA's requirement to solve multiple scenario-based MIPs.

Significance and Claims
The paper claims that the proposed framework offers a viable alternative heuristic for freight consolidation carriers facing the SSND problem. By replacing the intractable second-stage subproblem with a neural network surrogate, the approach simplifies the optimization process. The author emphasizes that the specific data generation strategies (Perturbation and Hybrid) are crucial for the success of this method when dealing with general integer variables, as they ensure the training data adequately covers the relevant regions of the solution space. The work suggests that while the training phase requires computational effort to generate labels, the subsequent optimization is efficient, and the approach provides a complementary trade-off to traditional methods like SAA. The author modestly positions this as an extension of existing learning-assisted optimization, noting that future work could explore training a single generalizable model across different network instances or utilizing Graph Neural Networks to better exploit network structures.

Technical Summary: A Joint Learning and Optimization Approach for the Two-Stage Stochastic Service Network Design Problem

More like this