基于微粒群算法的配送中心選址研究

摘要：作為挖掘現代企業利潤源泉的突破口，配送在物流活動中占有舉足輕重的地位。多網點配送中心選址是后續物流活動開展的首要條件，對于該問題的研究具有現實意義。由于微粒群算法的普適性、魯棒性、全局搜索性等特點，在求解復雜問題中能夠較好地體現其優越性。結合運籌學中的運輸規劃的思想，對復雜的數學模型進行了簡化，并針對問題的特點構造了求解編碼機制。根據文獻資料，將其中的仿真數據進行了整合，使得數據具有一定的現實意義，并用微粒群算法進行求解，得到了較好的效果。

關鍵詞：配送中心；多網點選址；微粒群算法；普適性；魯棒性

中圖分類號：TP301.6 文獻標識碼：A

文章編號：1002-3100(2007)11-0066-05

Abstract: As the breakthrough of excavating the source of profit of modern enterprises， distribution is crucial in the logistics activities. Multiple point location is the primary condition of conducting follow-up involving logistics activities. To conduct the study is meaningful because in the real world such problem exists. Since particle swarm optimization algorithm has such characteristics as universality， robustness， global search， it signifies its advantage absolutely in solving complicate problems. Thanks to the ideology of the transportation programming in the operational research， the complicate mathematic model gets simplified， and a coding mechanism， which corresponded with the problem， is formed as a mean to the problem. According to the literature and reference， the simulated data gets integrated， which enables the data to be realistic and credible. The particle swarm optimization algorithm is adopted to searching the optimum solution， and the conclusionis proved to be effective.

Key words: distribution center; multiple point location; particle swarm optimization algorithm; universality; robustness

配送中心是在經濟合理區域范圍內，根據用戶要求，對物品進行揀選、加工、包裝、分割、組配等作業，并按時送達指定地點的物流活動[1]。在整個配送活動中，運輸占據很重要的地位。物流配送中心選址研究有很多方法，但仍需要得到科學的模型化、數量化方法的支持。這些方法大致可以分為定性和定量兩大類。定性的方法主要是層次分析法和模糊綜合評價相結合對各個方案進行指標評價，找出最優地址；定量的方法主要包括重心法、運輸規劃法、Cluster法、CFLP法、Baumol-Wolfe法、混合0-1整數規劃法、雙層規劃法、遺傳算法等[2]。

微粒群算法（Particle Swarm Optimization）又稱為粒子群算法，是由美國心理學博士James Kennedy和電子工程學博士Russell Eberhart于1995年共同提出的，其基本思想是受他們早期對許多鳥類的群體行為進行建模與仿真研究結果的啟發，將優化問題的解看成空間中不斷飛行的，沒有質量，沒有體積的一個個微粒。目前已廣泛應用于函數優化、神經網絡訓練、數據挖掘、模糊系統控制以及其他的應用領域[3]。與其他智能算法相比，微粒群算法編碼受限制少，容易實現，搜索范圍大，應用更靈活，受到很多研究者的青睞。

1選址問題描述及其數學模型

作為挖掘企業“第三利潤源泉”——物流的突破口，配送中心正逐漸顯現其重要性。市場需求的多樣性，如今的產品需求向多品種中小批量的方向發展，定制已替代了大量制造，大批供應的傳統模式。同樣地，由于產品品種的多樣性，產品結構的復雜性，傳統的送貨模式已無法高效，及時地滿足客戶的要求。此時，配送中心應運而生，它以便利，靈活，準時，低成本的優勢受到企業的青睞，并以規模經濟縮減成本。配送中心的出現無疑為如今的企業帶來了新的希望。

配送中心的地址選擇在物流活動中占舉足輕重的地位，有廣泛的實際應用背景。配送中心的選址決策不僅直接關系到其未來的運營費用及服務水平，還關系到整個社會物流的合理化，因而配送中心選址問題是配送中心建設項目中至關重要的問題。由于配送中心選址屬于長期規劃項目，一旦確定了地點，很難變更，因此在選址決策前需要考慮眾多影響因素。如果將配送中心規劃在同一區域的各個地點，不同布局方案可能使整個物流系統的運作成本產生很大的差異[4]，這就對選址決策提出了更高的要求。

