基于蟻群算法的物流中心選址優(yōu)化設(shè)計(jì)與算法實(shí)現(xiàn)

陸麗丹，曹陸鋮

摘? 要：物流中心的選址應(yīng)在全面考慮選址影響因素基礎(chǔ)上，運(yùn)用數(shù)學(xué)的方法進(jìn)行量化比較。物流中心的優(yōu)化選址需要模型化、數(shù)量化，文章將蟻群算法應(yīng)用到物流中心優(yōu)化選址問(wèn)題中，給出模型的構(gòu)建和實(shí)現(xiàn)步驟，應(yīng)用Matlab編程驗(yàn)證模型和算法的有效性，以某種模型數(shù)據(jù)假設(shè)為例，給出一系列分析數(shù)據(jù)，從軟件分析結(jié)果中找出物流中心優(yōu)化選址方案，最終實(shí)驗(yàn)結(jié)果表明，利用蟻群算法求解最優(yōu)路徑時(shí)具有一定的優(yōu)越性。

關(guān)鍵詞：蟻群算法；物流中心；優(yōu)化選址；Matlab

中圖分類號(hào)：F252.14? ? 文獻(xiàn)標(biāo)志碼：A? ? DOI：10.13714/j.cnki.1002-3100.2023.11.004

Abstract： The location selection of logistics center should be based on the comprehensive consideration of the factors affecting the location selection， and the quantitative comparison should be carried out using mathematical methods. The optimal location of logistics center needs to be modeled and quantized. In this paper， ant colony algorithm is applied to the optimal location of logistics center， and the construction and implementation steps of the model are given. Matlab programming is used to verify the effectiveness of the model and algorithm. Taking a certain model data assumption as an example， a series of analysis data are given， and the optimal location scheme of logistics center is found out from the software analysis results. The final experimental results show that， ant colony algorithm has some advantages in solving the optimal path.

Key words： Ant Colony（AC）algorithm; logistics centre; optimize site selection; Matlab

物流中心選址與規(guī)劃是影響物流運(yùn)行效率的關(guān)鍵因素，研究物流中心選址問(wèn)題具有重要的現(xiàn)實(shí)意義，物流中心選址需要模型化、數(shù)量化，這是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，在運(yùn)籌學(xué)和理論計(jì)算機(jī)科學(xué)中非常重要。從圖論的角度來(lái)看，由于該問(wèn)題的可行解是所有頂點(diǎn)的全排列，隨著頂點(diǎn)數(shù)的增加，會(huì)產(chǎn)生n！增長(zhǎng)的組合爆炸。由于其在交通運(yùn)輸、物流配送等領(lǐng)域內(nèi)有著廣泛的應(yīng)用，國(guó)內(nèi)外學(xué)者對(duì)其進(jìn)行了大量的研究。早期的研究者使用精確算法求解該問(wèn)題，常用的方法包括：分枝定界法、線性規(guī)劃法、動(dòng)態(tài)規(guī)劃法等。但是，隨著問(wèn)題規(guī)模的增大，精確算法將變得無(wú)能為力。意大利學(xué)者Dorigo于20世紀(jì)90年代提出蟻群算法，可用于計(jì)算此類問(wèn)題，使計(jì)算于短時(shí)間內(nèi)收斂至較優(yōu)解。本文以物流中心優(yōu)化選址為應(yīng)用背景，通過(guò)建立數(shù)學(xué)模型，應(yīng)用Matlab編程對(duì)其進(jìn)行了算法驗(yàn)證，實(shí)驗(yàn)證明該方法能較好地解決物流中心優(yōu)化選址的問(wèn)題。

1? 問(wèn)題描述與分析

現(xiàn)實(shí)中有一類單配送中心選址問(wèn)題：在某區(qū)域中選擇合適配送中心，物流車從配送中心出發(fā)，單次遍歷所有配送點(diǎn)，作為一個(gè)配送周期。使用模型算法選擇最優(yōu)配送中心和最優(yōu)配送周期路線。配送周期可循環(huán)使用，以增大配送頻率。

對(duì)于單配送中心選址模型而言，林雄[1]曾提出目前所采用的連續(xù)模型（如重心法等）要求在區(qū)域中任意點(diǎn)皆可建造物流中心，但在現(xiàn)實(shí)中無(wú)法做到，而蟻群算法可優(yōu)化上述局限。核心思路在于，首先確定物流中心的備選地址，其次通過(guò)蟻群算法計(jì)算每一物流中心遍歷所有配送站的最短距離，從而進(jìn)行比較優(yōu)化。

2? 模型的建立

