蟻群優化算法在圖書配送路徑規劃中的應用研究

宇婷

摘 ?要： 針對圖書物流配送中的多目標優化問題，提出一種基于蟻群優化算法的圖書配送路徑規劃模型，使配送成本最小化。首先對圖書物流配送路徑規劃模型進行分析，并選擇作業成本法對成本目標進行優化;然后采用單親遺傳混合蟻群算法對建立的模型進行求解，解決全局優化問題和求解效率問題。以某圖書配送中心為例進行優化仿真測試，驗證了模型的有效性。相比傳統的人工方案，采用的圖書物流配送路徑規劃模型及單親遺傳混合蟻群算法的配送方案有效降低了物流配送作業的成本。

關鍵詞： 圖書配送; 路徑規劃; 蟻群算法; 遺傳算法; 模型求解; 成本降低

中圖分類號： TN98?34; TP393 ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）15?0113?03

Application of ant colony optimization algorithm in book distribution path planning

YU Ting

（Zhengzhou University of Industry Technology， Zhengzhou 450000， China）

Abstract： Aiming at the problem of multi?objective optimization in book logistics distribution， a book distribution path planning model based on ant colony optimization algorithm is proposed to minimize the distribution cost. The book logistics distribution route planning model is analyzed， and the activity cost method is selected to optimize the cost target. The single?parent genetic hybrid ant colony optimization algorithm is used to solve the established model， which can solve the global optimization problem and solution efficiency. The optimization simulation test was carried out by taking a book distribution center as the example to verify the validity of the model. In comparison with the traditional manual scheme， the distribution scheme of book logistics distribution path planning model and single?parent genetic hybrid ant colony optimization algorithm can reduce the logistics distribution cost effectively.

Keywords： book distribution; path planning; ant colony algorithm; genetic algorithm; model solution; cost reduction

0 ?引 ?言

隨著經濟的快速發展，我國的GDP已經連續保持高速增長，人們的生活在物質方面得到了長足的進步， 生活富足。與此同時，人們的娛樂和文化需求日益增長。圖書作為一種傳統的知識載體，在人類歷史上扮演著十分重要的作用，是人類智慧的結晶。圖書能夠在很大程度上滿足人們精神文化需求，提高知識水平，提升文明素養，因此，近幾年來圖書出版與發行業能夠維持穩定的增長趨勢[1]。但是，隨著用戶需求和圖書數量的不斷增多，圖書物流配送問題成為近期研究的熱點[2?3]。

如何在保障配送效率和準確率的前提下，盡可能地降低圖書配送的作業成本是圖書物流管理系統的關鍵。隨著計算機、應用數學和網絡交通等學科的交叉研究，作為NP問題的車輛路徑是解決圖書物流管理系統關鍵的有效手段[4]。近期，啟發式算法求解車輛路徑問題成為研究的新途徑。文獻[5]采用蟻群算法對周期性車輛路徑問題進行求解，并提出采用兩種改進措施（多維信息素的運用和基于掃描法的局部優化方法）來提高算法的性能，表現出顯著的性能提升。算法測試結果驗證了提出方法的可行性。相比傳統的遺傳算法，提出的蟻群優化遺傳算法表現出較好的性能。針對最小最大車輛路徑求解問題，文獻[6]提出一種動態自適應蟻群優化算法。該算法采用動態最大最小螞蟻系統策略調整最優解，每次迭代更新將作為當前信息素矩陣最大值的函數，并通過灰色模型預測和信息素矩陣的邊界控制來增強蟻群算法參數的自適應性能。

與其他相關的蟻群算法相比，單親遺傳混合蟻群算法收斂速度更快，具有更好的優化性能和應用效果。因此，本文提出一種基于蟻群優化算法的圖書配送路徑規劃模型，使配送成本最小化。仿真測試結果驗證了提出方法的可行性。實驗結果表明，基于單親遺傳混合蟻群算法的圖書物流配送路徑規劃模型表現出較好的性能。

1 ?圖書物流配送路徑規劃模型

1.1 ?優化目標選擇

物流配送車輛調度過程需要根據貨物和車輛信息在配送區域劃分后進行車輛的具體安排。其中，配送區域劃分涉及配送中心分布和需求點分布。用戶需求一般包括訂貨信息和退貨信息，并需要事先進行分類匯總。在車輛安排完成后，需要根據交通狀況、客戶的具體位置和送貨時間來選擇配送路線，這時涉及模型的兩個關鍵指標：交貨時間信息和運輸成本費用，這也是選擇算法的優化目標。在選擇完成后，根據配送路線和配送順序進行車輛裝配并完成配送，通常會對車輛的位置進行周期采集跟蹤。

通過上述分析，可以將配送作業的優化目標分為：車輛利用率高;準時送達;配送距離最短;配送成本最低;每噸貨物運送1 km所需要的運費最少。

由于圖書物流配送的行業特征，對配送的效率要求不是很高，最大的需求點是降低成本，因此本文將降低配送成本作為配送作業的優化目標。

1.2 ?基于作業成本法的模型優化

圖書物流中心配送模型研究已經較為成熟，因此本文重點采用作業成本法對現有圖書物流配送的車輛路徑規劃問題的數學模型進行優化。

通過圖書配送成本項分析，采用作業成本法計算優化目標后，車輛路徑規劃問題的數學模型的形式如下：

2 ?單親遺傳混合蟻群算法

