基于多樣化方案池的即時配送訂單實時響應方法

王 征，李婷玉，侯鑫垚

1 大連海事大學 航運經濟與管理學院，遼寧 大連 116026 2 大連理工大學 軟件學院，遼寧 大連 116620

引言

在現代電子商務環境下，一系列生鮮果蔬、零食小吃和鮮花禮物等顧客需求緊急且應快速完成配送的商品已成為大眾網購的對象。該類緊急商品的訂單需求在近年來呈快速增長趨勢，季度訂單超4億[1]，市場規模保持了年逾40%的高速增長[2]。

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

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

(1)訂單的實時響應，不能通過簡單地將訂單插入到某條車輛路線中來實現。一個新訂單的插入，很有可能會導致路線上其他若干已有訂單的送貨時間超出要求，但由于系統已經給出了對已有訂單按時送貨的承諾，因此必須對受影響的已有訂單進行相應的路線調整，而這一調整通常又會引發其他車輛已有訂單路線調整的連鎖反應，從而導致車輛路線的大范圍修改，最終往往會得到與原先截然不同的配送方案。

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

(3)訂單響應不僅要快，而且要準。若給顧客反饋的結果不準確，則會產生極為負面的后果，即本來能按時服務卻反饋給顧客“不能”，會損失掉該訂單的利潤；本來不能按時服務卻反饋給顧客“能”，顧客會大失所望；本來能更早送貨卻反饋給顧客一個較遲的時間，顧客很可能會取消訂單。

為此，本研究根據該問題的特點，提出基于多樣化方案池的訂單實時響應方法，并通過大規模實驗，驗證方法的科學性和有效性。

1相關研究評述

即時配送訂單實時響應問題屬于一類帶時間窗的車輛路徑問題[9]，同時兼有動態車輛路徑問題(dynamic vehicle routing problem, DVRP)、取送一體化車輛路徑問題(vehicle routing problem with pickup and delivery, VRPPD)和多回程車輛路徑問題(multi-trip vehicle routing problem, MTVRP)的特點。

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

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

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

綜上，即時配送訂單的實時響應問題是現代電子商務環境下的新問題，已有研究成果對該問題并不適用。該問題在求解上的快和準的雙重要求以及特殊的問題約束和目標，使問題的求解極具挑戰性，已有相關研究在求解時間、問題約束和目標方面無法滿足要求。因此，本研究根據問題特點，通過緩存多樣化的路徑方案，滿足求解速度和解的質量的雙重要求，開發出一種新穎的、基于多樣化方案池的在線求解算法。

2問題及其重調度模型

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

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

需要說明的是，車輛每次從商戶取得部分貨物并離開商戶進行配送后，車輛路線不會更改，車輛在本次旅途中即將服務的顧客應從未服務的訂單中刪除，同時該輛車的可用時間也應被設置為其結束本次配送、返回商戶的時間。那么，新訂單實時響應問題的模型應以所有車輛的可用時間要求、所有未服務訂單的配送要求和車輛在途送貨時限等為約束，以最小化物流配送成本和新訂單的時間窗偏離懲罰為目標建立。

表1給出該問題涉及的一些參數和變量。

當新訂單進入時，該訂單的實時響應問題可基于上述參數和變量建模，即

(1)

(2)

(3)

(4)

(5)

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

(6)

(7)

(8)

(9)

(10)

表1參數和變量Table 1Parameters and Variables

由上述模型可知，即使對于一個含有幾十個訂單和幾輛車的問題而言，模型的變量和約束數量也會十分龐大，精確算法根本無法實時給出最優方案，而建立啟發式算法是解決該問題的有效途徑。為此，本研究將建立該問題的啟發式求解方法。

3基于多樣化方案池的實時響應方法

