基于多樣化方案池的即時(shí)配送訂單實(shí)時(shí)響應(yīng)方法

王 征，李婷玉，侯鑫垚

1 大連海事大學(xué) 航運(yùn)經(jīng)濟(jì)與管理學(xué)院，遼寧 大連 116026 2 大連理工大學(xué) 軟件學(xué)院，遼寧 大連 116620

引言

在現(xiàn)代電子商務(wù)環(huán)境下，一系列生鮮果蔬、零食小吃和鮮花禮物等顧客需求緊急且應(yīng)快速完成配送的商品已成為大眾網(wǎng)購(gòu)的對(duì)象。該類(lèi)緊急商品的訂單需求在近年來(lái)呈快速增長(zhǎng)趨勢(shì)，季度訂單超4億[1]，市場(chǎng)規(guī)模保持了年逾40%的高速增長(zhǎng)[2]。

然而，在該類(lèi)緊急需求訂單快速擴(kuò)張的背后，卻存在著物流能力約束的致命問(wèn)題。面對(duì)顧客隨時(shí)提出的訂單要求，配送公司通常在一兩個(gè)小時(shí)內(nèi)就必須完成貨物的取送服務(wù)；目前幾乎所有電商面對(duì)顧客訂單往往都采取“來(lái)者不拒、一律接單”的態(tài)度；在配送公司既定的物流能力下，一旦顧客訂單超出物流能力，延遲送貨的情況就在所難免，進(jìn)而容易導(dǎo)致顧客滿意度降低、甚至大面積取消訂單的連鎖反應(yīng)。以上問(wèn)題是相關(guān)電商及其配送公司都難以逾越且影響其生死存亡的關(guān)鍵問(wèn)題，若處理不當(dāng)，將會(huì)嚴(yán)重打擊顧客信心，制約現(xiàn)代電子商務(wù)的健康持續(xù)發(fā)展[3]。

在顧客下單的瞬間，系統(tǒng)基于當(dāng)前的物流能力實(shí)時(shí)判斷該單是否能夠按時(shí)送貨，并對(duì)顧客給予預(yù)計(jì)送達(dá)時(shí)間的實(shí)時(shí)反饋，讓顧客心中有數(shù)(若無(wú)法按時(shí)送貨，則顧客可選擇取消訂單)，這成為解決這一問(wèn)題的有效途徑。然而，由于該問(wèn)題所具有的復(fù)雜性，如何能夠又快又準(zhǔn)的對(duì)物流能力做出實(shí)時(shí)評(píng)估具有極高的難度。

(1)訂單的實(shí)時(shí)響應(yīng)，不能通過(guò)簡(jiǎn)單地將訂單插入到某條車(chē)輛路線中來(lái)實(shí)現(xiàn)。一個(gè)新訂單的插入，很有可能會(huì)導(dǎo)致路線上其他若干已有訂單的送貨時(shí)間超出要求，但由于系統(tǒng)已經(jīng)給出了對(duì)已有訂單按時(shí)送貨的承諾，因此必須對(duì)受影響的已有訂單進(jìn)行相應(yīng)的路線調(diào)整，而這一調(diào)整通常又會(huì)引發(fā)其他車(chē)輛已有訂單路線調(diào)整的連鎖反應(yīng)，從而導(dǎo)致車(chē)輛路線的大范圍修改，最終往往會(huì)得到與原先截然不同的配送方案。

(2)訂單響應(yīng)具有實(shí)時(shí)性要求，必須在顧客下單的瞬間(通常1秒內(nèi))就給顧客一個(gè)實(shí)時(shí)的反饋。無(wú)論是該領(lǐng)域的精確算法[4]，還是大量的元啟發(fā)式算法[5-7]和迭代搜索算法[8]，都致力于在大面積范圍內(nèi)搜索全局最優(yōu)解，通常需要消耗很長(zhǎng)的求解時(shí)間，因此對(duì)此問(wèn)題并不適用。

(3)訂單響應(yīng)不僅要快，而且要準(zhǔn)。若給顧客反饋的結(jié)果不準(zhǔn)確，則會(huì)產(chǎn)生極為負(fù)面的后果，即本來(lái)能按時(shí)服務(wù)卻反饋給顧客“不能”，會(huì)損失掉該訂單的利潤(rùn)；本來(lái)不能按時(shí)服務(wù)卻反饋給顧客“能”，顧客會(huì)大失所望；本來(lái)能更早送貨卻反饋給顧客一個(gè)較遲的時(shí)間，顧客很可能會(huì)取消訂單。

為此，本研究根據(jù)該問(wèn)題的特點(diǎn)，提出基于多樣化方案池的訂單實(shí)時(shí)響應(yīng)方法，并通過(guò)大規(guī)模實(shí)驗(yàn)，驗(yàn)證方法的科學(xué)性和有效性。

1相關(guān)研究評(píng)述

即時(shí)配送訂單實(shí)時(shí)響應(yīng)問(wèn)題屬于一類(lèi)帶時(shí)間窗的車(chē)輛路徑問(wèn)題[9]，同時(shí)兼有動(dòng)態(tài)車(chē)輛路徑問(wèn)題(dynamic vehicle routing problem, DVRP)、取送一體化車(chē)輛路徑問(wèn)題(vehicle routing problem with pickup and delivery, VRPPD)和多回程車(chē)輛路徑問(wèn)題(multi-trip vehicle routing problem, MTVRP)的特點(diǎn)。

