基于遺傳算法的末端配送優(yōu)化
——以M快遞點(diǎn)部生鮮配送為例

楊麗英，黃漢強(qiáng)，楊從平

一、引 言

艾瑞咨詢發(fā)布《2018年中國(guó)生鮮電商行業(yè)消費(fèi)洞察報(bào)告》一文顯示，2017年中國(guó)生鮮電商市場(chǎng)交易規(guī)模約為1391.3億元，同比增長(zhǎng)59.7%，預(yù)計(jì)2018年交易規(guī)模達(dá)到1947.8億元[1]。與此同時(shí)，天貓、京東、蘇寧易購(gòu)等大型網(wǎng)上購(gòu)物平臺(tái)全面涉足生鮮市場(chǎng)的同時(shí)還致力于布局冷庫(kù)建設(shè)與冷鏈配送，這些數(shù)據(jù)均表明人們對(duì)生鮮產(chǎn)品的需求量呈現(xiàn)出快速增長(zhǎng)的發(fā)展趨勢(shì)，而由此帶來(lái)的生鮮電商配送問(wèn)題亦成為企業(yè)、學(xué)者專家研究和關(guān)注的熱點(diǎn)問(wèn)題。

Hsu C等人（2011）對(duì)蓄冷箱式多溫共配系統(tǒng)與傳統(tǒng)多車(chē)配送方法進(jìn)行比較分析，提出適合城市末端配送的蓄冷箱式多溫共配系統(tǒng)方案[2]。詹斌等人（2016）借助云計(jì)算和大數(shù)據(jù)等先進(jìn)的互聯(lián)網(wǎng)技術(shù)對(duì)電商物流末端配送進(jìn)行系統(tǒng)地分析，提出可視化配送服務(wù)、合作共用自提柜、無(wú)人機(jī)送快遞等一系列創(chuàng)新思路[3]。申風(fēng)平等人（2017）則采用熵值法和灰色絕對(duì)關(guān)聯(lián)度進(jìn)行分析，提出管控生鮮配送風(fēng)險(xiǎn)的有效性策略[4]。

在實(shí)際生活中，生鮮配送屬于末端配送，是二次投遞，本文結(jié)合生鮮末端配送特點(diǎn)，選取M快遞點(diǎn)部其生鮮配送路徑問(wèn)題，構(gòu)建以配送成本最小的優(yōu)化模型（最終轉(zhuǎn)化為路徑最短的優(yōu)化模型），利用遺傳算法在路徑優(yōu)化的便捷性與有效性對(duì)其配送路線進(jìn)行路徑優(yōu)化，以此來(lái)求解出具體的生鮮末端的配送路線。

二、M快遞點(diǎn)部生鮮末端配送現(xiàn)狀及問(wèn)題分析

（一）M快遞點(diǎn)部生鮮配送現(xiàn)狀分析

M快遞點(diǎn)部的倉(cāng)庫(kù)位于南寧市竹溪大道43號(hào)容桂商廈一樓，倉(cāng)庫(kù)占地面積250平方米，其配送業(yè)務(wù)主要集中在各類(lèi)網(wǎng)購(gòu)快遞包裹和生鮮配送。配送設(shè)備主要是13輛三輪車(chē)及37輛兩輪電動(dòng)車(chē)。其中生鮮配送采用兩輪電動(dòng)車(chē)進(jìn)行配送，承諾在兩個(gè)小時(shí)左右送達(dá)給客戶。另外設(shè)有3個(gè)冰柜以滿足當(dāng)客戶需要滯留生鮮產(chǎn)品時(shí)對(duì)生鮮產(chǎn)品進(jìn)行冷藏，保證其新鮮度，配送的生鮮種類(lèi)產(chǎn)品如表1。

表1 M快遞點(diǎn)部配送的生鮮產(chǎn)品種類(lèi)

從表1生鮮產(chǎn)品種類(lèi)來(lái)看，水果類(lèi)具有較明顯的季節(jié)性，所以M點(diǎn)部的生鮮配送量會(huì)在每年的5—7月有明顯增加。此外，在整理M點(diǎn)部2015—2017年近三年的生鮮配送量數(shù)據(jù)中，不難發(fā)現(xiàn)人們網(wǎng)購(gòu)郵寄生鮮產(chǎn)品數(shù)量在逐年上升中，具體見(jiàn)圖1。

