基于遺傳算法的多目標(biāo)外賣路徑規(guī)劃

龔藝冉　金超　侯明明

摘要：本文針對(duì)外賣配送服務(wù)的車輛調(diào)度問題，根據(jù)外賣配送服務(wù)建立了路徑最短的帶時(shí)間窗約束的車輛路徑模型，利用遺傳算法對(duì)模型進(jìn)行求解，以國內(nèi)某外賣商家實(shí)際數(shù)據(jù)進(jìn)行了仿真實(shí)驗(yàn)，通過對(duì)實(shí)驗(yàn)結(jié)果分析，驗(yàn)證了算法的合理性和有效性。該方法也適用于不同外賣配送模式下的車輛調(diào)度。

[關(guān)鍵詞]外賣配送 路徑規(guī)劃 遺傳算法 時(shí)間窗

1緒論

1.1研究背景

前瞻產(chǎn)業(yè)研究院發(fā)布的《中國在線外賣商業(yè)模式與投資戰(zhàn)略規(guī)劃分析報(bào)告》統(tǒng)計(jì)數(shù)據(jù)顯示，2015-2018年中國在線外賣收入年均增速約為117.5%，是傳統(tǒng)餐飲業(yè)的12.1倍，我國在線外賣收入從2015的458億元增長至2018年的4712億元左右，占全國餐飲業(yè)收入比重從1.4%提高到10.6%。

隨著外賣逐漸普及，問題也隨之涌現(xiàn)。作為主要消費(fèi)群體的白領(lǐng)階層和學(xué)生對(duì)服務(wù)體驗(yàn)的要求較高，而配送慢是他們對(duì)外賣服務(wù)最為直觀的感受。從商家的角度看，外賣配送也是最棘手的問題。

現(xiàn)如今主要存在三種配送模式，各配送模式提供方不同、服務(wù)人群與范圍不同，各自的作用也不同。

自運(yùn)營配送模式：商家在接到顧客訂單后，由商家自身員工或是商家招聘的兼職人員負(fù)責(zé)外賣的配送，外賣平臺(tái)只負(fù)責(zé)線上整合商家信息。

合作加盟配送模式：由于存在商家的自營外賣配送模式不能滿足顧客需求的情況，外賣平臺(tái)則會(huì)根據(jù)具體情況與第三方物流配送團(tuán)隊(duì)進(jìn)行合作加盟，為這些商家提供物流支持。

眾包物流配送模式：每一個(gè)自愿兼職且通過考核認(rèn)證的個(gè)人都可以成為外賣配送員，也就是現(xiàn)在的“騎手”。這種模式通過利用社會(huì)的零散人力能夠有效的整合資源，使得人力資源成本大大降低，即使在送餐高峰期，也有充足的人力滿足外賣的配送，外賣平臺(tái)也不必增加額外的運(yùn)營成本。但外賣平臺(tái)對(duì)這一模式的配送環(huán)節(jié)無法進(jìn)行實(shí)施監(jiān)控，騎手會(huì)因個(gè)人原因?qū)е屡渌统鲥e(cuò)、配送不及時(shí)、服務(wù)質(zhì)量差等一系列問題。

本文以眾包物流配送模式作為研究對(duì)象，基于物流路徑規(guī)劃提出以遺傳算法提高配送速度的配送方案，借以提高用戶用餐體驗(yàn)，實(shí)現(xiàn)商家與用戶的雙贏。

1.2國內(nèi)外現(xiàn)狀分析

1.2.1國外現(xiàn)狀分析

以國外外賣020標(biāo)桿的Grub Hub為例，Grub Hub在模式上兩頭兼顧，在發(fā)展客戶服務(wù)的同時(shí)也為商家提供優(yōu)質(zhì)可靠的服務(wù)。面向用戶的終端，Grub Hub實(shí)現(xiàn)了標(biāo)準(zhǔn)化服務(wù)，規(guī)范有序忙而不亂，并提供TrackYourGrub，使得用戶能夠在終端直觀監(jiān)測外賣的配送情況，這一點(diǎn)國內(nèi)外賣平臺(tái)設(shè)計(jì)中值得借鑒。面向商家，Grub Hub商家系統(tǒng)提供商戶統(tǒng)計(jì)、安排訂單等基礎(chǔ)服務(wù)，還提供了對(duì)訂單數(shù)、利潤率、重復(fù)訂餐率等數(shù)據(jù)進(jìn)行綜合分析為商家提出相應(yīng)合理的調(diào)整建議功能，這吸引了美國市場份額超過6成的個(gè)體餐廳加入Grub Hub。

1.2.2國內(nèi)現(xiàn)狀分析