在DVRP的研究中，問(wèn)題的部分信息在車(chē)輛執(zhí)行配送任務(wù)的過(guò)程中會(huì)逐漸被揭露或發(fā)生改變，從而車(chē)輛的任務(wù)安排和配送路線會(huì)因此而不斷調(diào)整[10]。貪婪式的重調(diào)度方法是學(xué)者們通常采用的一種求解思路，即問(wèn)題信息一旦改變，則根據(jù)當(dāng)前已知的問(wèn)題狀態(tài)重新快速生成新的配送方案。動(dòng)態(tài)規(guī)劃[11]、列生成方法[12]、蟻群算法[13]、禁忌搜索[14]、適應(yīng)性記憶[15]、多計(jì)劃方法[16]、遺傳算法[17-18]、變鄰域搜索算法[19]是學(xué)者們采用的較多的一些方法。這些方法或者每隔一段時(shí)間就調(diào)度一次，或者在問(wèn)題信息不變時(shí)不斷優(yōu)化已有方案，一旦問(wèn)題信息發(fā)生變化就立即重調(diào)度[20]。另一類(lèi)DVRP的研究假設(shè)問(wèn)題動(dòng)態(tài)信息的概率分布已知，通過(guò)建立隨機(jī)規(guī)劃模型或采用Sampling的方法加以解決。該類(lèi)問(wèn)題的主要研究成果包括馬爾可夫決策過(guò)程[21]、近似動(dòng)態(tài)規(guī)劃(approximate dynamic programming, ADP)[22]和線性規(guī)劃方法[23]等。然而本研究問(wèn)題與DVRP有著本質(zhì)的區(qū)別，DVRP通常以必須接受顧客訂單為前提，致力于找出一種物流成本最小化的配送方案，且新顧客的插入很可能會(huì)導(dǎo)致已有顧客時(shí)間窗的偏離。本研究問(wèn)題以不能違反已有訂單的時(shí)間窗約束、但可以違反新訂單時(shí)間窗約束為條件，計(jì)算出一種使違反新訂單時(shí)間窗約束最小化且物流成本最小化的配送方案。

VRPPD是指顧客同時(shí)有送貨和取貨需求、每輛車(chē)需同時(shí)完成取貨和送貨服務(wù)的路徑規(guī)劃問(wèn)題[24]。多數(shù)已有研究通常假設(shè)要送的貨物都在車(chē)輛出發(fā)地裝載，從顧客處所取的貨物都送回至車(chē)輛終止地，從而車(chē)輛在途中既有送貨又有取貨的服務(wù)[25-26]。還有研究考慮取貨點(diǎn)與送貨點(diǎn)一對(duì)一關(guān)系的VRPPD問(wèn)題，即每個(gè)訂單所要求的貨物都必須先從某個(gè)地點(diǎn)取貨然后才能送貨[27-28]。本研究問(wèn)題與后一類(lèi)VRPPD問(wèn)題相似，但與其不同的是，本研究的即時(shí)配送問(wèn)題中，取貨點(diǎn)與送貨點(diǎn)具有復(fù)雜的一對(duì)多的關(guān)系。該種關(guān)系導(dǎo)致訂單與車(chē)輛間具有更多樣的任務(wù)分配組合，并衍生出每輛車(chē)應(yīng)何時(shí)出發(fā)、出發(fā)路線又應(yīng)如何安排等一系列問(wèn)題。相對(duì)于一對(duì)一關(guān)系中僅需要一輛車(chē)從某個(gè)取貨點(diǎn)到其送貨點(diǎn)行駛一次的安排而言，一對(duì)多關(guān)系中的多車(chē)協(xié)作配送方案顯然具有更高的處理難度。

在MTVRP的研究中，由于車(chē)輛容量、顧客特殊要求等原因，為完成顧客訂單，車(chē)輛需多次返回倉(cāng)庫(kù)取貨。FLEISCHMANN[29]首次針對(duì)該問(wèn)題提出先構(gòu)造路徑、再安排車(chē)輛任務(wù)的兩階段求解方法，其他學(xué)者針對(duì)這一問(wèn)題相繼進(jìn)行研究，代表性成果包括禁忌搜索[30]、適應(yīng)性記憶[31]、遺傳算法[32]、文化基因[33]、大鄰域搜索[34]等啟發(fā)式算法，以及分支定界[35]、列剪枝[36]等精確算法。然而，這些研究均聚焦于靜態(tài)MTVRP，且求解耗時(shí)相對(duì)較長(zhǎng)，不能滿足即時(shí)配送訂單的實(shí)時(shí)響應(yīng)要求。

綜上，即時(shí)配送訂單的實(shí)時(shí)響應(yīng)問(wèn)題是現(xiàn)代電子商務(wù)環(huán)境下的新問(wèn)題，已有研究成果對(duì)該問(wèn)題并不適用。該問(wèn)題在求解上的快和準(zhǔn)的雙重要求以及特殊的問(wèn)題約束和目標(biāo)，使問(wèn)題的求解極具挑戰(zhàn)性，已有相關(guān)研究在求解時(shí)間、問(wèn)題約束和目標(biāo)方面無(wú)法滿足要求。因此，本研究根據(jù)問(wèn)題特點(diǎn)，通過(guò)緩存多樣化的路徑方案，滿足求解速度和解的質(zhì)量的雙重要求，開(kāi)發(fā)出一種新穎的、基于多樣化方案池的在線求解算法。

2問(wèn)題及其重調(diào)度模型

即時(shí)配送訂單的實(shí)時(shí)響應(yīng)問(wèn)題可描述為：某商戶擁有多個(gè)同型車(chē)輛，為在線訂單提供即時(shí)配送服務(wù)；當(dāng)新訂單實(shí)時(shí)下達(dá)后，商戶需根據(jù)當(dāng)時(shí)的車(chē)輛狀態(tài)和訂單要求，在保證已有訂單按時(shí)送貨的承諾下，向新訂單的顧客給予能否按時(shí)送貨的反饋；若不能按時(shí)送貨，則向顧客反饋可行的送貨時(shí)間，待顧客確認(rèn)或取消訂單。由于商戶每天在確定的時(shí)段內(nèi)(如9:00～21:00)接收顧客訂單并進(jìn)行配送活動(dòng)，因此，顧客訂單時(shí)間窗只能在該配送時(shí)段內(nèi)。