問(wèn)題的核心函數(shù)表達(dá)為：D■=minD■+D■+D■+…＋D■，D■。

其中：D■為所有配送點(diǎn)與一個(gè)可能的配送中心組成的距離矩陣（矩陣大小為n+1×n+1，n為配送點(diǎn)的個(gè)數(shù)）第j行，第k列的元素，X■，X■，…，X■，X■為配送站1，2，3，…，n和一個(gè)可能的配送中心i的重排列。

2.1? 原數(shù)據(jù)假設(shè)

假設(shè)區(qū)域中的配送點(diǎn)坐標(biāo)為：B=[1 534 1 559; 3 524 3 035; 2 336 1 488; 2 206 3 418; 2 055 2 874; 3 915 2 253; 3 242

1 535; 3 307 1 242; 4 242 1 476; 3 805 2 978; 3 095 2 461; 2 638 3 388; 2 790 3 246; 2 366 1 553; 3 868 2 329; 2 120 2 518;

1 771 1 195; 3 790 3 453; 4 294 1 121; 2 120 2 370; 2 342 2 044; 1 993 1 983; 4 209 2 400; 1 343 1 298; 3 612 1 375; 2 020

3 170; 4 196 1 770; 2 053 3 001; 3 146 847; 2 401 3 292]。

假設(shè)區(qū)域中可能的配送中心坐標(biāo)為：A=[1 761 1 203; 1 823 2 008; 2 068 1 827; 2 626 2 908; 3 837 2 788; 2 723 1 927;

2 382 2 165; 3 955 2 229; 1 516 1 410; 2 468 3 375; 3 207 2 821; 3 403 1 511; 2 211 3 195; 2 005 1 581; 1 345 2 126; 2 319

2 106; 2 150 1 199; 3 502 2 769; 2 681 744; 1 789 1 411; 3 746 719; 4 194 1 957; 1 758 1 017; 2 480 1 255; 2 266 2 591;

2 659 910; 2 862 1 851; 3 710 1 597; 2 135 3 529; 2 936 1 018]

以A1，：為例，將所有配送點(diǎn)和A1，：作為新的遍歷集合，記為C，配送點(diǎn)和配送中心分布圖如圖1所示。

2.2? 計(jì)算距離矩陣

計(jì)算其距離矩陣：

M，N=sizeC;

%M為問(wèn)題的規(guī)模M-1個(gè)配送點(diǎn)，1個(gè)配送中心

distance=zerosM，M; %用來(lái)記錄任意兩個(gè)站點(diǎn)之間的距離

%求任意兩個(gè)站點(diǎn)之間的距離

for m=1：M

for n=1：M

distancem，n=sqrtsumCm，：-Cn，：.^2;

end

end

距離矩陣distance為：■。

3? 算法的實(shí)現(xiàn)

定義如下參數(shù)：m為螞蟻的個(gè)數(shù)，a為信息素的重要程度，β為啟發(fā)式因子的重要程度，ρ為信息素蒸發(fā)系數(shù)，G為迭代次數(shù)，Q為信息素增加系數(shù)，distance為距離矩陣，η為啟發(fā)式因子η=1÷distance，τ為信息素矩陣，Tabu為禁忌表，R■為各代的最佳路線，L■為各代最佳路線的長(zhǎng)度（初始值假設(shè)為無(wú)窮大）。

初始時(shí)刻，設(shè)：所有路徑上的信息素都相等τ■t=0=0。螞蟻kk=1，2，…，m在運(yùn)動(dòng)過(guò)程中，根據(jù)各條路徑上的信息素大小以概率P■■t轉(zhuǎn)移方向，其計(jì)算公式為：P■■t=■。

在蟻群算法執(zhí)行過(guò)程中，Tabu禁忌表用于記錄螞蟻已經(jīng)走過(guò)的點(diǎn)，allowed■表示螞蟻未走過(guò)，可供選擇的點(diǎn)。

在每一個(gè)循環(huán)周期結(jié)束，進(jìn)入t+1時(shí)刻時(shí)，對(duì)各路徑上的信息素進(jìn)行調(diào)整（本文采用ant-circle模型）：

τ■t+1=1-ρ·τ■t+Δτ■t，t+1，Δτ■t，t+1=■Δτ■■t，t+1，Δτ■■t，t+1=■

其中：Δτ■■t，t+1表示第k只螞蟻在t，t+1時(shí)刻內(nèi)留在路徑i，j的信息素量，其值等于信息素增加系數(shù)Q除以第k只螞蟻?zhàn)哌^(guò)的路徑L■，路徑越短，信息素增加越多；Δτ■t，t+1表示本次循環(huán)中路徑i，j的信息素增加量；ρ為信息素蒸發(fā)系數(shù)，

