王 迪，金 輝，靳澤宇，常廣文

基于改進(jìn)遺傳算法的校園食堂外賣配送路徑優(yōu)化研究

王 迪，金 輝，靳澤宇，常廣文

（遼寧工業(yè)大學(xué) 汽車與交通工程學(xué)院，遼寧 錦州 121001）

以遼寧工業(yè)大學(xué)校園食堂外賣配送為研究對象，建立以行駛距離最短為優(yōu)化目標(biāo)的外賣配送路徑數(shù)學(xué)模型，采用改進(jìn)的遺傳算法進(jìn)行求解，并利用模擬退火算法求解進(jìn)行對比分析，結(jié)果證明改進(jìn)遺傳算法的有效性。

外賣配送；路徑優(yōu)化；改進(jìn)遺傳算法；MATLAB

隨著互聯(lián)網(wǎng)以及O2O商業(yè)模式的不斷發(fā)展，人們的生活節(jié)奏不斷加快，網(wǎng)絡(luò)訂餐平臺得到高速發(fā)展，越來越多的人開始通過的O2O方式(即消費者通過手機(jī)、電腦等移動終端，在網(wǎng)絡(luò)上購買商品，由商家接單后送貨上門的方式)購買外賣。由于現(xiàn)在物流配送不能有效滿足網(wǎng)上訂餐服務(wù)的急切需求，導(dǎo)致外賣物流市場中第三方物流企業(yè)的進(jìn)入。第三方外賣配送企業(yè)即商家將外賣配送業(yè)務(wù)外包給物流企業(yè)，商家只需要專注于餐飲服務(wù)即可，其他的一系列配送服務(wù)由這些專業(yè)的物流企業(yè)來進(jìn)行，這樣既節(jié)約成本，也保障了配送服務(wù)的標(biāo)準(zhǔn)化[1]。

外賣物流為“短物流運輸”，隨著手機(jī)網(wǎng)絡(luò)的快速發(fā)展，手機(jī)訂餐服務(wù)也快速蔓延開來，尤其是在大學(xué)校園，這種以美團(tuán)、餓了么為代表的訂餐APP廣受在校大學(xué)生的喜愛。這種新型的用餐服務(wù)模式得到迅速發(fā)展的原因主要由以下3點：第一，學(xué)生群體的易接受性。學(xué)生是接受新奇事物最快的群體，利于新消費模式的推廣。第二，高校區(qū)域的密集性。高校是各商家集中最緊密的區(qū)域之一，這樣的集中性使得配送物流的管理更加的容易。第三，因為學(xué)生有固定的作息時間，校園食堂就會存在就餐高峰期，因為某些原因有些學(xué)生無法去餐廳就餐，只得借助外賣配送，節(jié)約時間，緩解就餐壓力。因此做好校園外賣配送管理，不僅有利于學(xué)校安全管理，更有利于學(xué)生的學(xué)習(xí)和生活[2]。

涂漢江[3]利用TSP問題對外賣配送進(jìn)行建模，使用分支限界法進(jìn)行求解，從而建立一個外賣訂餐系統(tǒng)。王帥等[4]利用旅行時間隨機(jī)的VRP問題建立外賣配送模型，并使用遺傳算法進(jìn)行求解，提高了顧客滿意度，并設(shè)計了一種配送時間隨機(jī)的外賣配送方案。郭月等[5]通過研究北京物資學(xué)院的校園外賣配送情況，建立基于節(jié)約里程法校園外賣路線規(guī)劃模型，改善了校園外賣配送情況。

外賣配送問題一直是一個難以解決的問題，在配送服務(wù)過程中，顧客與商家約定送達(dá)時間，一旦外賣未能及時送抵，顧客便會不滿，甚至于將這些不好的信息反饋到外賣平臺之上，這些信息在別的顧客進(jìn)行購買時會有很大的消極作用，會損傷商家的信譽(yù)，因此，如何合理地解決外賣配送問題具有十分重要的意義[6]。

1 問題描述