由于即時(shí)配送問(wèn)題所送的貨物通常具有保鮮要求，其在途時(shí)間不宜過(guò)長(zhǎng)，否則新鮮度將大打折扣。車(chē)輛如果針對(duì)其配送任務(wù)一次性裝載所有貨物，在途時(shí)間很可能超出最長(zhǎng)時(shí)限的要求。因此，為滿足最長(zhǎng)在途時(shí)限的要求，車(chē)輛每次應(yīng)從商戶取走部分訂單的貨物，將其送完后再回商戶取貨。如此下來(lái)，車(chē)輛應(yīng)多次返回商戶取貨，并不斷地往返于商戶與顧客之間，以便在最長(zhǎng)在途時(shí)限的要求下，完成所有訂單的取送任務(wù)。此外，由于車(chē)輛到達(dá)顧客處后僅需將貨物交予顧客，所以假設(shè)每個(gè)訂單點(diǎn)的服務(wù)時(shí)間為0。

需要說(shuō)明的是，車(chē)輛每次從商戶取得部分貨物并離開(kāi)商戶進(jìn)行配送后，車(chē)輛路線不會(huì)更改，車(chē)輛在本次旅途中即將服務(wù)的顧客應(yīng)從未服務(wù)的訂單中刪除，同時(shí)該輛車(chē)的可用時(shí)間也應(yīng)被設(shè)置為其結(jié)束本次配送、返回商戶的時(shí)間。那么，新訂單實(shí)時(shí)響應(yīng)問(wèn)題的模型應(yīng)以所有車(chē)輛的可用時(shí)間要求、所有未服務(wù)訂單的配送要求和車(chē)輛在途送貨時(shí)限等為約束，以最小化物流配送成本和新訂單的時(shí)間窗偏離懲罰為目標(biāo)建立。

表1給出該問(wèn)題涉及的一些參數(shù)和變量。

當(dāng)新訂單進(jìn)入時(shí)，該訂單的實(shí)時(shí)響應(yīng)問(wèn)題可基于上述參數(shù)和變量建模，即

(1)

(2)

(3)

(4)

(5)

xi,j,k(Ti+ti,j-Tj)≤0?i,j∈P,k∈K

(6)

(7)

(8)

(9)

(10)

表1參數(shù)和變量Table 1Parameters and Variables

由上述模型可知，即使對(duì)于一個(gè)含有幾十個(gè)訂單和幾輛車(chē)的問(wèn)題而言，模型的變量和約束數(shù)量也會(huì)十分龐大，精確算法根本無(wú)法實(shí)時(shí)給出最優(yōu)方案，而建立啟發(fā)式算法是解決該問(wèn)題的有效途徑。為此，本研究將建立該問(wèn)題的啟發(fā)式求解方法。

3基于多樣化方案池的實(shí)時(shí)響應(yīng)方法

即時(shí)配送訂單的實(shí)時(shí)響應(yīng)問(wèn)題屬于一類(lèi)動(dòng)態(tài)的車(chē)輛路徑問(wèn)題，該類(lèi)問(wèn)題通常采用經(jīng)典的事件驅(qū)動(dòng)型處理方式[37]，即在特定事件發(fā)生時(shí)系統(tǒng)應(yīng)立即響應(yīng)或改變狀態(tài)。新訂單的產(chǎn)生、車(chē)輛的出發(fā)和返回是導(dǎo)致問(wèn)題狀態(tài)改變的3類(lèi)事件，當(dāng)新訂單產(chǎn)生時(shí)，系統(tǒng)應(yīng)立即向顧客反饋能否按時(shí)送貨的信息；當(dāng)車(chē)輛出發(fā)時(shí)，由于車(chē)輛每次出發(fā)的路線不會(huì)改變，應(yīng)將車(chē)輛此次配送所服務(wù)的訂單從未服務(wù)訂單中刪除，同時(shí)設(shè)置車(chē)輛的可用時(shí)間為其結(jié)束本次配送、返回商戶的時(shí)間；當(dāng)車(chē)輛返回時(shí)，應(yīng)立即為車(chē)輛確定下一次配送任務(wù)和出發(fā)時(shí)間，本研究基于當(dāng)前最優(yōu)的候選方案而確定。本節(jié)給出新訂單產(chǎn)生時(shí)的實(shí)時(shí)響應(yīng)方法。

即時(shí)配送訂單的實(shí)時(shí)響應(yīng)問(wèn)題具有實(shí)時(shí)和準(zhǔn)確兩種求解要求，問(wèn)題的精確算法雖然可以準(zhǔn)確給出最優(yōu)方案，但無(wú)法滿足實(shí)時(shí)要求；而與精確算法相比，盡管目前流行的元啟發(fā)式算法[5-7]和迭代啟發(fā)式算法[8]使用了更少的求解時(shí)間，但與實(shí)時(shí)要求仍有相當(dāng)大的差距，需進(jìn)行較大改進(jìn)?，F(xiàn)代啟發(fā)式算法的精髓在于，通過(guò)禁忌表[38]、毀壞重建算子[34]、模擬退火思想[39]、參數(shù)的適應(yīng)性調(diào)整策略[40]和多樣化隨機(jī)技術(shù)[41-42]等各種技術(shù)，不斷在當(dāng)前解的鄰域范圍內(nèi)搜索更好的解，這些技術(shù)往往需要一定的收斂時(shí)間才能找到優(yōu)質(zhì)解。本研究采用多樣化方案池的策略，即在新訂單到來(lái)之前，事先在池中緩存各種各樣的優(yōu)質(zhì)方案，一旦新訂單到來(lái)，利用池中的緩存方案快速生成最佳的應(yīng)對(duì)方案，從而大大縮短計(jì)算時(shí)間，既滿足實(shí)時(shí)響應(yīng)的要求，又能保證解的優(yōu)化性。圖1給出目前啟發(fā)式算法的主流思想和本研究的多樣化方案池策略示意圖。

