基于改進遺傳算法的卷煙物流配送線路優(yōu)化模型構(gòu)建

0 引 言

配送線路優(yōu)化是卷煙物流配送工作中的重要環(huán)節(jié)。隨著物流業(yè)務(wù)的不斷發(fā)展，推進行業(yè)內(nèi)物流降本增效、個性化配送服務(wù)的建立和應(yīng)急物流保障服務(wù)體系的健全成為了煙草行業(yè)物流高質(zhì)量發(fā)展過程中亟需解決的重要問題。

本文以R縣配送業(yè)務(wù)作為研究對象，利用DMAIC管理模式開展物流配送線路優(yōu)化的試點探索，通過有效調(diào)整送貨線路、控制送貨人員的勞動強度和作業(yè)時間來保障卷煙物流配送工作高效運行。

1 算法概述

1.1 傳統(tǒng)的遺傳算法

遺傳算法是基于“適者生存”的一種高度并行、隨機和自適應(yīng)的優(yōu)化算法。它將問題的求解表示成“染色體”的適者生存過程，通過“染色體”群的逐代不斷進化，包括復(fù)制、交叉和變異等操作，最終收斂到“最適應(yīng)環(huán)境”的個體，從而求得問題的最優(yōu)解[1]。相對于一些常規(guī)的優(yōu)化算法，它在求解較為復(fù)雜的組合優(yōu)化問題時通常能夠快速獲得較好的優(yōu)化結(jié)果。

1.2 改進的遺傳算法

遺傳算法中起核心作用的就是交叉運算[2]。傳統(tǒng)遺傳算法的交叉運算是指染色體在遺傳過程中，依照一定規(guī)則互相交換特定位置的基因信息，從而產(chǎn)生繼承父代的大部分信息而又不同于父代的子代染色體[3]。

本文考慮到優(yōu)化后的配送線路必須涵蓋轄區(qū)內(nèi)的所有零售客戶，且訪銷周期調(diào)整盡量少的情況，在交叉運算方面做出了一些改變。改進的遺傳算法在交叉運算操作中，個體編碼路段按照窮舉法隨機進行交叉重組產(chǎn)生新線路，從而避免了在變異算子作用下對訪銷周期進行重新調(diào)整。圖1為改進后的遺傳算法概述圖。

圖1 改進的遺傳算法概述圖

2 編碼方式

2.1 配送線路

配送線路是指某臺單獨的送貨車在一個周期中某天的送貨路徑。截至2021年3月1日，R縣的配送線路共計14條，在每周工作5天的情況下，需要由3個班組來完成配送任務(wù)。

2.2 路段

每一條配送線路由不同路段組成，每個路段由連續(xù)排列的一部分客戶組成。在遺傳算法計算的過程中，每條路段被視為單個需要進行交叉重組的染色體。為便于拆分重組，以R縣城區(qū)一線為例，可拆分為“鎮(zhèn)政府”“南環(huán)東路（東段）”和“壩廠村”3個路段。如圖2所示。

圖2 R縣城區(qū)一線路段分布圖

2.3 編碼規(guī)則

傳統(tǒng)遺傳算法主要采用二進制方式編碼[4]，它使用的編碼集是由二進制符號0和1所組成的二值符號集{0，1}。對于一些連續(xù)函數(shù)的優(yōu)化問題，其存在連續(xù)函數(shù)離散化時的映射誤差，不利于反映問題的特定知識。改進的遺傳算法則參照符號編碼方法制定了一套編碼規(guī)則，通過設(shè)立中心點將所有路段按照距離中心點的遠近進行取值，具體的編碼規(guī)則如下。

2.3.1 按距離遠近設(shè)置一級編碼

如城區(qū)范圍內(nèi)的路段統(tǒng)一用“1”作為其一級編碼，鄉(xiāng)鎮(zhèn)范圍內(nèi)的路段則按照與城區(qū)的距離分別以“2”“3”作為其一級編碼。其中，離城區(qū)較近的區(qū)域，如R縣一六鎮(zhèn)和桂頭近郊（即靠近城區(qū)的5公里范圍內(nèi)）的一級編碼為“2”；離城區(qū)較遠的區(qū)域，如大橋鎮(zhèn)、大布鎮(zhèn)，包括桂頭圩鎮(zhèn)的一級編碼為“3”。

2.3.2 按線路位置設(shè)置二級編碼

將城區(qū)和鄉(xiāng)鎮(zhèn)的具體線路進行分類，并將其區(qū)域排列序號作為二級編碼。

2.3.3 按路段排序設(shè)置三級編碼

將每一條線路按不同街道、鄉(xiāng)村再劃分為1～3個路段，并用“a”“b”“c”等字母作為三級編碼。第三級編碼僅作為序號使用，不作為距離的判斷依據(jù)。