為了研究遼寧工業(yè)大學(xué)校園外賣配送路徑，可以將該項目描述為：在遼寧工業(yè)大學(xué)內(nèi)，共有4個食堂，可以將這4個食堂看作出發(fā)點，4個食堂都要向位于學(xué)校內(nèi)的各個宿舍樓以及各個教學(xué)樓和不同地點配送外賣，每個需求點在不同時間段內(nèi)都有著各自的需求情況，現(xiàn)各個食堂選擇的配送方式都默認(rèn)為電動車配送，且配送車輛都存在容量限制，以行駛距離或時間最短為目標(biāo)。因為校園外賣配送都在固定的時間段內(nèi)，因此在滿足要求的情況下，本文主要研究各食堂在中午和晚上高峰期外賣配送的最優(yōu)路徑。

2 數(shù)學(xué)模型的建立過程

2.1 模型假設(shè)

(1)每名送餐員都是從食堂出發(fā)進(jìn)行外賣的配送，即把每個食堂點作為外賣配送的出發(fā)點即“配送中心”，并且每個食堂的位置已知，送餐員從食堂出發(fā)進(jìn)行外賣配送任務(wù)，任務(wù)完成后都返回食堂。

(2)每個需求點的位置和外賣需求量均為已知的，并且保證每個配送點都會被服務(wù)到，而且每個需求點僅有1名送餐員為其提供送餐服務(wù)。

(3)每輛電動車都是有載重限制的，即送餐員在進(jìn)行外賣配送時，攜帶的餐盒數(shù)量不能超過每輛電動車的最大載重數(shù)量。

(4)進(jìn)行外賣配送的電動車由食堂統(tǒng)一提供，因此電動車的外形、載重能力、車型大小、電池續(xù)航能力都是相同的，其中電動車的最大行駛距離也是相同的。

(5)在固定時間段內(nèi)完成外賣配送，按照遼寧工業(yè)大學(xué)校園外賣情況調(diào)查問卷顯示，食堂配送基本上都在中午以及下午的固定時間，在這段時間內(nèi)，基本上所有的開始送餐時間以及最晚送達(dá)時間大致相同，因此所有車輛都會在固定時間段內(nèi)完成外賣配送。

2.2 數(shù)學(xué)模型

針對本文的目標(biāo)，建立如下的模型。

(1)目標(biāo)函數(shù)：

(2)決策變量：

(3)約束條件：

式(3)表示送餐員需要在完成任務(wù)后，返回食堂。

式(4)表示在每一次配送過程中，每一個有需求的地點都將會被服務(wù)到，每一條配送路徑都會連接一個配送中心，并且從該“配送中心”出發(fā)只連接一個需求點。

式(5)表示在快遞配送服務(wù)過程中，每個需求點都有1個送餐員服務(wù)，而且僅能被服務(wù)1次。

式(6)表示每次配送的送餐量不能超過配送電動車輛的最大載量限制。

式(7)表示優(yōu)化路徑距離不超過電動車可行駛的最大距離。

式(8)表示在每一次配送開始的時候，送餐員都是從食堂出發(fā)。

3 模型求解

3.1 改進(jìn)遺傳算法

(1)染色體的編碼

遺傳算法運算效率和運算結(jié)果絕大程度上由染色體的編碼方式的好壞直接影響，因此選擇合適的染色體編碼方式對于遺傳算法的實現(xiàn)是至關(guān)重要的。

由于本文的外賣配送問題只存在3個食堂點(即配送中心)和18個需求點，數(shù)目較小，因此采用較為簡單自然數(shù)編碼的方式對染色體進(jìn)行編碼，將染色體分為21段，其中每一段代表每一個需求點的編號，分別用1，2，…，21表示，其中1，2，3表示的是配送中心，即各個食堂出發(fā)點。例如，|19|5|7|9|20|11|13|1|21|3|15|4|8|12|2|6|10|14|17|18|16|就是一條染色體。

(2)初始群體的選取

在遺傳算法的求解過程中，初始種群的個體一般是通過隨機(jī)選取產(chǎn)生的。因此在本文中也采取隨機(jī)的策略來生成初始種群，首先根據(jù)外賣配送的范圍，確定大致初始解的空間范圍，根據(jù)最優(yōu)個體在空間內(nèi)的分布，以此選擇初始種群范圍。

