基于重心法和禁忌搜索算法的配送中心選址

褚東亮 李帆

[摘要]在考慮運輸費用和運輸碳排放成本的因素下，研究了配送中心的選址問題。針對重心法在配送中心選址中存在的局限性，在重心法的基礎上，通過禁忌搜索算法（Tabu Search Algorithm，TSA），進一步優(yōu)化選址，從而選出適合建立配送中心的城市。以Z公司為例，綜合運用重心法和TSA進行選址，以運輸成本為目標同時與位置度量法、重心法與層次分析法相結(jié)合的選址結(jié)果分別進行對比，證明了重心法與TSA在配送中心選址中的實用可行性和優(yōu)越性。

[關(guān)鍵詞]配送中心;選址;重心法;禁忌搜索算法

[中圖分類號]F252.14???? [文獻標識碼]A[文章編號]1005-152X（2022）03-0063-06

Site Selection of Distribution Centers Based on Centroid Method and Tabu Search Algorithm

CHU Dongliang， LI Fan

（Beijing Key Laboratory of Logistics System &Technology（School of Logistics， Beijing Wuzi University）Beijing Tongzhou 101149， China）

Abstract： Considering the transportation and carbon emission cost， the paper studied the site selection of distribution centers. In view of the limitations of the centroid method in this problem， the paper combined the centroid method and the tabu search algorithm so as to pick out suitable cities to host the distribution centers. Taking the company Z as an example， it used centroid method and tabu search algorithm comprehensively for site selection. With the goal of transportation cost optimization， it compared the result from the location metric method and from the method of this paper， which proved the feasibility and superiority of the centroid method and TSA in distribution center site selection.

Keywords： distribution center; site selection; centroid method; tabu search algorithm

0 引言

配送中心被稱為物流系統(tǒng)的中樞或樞紐，是物流系統(tǒng)中的重要設施。而配送中心建設成本高，并且建成之后難以進行遷移，所以合理的配送中心選址能夠做到在盡量控制成本的情況下，提升物流服務水平，使企業(yè)在同類中脫穎而出。因此配送中心選址的合理性與實現(xiàn)企業(yè)物流降本增效有密切聯(lián)系，配送中心的選址能夠影響企業(yè)未來的發(fā)展。

國外在選址問題方面的研究開始得比較早。 Alfred，等[1]是最早提出選址理論的，其思索的選址問題是選定一個倉庫的方位，使倉庫到幾個分散的需求點的距離最短。Bettinger，等[2]較早采用TSA，從多個方案中選取最佳的方案來計劃木材的采伐。在此基礎上國內(nèi)外學者都對選址問題進行了進一步研究，在研究方法上不斷創(chuàng)新和改進。楊娜娜，等[3]將 SIC模型應用于東莞市公交冗余站點優(yōu)化中，采用 TSA進行最優(yōu)求解。楊珺，等[4]提出了電動汽車換電站選址與配送路徑優(yōu)化問題，建立了使用TSA-改進 Clarke-Wright 節(jié)省的兩階段啟發(fā)式算法來求解模型。陳詩軍，等[5]對TSA 的代價函數(shù)、鄰域產(chǎn)生規(guī)則以及解禁規(guī)則進行了改進，通過這種改進算法對基站布局進行了優(yōu)化。Mauricio，等[6]采用基于TSA 的方法來解決容量p值中位數(shù)問題，對肉制品公司的配送中心進行了選址。Alavi S，等[7]為降低配送中心到制造商的運輸成本建立了模型，運用TSA求解該模型。Zhen Lu，等[8]針對大規(guī)模問題使用TSA，驗證了其所提出的確定配送中心位置的模型的有效性。

由此可以看出，TSA在選址優(yōu)化方面的運用是有跡可循的，通過與其它算法相結(jié)合，互相彌補，能夠有效解決一些問題。而重心法通過與其它算法聯(lián)合使用，同樣能夠解決最優(yōu)選址決策問題，提高選址的精確性與合理性。