(a)目前啟發(fā)式算法的主流思想

(b)本研究的多樣化方案池策略

圖2給出即時(shí)配送訂單實(shí)時(shí)響應(yīng)問(wèn)題的一個(gè)小例子，其中包含顧客、商戶點(diǎn)間的行駛時(shí)間和顧客的時(shí)間窗要求。下面利用這個(gè)例子對(duì)多樣化方案池策略進(jìn)一步給出說(shuō)明。表2依據(jù)圖2所示的數(shù)據(jù)要求，給出針對(duì)0時(shí)刻的初始方案1、方案2、方案3以及在訂單D出現(xiàn)后的調(diào)整方案4、方案5、方案6。該例在0時(shí)刻有3個(gè)訂單，其最優(yōu)配送方案為表2中的方案1。相對(duì)于表2中的方案2和方案3，方案1具有更少的行駛成本。因此，若按照目前啟發(fā)式算法的主流思想，系統(tǒng)僅保留方案1，兩輛車(chē)的最遲出發(fā)時(shí)刻分別為2.5和5.5；但根據(jù)本研究提出的多樣化方案池策略，這3個(gè)方案都被保存在方案池中，以便后續(xù)的快速優(yōu)化。在2時(shí)刻，訂單D出現(xiàn)，此時(shí)兩輛車(chē)仍未出發(fā)，而只要將訂單D插入到方案3的第二條路線上即可快速得到新問(wèn)題的最優(yōu)解(表2的方案6)，兩輛車(chē)按照新問(wèn)題的最優(yōu)解執(zhí)行即可；而前兩種方案無(wú)論如何調(diào)整，都很難一步到位，即若每次迭代僅修改一個(gè)顧客位置，則方案4和方案5都最少需要5次鄰域變換才能達(dá)到方案6的最優(yōu)解。

(a)0時(shí)刻已知訂單A、B、C(b)2時(shí)刻新增訂單D

注：此例中有兩輛車(chē)；P0為商戶；A～D為訂單；方括號(hào)中數(shù)字為訂單時(shí)間窗；點(diǎn)間連線上的數(shù)字為行駛時(shí)間。

圖2多樣化方案池策略的說(shuō)明示例Figure 2An Example for the Strategies for a Pool of Various Solutions

注：方案4、方案5、方案6分別為與方案1、方案2、方案3對(duì)應(yīng)的調(diào)整方案，0代表P0，即商戶。

當(dāng)訂單數(shù)很多時(shí)，啟發(fā)式算法采用的迭代式鄰域搜索相當(dāng)耗時(shí)，且不見(jiàn)得每次迭代都能朝著最優(yōu)解的方向遞進(jìn)一步，通常需要在嘗試多個(gè)搜索方向之后才能確定哪個(gè)搜索途徑最有希望。與之相比，本研究通過(guò)在系統(tǒng)閑置期間(本例中的0～2的時(shí)間內(nèi))搜索并緩存多樣化的優(yōu)秀方案，為實(shí)現(xiàn)從緩存方案到最優(yōu)方案“一步到位”的實(shí)時(shí)響應(yīng)奠定了基礎(chǔ)，在求解速度和質(zhì)量上都明顯優(yōu)于單一解的鄰域搜索過(guò)程。應(yīng)該看到，本例即使僅緩存了方案1和方案2，也比只存儲(chǔ)當(dāng)前運(yùn)行方案1要好。

由該例可知，基于多樣化方案池的實(shí)時(shí)響應(yīng)方法有3個(gè)關(guān)鍵問(wèn)題：①如何生成候選方案(即表2中的方案1、方案2、方案3)；②如何在候選方案中選擇緩存方案(若方案池的容量有限，僅能容納兩個(gè)方案，那應(yīng)選擇哪兩個(gè)方案)；③在新訂單來(lái)臨時(shí)，如何基于緩存方案生成最優(yōu)的配送方案。下面將對(duì)這3個(gè)問(wèn)題依次闡述。

車(chē)輛在按計(jì)劃執(zhí)行的過(guò)程中，沒(méi)有新訂單進(jìn)入時(shí)，系統(tǒng)將使用3.1中的候選方案生成方法和3.2中的緩存方案選擇策略，不斷優(yōu)化方案池中的候選方案；一旦有新訂單進(jìn)入，算法立即停止方案池的更新，并利用3.3中的方法對(duì)顧客進(jìn)行實(shí)時(shí)的響應(yīng)。

需要說(shuō)明的是，方案池中的候選方案所面向的訂單是所有未服務(wù)的訂單，但不包括在途車(chē)輛即將服務(wù)的訂單；一旦車(chē)輛從商戶出發(fā)，即將該車(chē)輛服務(wù)的訂單從未服務(wù)的訂單集合中刪除，該輛車(chē)的可用時(shí)間設(shè)置為其返回商戶的時(shí)間，同時(shí)，系統(tǒng)再次面向未服務(wù)的訂單集合生成并優(yōu)化方案池中的候選方案。

3.1候選方案生成方法