圖1 2015—2017年M點(diǎn)部生鮮配送數(shù)量變化情況

從圖1可以看出M快遞點(diǎn)部生鮮配送逐年增長(zhǎng)，但增幅較小。其原因主要是位于該點(diǎn)部成熟老城區(qū)，周邊生活配套完善，各類(lèi)生鮮產(chǎn)品購(gòu)買(mǎi)便利，而客戶開(kāi)發(fā)容量有限，需要增加新配送模式，提升配送附加值才能吸引有限客戶群的購(gòu)買(mǎi)配送需求，從而使得更多客戶愿意網(wǎng)購(gòu)生鮮產(chǎn)品，進(jìn)而提高點(diǎn)部的生鮮配送量。

（二）M快遞點(diǎn)部生鮮配送的問(wèn)題分析

在M點(diǎn)部運(yùn)營(yíng)中存在許多不可控因素，在降低運(yùn)營(yíng)成本過(guò)程中可能就會(huì)帶來(lái)不利于生鮮產(chǎn)品配送的問(wèn)題，如：未滿載就發(fā)車(chē)、缺乏溫控設(shè)施、存在二次投遞質(zhì)量無(wú)法保證、不適混載的配送等，造成資源浪費(fèi)、產(chǎn)品變質(zhì)等問(wèn)題。同時(shí)，由于承諾兩小時(shí)送達(dá)服務(wù)，現(xiàn)M點(diǎn)部的生鮮配送基本上到件分揀后就開(kāi)始派送，缺乏合理的配送規(guī)劃而造成人員浪費(fèi)，多人送、線路重合，使得配送效率低下。

為了解決這類(lèi)由于多人送、線路重合的配送效率低下的問(wèn)題，即以最低配送成本作為最終優(yōu)化目標(biāo)，其配送成本包括運(yùn)輸成本、固定成本和貨損成本，其中運(yùn)輸成本和貨損成本與配送的里程存在正比關(guān)系。在結(jié)合實(shí)際情況忽略一些因素的情況下，可以將配送成本最低轉(zhuǎn)換為以配送路程最小作為最終的優(yōu)化目標(biāo)。本文借助MATLAB軟件進(jìn)行遺傳算法的路徑優(yōu)化，計(jì)算出M點(diǎn)部在采用兩條配送線路時(shí)，如何更好地完成9個(gè)客戶點(diǎn)的配送任務(wù)。

三、M點(diǎn)部生鮮配送路徑優(yōu)化模型構(gòu)建假設(shè)

（一）模型思路

所謂路徑優(yōu)化目標(biāo)，就是指在滿足一定的約束條件（比如對(duì)裝載量、配送量、配送時(shí)效、收貨或發(fā)貨時(shí)間等進(jìn)行條件的限制）情況下，生鮮產(chǎn)品的配送員按照設(shè)定好的路線進(jìn)行配送服務(wù)，最終能夠?qū)崿F(xiàn)既定的目標(biāo)（比如總里程最短、總費(fèi)用最低、總配送車(chē)輛數(shù)量最少、總配送時(shí)間最短等）的過(guò)程。

由于生鮮的配送需要考慮到時(shí)效性問(wèn)題，因此，對(duì)路徑的選擇上需要采用嚴(yán)格而科學(xué)的方法才能更好地進(jìn)行理論支撐及分析。因此，在構(gòu)建配送路徑優(yōu)化的模型中，為了使模擬出的計(jì)算結(jié)果更加符合實(shí)際的要求，本文將主要采用遺傳算法進(jìn)行配送路徑的優(yōu)化。

（二）模型的假設(shè)和約束條件

1.假設(shè)條件

為了便于對(duì)路徑進(jìn)行計(jì)算研究，將配送員進(jìn)行生鮮配送過(guò)程中的問(wèn)題能夠轉(zhuǎn)化為可以求解的數(shù)學(xué)模型，使得計(jì)算機(jī)的模擬結(jié)果與實(shí)際結(jié)果更加接近，此時(shí)需要對(duì)生鮮配送人員在配送過(guò)程中做出假設(shè)：

（1）點(diǎn)部能夠給各個(gè)客戶點(diǎn)進(jìn)行配送；

（2）進(jìn)行生鮮配送的車(chē)輛規(guī)格以及行駛速度相同；

（3）配送車(chē)輛只從M點(diǎn)部出發(fā)，完成配送任務(wù)后必須回到點(diǎn)部，最終形成閉合回路；