對(duì)于國內(nèi)外賣市場而言，小餐飲商家和品牌餐飲幾乎囊括整個(gè)外賣市場，而兩者面向消費(fèi)者的意愿存在較大差異，使得比較成熟的輕模式平臺(tái)都在向輕重結(jié)合的混合模式轉(zhuǎn)變。大部分商家會(huì)選擇加入多家第三方外賣平臺(tái)，但問題出現(xiàn)了，不同平臺(tái)有不同的配送解決方案，甚至有的第三方平臺(tái)并未提供配送解決方案，這樣從一臺(tái)打印機(jī)中出來的訂單得按照平臺(tái)不同區(qū)分開來給不同平臺(tái)配送團(tuán)隊(duì)，而未提供配送解決方案平臺(tái)的訂單配送還要自己消化，繁瑣至極，極易出亂。

總的來說，在配送方面，較為成熟的第三方O2O外賣平臺(tái)都在發(fā)展自己的配送業(yè)務(wù)，但由于存在內(nèi)部競爭關(guān)系使得對(duì)于整個(gè)外賣配送環(huán)節(jié)的高度整合難以實(shí)現(xiàn)。此外，我國消費(fèi)者普遍付費(fèi)意識(shí)比較差，消費(fèi)者對(duì)有償配送服務(wù)收取傭金的接受程度很低，使得商家在配送環(huán)節(jié)的花費(fèi)的成本居高不下。開發(fā)一套整合配送服務(wù)增加客戶體驗(yàn)降低配送成本的解決方案顯得尤為重要。

國內(nèi)王荃菲[1]重點(diǎn)研究了針對(duì)城市復(fù)雜路況的外賣配送路徑的優(yōu)化問題。楚尚軒[2]研究了外賣和快遞共同配送的問題。沙小卜[3]對(duì)外賣配送網(wǎng)絡(luò)進(jìn)行了研究。

本文將基于遺傳算法，針對(duì)“眾包”配送模式提出一種路徑優(yōu)化方法，并且使得各外賣平臺(tái)配送方案不統(tǒng)一問題得到解決。

2問題描述和數(shù)學(xué)模型

2.1模型假設(shè)

外賣配送的實(shí)際運(yùn)行是一個(gè)復(fù)雜的過程，受諸多因素影響，為了建立調(diào)度模型，本文做如”下假設(shè)。

（1）外賣配送更多的是服務(wù)特殊群體，所以本文認(rèn)為外賣配送是一種預(yù)約型配送，即在進(jìn)行調(diào)度安排前，已經(jīng)獲取了所有顧客的地理信息。

（2）在實(shí)際運(yùn)行中，顧客的出行分布具有很強(qiáng)的時(shí)空特征，但本文更注重方法論的介紹。所以，假設(shè)服務(wù)區(qū)域內(nèi)的顧客地理位置分布在時(shí)間和空間上都服從均勻分布。

（3）外賣配送車輛的調(diào)度與路網(wǎng)條件息息相關(guān)，為了簡化模型以及便于說明設(shè)計(jì)思路，忽略路網(wǎng)對(duì)調(diào)度的影響。Quadrifogli等已經(jīng)證明“對(duì)角”路徑能夠反映車輛真實(shí)的運(yùn)行情況。本文假設(shè)車輛按“對(duì)角"路徑運(yùn)行，即車輛只能沿水平或垂直方向運(yùn)行。

（4）可配送車輛常用于低密度區(qū)域，顧客購買總量小，所以為了簡化模型不考慮車輛的容量約束。

2.2模型建立

外賣配送的車輛調(diào)度是在確定總的配送計(jì)劃之后，根據(jù)顧客的位置信息，解決“每個(gè)車次服務(wù)哪些顧客，怎么配送”的問題。外賣配送從運(yùn)營者和顧客角度出發(fā)建立雙層規(guī)劃模型，運(yùn)營者希望在投入下能夠服務(wù)更多的顧客，顧客則希望送達(dá)的時(shí)間越短越好。

假如有一個(gè)取餐地點(diǎn)以及送餐地點(diǎn)n，配送車輛每經(jīng)過一段距離的配送成本c，取餐地點(diǎn)和送餐地點(diǎn)距離d;能夠參與配送的車輛數(shù)量為m，把表示取餐地點(diǎn)的這個(gè)點(diǎn)當(dāng)作0點(diǎn)，送餐地點(diǎn)當(dāng)作1，2，…，n，定義變量為：

在表示目標(biāo)函數(shù)的公式（2）中，其結(jié)果代表外賣配送車輛從起始點(diǎn)到最終的目的地所花銷的總成本。利用公式（3），公式（4）和公式（5）讓不同地點(diǎn)的顧客至少有一輛車前往配送，公式（6）是指外賣配送車輛在配送的過程中總的花費(fèi)時(shí)間小于限制時(shí)間。