候選方案的整體質(zhì)量決定方案池中緩存方案的優(yōu)劣，也決定即時(shí)配送訂單實(shí)時(shí)響應(yīng)方案的好壞，因此候選方案生成工作是本研究實(shí)時(shí)響應(yīng)方法的基礎(chǔ)。盡管這一工作在系統(tǒng)閑置期間完成，但現(xiàn)實(shí)中很多商戶在訂單高峰期僅有平均幾分鐘的閑置時(shí)間，如何抓住有限的系統(tǒng)閑置時(shí)間、快速有效地生成高質(zhì)量的候選方案是首先要解決的關(guān)鍵問(wèn)題。

啟發(fā)式算法依然是生成候選方案的有效途徑。較早的啟發(fā)式算法包括遺傳算法[17-18,32]、蟻群算法[13]、禁忌搜索[14,38]、模擬退火[39]和神經(jīng)網(wǎng)絡(luò)[43]等，近年來(lái)該領(lǐng)域啟發(fā)式算法的研究已推進(jìn)到迭代鄰域搜索[8]、大鄰域搜索[34]、適應(yīng)性迭代搜索[44]以及多方法的混合應(yīng)用[8,45]。因?yàn)榇筻徲蛩阉骶哂锌焖偈諗康奶匦约昂軓?qiáng)的跳離局部最優(yōu)的能力而被眾多學(xué)者采納，該算法針對(duì)很多帶時(shí)間窗車(chē)輛路徑問(wèn)題的標(biāo)準(zhǔn)算例都超越其他算法，而得到當(dāng)前最優(yōu)解[46]。因此，本研究根據(jù)問(wèn)題特點(diǎn)建立候選方案生成的適應(yīng)性大領(lǐng)域搜索(adaptive large neighborhood search, ALNS)算法，利用該算法對(duì)問(wèn)題的初始解進(jìn)行迭代優(yōu)化，而問(wèn)題的初始解采用隨機(jī)最優(yōu)插入(randomized best insertion, RBI)[42]方法得到。

在候選方案的生成中，路線的摧毀、重建以及算子的選擇策略是算法的主要內(nèi)容。

(1)路線的摧毀算法

根據(jù)問(wèn)題特點(diǎn)，本研究給出改進(jìn)的隨機(jī)刪除、Shaw刪除和最壞刪除[46]3種算子，它們都是刪除一定比例的訂單即停止，本研究采用的比例為20%。隨機(jī)刪除算子隨機(jī)找一個(gè)訂單刪除，一旦刪除后有兩個(gè)相同的商戶點(diǎn)相鄰，就刪除其中任一個(gè)(后兩個(gè)刪除操作也包含此過(guò)程)。Shaw刪除算子根據(jù)訂單的相關(guān)性刪除，先隨機(jī)選擇一個(gè)訂單，然后刪除與其相關(guān)性最高的訂單，再在已刪除的訂單中隨機(jī)選擇一個(gè)，刪除與這個(gè)訂單相關(guān)性最高的訂單，……，直至刪除足夠的訂單。本研究將i訂單與j訂單的相關(guān)性Si,j定義為

(11)

最壞刪除算子則先計(jì)算每一訂單刪除之后成本差值，然后根據(jù)成本差值，使用輪盤(pán)賭方法隨機(jī)選擇訂單，成本差值越大的越容易被選擇。

(2)路線的重建算法

根據(jù)問(wèn)題特點(diǎn)，本研究給出貪婪和悔恨[46]兩種算子。貪婪算子將訂單依次插入到成本最小的位置上，如果是已知顧客，則插入位置必須符合顧客時(shí)間窗；如果是新訂單，則可違反時(shí)間窗約束(兩種算子都包含這一檢查過(guò)程)?；诤匏阕邮紫扔?jì)算每個(gè)訂單的最優(yōu)插入位置和次優(yōu)插入位置的成本差值，然后將差值最大的訂單插入到其最優(yōu)位置上。這兩種插入都需要將車(chē)輛的出發(fā)時(shí)間推遲至其可用時(shí)間之后，同時(shí)檢查車(chē)輛容量約束，如果不滿足，則通過(guò)在其前后位置插入商戶來(lái)滿足車(chē)輛容量約束。

(3)算子的適應(yīng)性選擇策略

算子的適應(yīng)性選擇策略是適應(yīng)性大鄰域搜索算法的基本組成部分，它將在算法執(zhí)行的不同階段動(dòng)態(tài)選擇有效的算子。由于算法迭代到不同的階段，路線的摧毀算子和重建算子對(duì)解的優(yōu)化效果不同。因此，本研究根據(jù)前N次迭代中(本研究設(shè)N=50)算子更新最優(yōu)解的次數(shù)對(duì)每個(gè)算子予以評(píng)價(jià)，并基于算子的評(píng)價(jià)值，利用輪盤(pán)賭方法在每次迭代時(shí)隨機(jī)選擇一個(gè)算子進(jìn)行摧毀和重建操作。

3.2緩存方案選擇策略

考慮到訂單響應(yīng)的實(shí)時(shí)要求，方案池中不能無(wú)限制地存儲(chǔ)大量的候選方案。在不同配置的計(jì)算機(jī)上，訂單響應(yīng)程序的執(zhí)行時(shí)間不同，為實(shí)現(xiàn)訂單實(shí)時(shí)響應(yīng)目標(biāo)(1秒內(nèi)響應(yīng))，可通過(guò)實(shí)驗(yàn)確定不同計(jì)算機(jī)的方案池中最大可存儲(chǔ)的方案?jìng)€(gè)數(shù)(本研究的實(shí)驗(yàn)結(jié)果為330)。

緩存哪些方案是需要解決的關(guān)鍵問(wèn)題。本研究希望在池中盡可能保留多樣化程度較高的優(yōu)質(zhì)方案，而不是保留過(guò)于相似的劣質(zhì)方案，以便在不同的新訂單進(jìn)入時(shí)都能找到一種有效方案應(yīng)對(duì)。方案的質(zhì)量和方案的相似度是選擇候選方案的兩個(gè)重要標(biāo)準(zhǔn)。

