翟勁松，臺玉紅?。ㄉ虾＠砉ご髮W(xué)，上海 200093）

ZHAI Jinsong,TAI Yuhong　(Shanghai University of Science and Technology,Shanghai 200093,China)

0　引言

隨著互聯(lián)網(wǎng)的發(fā)展以及生活節(jié)奏的加快，越來越多的人購買外賣。當下最主流的外賣銷售形式是通過的O2O方式，即消費者線上下單，商家接單后線下送貨上門。由于外賣配送的特殊性，于是配送問題一直是各大商家需要解決的難點，在提供配送服務(wù)的過程中，顧客往往約定外賣送達時間，商家需保障外賣的準時送達，一旦外賣未能準時送抵顧客處，顧客滿意度會受到影響，顧客會將不滿信息反饋到外賣平臺以供其他顧客參考，會損傷外賣提供商的品牌效應(yīng)，對經(jīng)營業(yè)績產(chǎn)生不良影響。因此，以時間窗為約束條件，以配送時間最短為目標，合理高效地組織配送服務(wù)對提高商家的自身競爭力具有重要意義。

帶時間窗的車輛路徑問題（Vehicle Routing problem with Time windows，VRPTW）是在VRP的基礎(chǔ)上增加了客戶要求訪問的時間窗口，是VRP的一類重要拓展，可簡單描述為：在不違背車輛限制的條件下，用于送貨的若干車輛從配送中心出發(fā)，在返回到配送中心前，以最低的總成本滿足處在不同地理位置的客戶對供貨數(shù)量、質(zhì)量和服務(wù)時間的要求。許多與時間相關(guān)的運輸調(diào)度問題都可歸結(jié)為VRPTW，例如郵件的投遞、公交的調(diào)度、JIT模式下物料的配送等，根據(jù)時間要求合理安排車輛路線是提高服務(wù)質(zhì)量和經(jīng)濟效益的重要手段。由于VRPTW本身的復(fù)雜性以及相應(yīng)的實踐問題，各國學(xué)者進行了大量研究。同時VRPTW屬于NP難問題，一般采用啟發(fā)式算法求解，例如節(jié)約法[1-2]、遺傳算法、捕食搜索算法[3]。張建強、潘立軍（2012）[4]等都曾利用遺傳算法求解物流配送路徑優(yōu)化問題。馬韶涵（2016）[5]等將外賣的配送分為了餐飲企業(yè)配送模式，外賣平臺配送模式，第三方物流企業(yè)配送模式三種方式，并對外賣平臺配送模式進行了研究，對該配送模式存在的問題進行了分析和提出了解決對策。郭月（2016）[6]等通過使用節(jié)約里程法對校園外賣配送路徑的優(yōu)化，從而達到配送的高效率。張弘穎（2014）[7]為了實現(xiàn)熟食運送的快速和經(jīng)濟合理，采用遺傳算法對配送路徑進行了優(yōu)化，最后通過實驗驗證該方法是可行的、有效的。王帥（2017）[8]通過遺傳算法有效地計算出響應(yīng)顧客需求的最優(yōu)車輛路徑，并分析了顧客完全滿意度區(qū)間大小、顧客滿意度敏感性以及配送車輛數(shù)量等因素對配送方案總體滿意度水平的影響，最后提出了提高外賣O2O配送滿意度的建議。

1　問題描敘

本文是研究帶有時間窗約束的外賣車輛配送問題，目標是在顧客需求時間約束的情況下，商家的配送總時間最短。通過對周邊的商家進行調(diào)研，將本論文的問題進行了簡單的描述，主要可描述為一個商家也是配送中心，所有的訂單都是在配送中心進行處理和分配，之后向周邊多個顧客點進行配送服務(wù)，由配送中心的多輛車從配送中心出發(fā)，在顧客約定的時間限制下進行配送，最后在配送完之后再返回配送中心的一個過程，如圖1所示：

圖1　一條路徑的配送過程

2　模型建立

2.1　問題假設(shè)

