Research Background
The logistics industry, particularly the trucking sector, is a critical component of modern freight transportation. Online Freight Exchange Systems (OFEX) platforms, such as Trans.eu and Full Truck Alliance, have emerged as digital marketplaces that facilitate real-time matching between shippers and carriers, reducing search and transaction costs. However, efficient combinatorial bundling of transportation jobs remains a significant challenge due to the computational complexity and real-time constraints.
Online Freight Exchange Systems (OFEX) are pivotal in modern freight logistics, enabling seamless freight matching, real-time monitoring, and payment processing. These platforms help reduce transport expenses for shippers and enable carriers, especially small operators, to find profitable backhauls, thereby reducing empty kilometers and improving market efficiency. However, the problem of efficiently bundling shipments and recommending route-level assignments in real-time is highly challenging. OFEX markets are computationally centralized but informationally decentralized, with key information being private and loads arriving asynchronously. This creates conflicts when similar bundles are provided to multiple carriers.
The core challenge is to couple combinatorial bundle selection with pickup-and-delivery routing under sub-second latency constraints. Traditional approaches, such as exact methods, are impractical due to the large search spaces and tight time budgets. Heuristic algorithms, while fast, often get trapped in local optima or require extensive manual tuning. Neural combinatorial optimization (NCO) methods, which leverage machine learning to generate approximate solutions, offer a promising alternative. However, existing NCO methods predominantly address unselective routing problems and struggle with selectivity and operational constraints.
In this context, the authors model the OFEX combinatorial bundling problem as a multi-commodity one-to-one pickup-and-delivery selective traveling salesperson problem (m1-PDSTSP). The objective is to maximize revenue over all feasible pickup-and-delivery completions, subject to capacity, precedence, and route-length constraints. To meet real-time constraints, they propose a learning–accelerated hybrid search pipeline that pairs a Transformer Neural Network-based constructive policy with an innovative Multi-Start Large Neighborhood Search (MSLNS) metaheuristic.
The m1-PDSTSP formulation captures the complexities of the OFEX environment, including the need to handle heterogeneous requests, selectivity, and operational constraints. The problem is NP-hard, even in static settings, making it a challenging task for real-time applications. The authors’ approach aims to bridge the gap between the need for high-quality solutions and the requirement for low-latency performance, a critical aspect in the dynamic and fast-paced nature of OFEX platforms.
Key Findings
The proposed method, Deep Learning–Accelerated Multi-Start Large Neighborhood Search (MSLNS), achieves superior performance in solution quality and runtime compared to state-of-the-art baselines. This section details the method principle, key design/algorithm logic, experimental setup, and evidence supporting these findings.
Transformer-Based Constructor
The Transformer-based constructor is a key component of the hybrid pipeline. It scores and assembles requests into a feasible route-level bundle, producing plausible seed solutions rapidly that already respect pickup-and-delivery precedence, capacity, and route-length limits. The Transformer decoding process is modeled as a deterministic Markov Decision Process (MDP), enabling efficient training and inference.
The constructor leverages a reinforcement learning (RL) framework, specifically the REINFORCE algorithm, to learn a stochastic policy that can generate high-quality initial solutions. This approach avoids the need for teacher labels, making it more robust and generalizable. The constructor’s ability to produce high-quality seeds is crucial for the subsequent improvement phase, as it positions the search close to promising basins, enabling efficient refinement.
Experimental results show that the DNN-generated solutions alone surpass metaheuristics initialized with greedy constructions, using less wall-clock time. For instance, on benchmark instances, the Transformer-based constructor achieved an average solution quality of 17.943 with a standard deviation of 6.75, compared to a baseline of 16.085 with a standard deviation of 12.134. The constructor’s performance is further enhanced by its ability to generalize across different problem sizes and constraint regimes, making it a versatile tool for real-world applications.
The Transformer-based constructor is trained using a combination of supervised and reinforcement learning. During the training phase, the model learns to construct feasible routes by iteratively selecting the next node to visit, guided by a reward function that encourages high-revenue and feasible solutions. The use of reinforcement learning allows the model to explore the solution space more effectively, avoiding the pitfalls of greedy strategies that often get stuck in local optima. The training process involves generating a large number of random instances and using them as the test set after each epoch. This ensures that the model is exposed to a wide variety of scenarios, enhancing its generalization capabilities.
Multi-Start Large Neighborhood Search (MSLNS)
The MSLNS is designed to refine the initial solutions generated by the Transformer-based constructor. It provides diversification through multi-start strategies and intensification through adaptive destroy sizes, allowing the search to escape local optima and reduce the remaining optimality gap. The MSLNS uses frequency signals from multiple neural trajectories to identify backbone requests and bias removal accordingly, creating a learning-driven diversification–intensification mechanism.
The MSLNS procedure is particularly effective in handling the complex neighborhood structure and feasibility constraints of the m1-PDSTSP. By combining the strengths of the learning-based constructor and the robustness of the improvement heuristics, the full DNN+MSLNS procedure achieves the lowest optimality gap in the majority of benchmark settings, under comparable wall-clock time. For example, the MSLNS improved the solution quality from 17.943 to 18.191, with a standard deviation of 3.53, achieving an optimality gap of less than 2% relative to the best available exact baseline method.
The MSLNS operates in a rolling-horizon scheme, where the platform repeatedly solves static instances of the m1-PDSTSP for a short timescale. This approach allows the system to adapt to the continuously evolving market conditions while maintaining low-latency performance. The multi-start strategy involves generating multiple initial solutions, each serving as a starting point for the improvement phase. The adaptive destroy sizes ensure that the search explores a diverse set of neighborhoods, increasing the likelihood of finding high-quality solutions. The MSLNS also employs softmax-biased removal and adaptive destroy sizes, which help in balancing diversification and intensification, leading to better overall performance.
Zero-Shot Generalization and Robustness
The proposed method demonstrates strong zero-shot generalization and robustness to varying constraint tightness and revenue settings. Across different route-length budgets and vehicle capacities, the method maintains consistent performance without retraining. For instance, as the route-length budget increases, the solution quality improves from 16.060 to 18.191, with a standard deviation of 4.41%. Similarly, across different revenue settings (Ton-Distance, Constant, and Uniform), the relative performance of the hybrid method remains consistent, achieving near-optimal performance in all cases.
The robustness of the method is further supported by its ability to adapt to changing operating conditions. As constraints loosen, the method’s performance closely tracks the trend with only minor deviations, indicating reliable adaptation to varying constraints. This is crucial for real-world applications where constraints may vary frequently. The method’s consistency across different revenue settings also highlights its versatility, making it suitable for a wide range of practical scenarios.
The zero-shot generalization capability of the method is attributed to the global ordering and selection priors learned by the Transformer-based constructor. These priors enable the model to make informed decisions about which requests to include in the bundle and how to sequence them, even in unseen problem instances. The MSLNS further enhances this capability by providing a robust improvement phase that can refine the initial solutions, ensuring high-quality outcomes across a variety of conditions. The method’s robustness to out-of-distribution data is demonstrated through extensive experiments, showing that it can maintain high performance even when faced with new and unseen constraints.
Limitations
While the proposed method demonstrates significant improvements in solution quality and runtime, it is not without limitations. This section enumerates the main limitations, their impact, and possible mitigations.
Computational Complexity
The MSLNS procedure, while effective, requires more computational effort compared to the Transformer-based constructor alone. The multi-start strategy and adaptive destroy sizes introduce additional complexity, which can be a bottleneck in extremely time-sensitive scenarios. For example, the full DNN+MSLNS procedure takes approximately 30 minutes to solve a benchmark instance, compared to 6 minutes for the DNN-generated solutions alone.
To mitigate this, future work could explore more efficient implementations of the MSLNS, such as parallelizing the multi-start strategy or optimizing the destroy and repair operators. Additionally, hardware acceleration, such as using GPUs, could significantly reduce the computational time. Parallelization techniques, such as distributing the computation across multiple cores or nodes, can help speed up the search process. Optimizing the destroy and repair operators, for example, by using more sophisticated heuristics or machine learning models, can also improve the efficiency of the MSLNS. Another potential approach is to develop more efficient algorithms for the destroy and repair phases, such as using approximate methods or leveraging parallel computing architectures to distribute the workload.
Generalization to Larger Instances
The method has been tested on benchmark instances with up to 82 nodes, but its performance on larger instances remains an open question. The complexity of the m1-PDSTSP grows exponentially with the number of nodes, and the method may struggle to scale to very large instances. For instance, the solution quality and runtime may degrade as the number of nodes increases beyond 100.
To address this, further research could focus on developing more scalable versions of the Transformer-based constructor and MSLNS. Techniques such as hierarchical clustering or graph partitioning could be used to break down large instances into smaller, more manageable subproblems. Additionally, transfer learning and pre-training on large-scale datasets could help improve the generalization of the method to larger instances. Hierarchical clustering can group nodes into clusters, allowing the method to first solve the problem at a coarser level and then refine the solution at a finer level. Graph partitioning can divide the problem into smaller subproblems, which can be solved independently and then combined to form the final solution. Another approach is to use more advanced neural network architectures, such as those with attention mechanisms, to better capture the relationships between nodes in large instances.
Dependency on Training Data
The effectiveness of the Transformer-based constructor relies heavily on the quality and diversity of the training data. If the training data is not representative of the real-world scenarios, the learned policy may not generalize well to new instances. For example, if the training data is biased towards certain types of requests or constraints, the constructor may produce suboptimal solutions in other settings.
To mitigate this, it is important to ensure that the training data is diverse and representative of the real-world scenarios. Data augmentation techniques, such as random perturbations and synthetic data generation, can help increase the diversity of the training set. Additionally, continuous learning and online adaptation mechanisms could be integrated to update the model as new data becomes available. Continuous learning can help the model adapt to changes in the data distribution over time, while online adaptation can allow the model to fine-tune its parameters based on real-time feedback from the environment. Another approach is to use active learning, where the model can query for more data in regions where it is uncertain, thereby improving its generalization capabilities.
Practical Implications
The proposed method has several practical implications for supply-chain and AI practitioners. This section outlines three concrete scenarios/decisions/implementation paths for leveraging the method in real-world applications.
Real-Time Freight Matching
The method can be directly implemented in OFEX platforms to provide real-time freight matching and bundling. By integrating the Transformer-based constructor and MSLNS, platforms can recommend high-quality, feasible bundles to carriers within sub-second latency. This can lead to increased revenue, equipment utilization, and overall market efficiency. For example, a platform could use the method to dynamically bundle shipments and assign them to carriers, ensuring that each carrier receives a feasible and profitable bundle. The real-time nature of the method allows the platform to adapt to the constantly changing market conditions, providing up-to-date and relevant recommendations to carriers. The method’s ability to handle real-time data and constraints makes it particularly suitable for dynamic environments where quick and accurate decisions are essential.
Route Optimization for Carriers
Carriers, especially small operators, can use the method to optimize their routes and maximize their profits. By leveraging the method’s ability to handle selectivity and operational constraints, carriers can assemble feasible, profitable bundles of loads, reducing empty kilometers and improving their bottom line. For instance, a carrier could use the method to plan their daily routes, taking into account the available loads, vehicle capacity, and route-length constraints. The method’s ability to handle selectivity ensures that the carrier can choose the most profitable loads, while the operational constraints ensure that the routes are feasible and efficient. The method can also be integrated into existing route planning software, providing carriers with a powerful tool to optimize their operations and increase their profitability.
Dynamic Pricing and Revenue Management
The method can also be used for dynamic pricing and revenue management in OFEX platforms. By continuously solving static instances of the m1-PDSTSP, platforms can adjust their pricing strategies based on the current market conditions and demand patterns. This can help platforms maximize their revenue and improve the overall efficiency of the freight ecosystem. For example, a platform could use the method to dynamically adjust the prices of available loads, ensuring that the most profitable bundles are matched with the right carriers. The method’s robustness to varying constraints and revenue settings makes it a valuable tool for dynamic pricing and revenue management, allowing the platform to respond quickly to changes in the market. The method can also be used to predict future demand and adjust pricing strategies accordingly, further enhancing the platform’s ability to manage its revenue effectively.
Source: https://arxiv.org/abs/2512.11187