關(guān)于方案質(zhì)量，3.1節(jié)大鄰域搜索算法每次迭代都會(huì)產(chǎn)生一個(gè)候選方案，在方案池中已存滿方案的情況下，只有方案池中存在物流成本比該候選方案高的方案時(shí)，本研究才將它作為優(yōu)質(zhì)方案來(lái)更新方案池。

(12)

在更新方案池時(shí)，若方案池未達(dá)到個(gè)數(shù)上限，則直接將找到的候選方案插入到池中；否則，計(jì)算候選方案與池中方案的平均多樣化程度，若大于池中所有方案之間的平均多樣化程度，則將其加入方案池，并刪除方案池中與其他方案平均多樣化程度最小的一個(gè)方案。通過(guò)這一方法，可以始終使池中保留多樣化程度較高的若干個(gè)方案。

3.3基于方案池的實(shí)時(shí)響應(yīng)方法

當(dāng)有新訂單進(jìn)入時(shí)，算法立即停止對(duì)方案池的更新。利用插入方法[9]，嘗試將新訂單插入到方案池中所有方案的最佳位置上，找出成本最小且面向新訂單的配送要求可行的方案；如果不存在可行方案，即新訂單的要求無(wú)法滿足，則找出滿足所有舊訂單送貨時(shí)間窗的成本最小的方案。根據(jù)找出的方案給顧客反饋能否按時(shí)送貨，若不能按時(shí)送貨，則將可送貨的最早時(shí)間告知顧客。如果顧客因不能按時(shí)送貨而取消訂單，則系統(tǒng)恢復(fù)到之前的狀態(tài)繼續(xù)更新方案池；如果能夠按時(shí)送貨，或者顧客接受了延遲后的送貨時(shí)間，則系統(tǒng)將該顧客插入到對(duì)應(yīng)方案上，然后重新初始化并更新方案池。

4實(shí)驗(yàn)和分析

本研究基于C#開(kāi)發(fā)技術(shù)實(shí)現(xiàn)了訂單實(shí)時(shí)響應(yīng)算法程序，并采用若干個(gè)國(guó)際上公認(rèn)的Solomon Benchmark算例[47]對(duì)算法的科學(xué)性和有效性進(jìn)行全面測(cè)試，整個(gè)測(cè)試過(guò)程在Win 10操作系統(tǒng)、配置為Intel i7 CPU、4GB內(nèi)存的機(jī)器上運(yùn)行。下面對(duì)測(cè)試算例、算法的參數(shù)設(shè)置、算法的計(jì)算結(jié)果進(jìn)行詳細(xì)闡述。

4.1測(cè)試算例和參數(shù)設(shè)置

根據(jù)訂單送貨點(diǎn)的地理分布特征，Solomon Benchmark的所有算例一共有3類(lèi)問(wèn)題，即聚簇分布類(lèi)問(wèn)題(標(biāo)號(hào)為C)、平均分布類(lèi)問(wèn)題(標(biāo)號(hào)為R)、聚簇分布和平均分布混合類(lèi)問(wèn)題(標(biāo)號(hào)為RC)。每類(lèi)問(wèn)題的時(shí)間窗寬窄不同，本研究從窄時(shí)間窗的問(wèn)題中選擇6個(gè)算例，即C101、C106、R101、R105、RC101、RC106。每個(gè)算例從0時(shí)刻起，系統(tǒng)就不斷地接到顧客訂單，每接到一個(gè)訂單，系統(tǒng)立即給出是否能夠按時(shí)送貨的響應(yīng)。假設(shè)在不能按時(shí)送貨時(shí)，顧客對(duì)延遲送貨的結(jié)果都表示接受，當(dāng)所有顧客的訂單都已服務(wù)完成后，車(chē)輛返回商戶。

針對(duì)目標(biāo)函數(shù)中的系數(shù)，本研究設(shè)置α=1，而β設(shè)置為一個(gè)較大的值，即β=10，表示對(duì)新訂單超時(shí)服務(wù)的懲罰。根據(jù)新訂單實(shí)時(shí)響應(yīng)的要求，本研究設(shè)置方案池中方案?jìng)€(gè)數(shù)為330個(gè)。在這一方案數(shù)內(nèi)，利用現(xiàn)有臺(tái)式機(jī)可在1秒內(nèi)完成新訂單的響應(yīng)時(shí)間，超過(guò)這一方案數(shù)，則新訂單響應(yīng)時(shí)間增加。在路線摧毀算法中，本研究每次刪除訂單的比例為20%。

4.2計(jì)算結(jié)果及其分析

針對(duì)轉(zhuǎn)換后的算例，本研究在系統(tǒng)中模擬每個(gè)訂單實(shí)時(shí)下單、車(chē)輛動(dòng)態(tài)調(diào)度的整個(gè)過(guò)程，并運(yùn)用本研究基于多樣化方案池的訂單實(shí)時(shí)響應(yīng)方法對(duì)每一個(gè)新訂單進(jìn)行在線計(jì)算，判斷能否按時(shí)送貨，給出響應(yīng)結(jié)果。顧客接受響應(yīng)的結(jié)果后，車(chē)輛按照新方案繼續(xù)運(yùn)行，直至所有訂單服務(wù)完成，車(chē)輛返回商戶。