在外賣配送過程中，會有出現(xiàn)很多情況，導(dǎo)致配送時間的浪費。（1）配送物損傷，如果配送車輛裝載過多，可能出現(xiàn)貨物被擠壓受損等情況，配送員需要花費時間解決該種情況；（2）配送車輛由于出現(xiàn)一些情況，無法進行配送，導(dǎo)致配送不及時；（3）出現(xiàn)重復(fù)配送情況，使得配送效率降低，等等。于是為了避免出現(xiàn)上述的一些情況，本文做出如下的假設(shè)：

假設(shè)一：在每條送餐路徑上，車載重不小于顧客訂單總需求和。

假設(shè)二：每條送餐路徑的配送時間不大于配送車輛的最大行駛時間。

假設(shè)三：一個客戶的訂單只能由一輛車進行配送。

2.2　模型參數(shù)

對于本論文模型，其中的主要參數(shù)如下：

K為商家配送車輛數(shù)；

Qk為每輛車的車載量；

Tk為車輛配送的最大行駛時間；

En為顧客訂單要求最早達到時間；

Fn為顧客訂單要求最晚達到時間；

L為配送送貨點個數(shù)，其訂單量記為qi（i=1,2,）…；

tij為客戶點i到j(luò)的配送時間；

nk為第k輛車配送的顧客配送點數(shù)；

Rk表示第k條路徑的集合；

rki表示顧客點rki在路徑k中的順序為i；

令rk0=0表示商家的配送中心。

2.3　模型設(shè)立

針對本論文的目標，建立如下的模型：

其中：式（1）為目標函數(shù)，式（2）確保顧客訂單在顧客規(guī)定的時間窗內(nèi)送到，式（3）確保每條配送路徑上的車載量顧客訂單的總和，式（4）確保每條路徑的配送時間≤配送車輛最大行駛時間，式（5）每條路徑的顧客訂單數(shù)≤總的顧客訂單總數(shù)，式（6）確保貨物送到每個客戶，式（7）確保每個顧客的訂單由一輛車進行配送，式（8）中的0表示該輛車沒有被使用。

3　算法求解

遺傳算法由美國J.H.Holland教授在20世紀70年代提出。該算法是基于生物進化理論的自適應(yīng)隨機搜索算法，對于求解路徑優(yōu)化問題十分有效。路徑優(yōu)化問題是遺傳算法應(yīng)用十分成熟的領(lǐng)域，該算法求解路徑優(yōu)化問題的基本步驟為：編碼操作、產(chǎn)生初始種群、計算適應(yīng)度函數(shù)、遺傳算子（包括選擇、交叉和變異）、終止規(guī)則。針對本文中的問題，采用遺傳算法進行求解，生成最優(yōu)的路徑。

（1）編碼。路徑優(yōu)化問題的編碼方式分為兩種：路徑表示法和相鄰表示法。本文采用第一種編碼方式。舉例說明：設(shè)某商家有9個配送點需要進行配送，其中一個可行閉合路徑為則對應(yīng)的染色體編碼可表示為1 4 3 7 2 5 8 6 9。

（2）產(chǎn)生初始種群。初始種群是進行遺傳進化操作的第一代種群，由N個個體組成。本文初始種群通過隨機方式生成，將初始種群規(guī)模設(shè)定為N=30，由此則隨機生成30個個體，每個個體代表了一個初始解，由于暫沒有進行遺傳進化，因此這一代種群中個體適應(yīng)度值偏低。

（3）計算適應(yīng)度函數(shù)。適應(yīng)度函數(shù)是目標函數(shù)在遺傳算法中的反映。在遺傳算法中，適應(yīng)度值大的個體將有更大概率將優(yōu)良基因信息傳遞給下一代。本文的目標函數(shù)是時間最低，因此本文采用時間的倒數(shù)作為適應(yīng)度函數(shù)，個體的適應(yīng)度值可表示為：Fitness=1/z。

（4）遺傳算子。本文遺傳算子分為三個部分為選擇、交叉和變異，選擇：本文依據(jù)種群中不同個體的適應(yīng)度值采用輪盤賭方式進行選擇，該方案能夠保證適應(yīng)度高的個體以更大的概率被選中。交叉：在遺傳算法中，新個體的產(chǎn)生主要依靠交叉操作。本文進行交叉操作時，為使子代依舊為可行解，采用部分匹配交叉法（PMX）：對兩個父代隨機產(chǎn)生2個位串交叉點，兩點間為交叉匹配區(qū)域，然后基于匹配區(qū)域內(nèi)基因的映射關(guān)系重新排列區(qū)域外重復(fù)基因。舉例如下：