因為根據(jù)遼寧工業(yè)大學(xué)校園外賣配送需求情況，本文共調(diào)查選取21個點，3個食堂出發(fā)點即“配送中心”，18個需求點，故本文將初始種群的數(shù)值設(shè)置為100。

(3)適應(yīng)度函數(shù)的選擇

適應(yīng)度函數(shù)值的大小代表的是染色體優(yōu)劣程度的標(biāo)準(zhǔn)，根據(jù)“優(yōu)勝劣汰，適者生存”的標(biāo)準(zhǔn)，適應(yīng)度函數(shù)值越大的染色體就說明它適應(yīng)環(huán)境的能力越強(qiáng)，表明其越優(yōu)質(zhì)，反之則越劣質(zhì)。由于外賣配送的目標(biāo)函數(shù)追求的是行駛距離最短，因此本文利用目標(biāo)函數(shù)D(=1，2，3)的倒數(shù)表示種群個體的適應(yīng)度函數(shù)。當(dāng)總的配送行駛距離越小即目標(biāo)函數(shù)值越小時，適應(yīng)度函數(shù)值也就越大，表明其適應(yīng)性越好，也就是被遺傳到下一代的概率也就越大。

(4)選擇操作

種群個體的選擇是建立在種群個體的適應(yīng)度評估的基礎(chǔ)上的[6]。隨機(jī)遍歷抽樣法、局部選擇法、適應(yīng)度占比選擇策略、輪盤賭選擇法等方法是遺傳算法中常用的選擇操作方法。本文采用的則是輪盤賭選擇法，具體操作步驟如下所示。

①由初始種群個體的適應(yīng)函數(shù)值(x)，將每個個體的適應(yīng)度值相加得到總的適應(yīng)度值D，公式如下：

②在[0，s]之間隨機(jī)產(chǎn)生一個數(shù)值；

③然后第一個開始，把每個個體的適應(yīng)度數(shù)值進(jìn)行相加，當(dāng)相加數(shù)值的大小超過s時，則最后一個累加的個體將作為被選中的個體。

(5)交叉操作

交叉操作是根據(jù)交叉率將兩個父代個體之間染色體上的基因進(jìn)行交叉互換，從而產(chǎn)生新的染色體個體的操作。染色體的交叉方法主要有單點交叉、兩點交叉、多點交叉等形式。本文采用的是適用自然數(shù)編碼的單點交叉法，具體操作是首先在個體串中隨機(jī)生成一個交叉點，在交叉過程中，將這兩個個體在交叉點前后的兩部分結(jié)構(gòu)進(jìn)行交叉互換，從而生成兩個新個體。若一個染色體的編碼長度，則共有-1個可供選擇的交叉點[6]。如下面所示，演示了染色體中基因進(jìn)行交叉變異產(chǎn)生的流程示意過程。

①父代個體染色體的基因排列方式：

②當(dāng)滿足交叉概率時進(jìn)行交叉變異：

③子代的交叉變異結(jié)果為：

(6)變異操作

遺傳變異指的是某些個體的染色體中的某個或幾個位置的基因發(fā)生突變，轉(zhuǎn)變?yōu)槠渌耐任恢没颍詈笊尚碌淖儺悅€體。變異能夠提高種群個體的多樣性，使遺傳算法具有局部搜索能力，防止算法過早收斂。傳統(tǒng)的變異算子有邊界變異、均勻變異、高斯變異等。本文根據(jù)自然數(shù)編碼的特點，設(shè)計如下所示的變異操作步驟。

①在（0，1）之間產(chǎn)生一個隨機(jī)數(shù)；

②判斷隨機(jī)數(shù)與m的大??；

③如果<=m，則隨機(jī)產(chǎn)生兩個基因突變位；

④將這兩個基因突變位上的基因進(jìn)行交換。

例如開始時的基因位置為：

9 5 1 | 6 | 3 8 | 7 | 10 4 2

變異后的基因位置為：

9 5 1 | 7 | 3 8 | 6 | 10 4 2

圖1所示為改進(jìn)遺傳算法求解外賣配送路徑問題時的基本流程圖。

圖1 算法流程圖

3.2 實例

