用深度学习加速货运打包,实现亚秒级高效匹配
Deep Learning--Accelerated Multi-Start Large Neighborhood Search for Real-time Freight Bundling
- 用Transformer构建初始解,再用多起点大邻域搜索优化
- 在亚秒内达成近似最优解,收益差距小于2%
- 适合实时货运平台、物流调度系统应用
在线货运交易平台(OFEX)在现代物流中起关键作用,但运输任务的组合打包仍存在效率瓶颈。本文将问题建模为多商品一对一取送货选择性旅行商问题(m1-PDSTSP),在容量、先后顺序和路线长度约束下优化收益驱动的货运打包。核心挑战是在亚秒级延迟内完成组合选择与路径规划。提出一种学习加速的混合搜索流程:基于Transformer的构造器生成高质量初始解,结合创新的多起点大邻域搜索(MSLNS)元启发式算法,在滚动时间窗框架下反复冻结市场快照并求解。该方法利用学习模型的低延迟高精度推理与改进搜索的鲁棒性,多起点设计和合理种子提升探索效率。在多个基准测试中,本方法在解质量上优于当前最先进的神经组合优化与元启发式基线,相较最优精确解法总收益差距小于2%。据我们所知,这是首个证明深度神经网络构造器可稳定提供高质量种子用于(多起点)改进启发式的方法,适用范围扩展至广泛的选择性旅行商问题与取送货问题。
原文摘要 · Abstract (English)
Online Freight Exchange Systems (OFEX) play a crucial role in modern freight logistics by facilitating real-time matching between shippers and carrier. However, efficient combinatorial bundling of transporation jobs remains a bottleneck. We model the OFEX combinatorial bundling problem as a multi-commodity one-to-one pickup-and-delivery selective traveling salesperson problem (m1-PDSTSP), which optimizes revenue-driven freight bundling under capacity, precedence, and route-length constraints. The key challenge is to couple combinatorial bundle selection with pickup-and-delivery routing under sub-second latency. We 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 within a rolling-horizon scheme in which the platform repeatedly freezes the current marketplace into a static snapshot and solves it under a short time budget. This pairing leverages the low-latency, high-quality inference of the learning-based constructor alongside the robustness of improvement search; the multi-start design and plausible seeds help LNS to explore the solution space more efficiently. Across benchmarks, our method outperforms state-of-the-art neural combinatorial optimization and metaheuristic baselines in solution quality with comparable time, achieving an optimality gap of less than 2\% in total revenue relative to the best available exact baseline method. To our knowledge, this is the first work to establish that a Deep Neural Network-based constructor can reliably provide high-quality seeds for (multi-start) improvement heuristics, with applicability beyond the \textit{m1-PDSTSP} to a broad class of selective traveling salesperson problems and pickup and delivery problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。