蟻群優(yōu)化算法在圖書配送路徑規(guī)劃中的應(yīng)用研究

宇婷

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

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

中圖分類號(hào)： TN98?34; TP393 ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 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 ?引 ?言

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

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

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

1 ?圖書物流配送路徑規(guī)劃模型

1.1 ?優(yōu)化目標(biāo)選擇

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

通過上述分析，可以將配送作業(yè)的優(yōu)化目標(biāo)分為：車輛利用率高;準(zhǔn)時(shí)送達(dá);配送距離最短;配送成本最低;每噸貨物運(yùn)送1 km所需要的運(yùn)費(fèi)最少。

由于圖書物流配送的行業(yè)特征，對(duì)配送的效率要求不是很高，最大的需求點(diǎn)是降低成本，因此本文將降低配送成本作為配送作業(yè)的優(yōu)化目標(biāo)。

1.2 ?基于作業(yè)成本法的模型優(yōu)化

圖書物流中心配送模型研究已經(jīng)較為成熟，因此本文重點(diǎn)采用作業(yè)成本法對(duì)現(xiàn)有圖書物流配送的車輛路徑規(guī)劃問題的數(shù)學(xué)模型進(jìn)行優(yōu)化。

通過圖書配送成本項(xiàng)分析，采用作業(yè)成本法計(jì)算優(yōu)化目標(biāo)后，車輛路徑規(guī)劃問題的數(shù)學(xué)模型的形式如下：

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

求解多目標(biāo)優(yōu)化的車輛路徑問題時(shí)，與基本蟻群算法相比，單親遺傳混合蟻群算法具有計(jì)算效率高、收斂性好等優(yōu)點(diǎn)，尤其單點(diǎn)單親遺傳混合蟻群算法不僅具有較好的計(jì)算性能，而且具有較高的穩(wěn)定性。因此，本文引入單親遺傳混合蟻群算法對(duì)構(gòu)建的模型進(jìn)行求解。

2.1 ?蟻群算法求解路徑規(guī)劃問題

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

重復(fù)執(zhí)行以上過程直到允許的最大迭代次數(shù)，或者所有螞蟻均獲得唯一個(gè)元素，即得到了優(yōu)化后的初始種群相關(guān)參數(shù)。

2.2 ?單親遺傳混合蟻群算法的實(shí)現(xiàn)

傳統(tǒng)蟻群?遺傳算法在通過蟻群算法生成初始種群之后，需要繼續(xù)執(zhí)行遺傳操作。遺傳操作的主要內(nèi)容為：選擇算子、交叉算子和變異算子[6]。傳統(tǒng)遺傳過程的交叉算子操作會(huì)存在計(jì)算復(fù)雜度較大和早熟收斂現(xiàn)象，文獻(xiàn)[7]將單親遺傳算法和基本蟻群算法相結(jié)合，使其優(yōu)勢(shì)互補(bǔ)，并利用單親遺傳算法的特點(diǎn)，構(gòu)建出兩種求解該問題的單親遺傳混合蟻群算法。因此針對(duì)構(gòu)建的成本優(yōu)化圖書物流配送路徑規(guī)劃模型引入單親遺傳混合蟻群算法，以便提高收斂速度并獲取更優(yōu)解，單親遺傳混合蟻群算法的流程如圖1所示。

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

3 ?實(shí)驗(yàn)結(jié)果與分析

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

3.1 ?算法性能分析

經(jīng)過100次仿真運(yùn)算，設(shè)置最大迭代次數(shù)均為200。優(yōu)化前的配送路徑如圖2所示。經(jīng)過單親遺傳蟻群算法計(jì)算合理的配送順序后，優(yōu)化后的揀選路徑如圖3所示。

圖2 ?優(yōu)化前的配送路徑（9網(wǎng)點(diǎn)）

圖3 ?優(yōu)化后的配送路徑（9網(wǎng)點(diǎn)）

3.2 ?配送方案比較

最后，將提出模型計(jì)算出的配送方案與人工經(jīng)驗(yàn)設(shè)計(jì)的配送方案[8]進(jìn)行對(duì)比分析，如表1所示。

表1 ?配送方案比較

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

4 ?結(jié) ?語

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

參考文獻(xiàn)

[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ìn)蟻群算法優(yōu)化周期性車輛路徑問題[J].運(yùn)籌與管理，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] 葛斌，韓江洪，魏臻，等.最小最大車輛路徑問題的動(dòng)態(tài)自適應(yīng)蟻群優(yōu)化算法[J].模式識(shí)別與人工智能，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] 劉云，張惠珍.多目標(biāo)帶時(shí)間窗的車輛路徑問題的單親遺傳混合蟻群算法[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.