遼寧工業(yè)大學(xué)校園共有4個食堂(其中南區(qū)2個，北區(qū)2個)，由于南區(qū)的2個食堂(一、二食堂)建立在一起，故這里以1個配送中心來計算，以下統(tǒng)稱為南區(qū)一二食堂，北區(qū)2個食堂距離較遠(yuǎn)，故以2個配送中心來分別計算，分別為北區(qū)三食堂、北區(qū)四食堂。

如圖2所示，利用百度地圖標(biāo)記的各食堂的具體位置以及校園內(nèi)各個需求點位置。

3.2.1 數(shù)據(jù)處理

(1)得到調(diào)查的原始數(shù)據(jù)后，根據(jù)地址在百度地圖中查找出其經(jīng)緯度。例如圖中標(biāo)記的“南區(qū)一二食堂”，在百度地圖中查找該點，得到的經(jīng)緯度坐標(biāo)為(121.130563，41.147333)。表1所示為各個標(biāo)記點的經(jīng)緯度坐標(biāo)。

圖2 各點百度地圖分布圖

表1 各點經(jīng)緯度表

(2)利用Excel軟件進(jìn)行高斯投影換算，將經(jīng)緯度坐標(biāo)換算到高斯平面直角坐標(biāo)。例如編號為1的“南區(qū)一二食堂”經(jīng)緯度坐標(biāo)為(121.130563，41.147333)，換算之后得到的平面直角坐標(biāo)為(4568831.498，5718.080486)。因為本文所研究范圍在遼寧工業(yè)大學(xué)校區(qū)內(nèi)，所有編號點的經(jīng)緯度坐標(biāo)的差異值很小，經(jīng)過換算得到的平面直角坐標(biāo)值的差異主要從千位開始，因此為了方便計算，將坐標(biāo)值進(jìn)行處理后得到(8831，5718)。表2所示為各點處理后的平面直角坐標(biāo)。

表2 各點平面直角坐標(biāo)

(3)建立坐標(biāo)系，并用MATLAB繪制散點圖，如圖3所示。

圖3 各點分布散點圖

3.2.2 仿真模擬及結(jié)果分析

根據(jù)實際情況設(shè)定參數(shù)值，交叉和變異概率分別為c=0.7%、m=0.06%，迭代次數(shù)為200。通過MATLAB進(jìn)行程序仿真模擬，得到配送路徑軌跡圖。并利用模擬退火算法求解各個食堂到各個需求點(寢室樓、教學(xué)樓等)的最短路徑，通過兩者之間的比較，直觀看出改進(jìn)遺傳算法的求解效果和收斂性。

如圖4所示，為改進(jìn)遺傳算法和模擬退火算法求解的以一二食堂為出發(fā)點的最優(yōu)配送路徑圖，圖5為其迭代次數(shù)。

由運行結(jié)果可知改進(jìn)遺傳算法求得的最優(yōu)解：3→8→10→14→2→15→1→11→16→17→19→12→18→1→7→9→5→6→4→3；總距離4 465 m。

模擬退化算法求得的最優(yōu)解：11→1→15→2→14→10→8→9→3→4→6→5→7→13→18→12→19→17→16→11；總距離：4 605 m(此時“1”表示的為出發(fā)點，即“一二食堂”坐標(biāo)點位置)。

圖4 一二食堂到各點的最優(yōu)配送路徑圖

圖5 迭代次數(shù)對比圖

圖6所示為三食堂為出發(fā)點的最優(yōu)配送路徑圖，圖7為其迭代次數(shù)。

圖6 南區(qū)三食堂到各點的最優(yōu)配送路徑圖

圖7 迭代次數(shù)對比圖

由運行結(jié)果可知改進(jìn)遺傳算法求得的最優(yōu)解：5→6→4→3→2→1→15→16→11→17→19→12→18→14→10→8→13→7→9→5；總距離：4 498 m。

模擬退化算法求得的最優(yōu)解：15→1→10→8→13→7→9→5→6→4→3→2→14→18→12→19→17→11→16→15；總距離：4 744 m(此時“1”表示的為出發(fā)點，即“三食堂”坐標(biāo)點位置)。

圖8所示為四食堂為出發(fā)點的最優(yōu)配送路徑圖，圖9為其迭代次數(shù)。