（4）每個(gè)配送員對(duì)各個(gè)配送客戶的配送路線是已經(jīng)安排好的路線；

（5）當(dāng)客戶不在家或者拒簽時(shí)，訂單會(huì)返回點(diǎn)部；

（6）地點(diǎn)簡(jiǎn)化為一個(gè)點(diǎn)，以便得出具體的位置信息。

2.約束條件

模型的構(gòu)建，需要滿足以下約束條件：

（1）每輛配送車(chē)的實(shí)際載貨總量不大于該車(chē)的最大載貨量；

（2）單個(gè)客戶僅對(duì)應(yīng)一個(gè)配送車(chē)輛的服務(wù)；

（3）車(chē)輛在完成上一個(gè)客戶點(diǎn)的配送后一定要給下一個(gè)客戶點(diǎn)配送或者返回到M快遞點(diǎn)部。

（三）模型的建立

1.目標(biāo)函數(shù)的構(gòu)建

在生鮮產(chǎn)品的配送過(guò)程中，由于生鮮產(chǎn)品具有非常鮮明的時(shí)效性和易腐性，因而在實(shí)際的配送過(guò)程中必然會(huì)存在著生鮮的損耗問(wèn)題，這樣會(huì)直接導(dǎo)致配送成本以及配送車(chē)輛成本的增加。因此，為能夠建立合理有效的目標(biāo)函數(shù)，本文在考慮生鮮產(chǎn)品自身存在的鮮明屬性前提下，將配送成本最小化作為最終的優(yōu)化目標(biāo)。此時(shí)，在對(duì)構(gòu)成配送總成本進(jìn)行系統(tǒng)地分析：一是在配送過(guò)程中，車(chē)輛使用成本以及運(yùn)輸成本是必然產(chǎn)生的費(fèi)用；二是在配送過(guò)程中由于生鮮產(chǎn)品具有非常鮮明的時(shí)效性和易腐性，會(huì)在配送過(guò)程中會(huì)造成生鮮產(chǎn)品的損失，這稱為貨損成本。綜上所述，本文所構(gòu)造的模型中總的配送成本主要是由固定成本、運(yùn)輸成本、貨損成本組成。

（1）固定成本

配送員在進(jìn)行配送的過(guò)程中使用到的電動(dòng)車(chē)會(huì)產(chǎn)生一定的費(fèi)用，主要是由車(chē)輛的保養(yǎng)費(fèi)、維修費(fèi)及人工費(fèi)用等構(gòu)成。這部分的成本一般是固定的，與行駛的時(shí)間和路程無(wú)關(guān)，用代表固定成本，則有：

式中：C1——完成單次配送任務(wù)的電動(dòng)車(chē)所消耗的固定成本；m——配送車(chē)輛的數(shù)目。

（2）運(yùn)輸成本

配送員在配送過(guò)程中使用到的電車(chē)會(huì)產(chǎn)生一定的成本，這部分費(fèi)用主要由電車(chē)充電所消耗的電費(fèi)以及進(jìn)行維修保養(yǎng)費(fèi)。運(yùn)輸成本費(fèi)用主要是由行駛的路程決定，在優(yōu)化該部分的成本時(shí)，可以對(duì)行駛路程進(jìn)行考慮。因而，用與運(yùn)輸距離成正比例關(guān)系的函數(shù)表示運(yùn)輸成本函數(shù)，用Ct表示運(yùn)輸成本，則有：

式中，C1——電車(chē)每行駛一公里產(chǎn)生的費(fèi)用；

dij——客戶i和客戶j之間的實(shí)際距離；

Xijk——0-1 變量，若車(chē)輛 k 在路段（i，j）上行駛，則Xijk=1，否則Xijk=0。

（3）貨損成本

貨損成本是指在生鮮產(chǎn)配送過(guò)程中，由于時(shí)間、溫度等一系列不可控因素引起生鮮產(chǎn)品質(zhì)量的下降，造成生鮮產(chǎn)品損失而需要額外支付的費(fèi)用。運(yùn)輸過(guò)程中溫度、時(shí)間是造成貨損成本的根本原因，但是在順豐瑯西點(diǎn)部配送過(guò)程中沒(méi)有控制溫度設(shè)備的保障，此時(shí)不把溫度劃入考慮范圍，因此在考慮生鮮貨損成本時(shí)，可以用與運(yùn)輸距離成正比例關(guān)系的函數(shù)表示貨損成本函數(shù)。

