基于時(shí)間窗約束下的外賣(mài)配送路徑優(yōu)化

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

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

0　引言

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

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

1　問(wèn)題描敘

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

圖1　一條路徑的配送過(guò)程

2　模型建立

2.1　問(wèn)題假設(shè)

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

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

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

假設(shè)三：一個(gè)客戶(hù)的訂單只能由一輛車(chē)進(jìn)行配送。

2.2　模型參數(shù)

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

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

Qk為每輛車(chē)的車(chē)載量；

Tk為車(chē)輛配送的最大行駛時(shí)間；

En為顧客訂單要求最早達(dá)到時(shí)間；

Fn為顧客訂單要求最晚達(dá)到時(shí)間；

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

tij為客戶(hù)點(diǎn)i到j(luò)的配送時(shí)間；

nk為第k輛車(chē)配送的顧客配送點(diǎn)數(shù)；

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

rki表示顧客點(diǎn)rki在路徑k中的順序?yàn)閕；

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

2.3　模型設(shè)立

針對(duì)本論文的目標(biāo)，建立如下的模型：

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

3　算法求解

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

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

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

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

（4）遺傳算子。本文遺傳算子分為三個(gè)部分為選擇、交叉和變異，選擇：本文依據(jù)種群中不同個(gè)體的適應(yīng)度值采用輪盤(pán)賭方式進(jìn)行選擇，該方案能夠保證適應(yīng)度高的個(gè)體以更大的概率被選中。交叉：在遺傳算法中，新個(gè)體的產(chǎn)生主要依靠交叉操作。本文進(jìn)行交叉操作時(shí)，為使子代依舊為可行解，采用部分匹配交叉法（PMX）：對(duì)兩個(gè)父代隨機(jī)產(chǎn)生2個(gè)位串交叉點(diǎn)，兩點(diǎn)間為交叉匹配區(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即為通過(guò)部分匹配交叉法獲得的新一代個(gè)體。

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

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

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

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

4　算例分析

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

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

表1　各點(diǎn)之間的行駛時(shí)間　單位：分鐘

表2　各點(diǎn)的需求量和時(shí)間窗

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

5　結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

[8] 王帥，趙來(lái)軍，胡青蜜.隨機(jī)旅行時(shí)間的外賣(mài)O2O配送車(chē)輛路徑問(wèn)題[J].物流科技，2017,40(1):93-101.