文獻[5]將選址問題分為一元網點和多元網點問題，一元網點問題通過解析方法可以近似得到合理的選址方案。而多元網點問題由于不僅要考慮選擇幾個地點及其組合方案，還要考慮如何協調供應商與客戶之間的關系，以保證能及時得到供應，并準時送達客戶，這就要求模型基于供求雙方用多個約束條件來保證貨物流通的合理性，最終造成問題本身的規模巨大。

配送中心的選址問題描述如下：有m個供貨點和l個客戶需求點，現已經根據定性方法大體確定了n個地點作為備選地點，并且知道貨物運輸費率，建造配送中心的費用以及配送中心以后運營費率。要求從已確定的n個備選地點中選擇P個地點建造配送中心，使得費用支出最少。根據文獻[6]所給出的選址模型，費用函數由運輸費用，運營費用以及建造費用構成，從供應點供貨能力，滿足需求，容量要求，個數要求幾個方面考慮，將文獻給出的模型稍做變化，模型描述如（1）。

式（2）的第一部分是微粒對當前自身運動狀態的信任，搜索范圍的大小取決于慣性權重ω。第二部分是“認知”部分，微粒考慮了自身的經驗，體現了通過自我“認知”，實現增強學習的過程。第三部分是“社會”部分，微粒通過群體之間的交互，實現信息共享，有能力達到新的搜索空間。算法流程描述如下：（1）在可行域內，隨機初始化微粒和速度；（2）評價每個微粒的適應值；（3）標記本代各微粒為pbest，并從中挑出適應值最好的標記為gbest；（4）在可行域內，按式（2）和（3）更新微粒；（5）評價每個新微粒的適應值；（6）通過優勝劣汰更新pbest和gbest；（7）如滿足終止要求，停止；否則，轉（4）。

2.2運輸規劃。1947年G.B.Danzig在研究美國空軍資源的優化配置時提出了線性規劃及其通用解法—單純形法[7]。從此以后，電子計算機求解線性規劃獲得成功，著作的出版標志著運籌學這門學科基本形成。運輸規劃在運籌學中屬于線性規劃的一個分支，主要研究在供需雙方供貨能力，需求及運輸費率已知的條件下，如何安排貨物的調運，使總運輸費用最小化。其中，包含產銷平衡，不平衡的情況，有廣泛的應用背景。運輸規劃與一般線性規劃不同之處在于，經轉換，可以通過表上作業法這一簡便而有效的方法解決，因其構造簡單，求解方便，能保證在有限的迭代步驟中得到最優解，應用十分廣泛。

3基于問題的預處理

3.1模型轉型。根據具體問題，將數學模型轉化成可以求解的計算機模型，這是求解優化問題首要考慮的問題。對于用優化算法求解來說，通過模型轉換，可以使問題的描述更有針對性。原本求解規模大，數學模型復雜的問題經過轉換，往往可以減小求解規模，簡化模型，程序設計人員能夠更好地發揮主觀能動性，將算法求解實現。

3.2編碼。現在由于制造業中，加工裝配式生產較為普遍，而大批大量生產和供應的計劃經濟時代已銷聲匿跡了。因此，各個廠家從成本和效率方面考慮，從量上來說適可而止，僅滿足需求即可，而時間上，我們在運用MRP做計劃時，可以從歷史數據上估出供應商的功效，以提前期作為約束供應商的發貨時間。因此，從數量上來說，現實的供應量和需求量大致相當更為合理，并且供應量、需求量與庫存量的相差也不會太大，這就造成了編碼的困難。

編碼就是將問題的解用一種碼來表示，從而將問題的狀態空間與算法的碼空間相對應[8]。因為微粒要在一個區域內運動，其運動范圍一大，就會超越區域；而運動范圍一小，其變化量就小，如此一來，解的可行性得不到保證，且微粒的變化小會造成搜索能力的下降。

所用的數據中，供應點的總供貨量與需求點的總需求量相等，而配送中心的庫存量總和要超過供貨量及需求量一點，這正是體現了供應鏈管理的思想。現在的加工裝配式生產，一個部件對應多個其他部件或零件，要保證按時供應，按需生產，這就要求供應商能夠在必要的時間，供應必要數量的貨物。供應商的存貨量不能過大，超過一定的閾值，供應商無法保證所有貨物都能銷出去。另一方面，囤積的貨物過多，就會增加管理費用和貨損造成的費用，很不經濟。因此，這套數據具有一定的現實意義。