即時配送訂單的實時響應問題屬于一類動態的車輛路徑問題，該類問題通常采用經典的事件驅動型處理方式[37]，即在特定事件發生時系統應立即響應或改變狀態。新訂單的產生、車輛的出發和返回是導致問題狀態改變的3類事件，當新訂單產生時，系統應立即向顧客反饋能否按時送貨的信息；當車輛出發時，由于車輛每次出發的路線不會改變，應將車輛此次配送所服務的訂單從未服務訂單中刪除，同時設置車輛的可用時間為其結束本次配送、返回商戶的時間；當車輛返回時，應立即為車輛確定下一次配送任務和出發時間，本研究基于當前最優的候選方案而確定。本節給出新訂單產生時的實時響應方法。

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

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

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

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

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

注：此例中有兩輛車；P0為商戶；A～D為訂單；方括號中數字為訂單時間窗；點間連線上的數字為行駛時間。

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

注：方案4、方案5、方案6分別為與方案1、方案2、方案3對應的調整方案，0代表P0，即商戶。

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

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

車輛在按計劃執行的過程中，沒有新訂單進入時，系統將使用3.1中的候選方案生成方法和3.2中的緩存方案選擇策略，不斷優化方案池中的候選方案；一旦有新訂單進入，算法立即停止方案池的更新，并利用3.3中的方法對顧客進行實時的響應。

需要說明的是，方案池中的候選方案所面向的訂單是所有未服務的訂單，但不包括在途車輛即將服務的訂單；一旦車輛從商戶出發，即將該車輛服務的訂單從未服務的訂單集合中刪除，該輛車的可用時間設置為其返回商戶的時間，同時，系統再次面向未服務的訂單集合生成并優化方案池中的候選方案。

3.1候選方案生成方法

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

啟發式算法依然是生成候選方案的有效途徑。較早的啟發式算法包括遺傳算法[17-18,32]、蟻群算法[13]、禁忌搜索[14,38]、模擬退火[39]和神經網絡[43]等，近年來該領域啟發式算法的研究已推進到迭代鄰域搜索[8]、大鄰域搜索[34]、適應性迭代搜索[44]以及多方法的混合應用[8,45]。因為大鄰域搜索具有快速收斂的特性及很強的跳離局部最優的能力而被眾多學者采納，該算法針對很多帶時間窗車輛路徑問題的標準算例都超越其他算法，而得到當前最優解[46]。因此，本研究根據問題特點建立候選方案生成的適應性大領域搜索(adaptive large neighborhood search, ALNS)算法，利用該算法對問題的初始解進行迭代優化，而問題的初始解采用隨機最優插入(randomized best insertion, RBI)[42]方法得到。

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

(1)路線的摧毀算法

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

(11)

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

(2)路線的重建算法

根據問題特點，本研究給出貪婪和悔恨[46]兩種算子。貪婪算子將訂單依次插入到成本最小的位置上，如果是已知顧客，則插入位置必須符合顧客時間窗；如果是新訂單，則可違反時間窗約束(兩種算子都包含這一檢查過程)。悔恨算子首先計算每個訂單的最優插入位置和次優插入位置的成本差值，然后將差值最大的訂單插入到其最優位置上。這兩種插入都需要將車輛的出發時間推遲至其可用時間之后，同時檢查車輛容量約束，如果不滿足，則通過在其前后位置插入商戶來滿足車輛容量約束。

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

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

3.2緩存方案選擇策略

考慮到訂單響應的實時要求，方案池中不能無限制地存儲大量的候選方案。在不同配置的計算機上，訂單響應程序的執行時間不同，為實現訂單實時響應目標(1秒內響應)，可通過實驗確定不同計算機的方案池中最大可存儲的方案個數(本研究的實驗結果為330)。

緩存哪些方案是需要解決的關鍵問題。本研究希望在池中盡可能保留多樣化程度較高的優質方案，而不是保留過于相似的劣質方案，以便在不同的新訂單進入時都能找到一種有效方案應對。方案的質量和方案的相似度是選擇候選方案的兩個重要標準。

