アーカイブ / Robotics
訪問先を経路の途中へ挿入するL2C-Insert：配送経路の長さと計算時間を検証
L2C-Insert
L2C-Insertの原論文から掲載した図です。細部はクリックして拡大できます。
原論文の図の説明を読む
Figure 1: Appending-based construction vs. Insertion-based construction. Given the same intermediate state in the construction process: (a) The appending-based paradigm restricts the addition of a selected node exclusively to the end of the current partial solution. This inflexibility leads to path intersections, a common cause of suboptimal solutions. (b) In contrast, the insertion-based construction offers greater flexibility by allowing the selected node to be inserted into any feasible position within the partial solution. Such flexibility is crucial for avoiding the intersections and thereby enhancing the potential for generating high-quality solutions.
概要
- L2C-Insertは、選んだ未訪問地点を部分経路の有効な位置へ挿入し、その位置を学習モデルで予測する。
- 著者らはTSPとCVRPの100地点の教師付きデータで学習し、合成問題とTSPLIB・CVRPLIBの問題で経路長、基準との差、推論時間を評価した。
- 合成TSP1KのII=1000設定はLEHD RRC1000より短い経路を報告した。一方、合成CVRP100ではHGSの経路長が短く、手法間の時間比較には実行条件の違いがある。
補足：編集した模式図で仕組みを確認する
VISUAL EXPLAINER
図でつかむ、L2C-Insertの仕組み
- 01地点の座標
- 02近い未訪問点を選択
- 03挿入位置を予測
- 04局所再構築
- 05訪問順
原論文の説明をもとにした模式図です。処理の細部は省略しています。
研究の背景
L2C-Insertが扱うのは、複数の地点をどの順に訪れるかを決める経路問題である。巡回セールスマン問題（TSP）では全地点を一度ずつ訪れ、積載制約付き配送経路問題（CVRP）では車両容量も守る。地点が増えると厳密な最適解を求める計算は難しくなる。
ニューラル組合せ最適化とは、訪問順などの選び方をデータから学ぶ手法群をいう。従来の構築型手法の多くは地点を経路の末尾へ追加するため、構築途中で既存の二地点の間に新しい地点を置く選択ができない。
手法
L2C-Insertは地点の特徴を数値表現に変え、部分経路へ未訪問地点を一つずつ挿入する。TSPでは各地点の二次元座標から、全地点を回る訪問順を作る。次に挿入する地点は、直前に挿入した地点からのユークリッド距離、つまり直線距離が最も短い未訪問地点から選ぶ。モデルは、その地点を既存経路のどの二地点の間に置くかを予測する。
予測には挿入対象、残る未訪問地点、隣り合う訪問済み地点を組にした位置の数値表現を使う。アテンション層はそれらの関係を計算し、有効な位置に挿入確率を割り当てる。学習では完成経路から正解位置を作る。推論では初期経路を作った後、近い地点群を外して差し直す局所再構築を行い、良い経路を残す。
新規性
著者らは、学習を用いて経路を順に組み立てる手法に、挿入方式を導入した点を新規性として主張する。モデルが主に学ぶのは次の訪問先の選択ではなく、選んだ地点を部分経路のどこに置くかという判断である。
完成経路を教師ラベルとして挿入位置の正解を作り、推論時には近い地点を外して差し直す局所再構築も組み合わせる。新規性の主張は、この構築手法の枠組みに関するものだ。
従来手法との違い
従来の末尾追加型の構築法は、未訪問地点を現在の経路の最後に足す。L2C-Insertは選んだ地点を有効な途中位置にも置けるため、構築中に訪問順を変えられる。その分、挿入位置を決める処理が必要になる。
論文の表には学習型のLEHDやGLOP、古典的手法のLKH3やHGSなどが並ぶ。L2C-Insert内でも初期経路のみのGreedyと、局所再構築を反復する設定では処理量が異なる。時間比較にはCPUとGPUの実行条件の違いもある。
実験結果
著者らはTSPとCVRPについて、それぞれ100地点の学習問題を100万件生成し、ConcordeとHGSの解を教師ラベルに用いた。評価には100～10万地点の合成問題と、TSPLIBのTSP49件、CVRPLIB Set-XのCVRP100件を使った。指標は平均経路長（Length）、基準ソルバーとの差（Gap）、総推論時間（Time）である。
合成TSP1KではL2C-InsertのII=1000、つまり局所再構築1000回の設定がLength 23.230、Gap 0.481%、Time 46.4分で、LEHD RRC1000は23.288、0.731%、5.2時間だった。一方、合成CVRP100では同設定が15.627、0.413%、10.6時間で、基準のHGSは15.56、0.000%、4.5時間だった。
応用の可能性
編集上の応用案 · 論文が実証した用途とは区別しています。
編集上の応用案：配送拠点から複数の届け先を回る一日の訪問順の候補を作る。入力候補は拠点と届け先の座標、各届け先の需要量、車両の積載上限で、出力は訪問順と移動距離の候補とする。CVRPは車両の積載制約を含む配送経路問題を指す。
導入には対象地域の地点データと、学習用の実行可能な完成経路を示す教師ラベルが必要になる。位置情報の取得元や追加センサーの要否を現場で確認し、CVRP向けの入力表現と制約処理を原文の付録Bに照らして調整する。採用する経路は担当者が制約とともに確認する。
導入時の検証
導入時の検証案 · 対象データでの再評価が必要です。
導入時の検証案：過去の配送日から拠点と届け先の座標、需要量、車両容量を集め、欠損と容量制約を点検する。学習には同じ条件で作られた実行可能な完成経路の教師ラベルを用意する。座標の取得元と追加センサーの要否を確認し、CVRP向けの特徴量と制約処理は付録Bで確かめてから対象地域へ合わせる。
同じ配送日を使い、現行の経路作成手順を比較基準にする。全地点の訪問と容量制約を確認したうえで、総移動距離と作成時間を測る。局所再構築の反復回数も変え、改善量と所要時間を記録する。
限界と課題
著者らは、CPUで動く古典的手法とGPUで動く学習型手法の推論時間を直接比較できないと注記する。また、局所再構築は反復によって経路を改善する処理なので、報告値は反復回数と所要時間を併せて読む必要がある。
編集上の検証事項は、対象地域に移した場合の経路長と実行時間、積載上限を含む制約の満たし方、現場の追加条件への対応である。確認できた本文の範囲ではCVRP向けの変更点は付録B参照とされており、入力形式や制約判定の詳細はここから確定できない。
出典
元のタイトル・要旨を確認する（英語）
Learning to Insert for Constructive Neural Vehicle Routing Solver
Neural Combinatorial Optimisation (NCO) is a promising learning-based approach for solving Vehicle Routing Problems (VRPs) without extensive manual design. While existing constructive NCO methods typically follow an appending-based paradigm that sequentially adds unvisited nodes to partial solutions, this rigid approach often leads to suboptimal results. To overcome this limitation, we explore the idea of insertion-based paradigm and propose Learning to Construct with Insertion-based Paradigm (L2C-Insert), a novel learning-based method for constructive NCO. Unlike traditional approaches, L2C-Insert builds solutions by strategically inserting unvisited nodes at any valid position in the current partial solution, which can significantly enhance the flexibility and solution quality. The proposed framework introduces three key components: a novel model architecture for precise insertion position prediction, an efficient training scheme for model optimization, and an advanced inference technique that fully exploits the insertion paradigm's flexibility. Extensive experiments on both synthetic and real-world instances of the Travelling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that L2C-Insert consistently achieves superior performance across various problem sizes.
論文本体の取得範囲に基づく解説。AIが作成した未校閲の記事です。性能の数値は著者の評価条件に依存します。応用例と検証計画は編集上の提案です。解説更新：2026-10-01