運輸成本和碳排放一直是學者在各類優(yōu)化問題中考慮的重要因素。李明，等[9]在多物流配送中心選址布局問題的研究中，其目標函數(shù)設定為直接與間接運輸成本之和。戴卓[10]關(guān)于三層物流網(wǎng)絡研究問題中，運輸成本是總成本的重要構(gòu)成因素。孟燕萍，等[11]在動態(tài)應急物資選址問題中，建立了以最小化應急物資運輸成本和災民等待物資心理懲罰成本為目標的多目標混合整數(shù)規(guī)劃模型。戢守峰，等[12]考慮存在擁堵和限速的路況依賴下，構(gòu)建了以經(jīng)濟總成本最小和碳排放量最小為目標的多目標模型。王夢夢，等[13]以最小化成本和碳排放為目標，建立了供應鏈優(yōu)化模型。蔣海青，等[14]在開放選址-路徑問題中考慮了碳排放的因素。

由于重心法本身的局限性，選出的位置可能并不是建立配送中心最優(yōu)的位置，就需要進一步的計算。首先采用重心法進行選址，對得到的地理位置進行分析探討，在該地建立配送中心是否具有可行性，若是，則建立配送中心;若否，則通過觀察地圖得到被選中城鎮(zhèn)附近的城鎮(zhèn)，通過TSA在這些附近的城鎮(zhèn)中選出最適合建立配送中心的城鎮(zhèn)，作為配送中心建立的地址，計算思路流程如圖1所示。

1 配送中心選址模型構(gòu)建

本文以城市的配送中心為研究對象，對配送中心的選址問題進行研究。設有n個需求點，xi為需求點的橫坐標，yi為需求點的縱坐標，需求點的坐標為各個需求點的經(jīng)緯度 M（xi，yi）（i=1，2， …，n），例如北京（116，39），擬建立的配送中心的坐標為（x，y）。

1.1 模型假設

重心法和禁忌搜索算法的配送中心選址模型構(gòu)建基于以下假設條件：

（1）配送中心到需求點之間的道路問題忽略不計;

（2）暫時不考慮工程建設項目的總投資，比如建立配送中心地址的土地價格等;

（3）假設運輸費用是線性函數(shù)，隨著距離的增加而增加相同的比例;

（4）需求點的需求量都是已知條件，并且需求點與需求數(shù)量不變;

（5）假設經(jīng)線緯線是坐標系，各個地點的經(jīng)緯度為各個需求點的坐標，并且需求都來自于這一個點;

（6）不考慮運輸車輛遇到不可抗力時增加的碳排放成本;

（7）假設運輸過程中車輛運載量與所需消耗的燃油量呈線性函數(shù)。

1.2 符號說明

本文中涉及的符號及其含義如下：

ci表示貨物從（x，y）運送到需求點M（xi，yi）所在地所需費用;

hi表示運輸費率，即每運送1km 的1t貨物所需費用;

di表示從配送中心到需求城市的距離;

wi表示貨物的運輸量;

λ表示車輛的平均耗油量;

m表示車輛負載;

α表示燃油的二氧化碳排放系數(shù);

H1表示貨物的運輸費用;

H2表示貨物運輸?shù)奶寂欧懦杀?

K為常數(shù)參數(shù)，較正從坐標到距離計算過程中的誤差;

Q表示備選配送中心的位置。

1.3 模型構(gòu)建

本文主要考慮了配送過程中的運輸費用及運輸過程中的碳排放成本。

運輸費用：

因此，兩個目標分別為運輸費用 H1和碳排放成本H2，即總目標函數(shù)為運輸成本H。

1.4 算法設計

1.4.1 重心法。重心法只考慮配送中心與需求點之間的距離 d1i ，故通過式（5）作為距離計算公式對運輸費用進行計算。

求解運費的最小值，即對函數(shù) H1（x，y）求極值問題，分別對x，y求偏導數(shù)，令偏導數(shù)為零，解得：

由于算式中含有di1，而 di1含有未知數(shù)，所以首先假設開始時的 x 和 y 是生產(chǎn)基地的位置，再進行迭代，直到求出最小的運輸成本，以及最小成本所對應的坐標。

1.4.2 TSA模型。初始解：由于TSA對初始解的要求比較高，所以初始解設定為由重心法計算出來的選址地點。

代價函數(shù)：由于得到的是地理坐標，也就是經(jīng)緯度，所以要通過計算求出實際配送距離。假設A，B 兩點之間的地理坐標分別為A（X1，Y1）、B（X2，Y2），經(jīng)過 AB兩點的大圓的劣弧長度即為兩點的實際距離。以地心作為原點坐標，赤道平面為XOY平面，以0度經(jīng)線圈所在的平面建立空間直角坐標系，則AB兩點的球坐標分別為 A（RcosX1 cos Y1，R sin Y1 cos Y1， R sin Y1）， BR cosX2 cos Y2，R sinX2 cos Y2，R sin Y2，其中 R 為地球半徑6 370km，則AB兩點之間的實際距離為：