筆者在C-Free的開發環境下，采用C語言編寫了微粒群算法的程序，在2.00GHz的CPU，256MB內存的計算機上運行。參數設置如下：

由于上述計算是純理論計算，計算的結果可能存在理想性、非理性的問題。因此，理論的計算結果往往要結合實際情況進行進一步分析，在得到實踐的檢驗后，理論數據才能應用到實踐活動中去。問題要求建設4個配送中心，但從流通量來看第3個配送中心的流通量只有一個單位，說明4個配送中心的業務量其實只靠3個配送中心就能完成大部分工作量。由于配送中心能夠盈利，靠的是規模經濟，如果沒有大量的貨物流通，顯然，這個配送中心如果建設運營，很可能會面臨虧本的威脅。因此，在這個位置可以考慮建一個輔助型的配送中心，這個配送中心以維護為主，兼具輔助其他配送中心的職能。由于配送中心有許多保證其正常運營的高成本的設備和設施（包括車輛、輸送機、堆垛機、揀選設備、AGV等），在其生命周期內不可避免要對其進行維護和更新。設備和設施是企業用以生產產品和提供服務的物質基礎，對設備和設施的維護和管理工作的好壞將直接影響企業競爭能力和經濟效益[9]。這第3個配送中心的位置可以建設用來經營其他配送中心硬件的維護和管理的工作，同時，它又擁有配送中心的部分職能可以分擔一部分配送業務或者在其他配送中心發生緊急情況的時候給予支援。

基于上述參數設置，用微粒群算法，總共迭代200次，以達到最優解迭代次數和用時這兩個指標進行考察，結論請參考表3。當種群n=10時，平均達到最優解迭代次數36.8，平均用時0.0825s；當種群n=30時，平均達到最優解迭代次數15.4，平均用時0.1981s。選取種群為10，模擬次數為4，定迭代次數為35次的運算結果，用Excel工具繪出趨勢圖，請參考圖1。從表3的數據和趨勢圖可以看到采用微粒群算法求解上述問題具有種群少，迭代次數少，用時短等優點。但其中也不乏缺陷，如：達到最優解的迭代次數有好有壞，參差不齊等。

5結束語

物流配送中心選址問題是一混合整數規劃，當備選地點增加，就會造成配送中心地點選擇的范圍增大，地點的選擇范圍又制約著呈整數變化的貨物調運變量，整個問題的規模就會大幅增加，造成求解的困難。本文通過對模型進行變換，縮小了求解規模，采用了特別的編碼機制，保障了解的可行性，運用微粒群算法，在有效的時間內取得了良好的結果。從建模，分析到運算整個過程來看，可以得到這樣的結論：微粒群算法能在混合整數規劃的求解中發揮效用；微粒群算法在求解配送中心選址問題中，可采用小規模種群，經過有限步的迭代，得到相當好的結果，具有速度上的優勢。

參考文獻：

[1] 孫宏嶺. 高效率配送中心的設計與經營[M]. 北京：中國物資出版社，2002:1.

[2] 魏興光. 物流配送中心選址方法綜述[J]. 物流與交通，2005(9):48-49.

[3] 高尚，楊靜宇. 群體智能算法及其應用[M]. 北京：中國水利水電出版社，2006:7.

[4] 王燕，蔣笑梅. 配送中心全程規劃[M]. 北京：機械工業出版社，2003:83，103.

[5] 李長江. 物流中心設計與運作[M]. 北京：中國物資出版社，2002:13-22，34-35.

[6] 羅榮桂，彭偉華. 物流配送中心選址優化模型與算法實現[J]. 臺聲·新視角，2005(10):47-48.

[7] 胡運權. 運籌學教程[M]. 2版. 北京：清華大學出版社，2003:2.

[8] 王凌. 車間調度及其遺傳算法[M]. 北京：清華大學出版社，2003:36.

[9] 陳榮秋，馬士華. 生產與運作管理[M]. 北京：高等教育出版社，1999:353.

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文