JSPRIT在帶時間窗的車輛路徑規劃問題(VRPTW)上的表現總結

• 2019 年 10 月 6 日
• 筆記

在之前的推文車輛路徑優化問題求解工具Jsprit的簡單介紹與入門中，相信大家已經對Jsprit這款開源的車輛路徑規劃問題求解器有了基礎的了解，那麼Jsprit在具體的車輛路徑規劃問題上表現到底如何呢？

下面我們將以帶時間窗的車輛路徑規劃問題(Vehicle Routing Problem with Time Windows, 簡稱VRPTW)為例，詳細測試Jsprit在該問題上的表現。

1.VRPTW及輸入樣例介紹

什麼是VRPTW？

相信聰明的你看到VPRTW一定會和VRP模型聯繫起來：

車輛路徑規劃問題（VRP）最早是由Dantzig和Ramser於1959年首次提出，它是指一定數量的客戶，各自有不同數量的貨物需求。配送中心則負責向客戶提供貨物，分送貨物由一個車隊負責，通過組織適當的行車路線，目標是使得客戶的需求得到滿足，並能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的。

而VRPTW在容量約束的前提下，加入了時間窗的約束。對於每一個需求點，設定開始時間和結束時間，要求車輛在時間窗內開始服務顧客。

需求點的時窗限制可以分為兩種，一種是硬時窗（Hard Time Window），硬時窗要求車輛必須要在時窗內開始服務顧客，早到必須等待，而遲到則拒收；另一種是軟時窗（Soft Time Window），不一定要在時窗內開始服務顧客，但是在時窗之外開始服務必須要懲罰，以懲罰替代等待與拒收是軟時窗與硬時窗最大的不同。

測試樣例：

下面將給出本次測試樣例。在我們的測試樣例中，設定的優化的目標為路程最短，時窗限制為硬時窗。

文件最上方給出了車輛的數量和容量。

下方表格中的XCORD，YCORD為顧客的位置，Demand為顧客需求，Ready time和Due time為時間窗的開始時間和結束時間，Service time為服務時間。

下面我們介紹用於測試的幾種樣例形式：

• C-type：顧客成集群分布
• R-type ：顧客均勻分布
• RC-type ：上述兩種的混合

為了測試的準確性，我們選用Solomon數據集和Homberger數據集。其顧客的規模從25一直到到1000。

通過測試不同顧客數量的樣例，可以評測Jsprit在不同數據規模下對於帶時間窗車輛路徑規劃問題的表現。

2.測試結果

測試的電腦配置如下：Intel core i5 8300H,關閉睿頻，頻率保持為2.2Ghz，記憶體16GB。

我們利用Jsprit求解了Solomon和Gehring and Homberger的全部樣例，共497個，顧客規模覆蓋了25，100，400，1000幾種情況，這裡選取了其中部分結果進行展示：

其中縱軸代表了20次求解的平均成本，橫軸則是不同的測試樣例。

顧客數為25時：

花費指的是Jsprit的求解結果；最好情況是指已知的（從文獻中或者某些網站上獲取）最好的結果。

在所有顧客數為25的測試樣例中，Jsprit的偏差最大值為6.34%，最小為0.23%，偏差平均值為1.84%。

顧客數為100時：

在所有顧客數為100的測試樣例中，Jsprit的偏差最大值為18.77%，最小值3.78%，偏差平均值為8.01%。

顧客數為400時：

在所有顧客數為400的測試樣例中，Jsprit的偏差最大值27.15%，最小值為16.35%，偏差平均值為20.73%。

顧客數為1000時：

在所有顧客數為1000的測試樣例中，Jsprit的最大偏差為19.86%，最小偏差為4.58%，偏差平均值為12.94%。

下面我們來分析下Jsprit在時間上的表現：

在圖中，時間單位為秒，縱軸為求解20次的平均時間，橫軸為求解的問題的顧客規模數。

我們可以看到當顧客數逐漸呈線性增加時，時間也幾乎呈線性增加，而不是精確演算法的指數級別增加。這就是啟發式演算法的優點所在，以精度換時間。

下面我們來看看Jsprit的收斂情況：

在圖中縱軸為求解20次的平均成本，橫軸為不同的迭代次數。

我們分別在數據規模為25，100，200的樣例中抽取了幾個樣例作為測試樣本，可以看到大部分的樣例在迭代次數還不到1000的情況下已經開始收斂，在之後的迭代過程中得到解的改進也很小。這種只能通過達到固定迭代次數的方式來終止迭代的設置導致了一部分的算力的浪費。

總結

可以看到，Jsprit與其在官網上的介紹一致，求解非常方便，對於各種各樣的問題都能適用，值得一提的是，求解的可視化也做的很不錯。

但Jsprit也存在所求解的品質差的缺點。

欲下載求解的程式碼，測試樣例和測試結果，請移步留言區。

-The End-