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

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

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

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

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

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

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

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

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

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

1 問(wèn)題描述

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

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

2.1 模型假設(shè)

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

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

(3)每輛電動(dòng)車(chē)都是有載重限制的，即送餐員在進(jìn)行外賣(mài)配送時(shí)，攜帶的餐盒數(shù)量不能超過(guò)每輛電動(dòng)車(chē)的最大載重?cái)?shù)量。

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

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

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

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

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

(2)決策變量：

(3)約束條件：

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

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

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

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

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

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

3 模型求解

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

(1)染色體的編碼

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

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

(2)初始群體的選取

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

因?yàn)楦鶕?jù)遼寧工業(yè)大學(xué)校園外賣(mài)配送需求情況，本文共調(diào)查選取21個(gè)點(diǎn)，3個(gè)食堂出發(fā)點(diǎn)即“配送中心”，18個(gè)需求點(diǎn)，故本文將初始種群的數(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ù)值越大的染色體就說(shuō)明它適應(yīng)環(huán)境的能力越強(qiáng)，表明其越優(yōu)質(zhì)，反之則越劣質(zhì)。由于外賣(mài)配送的目標(biāo)函數(shù)追求的是行駛距離最短，因此本文利用目標(biāo)函數(shù)D(=1，2，3)的倒數(shù)表示種群個(gè)體的適應(yīng)度函數(shù)。當(dāng)總的配送行駛距離越小即目標(biāo)函數(shù)值越小時(shí)，適應(yīng)度函數(shù)值也就越大，表明其適應(yīng)性越好，也就是被遺傳到下一代的概率也就越大。

(4)選擇操作

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

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

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

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

(5)交叉操作

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

①父代個(gè)體染色體的基因排列方式：

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

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

(6)變異操作

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

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

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

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

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

例如開(kāi)始時(shí)的基因位置為：

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

變異后的基因位置為：

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

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

圖1 算法流程圖

3.2 實(shí)例

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

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

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

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

圖2 各點(diǎn)百度地圖分布圖

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

(2)利用Excel軟件進(jìn)行高斯投影換算，將經(jīng)緯度坐標(biāo)換算到高斯平面直角坐標(biāo)。例如編號(hào)為1的“南區(qū)一二食堂”經(jīng)緯度坐標(biāo)為(121.130563，41.147333)，換算之后得到的平面直角坐標(biāo)為(4568831.498，5718.080486)。因?yàn)楸疚乃芯糠秶谶|寧工業(yè)大學(xué)校區(qū)內(nèi)，所有編號(hào)點(diǎn)的經(jīng)緯度坐標(biāo)的差異值很小，經(jīng)過(guò)換算得到的平面直角坐標(biāo)值的差異主要從千位開(kāi)始，因此為了方便計(jì)算，將坐標(biāo)值進(jìn)行處理后得到(8831，5718)。表2所示為各點(diǎn)處理后的平面直角坐標(biāo)。

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

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

圖3 各點(diǎn)分布散點(diǎn)圖

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

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

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

由運(yùn)行結(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(此時(shí)“1”表示的為出發(fā)點(diǎn)，即“一二食堂”坐標(biāo)點(diǎn)位置)。

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

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

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

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

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

由運(yùn)行結(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(此時(shí)“1”表示的為出發(fā)點(diǎn)，即“三食堂”坐標(biāo)點(diǎn)位置)。

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

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

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

由運(yùn)行結(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(此時(shí)“1”表示的為出發(fā)點(diǎn)，即“四食堂”坐標(biāo)點(diǎn)位置)。

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

4 結(jié)論

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

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

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

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

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

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

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

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

[6] 許剛. 基于廣義多子代遺傳算法的外賣(mài)配送問(wèn)題研究[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

遼寧省教育廳重大科技平臺(tái)科技項(xiàng)目(JP2017009)

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

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

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

責(zé)任編校：孫 林