《Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks》
https：//
arxiv。org/pdf/1803。0962
1。pdf
現在對於多旅行商問題的研究太少了。 本文設計了一個將銷售員，城市和倉庫視為三組不同cardinalities的神經網路策略。 將針對
集合
開發的最新體系結構中的元素與圖網路中的元素融合。由於結合
新的強制執行輸出層的約束、專用損失和搜尋方法
，新演算法實驗表現優於該領域領先求解器的所有元啟發式演算法。
1。簡介
機器學習的基本目標之一是為難以解決的複雜組合最佳化問題提供學習的近似值。
影象分割，姿態估計，序列比對，解析，機器翻譯，蛋白質設計等可以被定義為大規模組合問題。經典的NP難組合問題帶來了一系列獨特挑戰。 首先，獲得訓練樣本通常需要解決問題本身，這僅在相對較小的規模上才可行。 其次，與感知資料不同，這些問題通常在無序或特殊結構的輸入中定義。 第三，可行解受到一系列複雜的約束。 這些挑戰要求進行專門的研究和設計可微分體系結構，這些體系可以（i）很
好地表示輸入中的不變性，並且（ii）對輸出施加約束。
MTSP formulation：
有n個城市，m個推銷員和城市間的距離度量d：［n］×［n］→R。 所有推銷員都從城市1（倉庫）開始各自走出一條路線，以使除推銷員外的每個城市都能被任何推銷員精確（總共）訪問一次，且所有推銷員在遊覽結束時都會返回倉庫。 當且僅當推銷員k從城市i到達城市j時，我們才將δ_i，j，k定義為1，否則為0。 目的是最小化行駛距離總和：
約束表示： 2a）每個銷售人員只離開倉庫一次； 2b）每個銷售人員恰好返回倉庫一次； 2c）每個非倉庫城市只離開一次； 2d）所有推銷員加起來僅返回每個非倉庫城市一次； 2e） 推銷員訪問非倉庫城市的次數等於離開城市的次數； ）2f）不存在subtours（不包括倉庫（僅使用不超過 n-1 個潛變數 u2，。。。，un）的退化路線）。
2相關工作
從技術角度來看，我們的架構涉及一個新興的工作主體——對集合形式的輸入進行編碼。類似於Pointnet： Deep learning on point sets for 3d classification and segmentation、Manzil Zaheer Deep Sets，我們使用池來獲得不隨元素順序變化的表示， 然後在每個元素上進行區域性計算。正如上述2篇論文所示，在溫和條件下，這 是實現排列不變性的唯一方法。如上所述，我們的網路適合
處理多個集合
。 此外，由於 mTSP 具有集合和圖形問題共有的屬性，我們的網路也受到圖網路（通常稱為圖卷積網路）最新進展Learning combinatorial optimization algorithms over graphs、Semi-supervised classification with graph convolutional networks的啟發。這些網路在圖上執行，並使用 節點間的底層度量以分層方式傳播資訊。Learning combinatorial optimization algorithms over graphs使用距離度量作為每個區域性計算的顯 式輸入，Semi-supervised classification with graph convolutional networks在傳播規則中隱式使用它，而我們使用
從距離到區域性權重的學習轉換， 將圖屬性整合到我們的集合專用架構中。
2。1 TSP
求解器
粗糙翻譯——
TSP 是最著名的 NP-hard 問題之一，且一些例項如對稱歐幾里得變型是 NP 完全的，沒有已知的多項式時間演算法能解決它。由於 TSP 在許多實際應 用中的重要性，它吸引了科學家的大量研究。克里斯托菲德斯（I）1976）提出了一種著名的旅行商問題近似演算法， 該演算法利用最小生成樹和最小權重完美匹配的計算達到 1。5 的近似比。
The Concorde solver
（Applegate et al。， 2006）使用高度最佳化和精心製作的方法，以有效地修剪搜尋空間，通常被認為是目
前最好的精確 TSP 求解器
。
指標網
絡（I）Vinyals 等人，2015b））是一種通用的順序到順序（I）seq2seq）結構，在現代文獻中重新點燃了對基 於神經網路的 TSP 求解器的興趣，Levy 和 Wolf （I）2017）緊隨其後，使用
LSTMs 和卷積層
匹配其效能。 Bello 等人（I）2016）將指
針網路與強化學習
（I）RL）結合使用，以
無監督的方式學習 TSP 啟發式
，Khalil 等人 （I）2017）將
structure2vec
（I）Dai 等人，2016）
圖表示與 Q-學習
一起使用，以實現同樣的目的，儘管沒有對 推理樣本進行主動訓練。在我們工作的同時，庫爾和韋林（I）2018）已經使用
基於注意力的編碼器-解碼器解
決了旅行商問題，該編碼器-解碼器是使用RL進行訓練的，並被證明是旅行商問題學習演算法的最先 進的（I）SOTA））。他們使用了一種類似的方法來解決容量受限的車輛路徑問題及其分次交付變體。 儘管可以將mTSP的解決方案定義為序列的串聯（每個推銷員一個序列），但是這樣的解決方案不會直接暴露問題的約束。 此外，根據定義，s
eq2seq解決方案不是置換
不變的。 如Vinyals等人所示。 （2015a），
seq2seq模型對輸入和輸出的順序極為敏感。
我們最初嘗試使用這種技術導致失敗。
對於基於mTSP的基於注意力的合併，我們無濟於事，發現更簡單的加
權最大合併更
為有效。 加權池利用了問題的圖結構。 在這項工作中，我們提出一種有監督的方法，儘管輸出結構複雜，但仍可以學會解決mTSP並勝過領先的mTSP求解器，同時仍保持TSP的競爭力。
Khalil等。 （2017），Bello等。 （2016）和Kool and Welling（2018）並沒有為領先的TSP求解器（Concorde）提供立即的替代方案，因此，對於RL是否會勝過現有的TSP求解器，以及RL是否是解決組合問題的正確方法仍存在爭議。
2。2 mTSP 求解器
與TSP相比，mTSP的研究相對較少。 許多現有的mTSP啟發式方法可應用於更大的問題集，如車輛路徑問題（VRP），不過這裡頭又有其他約束條件如推銷員的能力、應訪問城市的時間窗等。
Google OR-Tools（OR-Tools，2012）是經過高度最佳化和完善的運籌學計劃，它提供了一個能解決VRP和mTSP的路由模組。 OR-Tools先用一種相當簡單的啟發式方法來獲得初始解（如貪婪地擴充套件當前路線），然後使用選定的元啟發式方法來導航搜尋空間並獲得更好解，如“貪婪下降”，“模擬退火”和“禁忌搜尋”。 在搜尋過程中，OR-Tools能使用特定於VRP的啟發式演算法，如Lin-Kernighan（Lin和Kernighan，1973）和2-opt。
關於mTSP的經典神經網路文獻大多是對TSP解法進行擴充。 Wacholder等（1989）透過建立與銷售員數量相同的庫房副本，將mTSP還原為TSP。然後，透過每次訪問倉庫副本時都切斷路線，將TSP路線分為不同銷售員。這樣得到的解概括了Hopfield和Tank（1985）的TSP解，它是從一個（大小為非倉庫城市數量和銷售員數量的平方的）鄰接矩陣還原得到的。Vakhutinsky和Golden（1994）用彈性網解決了VRP，Torki等人（1997）用自組織特徵圖（SOFMs）解決了VRP。這兩種方法都是per-sample最佳化的方法（即不進行訓練），使用神經網路來描述模型動態，並使用問題定製的能量函式來收斂到區域性最小值。SOFMs後來被Somhom等人（1999）和Modares等人（1999）用來處理mTSP的minmax變體，其目標是為銷售人員尋找路線，以最小化他們之間的最大旅遊長度。
Nazari（2018）和Kool and Welling（2018）與我們工作同時進行，他們解決了mTSP的另兩種通用變體：Capacitated Vehicle Routing Problem（每輛車都限制了最大容量，每個城市都有需求）以及其Split Delivery變體（一輛車可能多次到達每個城市）。兩種方法都使用了基於注意力的使用RL訓練後在合成樣本上評估的編碼器-解碼器架構。他們的方法以auto-regressive的方式將解輸出為序列的連線，而不是我們的稀疏輸出。
4。 Method
4。1 Permutation Invariant Pooling Network
關於4.1，強烈安利屁屁踢-Permutation Invariance and Combinatorial Optimizations with Graph Deep
Learning
http：//www。
math。umd。edu/~rvbalan/P
RESENTATIONS/AUTalk2019。pdf
我們提供了一種用於處理k個不同元素組以便第i組長度為l_i的方法：
我們希望網路對每個組中的元素順序不變且支援可變長度的組。 我們推廣Pointnet： Deep learning on point sets for 3d classification and segmentation到多個組的情況，並在建立上下文向量時透過在每個組上使用置換不變池（如最大池或平均池）來保持每個組內的置換不變。
我們最終選擇了“留一法”（Leave-One-Out）型別的池。 （原因：
粗糙翻譯-我們希望避免描述一個組的上下文向量與該組中單個元素的嵌入重疊的情況。 例如，當在組上採用“最大池化”時，在某個座標中具有最高值的向量可能會受益於接收次高值的額外資訊，而不僅是最大值的副本。 因此，我們透過從組中每個成員的角度分別計算上下文來消除自合併。（沒很懂）
形式上，我們用g表示置換不變池函式，對每個i，j∈［k］和r∈［li］，計算上下文：
網路的主要構建模組是置換不變池層，它使用仿射投影f_i將每個元素
與其上下文
組合
|| 表示串聯運算子。 置換不變池層如圖1所示。
圖1：沒有 spatial weighting的單個置換不變池層。
對許多問題，元素間存在給定的距離度量，比如mTSP給出了城市間的歐式距離度量。 受圖網路的啟發，我們提供了一種用於池網路的空間傳播方案：用
表示元素a、b間的距離，用w（·）表示學習的加權函式。 當用加權的“留一法制”池時，我們將等式推廣，並使用合併向量及其相應權重的乘積來計算上下文向量：
表示逐元素乘法~
借鑑Attention is All you Need，每個置換不變池層之後是由單個隱藏層組成的全連線網路組合，其後是ReLU啟用函式。 我們將隱藏層大小設定為d_
ff。 全連線網路與投影f_
i的共享類似，它在相應的組間共享，因此實際上我們有k個不同的全連線網路。 置換不變池層和共享的全連線網路分別包裝在殘差塊中，然後進行層歸一化：
其中h是置換不變池層或共享的全連線層，而Norm是層歸一化運算子，對用於評估的樣本，它從每個啟用中去除均值併除以所在層所有啟用的標準差。
由排列不變池層和共享的全連線層組成的單個塊如圖2所示。
圖2：通用網路架構。
4。2 Learning the Multiple Traveling Salesmen Problem
透過將問題的每個例項表示為三組來更好地使用mTSP的排列不變池網路：一組銷售員，一組包含倉庫的singleton和一組其他城市（請注意，與TSP不同，在mTSP中 ，倉庫和其他城市的作用略有不同）。用
表示城市間距離矩陣的d_svd維近似。我們將城市編碼為US的行，並使用二維向量（k / m，m）對每個推銷員k∈［m］進行編碼，同時嵌入有關推銷員的本地和全域性資訊。
網路的計算始於將每個輸入元素的共享仿射嵌入到大小為d_
model的向量中，其中共享在同一組元素間進行，然後進行層歸一化。 之後，我們將這些組輸入N個連續的置換不變池塊中，以生成每個銷售員和城市（包括倉庫）的複雜隱藏表示。 在整個N
blocks
中，銷售員和組的
representations大小
保持為
d_model。
最後，對於每個i，j∈［n］和k∈［m］，我們將城市i，城市j和推銷員k的表示連線起來，以從路徑中獲得
推銷員k從城市i到城市j的
路徑大小為3d_
model的隱藏表示。 我們在每個表示上使用一個共享全連線網路，以獲得大小為m×n×n的多層鄰接張量，即，我們使用單個隱藏層大小為d
_model的全連線的網路，然後用ReLU和標量輸出以獲得推銷員k從城市i到城市j的得分。
4。2。1遵守mTSP約束
網路輸出是實值的m×n×n張量。 為使輸出更具可解釋性並使整個模型可微分，我們放寬了網路輸出必須是二進位制的限制，並允許其為0到1間的實數值。 基於通用的基於softmax的歸一化方案，透過對Gold和Rangarajan（1996）的Softassign方法進行概括，我們將網路輸出轉換為對semi multi-stochastic tensor半多隨機張量的估計。
半多隨機張量是介於0和1間的實值張量，它使約束2a到2d都得到滿足。 我們透過Alg 1獲得此張量。 在每次迭代中，演算法都滿足兩個約束：在奇數次迭代中，執行第5-10行，約束 2a和2c得到滿足，在偶數迭代中，執行第12–17行 2b和2d得到滿足。
例如，在第6行中，每個
均按某常數進行縮放，以使約束2a成立。 請注意，在每次迭代中，至少有兩個約束得到滿足，不過可能會違反其他兩個約束。 我們相信，透過推廣Concerning nonnegative matrices and doubly stochastic matrices可證明我們的經驗觀察：演算法收斂到一個同時滿足所有四個約束條件的張量。
T次迭代執行Alg1 後，我們獲得了一個軟的多層鄰接張量。為找到網路輸出中可能性最大的路線，執行搜尋很有必要。 具體來說，使用波束搜尋找到b個最可能有效的解，然後從中選擇最佳解作為最終解。波束搜尋詳細資訊如下，其中
是Alg1的輸出 ：
首先，考慮出庫路徑對應的輸出
，採用單獨的波束搜尋以找到銷售員開始的前b個選項；每個選項包括每個銷售員離開倉庫後要去的城市。形式上，第一階段波束搜尋找到前b個選項S1，。。。，Sb以最大化滿足以下probability-like值。
在獲取了此b個不完整解的第一個池後，執行以下過程：對當前池中的每個不完整解，用k表示路線尚未結束的第一個推銷員的序號。 此類推銷員路線的下一個城市最多有n個不違反約束2即每個城市都不會被多次訪問等的選擇。 對於每種可能的選擇，我們都向新的解池中新增一個新的可能不完整的解（由當前解及推銷員k繼續前往下個所選城市的路線組成）。對當前池中所有O（b）個解應用相同過程，將產生新的O（b·n）大小的解池。
修剪這些解（保留具有最高值（當前值乘以z中對應於新新增路徑的單元格的值）的前b個解）並重復此過程，直到找到O（b）個完整的有效解。 行程總和最短的最終解構成最終輸出。 請注意，為了使波束搜尋在數值上更穩定，我們最大化機率的對數之和而非機率的乘積。
4。2。2 Representation Invariant Loss
由於我們希望網路的輸入和輸出對問題的表示（即城市的順序，推銷員的順序以及行進的方向）不變，因此使用受Order matters： Sequence to sequence for sets啟發的自定義損失函式。 我們修改n個城市和m個銷售人員的每個樣本的target，並獲得2^m m！ 可能的targets，包括銷售員的每個可能訂單和每個可能的路線指示。 每個target都被編碼為大小為m×n×n的多層鄰接張量。 然後，將n個城市和m個銷售商的單個樣本的損失定義為Alg 1輸出
的最小歸一化負對數似然率，with respect to the possible targets：
其中λ∈［0，1］是給予倉庫出口路徑的相對權重，如果推銷員k從城市i到達目標標籤中的城市j則
，否則為0。
我們對方程9不變損失的樸素定義的實現需要O（2^m ·m！·m）大小為n×n的矩陣乘法（在應用負對數後，將輸出的m層中每層乘以target的每個可能表示中對應target層）。 一旦設定了推銷員的排列，我們就可輕鬆計算出最佳路線方向，因此我們可預先計算每對輸出層k與目標層p間的最佳損耗：
並獲得以下等效的損失定義：
公式 10在計算時需要O（m^2）次大小為n×n的矩陣乘法。 11不需任何矩陣乘法，但需要O（m！·m）= O（（m + 1）！）簡單運算。 對於常數m，損失計算是多項式的。即使m是一個變數，損失也只在訓練過程中計算，因
此網路實現的演算法在推理過程中是多項式的
。
整個模型，包括Alg。 1是可微分的，因此，模型的訓練是以端到端的方式，使用可變大小的透過ILP求解器求解到最優的樣本。
5。 Experiments
5。1 Datasets
為了實現有監督的訓練，我們按照以下方式生成了730萬個隨機mTSP例項：對於每個介於1和5之間的m、每個介於min（4，2m）和20之間的n，我們在unit square上均勻隨機抽取n個城市，設第一個被抽中的城市為倉庫，m為銷售員數量。利用式1、式2中描述的ILP公式，結合Matlab內建的intlinprog來求解每個例項，使其達到最優。我們為每個這樣的n、m的組合生成99，000個例項作為訓練集（mTSP-train），並生成1，000個例項作為測試集（mTSP-test）。在訓練集的99，000個樣本中，我們用1，000個作為驗證集，進行超引數交叉驗證。
除了mTSP-train和mTSP-test，我們還使用Tackling the Bi-criteria Facet of Multiple Traveling Salesman Problem with Ant Colony Systems定義的mTSPLib基準。該基準重用了公共資料集TSPLib（Reinelt，1991）中的樣本（包含了TSP的各種現實生活例項）。
具體來說，mTSPLib是從TSPLib中建立的，取四個問題（eil51、berlin52、eil76和rat99，分別包含51、52、76和99個城市），並從每個問題中定義四個mTSP樣本，將城市列表中的第一個城市設為倉庫，銷售員數量為2、3、5或7。因此，mTSPLib由16個獨立的mTSP樣本組成，其規模遠大於mTSP-train。
我們的網路必須以兩種方式進行泛化才能具有競爭力：（1）處理相當大的問題，（2）有效處理完全不同的process所產生的問題~
此外，我們在Vinyals等人（2015b）首次提出的三個TSP基準——TSP5、TSP10和TSP20上測試網路，其中TSPX包含X個城市的10000個TSP例項。我們將結果與Vinyals等人（2015b）；Levy和Wolf（2017）；Bello等人（2016）；Kool和Welling（2018）的公開結果進行比較。
5。1。1運籌學基準
我們將其與OR-Tools的路由模組進行比較，該模組支援針對路由問題（如VRP和mTSP）設計的大量配置和啟發式方法，通常用於解決現實生活中的問題。 OR-Tools使用本地搜尋來解決路由問題：首先找到問題的初始解，然後繼續使用預定義的元啟發法在解空間中進行本地導航，以嘗試改善當前的最佳解。
OR-Tools的策略多種多樣，既包含簡單的經驗法則，又包含更為複雜的啟發式方法：（1）path-cheapest-arc，它迭代地擴充套件了 選擇最近城市作為下一城市的當前路線； （2）path-most-constricted-arc，它使用基於比較的選擇器迭代擴充套件了當前路線，該選擇器傾向於最受約束的“ arc”（兩城市間的路徑）； （3）global–cheapest– arc，它以迭代的方式連線距離最小的兩個先前斷開的城市； （4）local–cheapest–arc，將沒有後繼城市的第一個城市按順序迭代地連線到一個自由城市，從而使它們間的距離最小。 （5）first–unbound–min–value，它將沒有後繼者的第一個城市連線到第一個自由城市。 解決mTSP例項時，OR-Tools中提供的其他策略（更專門針對TSP）無法使用。
OR-Tools中使用的本地搜尋元啟發法如下：（1）Greedy Descent，僅當解的成本降低時才接受鄰居解，直到找到區域性最小值為止； （2）指導性本地搜尋，它使用懲罰性成本函式來逃避本地最小和高原； （3）模擬退火，它使用不斷降低的溫度來平衡搜尋過程中的勘探和利用； （4）禁忌搜尋，它使用限制機制來逃避區域性最小值； （5）目標禁忌搜尋，它在解的成本而不是解本身上使用禁忌搜尋。
在每種測試方案中，我們將自己與兩個基於OR-Tools的模型進行比較：OR @ 25和ORmin。 OR @ 25是一個集合，由給定解限制的第一種策略和元啟發式方法的所有25種可能組合組成，這樣最終選擇的解便是找到的25種（可能）不同解中的最佳解。 ORmin is the combination of a first strategy and a meta-heuristic that out of the 25 possible combinations had the best performance on the dataset considered. 根據定義，OR @ 25總是比ORmin更好，並且ORmin在不同實驗之間可能會發生變化。
5。1。2 神經網路基準
指標網路沒有以包含問題約束的方式對mTSP進行直接概括。 為獲得神經網路基準，我們透過在源城市和目標城市的兩個現有維度中引入新的銷售員維度，將Levy和Wolf（2017）Learning to Align the Source Code to the Compiled Object Code的工作推廣到多銷售人員設定。 先透過LSTM，然後在三維網格中級聯，以生成每個樣本的三維編碼（第四維是編碼中的通道數）。 我們將此張量透過三維CNN，以獲得最終的多層輸出，然後繼續使用與我們相同的pipeline（演算法1，然後是我們的自定義損失）。 使用Levy和Wolf（2017）中報告的相同超引數，並使用其笛卡爾座標對城市進行編碼。 對於此基準網路，位置編碼（Vaswani等人，2017）的表現勝過我們自己的銷售員編碼。
5。1。3 我們的網路
我們的網路在第二節中有描述。設定d_svd = 4，d_model = 256，d_ff = 1024和N = 7，損失內部的權重為λ= 0。5。 根據經驗設定Alg 1的迭代次數T =100。對於置換不變集合g，我們選擇Max Pooling，並設w（d）= A
exp（-C·d）+ B，其中A，B和C是d_model大小的學習向量。 每當pool from a group of cities （or the depot） over other cities時，我們都會使用加權池化層。 否則，當涉及銷售員時，我們將使用常規池化層。 為保持尺度不變，我們在應用SVD逼近前將距離矩陣除以其均值。 在關於mTSP測試基準的實驗中，我們使用波束搜尋。但對於mTSPLib，為提高效能和通用性，我們將網路作為OR-Tools pipeline的第一個策略進行測試。 為確保公平，由於網路使用波束搜尋作為最後的解碼，當與OR-Tools元啟發式相結合時，我們將pipeline的波束大小定義為波束搜尋所檢查的解和本地搜尋方法所檢查的解之和。我們發現，將10%的波束大小分配給波束搜尋，其餘的分配給本地搜尋效果很好，其中作為後續的最佳元啟發式是Guided Local Search。在嘗試使用mTSPLib時，此配置定義了我們的pipeline。
5。1。4 消融研究
為證明我們的方法是充分必要的，我們測試了新網路的三個組成部分的必要性： 1）表示不變損失representation invariant loss， 2）加權彙集層，和 3）留一池。我們訓練了三個模型（每個模型都缺少相應的一個子部分），並在 mTSPLib和 mTSP-test 上測試它們相對於我們完整模型的效能。
5。1。5 訓練
使用adam學習率方案在 mTSP-train 上訓練所有神經網路，引數 β1 = 0。9，β2 = 0。999 和= 1e 8；神經網路基線在 32 個樣本的小批次上訓練，每個樣本使用 0。001 的恆定學 習率，而我們的網路在 128 個樣本的小批次上訓練，使用 0。0001 的恆定學習率。當不使用城市的 SVD 近似時，當我們不使用城市的SVD近似值時，我們使用仿射變換c‘= 2c − 1歸一化資料集中的城市表示，以使它們的座標均勻分佈在-1和1之間。 不受城市（除倉庫外）的順序和遊覽方向（例如NN基線）的影響，我們隨機排列城市的順序。
5。1。6 結果
表1：mTSP測試的平均誤差，以所獲得的路徑長總和與最佳路徑長度之比減1來衡量。
表1顯示了我們在mTSP測試中的表現。 我們的方法優於NN基線和針對每種波束尺寸分別選擇的最佳OR-Tools方法。從數量上可以看出，表示不變損失顯著有助於整體成功。
（圖3：對mTSP檢驗中n = 10和m = 3的樣本，表示不變損失的定性比較。 每個圖都是一個鄰接矩陣，並且每一列組成一個完整解（m個鄰接矩陣）。
對一列進行排列對應於更改推銷員的順序，換位矩陣對應於反轉推銷員路線的方向。 從左到右：（a）由ILP求解器求解的最優解；（b）我們網路的輸出；（c）不同推銷員及其換位的最優解的平均值；（d）the output of our network without the representation invariant loss。
圖3顯示了在有無表示不變損失的情況下我們網路間的定性比較：具有自定義損失的網路正確學習了輸出最優解的有效表示，其中，行的換位對應於一個銷售員的換位，每個矩陣的換位對應於改變路線的方向（（a）和（b））。然而，當我們使用Naıve負對數似然損失時，網路似乎為每個推銷員預測了一條路線，這條路線是每個推銷員的最優路線和他們的換位的平均值（（c）和（d））；這可以解釋為，對推銷員進行換位和扭轉他們的路線可以維持解的最優性，因此，在足夠大的資料集和損失函式不足的情況下，網路會在最優解的所有可能表示的平均值構成的區域性最小值處卡住。
儘管可能有人爭辯說，當不使用空間加權或LeaveOne-Out池時，基於mTSP測試的實驗僅顯示了網路效能的小幅下降， 表2顯示了這些模型在mTSPLib上的效能要差得多。 使用空間加權和留一出池有助於網路的通用性，這兩種方法對在使用較大波束尺寸時在mTSPLib上具有競爭力至關重要。
表3中顯示了mTSPLib基準測試的原始結果，其中包含更大更多樣化的樣本。 對於較小的光束，我們的方法在大多時候在每個單獨實驗中都超過了任何一個OR-Tools方法所獲得的最佳效能。
圖4展示了我們對管道“最佳例項”與不同OR-Tools方法的“最佳例項”數量的比較，如果對於給定的光束大小，沒有其他方法能達到更好的效果，則該方法的例項稱為“最佳” 結果。 它表明，儘管隨著波束大小的增加，我們嚴格優於OR @ 25的例項的數量會減少（表3），但當僅考慮一種方法時，我們仍是最佳選擇。
圖5顯示了每種方法（我們的方法或OR-Tools方法）與針對該光束尺寸的方法所獲得的最佳解間的平均誤差。 對於較小的光束，我們的pipeline平均誤差略低，且隨著光束尺寸的增加，差異會變小，但與OR-Tools的其他方法相比，我們仍然是最佳選擇。
表4顯示了我們的pipeline與OR-Tools中的其他方法一樣有效。 這是因為大部分時間都花在了公共本地搜尋上，而不是最初解上。
最後，表5顯示了我們在Vinyals等提供的TSP基準上的效能。當我們使用mTSP訓練時。 儘管網路完成的任務（mTSP）比TSP難，但它適用於TSP，並不會因支援mTSP訓練中的mTSP樣本而忽視它。
6。 Discussion
我們為mTSP提出的解非常籠統：輸入編碼是通用的，輸出是解的直接編碼。 實際上，我們僅在Alg 1中直接編碼特定於問題的資訊。 根據我們的經驗，即使使用此演算法的一次迭代，網路也可以進行訓練，這類似於傳統的softmax。 不過，實際上需要更多迭代才能與OR-Tools的所有複雜啟發式方法競爭。
產生稀疏和過分引數化的輸出，而不是簡化為便宜的序列表示
，是我們區別於seq2seq方法的一點。序列生成方法是否能夠對輸出空間比單個排列組合更復雜的組合問題進行建模，還有待觀察。
未來工作：
關於mTSP的其他風格和泛化——minmax變體、VRP；時間約束mTSP很有挑戰性，因為這些約束需新增到各城市的編碼中。