關于方案質量，3.1節大鄰域搜索算法每次迭代都會產生一個候選方案，在方案池中已存滿方案的情況下，只有方案池中存在物流成本比該候選方案高的方案時，本研究才將它作為優質方案來更新方案池。

(12)

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

3.3基于方案池的實時響應方法

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

4實驗和分析

本研究基于C#開發技術實現了訂單實時響應算法程序，并采用若干個國際上公認的Solomon Benchmark算例[47]對算法的科學性和有效性進行全面測試，整個測試過程在Win 10操作系統、配置為Intel i7 CPU、4GB內存的機器上運行。下面對測試算例、算法的參數設置、算法的計算結果進行詳細闡述。

4.1測試算例和參數設置

根據訂單送貨點的地理分布特征，Solomon Benchmark的所有算例一共有3類問題，即聚簇分布類問題(標號為C)、平均分布類問題(標號為R)、聚簇分布和平均分布混合類問題(標號為RC)。每類問題的時間窗寬窄不同，本研究從窄時間窗的問題中選擇6個算例，即C101、C106、R101、R105、RC101、RC106。每個算例從0時刻起，系統就不斷地接到顧客訂單，每接到一個訂單，系統立即給出是否能夠按時送貨的響應。假設在不能按時送貨時，顧客對延遲送貨的結果都表示接受，當所有顧客的訂單都已服務完成后，車輛返回商戶。

針對目標函數中的系數，本研究設置α=1，而β設置為一個較大的值，即β=10，表示對新訂單超時服務的懲罰。根據新訂單實時響應的要求，本研究設置方案池中方案個數為330個。在這一方案數內，利用現有臺式機可在1秒內完成新訂單的響應時間，超過這一方案數，則新訂單響應時間增加。在路線摧毀算法中，本研究每次刪除訂單的比例為20%。

4.2計算結果及其分析

針對轉換后的算例，本研究在系統中模擬每個訂單實時下單、車輛動態調度的整個過程，并運用本研究基于多樣化方案池的訂單實時響應方法對每一個新訂單進行在線計算，判斷能否按時送貨，給出響應結果。顧客接受響應的結果后，車輛按照新方案繼續運行，直至所有訂單服務完成，車輛返回商戶。

基于上述實驗思路，本研究得到最終的計算結果，見表3。表3給出每產生5個訂單后采用兩種方法計算的物流成本、按時服務訂單數、求解時間，兩種方法分別是本研究方法和使用Cplex求解模型的方法。按時服務訂單數是指系統已經向顧客反饋了能夠按時送達的訂單數。不同的算法給出不同的配送方案，并給顧客不同的反饋結果，因此按時服務訂單數從客戶服務的角度反映了算法的優劣。另外，由于Cplex方法針對超過30個訂單問題的求解難以在有限時間內完成，所以表3僅列出Cplex方法針對30個以內訂單規模問題的計算結果。為便于比較，表格的最后一列給出了兩種方法物流成本之差占本研究方法物流成本的百分比。

需要注意的是，在使用Cplex求解之前，必須對第2部分建立的問題模型進行線性化處理，因為該模型在目標函數和約束方程(5)式、(6)式、(10)式中都包含非線性成分。為此，本研究基于該領域的常用方法[48]，將模型中的非線性成分轉化為若干個線性不等式。

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

圖3針對算例C101從更細的層面上描繪了本研究訂單實時響應方法在每一個新訂單進入時的計算結果，給出每一個訂單到來時本研究方法得到的物流成本和平均每個訂單耗費的物流成本。

圖3針對C101算例在每個新訂單進入時的計算結果Figure 3Results Obtained from the Instance of C101 When Any New Order is Just Placed

