基于改進遺傳算法的卷煙物流配送線路優化模型構建

0 引 言

配送線路優化是卷煙物流配送工作中的重要環節。隨著物流業務的不斷發展，推進行業內物流降本增效、個性化配送服務的建立和應急物流保障服務體系的健全成為了煙草行業物流高質量發展過程中亟需解決的重要問題。

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

1 算法概述

1.1 傳統的遺傳算法

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

1.2 改進的遺傳算法

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

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

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

2 編碼方式

2.1 配送線路

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

2.2 路段

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

圖2 R縣城區一線路段分布圖

2.3 編碼規則

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

2.3.1 按距離遠近設置一級編碼

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

2.3.2 按線路位置設置二級編碼

將城區和鄉鎮的具體線路進行分類，并將其區域排列序號作為二級編碼。

2.3.3 按路段排序設置三級編碼

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

3 模型構建

3.1 線路優化原則

3.1.1 就近整合原則

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

3.1.2 均衡運力原則

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

3.1.2.1 服務零售戶數量

每條重組之后的新線路，城區零售戶數量范圍須在90～130戶，農網數量則在60～90戶。

3.1.2.2 單車裝載卷煙數量

依據零售戶訂單量的大小進行合理調配，城區線路卷煙配送量為4 000～6 000條，農網卷煙配送量為3 000～5 000條。

3.1.2.3 單車工作時長

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

3.2 設定適應度函數

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

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

3.3 運算過程

通過借鑒計算機關于網絡IP地址臨近關系的計算方法可對各路段的位置信息進行臨近程度分析。當人工智能系統收到關于減少線路數量、增加配送任務、增減零售網點等優化請求時，可自動選取臨近路段，在不超過單車配送能力的情況下，開展線路優化重組。若需要精簡線路時，人工智能程序將會逐條解除線路，解除后的配送經過點將依據戶數、配送量與距離等方面的參數要求分別按局部最小代價調整到其他相鄰路線。

生成所有新的線路組合方案后，系統將自動根據適應度函數進行橫向對比評分。按照適應度函數的判定結果，程序會自動選取出所有A類、B類方案供物流管理人員選擇出最優方案后還可用百度地圖開放平臺對線路細節進行人工微調。

4 基于DMAIC管理模式進行案例應用

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

圖3 運用DMAIC管理模式進行案例應用

4.1 D階段：編碼設置

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

4.1.1 R縣城區內的路段編碼以1開頭

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

4.1.2 鄉鎮線路則按其所在方向歸類編碼

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

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

4.2 M階段：測量差距

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

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

4.3 A階段：分析條件

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

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

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

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

4.4 I階段：線路優化

4.4.1 實施過程

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

圖5 2021年3月優化前城區線路分布圖示

圖6 2021年4月城區線路優化結果

圖7 2021年7月城區線路優化結果

4.4.2 利用百度地圖開放平臺優化增量線路

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

由于城市化建設步伐加快，卷煙物流配送環境常因網點調整、銷量變化、路橋新設、市政維護等原因發生變化，以致配送線路需要進行及時的調整和優化。針對此類情況，只需將變更的零售客戶經緯度坐標錄入百度地圖開放平臺，便可及時地對配送線路進行動態優化與調整。圖8為R縣城區二線配送路徑局部圖。

圖8 R縣城區二線配送路徑局部圖

4.5 C階段：效果檢測

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

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

表3 R縣物流配送線路優化測試效果對比統計表

5 結 論

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