3 模型構(gòu)建

3.1 線路優(yōu)化原則

3.1.1 就近整合原則

就近整合原則是指在重組路線時，應(yīng)當(dāng)按照各路段的編碼盡可能地選取臨近路段合并為新線路，做到下一個配送路段是距當(dāng)前配送路段最近且配送較方便的。這樣做便于管理和操作，分析編碼時只須計算前2位編碼。

3.1.2 均衡運力原則

在配送過程中，綜合考慮服務(wù)零售戶數(shù)量、單車裝載卷煙數(shù)量、單車工作時長3種因素，以實現(xiàn)要素均衡。各因素應(yīng)滿足以下條件。

3.1.2.1 服務(wù)零售戶數(shù)量

每條重組之后的新線路，城區(qū)零售戶數(shù)量范圍須在90～130戶，農(nóng)網(wǎng)數(shù)量則在60～90戶。

3.1.2.2 單車裝載卷煙數(shù)量

依據(jù)零售戶訂單量的大小進行合理調(diào)配，城區(qū)線路卷煙配送量為4 000～6 000條，農(nóng)網(wǎng)卷煙配送量為3 000～5 000條。

3.1.2.3 單車工作時長

按照線路長短和耗時、與零售戶交接時間以及途經(jīng)較差道路所導(dǎo)致的送貨時間延長，綜合計算每條線路的基本工作時長。每條線路的日均送貨時長應(yīng)盡量控制在6～8小時。路線長短、耗時可參照地圖導(dǎo)航軟件數(shù)據(jù)，初步預(yù)估每戶的交接時間約為2.5分鐘，途經(jīng)較差道路所導(dǎo)致的送貨時間延長則由送貨員人工錄入。

3.2 設(shè)定適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是評價每個重組線路優(yōu)劣的函數(shù)，是獲得最優(yōu)配送方案的基本依據(jù)。本文將各方案的最終得分設(shè)置為其中各線路評分的平均值，根據(jù)線路優(yōu)化原則設(shè)計評價各線路的適應(yīng)度函數(shù)為。

式中，S指某一線路中各路段接近程度的評分，其評分范圍為0～40分。N指與各線路平均戶數(shù)接近程度的評分，其評分范圍為0～40分。T指某一線路中單車裝載卷煙數(shù)量和工作時長的評分，當(dāng)兩者同時達標時，T=20分，反之T=0分。F為所有方案的最終得分。將方案得分依次排列，大概設(shè)置90分（含）以上的為A類方案，80分（含）以上的為B類方案，80分以下的為C類方案。

3.3 運算過程

通過借鑒計算機關(guān)于網(wǎng)絡(luò)IP地址臨近關(guān)系的計算方法可對各路段的位置信息進行臨近程度分析。當(dāng)人工智能系統(tǒng)收到關(guān)于減少線路數(shù)量、增加配送任務(wù)、增減零售網(wǎng)點等優(yōu)化請求時，可自動選取臨近路段，在不超過單車配送能力的情況下，開展線路優(yōu)化重組。若需要精簡線路時，人工智能程序?qū)饤l解除線路，解除后的配送經(jīng)過點將依據(jù)戶數(shù)、配送量與距離等方面的參數(shù)要求分別按局部最小代價調(diào)整到其他相鄰路線。

生成所有新的線路組合方案后，系統(tǒng)將自動根據(jù)適應(yīng)度函數(shù)進行橫向?qū)Ρ仍u分。按照適應(yīng)度函數(shù)的判定結(jié)果，程序會自動選取出所有A類、B類方案供物流管理人員選擇出最優(yōu)方案后還可用百度地圖開放平臺對線路細節(jié)進行人工微調(diào)。

4 基于DMAIC管理模式進行案例應(yīng)用

本文選定R縣物流對接點作為試點區(qū)域，并基于DMAIC管理模式對改進的遺傳算法進行實踐應(yīng)用。如圖3所示。截至2021年3月1日，R縣零售客戶共822戶，配送線路共14條，其中城區(qū)有9條線路，鄉(xiāng)鎮(zhèn)有5條線路。

圖3 運用DMAIC管理模式進行案例應(yīng)用

4.1 D階段：編碼設(shè)置

將覆蓋轄區(qū)內(nèi)所有零售客戶門店的14條線路合理地劃分成32個路段，并為各個路段設(shè)置運算編碼。

4.1.1 R縣城區(qū)內(nèi)的路段編碼以1開頭