化簡得到：

由前文的優(yōu)化目標可知，選址過程中的運輸費用和運輸碳排放成本即為由式（9）帶入式（3）得到的代價函數(shù)，見式（10）。

鄰域：鄰域是指初始解附近有建立配送中心條件的地區(qū)的坐標。鄰域產(chǎn)生規(guī)則是對這些坐標進行迭代，例如把配送中心擬選定的位置標號為ABCD，對于路徑1A23，將 A 替換成 B，就得到新的路徑1B23。

禁忌表：禁忌最先出現(xiàn)的距離值。禁忌表記錄了最近搜索過程中已經(jīng)出現(xiàn)的解，這些解禁止在近期內(nèi)重復出現(xiàn)，從而避免陷入局部最優(yōu)解。達到一定的迭代次數(shù)之后，禁忌表會依次釋放這些禁忌對象，對象被釋放之后，重新參與到計算中。設置適當?shù)慕砷L度，在該解添加到禁忌表中時，對禁忌長度進行初始化。與此同時，寫入加入禁忌表時解的代價值。算法每次對禁忌表進行寫入時，更新禁忌表，對上一步禁忌的元素的長度減1。直到禁忌長度為0時，解禁。

解禁規(guī)則：當有解優(yōu)于現(xiàn)今為止最好的解并且已經(jīng)被禁忌時，解禁這個解，并且將這個解當作是現(xiàn)今為止最好的解。如果沒有優(yōu)于現(xiàn)今為止最優(yōu)的解，即所有的解都解禁也沒有比當前最優(yōu)解更好的解了，那么，把禁忌表中代價值有所降低的解解禁。如果沒有代價已經(jīng)降低的可選的解存在，那么在禁忌表中選擇代價最低的進行解禁。

終止規(guī)則：當?shù)竭_最大迭代次數(shù)時，程序終止。根據(jù)以上的參數(shù)設計進行計算迭代即可。

2 實例驗證及結(jié)果分析

2.1 問題分析

Z公司承接的重點客戶在杭州、重慶、長春有三個生產(chǎn)基地，由于業(yè)務拓展到全國各地，公司決定建立配送中心服務客戶和自身發(fā)展。按照傳統(tǒng)的地區(qū)劃分，把全國劃分為華中、華北、華東、華南、西南以及西北地區(qū)和東北地區(qū)。在不同的區(qū)域建設各自的配送中心，這個配送中心就承擔該區(qū)域內(nèi)的物資配送的任務。

由于客戶公司在杭州、重慶和長春有生產(chǎn)基地，杭州的月生產(chǎn)量為4萬t，重慶的月生產(chǎn)量為4萬t，長春的月生產(chǎn)量為2萬t，并且其生產(chǎn)基地本身具備配送中心的功能，故為了節(jié)省成本，在東北地區(qū)、華北地區(qū)和西南地區(qū)暫不打算建立單獨的配送中心，并且由于長春現(xiàn)在運往華北地區(qū)的線路比較成熟，交通比較便利，暫不打算在華北地區(qū)建立配送中心，只需在西北和華南地區(qū)建立配送中心。由于重慶距離西北地區(qū)較近，為方便產(chǎn)品運輸，由重慶的生產(chǎn)基地運往西北各個城市。雖然杭州生產(chǎn)基地距離華南地區(qū)較近，但是根據(jù)需求量數(shù)據(jù)統(tǒng)計得出杭州生產(chǎn)基地的生產(chǎn)量不足以支持華東地區(qū)和華北地區(qū)兩個地區(qū)的需求，所以華南地區(qū)從另一稍近生產(chǎn)地重慶運往各個需求點。

2.2 計算

首先通過重心法進行選址計算。由于是從重慶的生產(chǎn)基地運往新建的配送中心，故初始坐標假設為重慶生產(chǎn)基地的坐標，再進行迭代。通過對表1數(shù)據(jù)進行整理和分析，運費率約為0.20CNY/t/km（運費數(shù)據(jù)來自鐵路貨物運費查詢官網(wǎng)）。