基于上述實(shí)驗(yàn)思路，本研究得到最終的計(jì)算結(jié)果，見(jiàn)表3。表3給出每產(chǎn)生5個(gè)訂單后采用兩種方法計(jì)算的物流成本、按時(shí)服務(wù)訂單數(shù)、求解時(shí)間，兩種方法分別是本研究方法和使用Cplex求解模型的方法。按時(shí)服務(wù)訂單數(shù)是指系統(tǒng)已經(jīng)向顧客反饋了能夠按時(shí)送達(dá)的訂單數(shù)。不同的算法給出不同的配送方案，并給顧客不同的反饋結(jié)果，因此按時(shí)服務(wù)訂單數(shù)從客戶服務(wù)的角度反映了算法的優(yōu)劣。另外，由于Cplex方法針對(duì)超過(guò)30個(gè)訂單問(wèn)題的求解難以在有限時(shí)間內(nèi)完成，所以表3僅列出Cplex方法針對(duì)30個(gè)以?xún)?nèi)訂單規(guī)模問(wèn)題的計(jì)算結(jié)果。為便于比較，表格的最后一列給出了兩種方法物流成本之差占本研究方法物流成本的百分比。

需要注意的是，在使用Cplex求解之前，必須對(duì)第2部分建立的問(wèn)題模型進(jìn)行線性化處理，因?yàn)樵撃Ｐ驮谀繕?biāo)函數(shù)和約束方程(5)式、(6)式、(10)式中都包含非線性成分。為此，本研究基于該領(lǐng)域的常用方法[48]，將模型中的非線性成分轉(zhuǎn)化為若干個(gè)線性不等式。

由表3可知，本研究的訂單實(shí)時(shí)響應(yīng)方法與Cplex方法所求解的模型結(jié)果非常接近，最大差異不超過(guò)2%，平均差異程度為0.556%。同時(shí)，本研究方法的求解時(shí)間不超過(guò)1秒，而Cplex方法的求解時(shí)間卻從幾秒到兩千多秒不等，在求解時(shí)間上本研究的方法具有明顯的優(yōu)勢(shì)。這說(shuō)明本研究的訂單實(shí)時(shí)響應(yīng)方法通過(guò)緩存多樣化的配送方案，將潛在的優(yōu)質(zhì)方案保存起來(lái)，既可在新訂單進(jìn)入時(shí)給出優(yōu)秀的配送方案，又可兼顧計(jì)算時(shí)間，滿足該問(wèn)題實(shí)時(shí)響應(yīng)的時(shí)間要求。而在按時(shí)服務(wù)訂單數(shù)方面，本研究方法的結(jié)果與Cplex方法的結(jié)果相差不大，在第30個(gè)顧客訂單下達(dá)時(shí)，兩種方法的按時(shí)服務(wù)訂單數(shù)基本一致，有兩個(gè)算例完全一樣，另外4個(gè)算例僅相差一到兩個(gè)訂單。本研究的訂單實(shí)時(shí)響應(yīng)方法雖然僅用了極短的求解時(shí)間，但仍保證了較高的求解結(jié)果質(zhì)量。

圖3針對(duì)算例C101從更細(xì)的層面上描繪了本研究訂單實(shí)時(shí)響應(yīng)方法在每一個(gè)新訂單進(jìn)入時(shí)的計(jì)算結(jié)果，給出每一個(gè)訂單到來(lái)時(shí)本研究方法得到的物流成本和平均每個(gè)訂單耗費(fèi)的物流成本。

圖3針對(duì)C101算例在每個(gè)新訂單進(jìn)入時(shí)的計(jì)算結(jié)果Figure 3Results Obtained from the Instance of C101 When Any New Order is Just Placed

由圖3可知，隨著新訂單的進(jìn)入，總物流成本一直呈上升趨勢(shì)，但平均每單的物流成本則呈緩慢下降趨勢(shì)，說(shuō)明本研究算法可以在不過(guò)多增加物流成本的情況下，針對(duì)新訂單給出配送方案，同時(shí)保證每個(gè)已有訂單的服務(wù)時(shí)間。另外，圖3給出的物流成本增量一直處于上下波動(dòng)的狀態(tài)。應(yīng)該看到，不同新訂單的進(jìn)入，在不同的車(chē)輛運(yùn)行狀態(tài)下，會(huì)有不同的調(diào)整方案。有的新訂單容易被插入到已有路線中，形成較低成本的配送方案，但有的新訂單則需要較多的物流成本來(lái)應(yīng)對(duì)。因此，為響應(yīng)新訂單而產(chǎn)生的物流成本增量就會(huì)呈現(xiàn)出正常的上下波動(dòng)現(xiàn)象，這也說(shuō)明本研究的訂單實(shí)時(shí)響應(yīng)方法會(huì)隨著新訂單和系統(tǒng)狀態(tài)的不同，而對(duì)物流方案進(jìn)行不同程度的調(diào)整。除C101算例外，其他算例的計(jì)算結(jié)果也都呈現(xiàn)出相似的變化趨勢(shì)。

表3實(shí)時(shí)響應(yīng)方法和Cplex方法的計(jì)算結(jié)果Table 3Results from the Presented Real-time Response Method and Cplex

在本研究的訂單實(shí)時(shí)響應(yīng)方法中，方案池中緩存方案的個(gè)數(shù)是影響計(jì)算效率和解的質(zhì)量的關(guān)鍵因素。為判斷不同個(gè)數(shù)緩存方案對(duì)算法結(jié)果的影響，本研究仍以C101算例為例，將緩存方案設(shè)置為從1到400(每次增加50個(gè)緩存方案)，分別計(jì)算每一個(gè)緩存方案?jìng)€(gè)數(shù)下本研究算法針對(duì)100個(gè)訂單都下達(dá)后的總體計(jì)算結(jié)果，包括總物流成本、按時(shí)服務(wù)訂單數(shù)、求解時(shí)間，得到的結(jié)果見(jiàn)圖4。

圖4不同緩存方案?jìng)€(gè)數(shù)下算法針對(duì)C101算例100個(gè)訂單都下達(dá)后的最終計(jì)算結(jié)果Figure 4Final Results Obtained from the Instance of C101 When All the 100 Orders are Placed with Different Numbers of Solutions

