JSPRIT在帶時(shí)間窗的車輛路徑規(guī)劃問(wèn)題(VRPTW)上的表現(xiàn)總結(jié)

在之前的推文車輛路徑優(yōu)化問(wèn)題求解工具Jsprit的簡(jiǎn)單介紹與入門中，相信大家已經(jīng)對(duì)Jsprit這款開源的車輛路徑規(guī)劃問(wèn)題求解器有了基礎(chǔ)的了解，那么Jsprit在具體的車輛路徑規(guī)劃問(wèn)題上表現(xiàn)到底如何呢？

下面我們將以帶時(shí)間窗的車輛路徑規(guī)劃問(wèn)題(Vehicle Routing Problem with Time Windows, 簡(jiǎn)稱VRPTW)為例，詳細(xì)測(cè)試Jsprit在該問(wèn)題上的表現(xiàn)。

1.VRPTW及輸入樣例介紹

什么是VRPTW？

相信聰明的你看到VPRTW一定會(huì)和VRP模型聯(lián)系起來(lái)：

車輛路徑規(guī)劃問(wèn)題（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求。配送中心則負(fù)責(zé)向客戶提供貨物，分送貨物由一個(gè)車隊(duì)負(fù)責(zé)，通過(guò)組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，達(dá)到諸如路程最短、成本最小、耗費(fèi)時(shí)間最少等目的。

而VRPTW在容量約束的前提下，加入了時(shí)間窗的約束。對(duì)于每一個(gè)需求點(diǎn)，設(shè)定開始時(shí)間和結(jié)束時(shí)間，要求車輛在時(shí)間窗內(nèi)開始服務(wù)顧客。

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

測(cè)試樣例：

下面將給出本次測(cè)試樣例。在我們的測(cè)試樣例中，設(shè)定的優(yōu)化的目標(biāo)為路程最短，時(shí)窗限制為硬時(shí)窗。

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

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

下面我們介紹用于測(cè)試的幾種樣例形式：

• C-type：顧客成集群分布

• R-type?：顧客均勻分布

• RC-type ：上述兩種的混合
  

為了測(cè)試的準(zhǔn)確性，我們選用Solomon數(shù)據(jù)集和Homberger數(shù)據(jù)集。其顧客的規(guī)模從25一直到到1000。

通過(guò)測(cè)試不同顧客數(shù)量的樣例，可以評(píng)測(cè)Jsprit在不同數(shù)據(jù)規(guī)模下對(duì)于帶時(shí)間窗車輛路徑規(guī)劃問(wèn)題的表現(xiàn)。

2.測(cè)試結(jié)果

測(cè)試的電腦配置如下：Intel core i5 8300H,關(guān)閉睿頻，頻率保持為2.2Ghz，內(nèi)存16GB。

我們利用Jsprit求解了Solomon和Gehring and Homberger的全部樣例，共497個(gè)，顧客規(guī)模覆蓋了25，100，400，1000幾種情況，這里選取了其中部分結(jié)果進(jìn)行展示：

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

顧客數(shù)為25時(shí)：

花費(fèi)指的是Jsprit的求解結(jié)果；最好情況是指已知的（從文獻(xiàn)中或者某些網(wǎng)站上獲取）最好的結(jié)果。

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

顧客數(shù)為100時(shí)：

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

顧客數(shù)為400時(shí)：

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

顧客數(shù)為1000時(shí)：

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

下面我們來(lái)分析下Jsprit在時(shí)間上的表現(xiàn)：

在圖中，時(shí)間單位為秒，縱軸為求解20次的平均時(shí)間，橫軸為求解的問(wèn)題的顧客規(guī)模數(shù)。

我們可以看到當(dāng)顧客數(shù)逐漸呈線性增加時(shí)，時(shí)間也幾乎呈線性增加，而不是精確算法的指數(shù)級(jí)別增加。這就是啟發(fā)式算法的優(yōu)點(diǎn)所在，以精度換時(shí)間。

下面我們來(lái)看看Jsprit的收斂情況：

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

我們分別在數(shù)據(jù)規(guī)模為25，100，200的樣例中抽取了幾個(gè)樣例作為測(cè)試樣本，可以看到大部分的樣例在迭代次數(shù)還不到1000的情況下已經(jīng)開始收斂，在之后的迭代過(guò)程中得到解的改進(jìn)也很小。這種只能通過(guò)達(dá)到固定迭代次數(shù)的方式來(lái)終止迭代的設(shè)置導(dǎo)致了一部分的算力的浪費(fèi)。

總結(jié)

可以看到，Jsprit與其在官網(wǎng)上的介紹一致，求解非常方便，對(duì)于各種各樣的問(wèn)題都能適用，值得一提的是，求解的可視化也做的很不錯(cuò)。

但Jsprit也存在所求解的質(zhì)量差的缺點(diǎn)。

欲下載求解的代碼，測(cè)試樣例和測(cè)試結(jié)果，請(qǐng)移步留言區(qū)。

-The End-

文案 ：李博驍

編輯 ：李欣羽

指導(dǎo)老師 / 秦虎 華中科技大學(xué)管理學(xué)院 [email protected]

如對(duì)代碼有疑問(wèn)，可聯(lián)系小編，無(wú)償提供服務(wù)。

李博驍（華中科技大學(xué)管理學(xué)院、[email protected])