通過表1計算出的運費H1，令K=111，對經(jīng)緯度坐標進行計算，把坐標距離轉(zhuǎn)化為估算的實際距離d1i，由需求量可得到運輸量為wi，把這些參數(shù)帶入到式（1），就能夠得到運輸費用;λ為1.25kg/t ·km，α為燃油二氧化碳排放系數(shù)[14]，為2.63kg ·L-1，碳稅價格依據(jù)澳大利亞政府碳稅法案中相關(guān)標準，每噸碳排放征收23澳元，折合成人民幣約每千克 CO2征收0.11425元[15-17]。以此計算碳排放成本H2。把迭代的初始坐標設置為重慶市的坐標，再用線性規(guī)劃進行求解，就能夠得到重心法求解出的兩個配送中心的備選地址，其地理坐標分別 Q1（103，35.9998）和 Q2（112.9999，22.99991）。

通過百度地圖的坐標拾取系統(tǒng)得到關(guān)于該位置的相關(guān)信息。對于位置 Q2來說，選中的位置雖然在佛山丹灶特大橋，但是該點附近不僅建有多個物流中心，而且還有佛山南莊碼頭，交通便利，可以多樣化貨物的運輸方式，所以在Q2附近進行選址，有獨特的優(yōu)勢。地理坐標為Q1的地點位于臨夏自治州的馬塔山附近，交通不便，故需要對該選址做調(diào)整。通過地圖可以看出 Q1附近臨近公路和鐵路的城鎮(zhèn)，選出數(shù)個城鎮(zhèn)，通過TSA進行迭代，得到最優(yōu)的組合是重慶→烏魯木齊→西安→銀川→小茨溝站，于是得出結(jié)論，配送中心的最優(yōu)選址位置在小茨溝站，與此同時，小茨溝站是火車的?？空军c，有利于貨物運輸。

2.3 結(jié)果分析

選擇既考慮定性因素，又考慮定量因素的選址方法，采用位置度量法進行計算，考慮到該配送中心選址的實際情況，為該公司選址時主要考慮的客觀因素有工資平均水平、工業(yè)用地成交均價（CNY/m2）以及運輸成本（CNY/km），主觀因素主要考慮競爭狀況、地理位置和環(huán)境3個因素。綜合客觀因素和主觀因素的度量值和重要性的總評比值，總評比值較大的為最優(yōu)方案，通過位置度量值的計算，可以得到配送中心的選址地址位于蘭州和武漢。

同時利用重心法選址能夠找到一個范圍，范圍中會包含幾個備選點，之后利用層次分析法輔助重心法完成最終的選址。在每個區(qū)域中通過重心法計算得到一個中心位置，以該中心為原點，合理長度為半徑，以求在該圓內(nèi)至少包含3個或更多的城市，之后通過層次分析法得到層次總排序表，確定最終的物流配送中心位置。計算得到配送中心的選址地址位于西安和廣州。

把本文通過重心法與TSA計算出的結(jié)果記作方案A，通過位置度量法計算的結(jié)果記作方案 B，而采用重心法和層次分析法計算的結(jié)果記作方案 C。通過式（9）分別計算運輸距離，通過給出和計算出的需求量與單位運費率計算，得到表2。圖2為方案A 與方案C 的成本對比情況，可以看出方案C 的費用所占面積略大于方案A，因此可以得出方案A總成本低于方案 C 的結(jié)論;與此同時，從數(shù)據(jù)上可以計算出，方案 C 高于方案A 成本3 259萬元。方案 A 與方案 B 的成本對比如圖3 所示，可以明顯看出方案B 的面積大于方案A，即方案A優(yōu)于方案B。通過計算同樣發(fā)現(xiàn)，采用重心法和TSA計算出的選址地址，其總運費大約為13566萬元。對于方案 B，其總運費費用為 16825萬元，對于運費來說，節(jié)省了19.37%的費用，使得企業(yè)的成本有了大幅度的下降。對于方案 C，其總運費費用為15249萬元，對于運費來說，節(jié)省了 11.04%的費用?？偟膩碚f，就運輸成本來看，方案 A優(yōu)于方案B和方案C。

3 結(jié)語

在考慮運輸距離、單位運輸費用、運量以及碳排放的條件下，本文采用重心法這一經(jīng)典的配送中心選址方法，計算出備選的配送中心地址是在佛山丹灶特大橋與佛山南莊碼頭以及臨夏自治州的馬塔山附近。但是在考慮運輸條件的情況下，通過TSA選址結(jié)果由馬塔山優(yōu)化為了小茨溝站，可以得出以下結(jié)論：