以位于城區(qū)最東端的物流對接點作為起始位置，其所在的候公渡線路區(qū)域的編碼為“1.1”，稍臨近的鷹峰東、新興線路區(qū)域的編碼為“1.2”，城區(qū)最遠端的鷹峰西、城西區(qū)域的編碼為“1.5”。具體線路按不同路段進行三級編碼，但第三級編碼不作為運算編碼使用。

4.1.2 鄉(xiāng)鎮(zhèn)線路則按其所在方向歸類編碼

其中東南方向包含一六鎮(zhèn)、桂頭鎮(zhèn)共計155戶零售客戶；東北方向為大橋鎮(zhèn)，共計79戶零售客戶；西南方向則包含了大布鎮(zhèn)和洛陽鎮(zhèn)2個區(qū)域，共計76戶零售客戶。 表1 為R縣卷煙物流配送路段編碼及零售客戶分布情況。

表1 R縣卷煙物流配送路段編碼及零售客戶分布情況

4.2 M階段：測量差距

優(yōu)化前，R縣的送貨里程為3 296公里，單車日均送貨量為51.95戶/車，當(dāng)月累積人均卷煙的配送效率為1 111.85萬支/人，低于全市平均水平的385.73萬支/人，圖4為2021年2月S市各縣級直屬單位人均卷煙配送效率情況。

圖4 2021年2月S市各縣級直屬單位人均卷煙配送效率

4.3 A階段：分析條件

根據(jù)前文的算法模型，通過分析配送線路的約束條件，對模型中的已知常量進行設(shè)置。

條件1：路段臨近程度。重組路線時，應(yīng)按照各路段的編碼盡可能地選取臨近路段合并為新線路，以便于管理和操作。分析編碼時只須計算前2位編碼。

條件2：單車配送能力。單車配送能力由服務(wù)零售戶數(shù)量、單車裝載卷煙數(shù)量和單車工作時長3個指標衡量。表2為單車配送能力指標賦值。

表2 單車配送能力指標賦值

4.4 I階段：線路優(yōu)化

4.4.1 實施過程

通過利用模型求解，R縣卷煙配送線路由14條優(yōu)化至9條，其中鄉(xiāng)鎮(zhèn)線路由4條優(yōu)化至3條，城區(qū)線路由10條優(yōu)化至6條；配送車輛由3臺減少至2臺。城區(qū)配送線路的具體優(yōu)化過程如圖5-7所示。

圖5 2021年3月優(yōu)化前城區(qū)線路分布圖示

圖6 2021年4月城區(qū)線路優(yōu)化結(jié)果

圖7 2021年7月城區(qū)線路優(yōu)化結(jié)果

4.4.2 利用百度地圖開放平臺優(yōu)化增量線路

百度地圖開放平臺是為開發(fā)者開發(fā)應(yīng)用軟件而推出的一套應(yīng)用調(diào)用接口；它為用戶提供在網(wǎng)站構(gòu)建時具有交互性的界面、多種數(shù)據(jù)處理服務(wù)和多種服務(wù)接口[5]，簡化了開發(fā)的復(fù)雜度，可以為卷煙配送線路優(yōu)化工作提供最合適的網(wǎng)點地圖定位服務(wù)。

由于城市化建設(shè)步伐加快，卷煙物流配送環(huán)境常因網(wǎng)點調(diào)整、銷量變化、路橋新設(shè)、市政維護等原因發(fā)生變化，以致配送線路需要進行及時的調(diào)整和優(yōu)化。針對此類情況，只需將變更的零售客戶經(jīng)緯度坐標錄入百度地圖開放平臺，便可及時地對配送線路進行動態(tài)優(yōu)化與調(diào)整。圖8為R縣城區(qū)二線配送路徑局部圖。

圖8 R縣城區(qū)二線配送路徑局部圖

4.5 C階段：效果檢測

2021年12 月，通過對R縣物流對接點的各項物流指標進行驗算分析，其送貨里程、送貨車次、配送費用、日均送貨戶數(shù)和人均配送效率5項指標都有明顯的優(yōu)化提升。如圖9和表3所示。

圖9 2021年2—9月人均卷煙配送效率趨勢圖

表3 R縣物流配送線路優(yōu)化測試效果對比統(tǒng)計表

5 結(jié) 論

本研究通過對遺傳算法的改進，結(jié)合DMAIC管理模式對R縣配送區(qū)域開展試點驗證，為卷煙物流配送探索了一種線路優(yōu)化的新模型，將智能化手段與卷煙物流配送業(yè)務(wù)進行創(chuàng)新性融合，進一步推動了綠色高效物流體系的建設(shè)與完善。未來人們還可利用“卷煙物流配送線路優(yōu)化模型”解決其他卷煙物流配送問題，如在柔性化配送和跨區(qū)域配送方面開展應(yīng)用，以進一步提升卷煙物流配送效率。