由圖4可知，隨著緩存方案?jìng)€(gè)數(shù)的不斷增長(zhǎng)，總物流成本持續(xù)下降，但求解時(shí)間卻快速增長(zhǎng)，并且針對(duì)100個(gè)訂單的按時(shí)服務(wù)訂單數(shù)也在增加。這說(shuō)明當(dāng)緩存較多方案時(shí)，算法能夠給出較高質(zhì)量的解，但需要花費(fèi)大量時(shí)間。由于給顧客的反饋需要控制在1秒內(nèi)實(shí)時(shí)完成，因此本研究選擇緩存330個(gè)方案這一策略，在保證系統(tǒng)實(shí)時(shí)響應(yīng)時(shí)間的同時(shí)，盡可能地提高解的優(yōu)化質(zhì)量。

5結(jié)論

即時(shí)配送問(wèn)題是支撐現(xiàn)代電子商務(wù)發(fā)展的一種新型物流活動(dòng)，在實(shí)際操作中，由于配送公司物流能力的限制，不是所有顧客訂單都能按時(shí)送貨。那么在顧客下單的瞬間，如何根據(jù)配送公司當(dāng)前車(chē)輛狀態(tài)及新舊訂單的配送要求，對(duì)顧客立即給出一個(gè)能否按時(shí)送貨以及最早可送貨時(shí)間的實(shí)時(shí)響應(yīng)是配送公司亟待解決的關(guān)鍵問(wèn)題。

針對(duì)這一問(wèn)題，本研究建立數(shù)學(xué)模型，根據(jù)該問(wèn)題實(shí)時(shí)性和準(zhǔn)確性?xún)煞矫媲蠼庖?，建立包含大鄰域搜索算法、緩存方案選擇策略以及基于多樣化方案池的即時(shí)配送訂單實(shí)時(shí)響應(yīng)方法。在新訂單到來(lái)之前，基于大鄰域搜索算法和候選方案選擇策略，事先在池中緩存各種各樣的優(yōu)質(zhì)方案，一旦新訂單到來(lái)，立即利用池中的緩存方案快速生成最佳的應(yīng)對(duì)方案，從而大大縮短計(jì)算時(shí)間。實(shí)驗(yàn)針對(duì)含有100個(gè)訂單的Solomon算例，模擬從0時(shí)刻起不斷接到訂單的過(guò)程，針對(duì)每一訂單采用本研究基于多樣化方案池的響應(yīng)方法加以應(yīng)對(duì)，并以Cplex方法求解重調(diào)度模型的結(jié)果作為比較。實(shí)驗(yàn)結(jié)果表明，本研究的訂單實(shí)時(shí)響應(yīng)方法求得的方案成本與Cplex方法針對(duì)重調(diào)度模型的最優(yōu)方案成本平均相差僅為0.556%，且本研究方法的計(jì)算時(shí)間在1秒以?xún)?nèi)，遠(yuǎn)遠(yuǎn)低于Cplex方法，表現(xiàn)出良好的求解效果，滿足了該問(wèn)題求解實(shí)時(shí)性和準(zhǔn)確性?xún)煞矫嬉蟆?/p>

本研究針對(duì)即時(shí)配送訂單的實(shí)時(shí)響應(yīng)問(wèn)題提出的基于多樣化方案池的響應(yīng)方法，通過(guò)在系統(tǒng)空閑時(shí)間緩存多樣化的方案，實(shí)現(xiàn)訂單進(jìn)入時(shí)從緩存方案到最佳方案的快速生成，既滿足了訂單實(shí)時(shí)響應(yīng)的要求，又能保證解的優(yōu)化質(zhì)量。在理論上，本研究結(jié)果為一類(lèi)在線、實(shí)時(shí)、優(yōu)化調(diào)度難題開(kāi)辟了新途徑，有利于提高即時(shí)配送訂單響應(yīng)的科學(xué)性、有效性和智能性，有利于提高優(yōu)化理論解決動(dòng)態(tài)問(wèn)題的自適應(yīng)能力。在實(shí)踐中，本研究為解決即時(shí)配送公司普遍面臨的線下物流能力不足以支撐線上訂單需求的問(wèn)題提供了有效途徑，對(duì)于提高顧客滿意度、避免顧客大面積取消訂單、促進(jìn)現(xiàn)代電子商務(wù)健康持續(xù)發(fā)展具有重要的實(shí)際意義。

本研究仍存在不足之處，有待未來(lái)加以解決。①本研究針對(duì)一個(gè)商戶訂單的實(shí)時(shí)響應(yīng)問(wèn)題進(jìn)行研究，這適用于商戶訂單量較多且配送公司僅為該商戶提供專(zhuān)門(mén)配送服務(wù)的情況。現(xiàn)實(shí)中也存在一個(gè)配送公司為多個(gè)商戶訂單提供統(tǒng)一即時(shí)配送服務(wù)的情況，而多商戶訂單的實(shí)時(shí)響應(yīng)要比單個(gè)商戶訂單的實(shí)時(shí)響應(yīng)問(wèn)題更復(fù)雜。在這種情況下，車(chē)輛面向多個(gè)商戶的訂單應(yīng)該如何協(xié)作、車(chē)輛連續(xù)取貨的路線順序應(yīng)該如何規(guī)劃、各個(gè)商戶訂單的服務(wù)質(zhì)量應(yīng)該如何權(quán)衡，都是本研究未涉及且在多商戶背景下亟待解決的關(guān)鍵問(wèn)題。②將本研究的理論方法與配送公司實(shí)際的背景和數(shù)據(jù)相結(jié)合，從而實(shí)現(xiàn)訂單實(shí)時(shí)響應(yīng)的智能決策系統(tǒng)，也是下一步的研究方向。