由圖3可知，隨著新訂單的進入，總物流成本一直呈上升趨勢，但平均每單的物流成本則呈緩慢下降趨勢，說明本研究算法可以在不過多增加物流成本的情況下，針對新訂單給出配送方案，同時保證每個已有訂單的服務時間。另外，圖3給出的物流成本增量一直處于上下波動的狀態。應該看到，不同新訂單的進入，在不同的車輛運行狀態下，會有不同的調整方案。有的新訂單容易被插入到已有路線中，形成較低成本的配送方案，但有的新訂單則需要較多的物流成本來應對。因此，為響應新訂單而產生的物流成本增量就會呈現出正常的上下波動現象，這也說明本研究的訂單實時響應方法會隨著新訂單和系統狀態的不同，而對物流方案進行不同程度的調整。除C101算例外，其他算例的計算結果也都呈現出相似的變化趨勢。

表3實時響應方法和Cplex方法的計算結果Table 3Results from the Presented Real-time Response Method and Cplex

在本研究的訂單實時響應方法中，方案池中緩存方案的個數是影響計算效率和解的質量的關鍵因素。為判斷不同個數緩存方案對算法結果的影響，本研究仍以C101算例為例，將緩存方案設置為從1到400(每次增加50個緩存方案)，分別計算每一個緩存方案個數下本研究算法針對100個訂單都下達后的總體計算結果，包括總物流成本、按時服務訂單數、求解時間，得到的結果見圖4。

圖4不同緩存方案個數下算法針對C101算例100個訂單都下達后的最終計算結果Figure 4Final Results Obtained from the Instance of C101 When All the 100 Orders are Placed with Different Numbers of Solutions

由圖4可知，隨著緩存方案個數的不斷增長，總物流成本持續下降，但求解時間卻快速增長，并且針對100個訂單的按時服務訂單數也在增加。這說明當緩存較多方案時，算法能夠給出較高質量的解，但需要花費大量時間。由于給顧客的反饋需要控制在1秒內實時完成，因此本研究選擇緩存330個方案這一策略，在保證系統實時響應時間的同時，盡可能地提高解的優化質量。

5結論

即時配送問題是支撐現代電子商務發展的一種新型物流活動，在實際操作中，由于配送公司物流能力的限制，不是所有顧客訂單都能按時送貨。那么在顧客下單的瞬間，如何根據配送公司當前車輛狀態及新舊訂單的配送要求，對顧客立即給出一個能否按時送貨以及最早可送貨時間的實時響應是配送公司亟待解決的關鍵問題。

針對這一問題，本研究建立數學模型，根據該問題實時性和準確性兩方面求解要求，建立包含大鄰域搜索算法、緩存方案選擇策略以及基于多樣化方案池的即時配送訂單實時響應方法。在新訂單到來之前，基于大鄰域搜索算法和候選方案選擇策略，事先在池中緩存各種各樣的優質方案，一旦新訂單到來，立即利用池中的緩存方案快速生成最佳的應對方案，從而大大縮短計算時間。實驗針對含有100個訂單的Solomon算例，模擬從0時刻起不斷接到訂單的過程，針對每一訂單采用本研究基于多樣化方案池的響應方法加以應對，并以Cplex方法求解重調度模型的結果作為比較。實驗結果表明，本研究的訂單實時響應方法求得的方案成本與Cplex方法針對重調度模型的最優方案成本平均相差僅為0.556%，且本研究方法的計算時間在1秒以內，遠遠低于Cplex方法，表現出良好的求解效果，滿足了該問題求解實時性和準確性兩方面要求。

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

本研究仍存在不足之處，有待未來加以解決。①本研究針對一個商戶訂單的實時響應問題進行研究，這適用于商戶訂單量較多且配送公司僅為該商戶提供專門配送服務的情況。現實中也存在一個配送公司為多個商戶訂單提供統一即時配送服務的情況，而多商戶訂單的實時響應要比單個商戶訂單的實時響應問題更復雜。在這種情況下，車輛面向多個商戶的訂單應該如何協作、車輛連續取貨的路線順序應該如何規劃、各個商戶訂單的服務質量應該如何權衡，都是本研究未涉及且在多商戶背景下亟待解決的關鍵問題。②將本研究的理論方法與配送公司實際的背景和數據相結合，從而實現訂單實時響應的智能決策系統，也是下一步的研究方向。