（1）以運輸成本最小化為目標，結(jié)合重心法和 TSA，對Z公司的配送中心進行了選址計算。重心法使用簡單方便，TSA是人工智能在組合優(yōu)化算法中的一個成功應用，但是單獨使用都具有局限性，通過Z 公司這一實例，互相補充了算法中的部分不足之處。

（2）通過與位置度量法、重心法與層次分析法相結(jié)合所計算出的結(jié)果進行對比，得出重心法與TSA 相結(jié)合，企業(yè)的運輸成本花費更小，總成本更低這一結(jié)論。

（3）計算得出的選址地址具備一定的實施價值。對于Z公司的配送中心選址問題的解決有所幫助，使Z公司能夠更加客觀地對物流配送中心選址進行規(guī)劃，從而選出更科學、更經(jīng)濟的配送中心。但是由于并未考慮地價等成本，所以其配送中心選址是有局限性的。

[參考文獻]

[1] ALFRED W，F(xiàn)RIEDRICH C J.Alfred weber’s theory of the location of industries[M].Chicago，Ill The University of Chi- cago Press，1929.

[2] BETTINGER P，SESSIONS J，BOSTON K.Using Tabu searchto schedule timber harves TSA subject to spatial wildlife goals for big game[J].Ecological Modelling，1997，94（2）：111-123.

[3] 楊娜娜，張青年，黃健鋒.禁忌搜索與SIC模型結(jié)合在公交冗余站點優(yōu)化中的應用[J].中山大學學報（自然科學版）， 2015，54（4）：150-157.

[4] 楊珺，馮鵬祥，孫昊，等.電動汽車物流配送系統(tǒng)的換電站選址與路徑優(yōu)化問題研究[J].中國管理學，2015，23（9）：87-96.

[5] 陳詩軍，王慧強，陳大偉，等.基于改進禁忌搜索的基站布局優(yōu)化算法[J].計算機工程與科學，2018，40（2）：341-347.

[6] MAURICIO R M，VELAZQUEZ R G，MARTIN E A，etal.Solution search for the capacitated p-median problem us- ing Tabu search[J].International Journal of Combinatorial Optimization Problems& Informatics，2019，10（2）：17-25.

[7] ALAVI S，AZAD N，HEYDAR M，etal.Integrated production，inventory， and location allocation decisions in designing sup- ply chain networks[J].International Journal of Information Systems and Supply Chain Management，2016，9（4）：22-42.

[8] ZHEN Lu，WUYiwei，WANGShuaian，etal.Capacitated closed-loop supply chain network design under uncertainty[J].Ad- vanced Engineering Informatics，2018，38：306-315.

[9] 李明，劉航，張曉建.多物流配送中心的選址布局問題優(yōu)化模型研究[J].重慶交通大學學報（自然科學版），2017，36（1）：97-102.

[10]戴卓.三層物流網(wǎng)絡選址：路徑優(yōu)化及混合啟發(fā)式算法研究[J].計算機應用研究，2017，34（8）：2349-2354.

[11]孟燕萍，申慢慢.考慮災后道路恢復情況下動態(tài)應急物資選址問題[J].重慶交通大學學報（自然科學版），2019，38（1）：89-96.

[12]戢守峰，唐金環(huán)，藍海燕，等.考慮選址-路徑-庫存聯(lián)合優(yōu)化的碳排放多目標模型與算法[J].管理工程學報，2016，30（3）：224-231.

[13]王夢夢，韓曉龍.考慮碳排放的易腐品供應鏈選址-路徑-庫存聯(lián)合優(yōu)化[J].上海海事大學學報，2019，40（4）：45-51.

[14]蔣海青，趙燕偉，張景玲，等.基于碳排放的開放選址-路徑問題及算法[J].系統(tǒng)工程理論與實踐，2020，40（1）：182-194.

[15]莫司丞.粵海火車渡輪燃油消耗原因分析與對策研究[D].成都：西南交通大學，2013.

[16]劉炎寶，王珂，楊智勇，等.考慮碳排放與新鮮度的冷鏈物流配送路徑優(yōu)化[J].江西師范大學學報（自然科學版）， 2019，43（2）：188-195.

[17]林殿盛，張智勇，王佳欣，等.需求不確定下的低碳物流配送中心選址[J].控制與決策，2020，35（2）：492-500.