2.優(yōu)化模型的構(gòu)建

根據(jù)對(duì)上述目標(biāo)函數(shù)的分析，在構(gòu)建以配送總成本最低為最優(yōu)目標(biāo)的情況下，固定成本一般是固定的，與行駛里程和在途時(shí)間無(wú)關(guān)，但是運(yùn)輸成本和貨損成本都與配送的距離存在著正相關(guān)的關(guān)系，因此，模型中的最優(yōu)目標(biāo)可以將配送總成本最低轉(zhuǎn)換為配送的總路程最小，于是可以認(rèn)為在模擬計(jì)算中路徑最小就是配送成本最低，經(jīng)過(guò)目標(biāo)函數(shù)的轉(zhuǎn)換后不僅能簡(jiǎn)化計(jì)算，還能夠保證模型及模擬計(jì)算的準(zhǔn)確性。

四、基于遺傳算法的M快遞點(diǎn)部生鮮配送路徑優(yōu)化

（一）基礎(chǔ)數(shù)據(jù)

M點(diǎn)部的生鮮配送主要集中在以下9個(gè)客戶（A-J）點(diǎn)，文中將選取這9個(gè)客戶點(diǎn)作為模型中的配送點(diǎn)，在以單一固定的生鮮配送中心形式，主要考慮載重量（該快遞點(diǎn)部車(chē)輛的最大載重量為500kg）及車(chē)輛數(shù)的約束下，通過(guò)MATLAB模擬出最佳的生鮮配送路徑，最終實(shí)現(xiàn)科學(xué)、合理地將生鮮配送到各個(gè)客戶手上的目標(biāo)。配送中心（其標(biāo)號(hào)為“M”）及9個(gè)客戶的位置坐標(biāo)數(shù)據(jù)（經(jīng)緯度坐標(biāo)由百度地圖查詢得到）、客戶對(duì)生鮮產(chǎn)品的需求量如下表2所示。

表2 快遞點(diǎn)部9個(gè)客戶（A—J）位置及需求信息表

將其具體的位置信息通過(guò)MATLAB表現(xiàn)出來(lái)如下圖2所示。

圖2 M點(diǎn)部配送中心及9個(gè)客戶（A—J）位置坐標(biāo)圖

（二）假設(shè)及約束條件

為了便于對(duì)路徑進(jìn)行計(jì)算研究，將配送員進(jìn)行生鮮配送過(guò)程中的問(wèn)題能夠轉(zhuǎn)化為可以求解的數(shù)學(xué)模型，使得計(jì)算機(jī)的模擬結(jié)果與實(shí)際結(jié)果更加接近，此時(shí)需要對(duì)生鮮配送人員在配送過(guò)程中做出假設(shè)及約束。其中假設(shè)：

1.假設(shè)條件

（1）點(diǎn)部能夠給各個(gè)客戶點(diǎn)進(jìn)行配送；

（2）進(jìn)行生鮮配送的車(chē)輛規(guī)格以及行駛速度相同；

（3）配送車(chē)輛只從順豐瑯西點(diǎn)部出發(fā)，完成配送任務(wù)后必須回到點(diǎn)部，最終形成閉合回路；

（4）每個(gè)配送員對(duì)各個(gè)配送客戶的配送路線是已經(jīng)安排好的路線；

（5）當(dāng)客戶不在家或者拒簽時(shí)，訂單會(huì)返回點(diǎn)部；

（6）地點(diǎn)簡(jiǎn)化為一個(gè)點(diǎn)，以便得出具體的位置信息。

2.約束條件

（1）每輛配送車(chē)的實(shí)際載貨總量不大于該車(chē)的最大載貨量；（2）單個(gè)客戶僅對(duì)應(yīng)一個(gè)配送車(chē)輛的服務(wù)；

（3）車(chē)輛在完成上一個(gè)客戶點(diǎn)的配送后一定要給下一個(gè)客戶點(diǎn)配送或者返回到M點(diǎn)部。

（三）基于MATLAB的計(jì)算過(guò)程

由于在實(shí)際配送中，兩客戶點(diǎn)間的距離不是單純兩點(diǎn)之間的距離，本文采用百度地圖對(duì)上述9個(gè)客戶點(diǎn)進(jìn)行測(cè)量，得出它們之間的距離，具體的距離矩陣（單位：km）如表3所示。

