基于遺傳算法的多目標外賣路徑規劃

龔藝冉　金超　侯明明

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

[關鍵詞]外賣配送 路徑規劃 遺傳算法 時間窗

1緒論

1.1研究背景

前瞻產業研究院發布的《中國在線外賣商業模式與投資戰略規劃分析報告》統計數據顯示，2015-2018年中國在線外賣收入年均增速約為117.5%，是傳統餐飲業的12.1倍，我國在線外賣收入從2015的458億元增長至2018年的4712億元左右，占全國餐飲業收入比重從1.4%提高到10.6%。

隨著外賣逐漸普及，問題也隨之涌現。作為主要消費群體的白領階層和學生對服務體驗的要求較高，而配送慢是他們對外賣服務最為直觀的感受。從商家的角度看，外賣配送也是最棘手的問題。

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

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

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

眾包物流配送模式：每一個自愿兼職且通過考核認證的個人都可以成為外賣配送員，也就是現在的“騎手”。這種模式通過利用社會的零散人力能夠有效的整合資源，使得人力資源成本大大降低，即使在送餐高峰期，也有充足的人力滿足外賣的配送，外賣平臺也不必增加額外的運營成本。但外賣平臺對這一模式的配送環節無法進行實施監控，騎手會因個人原因導致配送出錯、配送不及時、服務質量差等一系列問題。

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

1.2國內外現狀分析

1.2.1國外現狀分析

以國外外賣020標桿的Grub Hub為例，Grub Hub在模式上兩頭兼顧，在發展客戶服務的同時也為商家提供優質可靠的服務。面向用戶的終端，Grub Hub實現了標準化服務，規范有序忙而不亂，并提供TrackYourGrub，使得用戶能夠在終端直觀監測外賣的配送情況，這一點國內外賣平臺設計中值得借鑒。面向商家，Grub Hub商家系統提供商戶統計、安排訂單等基礎服務，還提供了對訂單數、利潤率、重復訂餐率等數據進行綜合分析為商家提出相應合理的調整建議功能，這吸引了美國市場份額超過6成的個體餐廳加入Grub Hub。

1.2.2國內現狀分析

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

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

國內王荃菲[1]重點研究了針對城市復雜路況的外賣配送路徑的優化問題。楚尚軒[2]研究了外賣和快遞共同配送的問題。沙小卜[3]對外賣配送網絡進行了研究。

本文將基于遺傳算法，針對“眾包”配送模式提出一種路徑優化方法，并且使得各外賣平臺配送方案不統一問題得到解決。

2問題描述和數學模型

2.1模型假設

外賣配送的實際運行是一個復雜的過程，受諸多因素影響，為了建立調度模型，本文做如”下假設。

（1）外賣配送更多的是服務特殊群體，所以本文認為外賣配送是一種預約型配送，即在進行調度安排前，已經獲取了所有顧客的地理信息。

（2）在實際運行中，顧客的出行分布具有很強的時空特征，但本文更注重方法論的介紹。所以，假設服務區域內的顧客地理位置分布在時間和空間上都服從均勻分布。

（3）外賣配送車輛的調度與路網條件息息相關，為了簡化模型以及便于說明設計思路，忽略路網對調度的影響。Quadrifogli等已經證明“對角”路徑能夠反映車輛真實的運行情況。本文假設車輛按“對角"路徑運行，即車輛只能沿水平或垂直方向運行。

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

2.2模型建立

外賣配送的車輛調度是在確定總的配送計劃之后，根據顧客的位置信息，解決“每個車次服務哪些顧客，怎么配送”的問題。外賣配送從運營者和顧客角度出發建立雙層規劃模型，運營者希望在投入下能夠服務更多的顧客，顧客則希望送達的時間越短越好。

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

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