τ■t+1表示現(xiàn)有信息素量。

算法的主要流程為：初始化參數(shù)，將m只螞蟻放到n個(gè)配送點(diǎn)上，根據(jù)概率及其禁忌表選擇路線，更新禁忌表，并計(jì)算待選擇配送點(diǎn)的概率，循環(huán)至完成所有遍歷。根據(jù)運(yùn)行結(jié)果，全局更新優(yōu)化信息素，清空禁忌表，重復(fù)上述操作，直至達(dá)到循環(huán)次數(shù)G。

以A1，：為例，將所有配送點(diǎn)和A1，：作為遍歷集合，記為C，其計(jì)算結(jié)果如圖2、圖3所示。

由圖可見(jiàn)，針對(duì)配送點(diǎn)和A1，：作為遍歷集合的情況，蟻群算法在循環(huán)次數(shù)150次時(shí)成功收斂到較優(yōu)解，路徑為

12 458.578 4。

這意味著如果以A1，：作為配送中心，單次配送需要12 458.578 4長(zhǎng)度的路程。接著，只需使用A2，：，A3，：等其他待選配送中心，做同樣上述操作，計(jì)算所需路程。此后對(duì)比所有方案，選擇最優(yōu)解作為配送中心。

Result_Table=zerosheightA，1;

parfor i=1：heightA

Result_Tablei，：=Ant_ColonyAi，：;

end

findResult_Table==minResult_Table

4? 結(jié)束語(yǔ)

本文在國(guó)內(nèi)外學(xué)者理論研究的基礎(chǔ)上，探討了利用蟻群算法在物流中心優(yōu)化選址問(wèn)題中的可行性，結(jié)合案例數(shù)據(jù)，對(duì)算法的有效性進(jìn)行了論證。應(yīng)用Matlab編程仿真后的實(shí)驗(yàn)結(jié)果表明，利用蟻群算法求解最優(yōu)路徑時(shí)具有一定的優(yōu)越性，對(duì)物流中心的優(yōu)化選址有一定的實(shí)踐參考價(jià)值。

參考文獻(xiàn)：

[1] 林雄. 基于蟻群算法考慮路線安排的單配送中心選址[J]. 物流科技，2009，32（10）：50-53.

[2] 曾勝，戴賢君，胡徐勝，等. 基于蟻群算法對(duì)調(diào)度車輛進(jìn)行路徑最優(yōu)化設(shè)計(jì)[J]. 自動(dòng)化與儀表，2022，37（4）：89-93.

[3] 劉全明. 新舊能源物流汽車替代過(guò)程中的博弈和效益優(yōu)化仿真研究[D]. 北京：北京交通大學(xué)，2020.

[4] 趙長(zhǎng)鮮，方木云. 基于貪心算法的物流配送系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 軟件工程，2020（5）：21-23.

[5] 陳雄，袁楊. 一種機(jī)器人路徑規(guī)劃的蟻群算法[J]. 系統(tǒng)工程與電子技術(shù)，2008（5）：952-955.

[6] 楊俊闖，趙超. K-Means聚類算法研究綜述[J]. 計(jì)算機(jī)工程與應(yīng)用，2019（23）：7-14.

[7] 張松燦，普杰信，司彥娜，等. 蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用綜述[J]. 計(jì)算機(jī)工程與應(yīng)用，2020（8）：10-19.

[8] 蔣大成. 基于數(shù)據(jù)挖掘的農(nóng)產(chǎn)品物流配送中心選址研究[D]. 長(zhǎng)沙：湖南農(nóng)業(yè)大學(xué)，2018.

[9] 羅慧，蹇興亮，盧偉. 基于動(dòng)態(tài)蟻群算法的模擬電路最優(yōu)測(cè)點(diǎn)選擇[J]. 儀器儀表學(xué)報(bào)，2014（10）：2231-2237.

[10] 江明，王飛，葛愿，等. 基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J]. 儀器儀表學(xué)報(bào)，2019，40（2）：113-121.

[11] 丁建立，陳增強(qiáng)，袁著祉. 遺傳算法與螞蟻算法的融合[J]. 計(jì)算機(jī)研究與發(fā)展，2003（9）：1351-1356.

[12] 王芳，李昆鵬，袁明新. 一種人工勢(shì)場(chǎng)導(dǎo)向的蟻群路徑規(guī)劃算法[J]. 計(jì)算機(jī)科學(xué)，2014，41（S2）：47-50.