表3 配送中心與客戶之間的距離矩陣

本模型主要是從路徑最小化入手，根據(jù)客戶的地理位置以及各個(gè)客戶點(diǎn)之間的距離，在滿足載重量以及車(chē)輛數(shù)目的前提下，利用MATLAB進(jìn)行編程，模型采用遺傳算法進(jìn)行求解，最終得到優(yōu)化路徑，具體如圖3所示。

圖3 遺傳算法求得最優(yōu)配送路線圖

在最優(yōu)的配送路徑中，共選用兩條路線對(duì)這9個(gè)客戶（A—J）點(diǎn)進(jìn)行配送，從上圖可看出，車(chē)輛對(duì)客戶的配送路線分別為：

第一條的配送路線：M—C—E—G—A—M，即配送中心M點(diǎn)部—南湖名都廣場(chǎng)—和興大夏—水產(chǎn)畜牧學(xué)?！樜鞑耸小渌椭行腗點(diǎn)部；

第二條的配送路線：M—D—J—H—F—B—M，即配送中心M點(diǎn)部—銘湖經(jīng)典—青湖中心—南寧三中—民歌湖—太平洋世紀(jì)廣場(chǎng)—配送中心M點(diǎn)部。

在此方案中，其具體的配送量和配送路程如表4所示。

表4 最優(yōu)方案的配送量以及路程

運(yùn)用MATLAB軟件得到遺傳算法最優(yōu)配送方案的最優(yōu)適應(yīng)度函數(shù)值隨迭代次數(shù)的變化情況如圖4所示。

圖4 適應(yīng)度值隨迭代次數(shù)的變化情況

從上圖4可以看出，適應(yīng)度值在迭代次數(shù)為160時(shí)，達(dá)到最優(yōu)解。

（四）計(jì)算結(jié)果

結(jié)合具體的問(wèn)題采用遺傳算法在滿足配送量以及車(chē)輛數(shù)目的情況下得出采用兩條路線方案的最優(yōu)配送路徑，第一條的配送路徑為：M—D—J—H—F—B—M，即配送中心M點(diǎn)部—南湖名都廣場(chǎng)—和興大夏—水產(chǎn)畜牧學(xué)校—瑯西菜市—配送中心M點(diǎn)部，路程為4.38km，配送量為150kg；第二條的配送路徑為：M—D—J—H—F—B—M，即配送中心M點(diǎn)部—銘湖經(jīng)典—青湖中心—南寧三中—民歌湖—太平洋世紀(jì)廣場(chǎng)—配送中心M點(diǎn)部，路程為6.32km，配送量為 134kg。兩條路線的總路程為10.7km。

五、結(jié) 論

快遞配送問(wèn)題是一個(gè)多元化復(fù)雜問(wèn)題，尤其在尋求經(jīng)濟(jì)效益與環(huán)境保護(hù)最優(yōu)組合上，其末端配送占據(jù)著整個(gè)物流配送成本中的大部分。如今生鮮電商快速發(fā)展，越來(lái)越多的人們選擇了線上下單線下取貨的方式，由此帶來(lái)的配送問(wèn)題已不容忽視。借助云大數(shù)據(jù)、數(shù)學(xué)模型來(lái)優(yōu)化配送線路已經(jīng)是企業(yè)配送線路優(yōu)化的發(fā)展趨勢(shì)。文中采用MATLAB軟件進(jìn)行遺傳算法的路徑優(yōu)化，也是基于以最低配送成本作為最終優(yōu)化目標(biāo)，考慮其配送成本與配送里程的關(guān)系，在結(jié)合實(shí)際情況忽略一些因素的情況下，將配送成本最低轉(zhuǎn)換為以配送路程最小作為最終的優(yōu)化目標(biāo)。通過(guò)軟件輔助計(jì)算得出M快遞點(diǎn)部對(duì)9個(gè)客戶點(diǎn)的最優(yōu)配送路徑為采用兩條路線進(jìn)行配送。另外在研究路徑優(yōu)化模型中的一些假設(shè)條件與約束條件可能會(huì)對(duì)最終結(jié)果造成一定的干擾，對(duì)研究的問(wèn)題還不夠完善，如何進(jìn)一步降低配送成本還需要進(jìn)行更加深入地研究。