求解多目標優化的車輛路徑問題時，與基本蟻群算法相比，單親遺傳混合蟻群算法具有計算效率高、收斂性好等優點，尤其單點單親遺傳混合蟻群算法不僅具有較好的計算性能，而且具有較高的穩定性。因此，本文引入單親遺傳混合蟻群算法對構建的模型進行求解。

2.1 ?蟻群算法求解路徑規劃問題

設蟻巢的螞蟻數為[R]，需要優化的元素集合為[D]，[Dφi]表示其第[i][（1≤i≤n）]個元素。為實現初始種群求解問題，在本文中需要優化的所有參數的數量為[n]。假設這些元素[φi]存在[K]種數值，則[ζj（Dφi）（0）]為初始條件下第[j]個元素的信息素。

重復執行以上過程直到允許的最大迭代次數，或者所有螞蟻均獲得唯一個元素，即得到了優化后的初始種群相關參數。

2.2 ?單親遺傳混合蟻群算法的實現

傳統蟻群?遺傳算法在通過蟻群算法生成初始種群之后，需要繼續執行遺傳操作。遺傳操作的主要內容為：選擇算子、交叉算子和變異算子[6]。傳統遺傳過程的交叉算子操作會存在計算復雜度較大和早熟收斂現象，文獻[7]將單親遺傳算法和基本蟻群算法相結合，使其優勢互補，并利用單親遺傳算法的特點，構建出兩種求解該問題的單親遺傳混合蟻群算法。因此針對構建的成本優化圖書物流配送路徑規劃模型引入單親遺傳混合蟻群算法，以便提高收斂速度并獲取更優解，單親遺傳混合蟻群算法的流程如圖1所示。

圖1 ?單親遺傳混合蟻群算法流程

3 ?實驗結果與分析

為了驗證提出的圖書物流配送路徑規劃問題模型及單親遺傳混合蟻群算法的可行性，以2018年10月—12月某省會城市圖書物流中心為例，進行某轄區內圖書銷售網點配送優化和仿真。該轄區內圖書銷售網點共9個，配送的貨物種類為一般印刷圖書。中心同類型配送車輛共6輛。車輛固定成本因子為102元 /（輛·次）。

3.1 ?算法性能分析

經過100次仿真運算，設置最大迭代次數均為200。優化前的配送路徑如圖2所示。經過單親遺傳蟻群算法計算合理的配送順序后，優化后的揀選路徑如圖3所示。

圖2 ?優化前的配送路徑（9網點）

圖3 ?優化后的配送路徑（9網點）

3.2 ?配送方案比較

最后，將提出模型計算出的配送方案與人工經驗設計的配送方案[8]進行對比分析，如表1所示。

表1 ?配送方案比較

從表1可以看出，相比現有人工設計的配送方案，本文圖書物流配送路徑規劃問題模型即單親遺傳混合蟻群算法的配送方案配送成本降低了22.1%，配送距離減少了15.9%。這說明單親遺傳混合蟻群算法在一定程度上克服了收斂“早熟”，得到了全局最優解。

4 ?結 ?語

本文提出一種基于蟻群優化算法的圖書配送路徑規劃模型，使配送成本最小化。結合某圖書物流中心的配送實例進行案例分析，驗證了模型的有效性。同時，通過算法的比較分析，證明單親遺傳混合蟻群算法具有較好的全局最優和快速收斂性能。但是，算法的復雜性有一定的提高，后續將對并行計算和算法步驟簡化開展進一步研究。

參考文獻

[1] MILLIOT J. The book publishing industry [J]. JRC?IPTS， 2014， 2（6）： 319?339.

[2] WOLL T， RACCAH D. Publishing for profit： successful bottom?line management for book publishers [J]. Library management， 2014， 13（8）： 16?17.

[3] WANG C， GUAN Z， SHAO X， et al. Simulation?based optimization of logistics distribution system for an assembly line with path constraints [J]. International journal of production research， 2014， 52（12）： 3538?3551.

[4] NIU Y F， LAM W H K， GAO Z. An efficient algorithm for evaluating logistics network reliability subject to distribution cost [J]. Transportation research Part E， 2014， 67（C）： 175?189.

[5] 蔡婉君，王晨宇，于濱，等.改進蟻群算法優化周期性車輛路徑問題[J].運籌與管理，2014（5）：70?77.

CAI Yijun， WANG Chenyu， YU Bin， et al. Improved ant colony algorithm for optimizing periodic vehicle routing problem [J]. Operations research and management science， 2014（5）： 70?77.

[6] 葛斌，韓江洪，魏臻，等.最小最大車輛路徑問題的動態自適應蟻群優化算法[J].模式識別與人工智能，2015，28（10）：930?938.

GE Bin， HAN Jianghong， WEI Zhen， et al. Dynamic adaptive ant colony optimization algorithm for minimum and maximum vehicle routing problem [J]. Pattern recognition & artificial intelligence， 2015， 28（10）： 930?938.

[7] 劉云，張惠珍.多目標帶時間窗的車輛路徑問題的單親遺傳混合蟻群算法[J].公路交通科技，2016，33（6）：95?100.

LIU Yun， ZHANG Huizhen. Single?parent genetic hybrid ant colony algorithm for vehicle routing problem with multiple time windows [J]. Journal of highway and transportation research and development， 2016， 33（6）： 95?100.

[8] REN Y， HU L， MA Y. Logistics distribution route optimization method for peach products transport [C]// 2015 International Conference on Measuring Technology & Mechatronics Automation. Nanchang： IEEE， 2015： 1?8.