圖8 南區(qū)三食堂到各點的最優(yōu)配送路徑圖

圖9 迭代次數(shù)對比圖

由運行結(jié)果可知改進(jìn)遺傳算法求得的最優(yōu)解：16→15→2→3→4→1→6→5→9→7→13→8→10→14→18→12→19→17→11→16；總距離：4 511 m。

模擬退化算法求得的最優(yōu)解：3→4→1→6→5→7→9→14→10→8→13→18→12→19→17→11→16→15→2→3；總距離：4 531 m(此時“1”表示的為出發(fā)點，即“四食堂”坐標(biāo)點位置)。

通過以上對比結(jié)果分析可以發(fā)現(xiàn)，改進(jìn)的遺傳算法求解最優(yōu)配送路徑距離比模擬退火算法求得的距離更優(yōu)些，但前者收斂速度較慢，迭代時間較長，后者收斂速度較快，因此對于求解較大規(guī)模的優(yōu)化問題時，此改進(jìn)方法還不能有效滿足求解要求，因此需要繼續(xù)改進(jìn)。

4 結(jié)論

通過本文的研究，優(yōu)化了遼寧工業(yè)大學(xué)校園食堂外賣配送路徑，在中午以及下午就餐高峰期間可以大大地減少配送成本，縮短配送時間，提高商家的收益。

(1)該配送方法減少了配送距離。相比于以往的人工配送，不同配送人員在配送的過程中會選擇不同的下一個配送節(jié)點，導(dǎo)致了部分不熟悉的配送人員在校園內(nèi)繞遠(yuǎn)，或者在校園內(nèi)來回往返，通過該方案可以減少不必要的路程，縮減配送距離，提高效率。

(2)該配送方法減少了客戶的等待時間。配送效率的提高就意味著顧客等待時間的減少，同時也意味著客戶滿意度的提高，配送人員可以在短時間內(nèi)完成配送，大大提高了客戶的好感，如果這種好的反饋到市場當(dāng)中，會導(dǎo)致越來越多的人接受并使用這種消費方式，尤其是這些反饋較好的商家，會提高很大的收益，同時推動整個市場的發(fā)展。

[1] 翟勁松, 臺玉紅. 基于時間窗約束下的外賣配送路徑優(yōu)化[J]. 物流科技, 2018, 41(3): 15-18.

[2] 徐鎮(zhèn)邦, 裴兵. 網(wǎng)絡(luò)訂餐服務(wù)的物流配送系統(tǒng)探析[J]. 商場現(xiàn)代化, 2014(22): 74-75.

[3] 涂漢江. 集中區(qū)域外賣即時配送調(diào)度系統(tǒng)的設(shè)計實現(xiàn)[D]. 南昌: 南昌大學(xué), 2016.

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

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

[6] 許剛. 基于廣義多子代遺傳算法的外賣配送問題研究[D]. 哈爾濱: 東北農(nóng)業(yè)大學(xué), 2017.

Research on Optimization of Delivery Path of Campus Canteen Delivery Based on Improved Genetic Algorithm

WANG Di, JIN Hui, JIN Ze-yu, CHANG Guang-wen

（School of Automotive and Traffic Engineering, Liaoning University of Technology, Jinzhou 121001, China）

This paper takes the delivery of the canteen in the campus of Liaoning University of Technology as the research object, and establishes the mathematical model of the take-away delivery path with the shortest driving distance as the optimization target. The improved genetic algorithm is used to solve the problem, and the simulated annealing algorithm is used to solve the comparative analysis. The result proves that the improved genetics the effectiveness of the algorithm.

takeaway distribution; path optimization; improved genetic algorithm; MATLAB

U116.2

A

1674-3261(2019)01-0047-06

10.15916/j.issn1674-3261.2019.01.011

2019-07-17

遼寧省教育廳重大科技平臺科技項目(JP2017009)

王迪(1994-)，男，河南南陽人，碩士生。

金輝(1963-)，女(滿族)，遼寧錦州人，教授，博士。

優(yōu)先出版地址：http://kns.cnki.net/kcms/detail/21.1567.T.20191227.1019.008.html

責(zé)任編校：孫 林