父代染色體

父代1：138|27|4965

父代2：726|45|8139

交叉匹配

匹配1：138|45|4965

匹配2：726|27|8139

子代染色體

子代1：138|45|2967

子代2：546|27|8139

其中：子代1和子代2即為通過部分匹配交叉法獲得的新一代個體。

變異：交叉操作能夠使子代保持父代的優(yōu)良特性，但也會導(dǎo)致算法過早收斂，陷入局部最優(yōu)。變異操作能夠彌補這一缺點，擴大遺傳算法的搜索空間。本文采用對換變異法：首先，隨機選擇染色體的兩個基因，然后交換位置，完成對換變異，舉例如下：

變異前：2 3 8 6 7 1 9 5 4

變異后：2 3 9 6 7 1 8 5 4

（5）終止條件設(shè)定。遺傳算法本質(zhì)上是隨機搜索算法，因此難以找到準確的收斂性判別標準。本文采用遺傳算法進化代數(shù)作為終止條件。當進化代數(shù)達到預(yù)先設(shè)定值200代時，算法終止，并輸出適應(yīng)值最大的個體作為最優(yōu)解。

4　算例分析

本文考慮某個餐廳在某天11:30到12:30時間段內(nèi)對其9個配送點（編號為1,2,…,9）進行外賣配送服務(wù)，各配送點之間的配送時間和到商家的之間的行駛時間如表1，配送點的需求量和客戶需求配送時間窗如表2，商家有三輛配送車，每輛車的最大裝載量為15份，車輛配送的最大行駛時間為120分鐘。

將以上數(shù)據(jù)帶入模型，經(jīng)過 Matlab編程進行總時間最小的最優(yōu)車輛路徑選擇求解運算，可以得到最優(yōu)配送路徑方案3條（如表3）分別為：路徑1：0-2-1-8-0；路徑2：0-4-9-5-0；路徑3：0-3-7-6-0；最小的配送總時間為93分鐘，平均每條路徑的配送時間為31分鐘。

表1　各點之間的行駛時間　單位：分鐘

表2　各點的需求量和時間窗

表3　配送最優(yōu)路徑

5　結(jié)束語

隨著人們生活節(jié)奏越來越快，顧客對外賣配送時間的要求變得更高。本文通過建立以顧客滿意時間為約束條件，以配送時間最短為目標，運用遺傳算法進行路徑優(yōu)化，最后通過實例驗證得出該模型可以進行外賣路徑進行優(yōu)化，即可以滿足客戶對時間的要求，同時還可以減少商家配送時間，提高了商家的競爭力。

參考文獻：

[1] 鄭靜，程幼明.基于時間約束的節(jié)約里程法配送路徑優(yōu)化研究[J].物流工程與管理，2010,32(10):89-90.

[2] 于航，張凱.基于節(jié)約里程法的鮮活農(nóng)產(chǎn)品物流配送車輛路線的最優(yōu)設(shè)計[J].安徽農(nóng)業(yè)科學(xué)，2011,39(28):17701-17703.

[3] 蔣忠中，汪定偉.有時間窗車輛路徑問題的捕食搜索算法[J].控制與決策，2007,22(1):59-62.

[4] 潘立軍，符卓.求解帶時間窗取送貨問題的遺傳算法[J].系統(tǒng)工程理論與實踐，2012,32(1):120-126.

[5] 馬韻涵，李品峣.OTO外賣配送分析及對策[J].合作經(jīng)濟與科技，2016(22):96-98.

[6]郭月，張涵.校園外賣配送體系研究[J].中國市場，2016(20):67-69.

[7] 張弘穎.基于遺傳算法的熟食配送路徑優(yōu)化[J].科技傳播，2014,6(16):166-167.

[8] 王帥，趙來軍，胡青蜜.隨機旅行時間的外賣O2O配送車輛路徑問題[J].物流科技，2017,40(1):93-101.