摘  要： 在分析了一類配送中心選址問題的基礎上，建立了該配送中心選址問題的數學模型。提出一種具有雙重信息的遺傳算法編碼方案，并結合相應的遺傳操作進行求尋優求解，最后通過實驗證明了該方法的可行性和有效性。
關鍵詞： 雙重信息；遺傳算法；配送中心；模型

　隨著市場競爭的日益加劇，越來越多的企業認識到，如何合理地設立分銷配送中心，加強對配送環節的有效管理，是提高企業競爭力非常有效的途徑。配送是指在經濟合理區域范圍內里，配送中心根據客戶要求，對物品進行揀選、加工、包裝、分割、組配等，并按時送達指定地點建立中間分銷配送中心[1]?？茖W建立配送中心，不僅可以使企業快速把握和響應市場反應，而且還能通過優化的配送中心以及相應的配送方案給企業節約很大的成本。
　目前，越來越多的研究人員趨向于采用遺傳算法、拉格朗日松弛法、模擬退火算法等啟發式算法來達到或逼近該問題的最優解[2]。參考文獻[3]使用兩步驟近似法構建在庫存和運輸雙重能力約束下，每個周期配送中心的庫存成本計算方法，分別用遺傳算法、克隆選擇算法、粒子群算法求解所建立的模型；參考文獻[4]使用經遺傳算法改進的人工神經網絡模型對糧食配送中心選址問題進行求解；參考文獻[5]采用以模擬退火的思想對遺傳算子參數進行自適應的改進方法，解決以區域分銷中心選址為基礎的汽車零部件物流網絡優化解決方案；參考文獻[6]采用改進的遺傳算法求解帶有時間窗的單配送中心的車輛調度模型。遺傳算法具有隨機和多點搜尋特性[7]。本文對遺傳算法進行改進，設計一種具有雙重信息的編碼方案和相應的遺傳操作，將之應用到配送中心選址模型，使算法能夠有效地收斂到該模型的全局最優解。
1 一類配送中心選址數學模型
1.1 問題描述
　若某企業需要在某市建立若干個配送中心，現有m個備選配送中心和n個配送點，并且已知每個備選配送中心的建設費用以及其建成后可具有的容量，以及配送中心向配送點配送時每單位重量需花費的運輸費用和每個配送點的需求量，現需要從m個備選配送點中選擇若干個建設成配送中心，那么選取哪些備用配送中心以及如何分配這些配送中心的配送點，使得配送中心建設費用以及向配送點配送時的花費最少[8]。
1.2 數學模型
　根據問題描述，該類配送中心選址問題的數學模型描述如下：

　式（1）表示總的建設費用和運輸費用最??；式（2）表示對i點的需求量應小于等于其容量；式（3）表示向配送點j配送的量應大于等于其需求量；式（4）Ai為標志整型變量，標明第i個備選點是否被選中。
2 針對此模型的改進遺傳算法
2.1 具有雙重信息的染色體編碼方案設計
　傳統的遺傳算法染色體編碼經常采用二進制編碼。對于本文所提出的選址中心數學模型，如果采用二進制編碼，可以用染色體的每個基因位相應的下標來代表每個備選配送中心，用染色體的每個基因位上的0-1值代表該備選配送中心是否被選中，若共有6個備選配送中心和8個配送點，則染色體長度應設置為6，如果某個染色體如圖1所示。

    則表示1號、2號、6號備選配送中心被選中，利用這種編碼方案雖然可以表示出哪些備選配送中心被選中，但是從染色體上體現不出這些選出來的配送中心為哪些配送點進行配送，如果要繼續確定這些配送中心的配送點，又需要在此基礎上進行相應的設計，這無疑會增加算法的復雜度和編程的工作量。
　針對二進制編碼的上述問題，本文提出了一種具有雙重信息的染色體編碼方案，使染色體可以體現雙重信息，從染色體上既可以體現出哪些備選配送中心被選中，而且還可以體現出這些選出來的配送中心為哪些配送點進行配送，這會很大程度上提高解決問題的效率。具體方法是：若要從m個備選配送中心選擇若干個為n個配送點進行配送服務，則設置染色體的長度是n，染色體由n個[1，m]之間的整數構成，如要從6個備選中心中選擇若干個為8個配送點服務，則染色體長度為8，染色體由8個[1，6]之間的整數構成。這樣染色體的每個基因位上的值就代表選中的配送中心的編號，而染色體的每個基因位相應的下標表示其所服務的配送點。如果某個染色體如圖2所示。

2.4 遺傳算法步驟設計
　將上述改進遺傳算法應用到本文的配送中心選址模型求解中，具體步驟如下：
?。?）設置遺傳算法基本參數：種群數量NIND，最大代數MAXGEN，代溝GGAP，交叉概率Pc，變異概率Pm，讀入各備選配送中心的建設費用和建設之后的容量，以及各個配送點的需求和配送單位重量需要的運輸費用。
?。?）產生初始種群：產生NIND行n列個范圍在[1，m]之間的隨機整數作為初始種群Chrom，其中n為配送點的個數，m為備用配送中心的個數。
?。?）分別計算種群Chrom中各染色體的目標值Objv，根據各自的目標值按照代溝GGAP按前述方法進行選擇操作，形成Selch。
　（4）對Selch按照交叉概率Pc和變異概率Pm依次進行交叉和變異操作，形成子代種群。
?。?）記錄子代種群的最優目標值，并對子代種群按步驟（2）的方法產生若干個染色體對子代種群進行補充。
?。?）判斷Gen是否大于MAXGEN，是則退出，否則轉向步驟（3）。
3 仿真測試
　假設某公司需要為其在某市的8個配送點選擇配送中心，需要從6個備選點選擇若干個對其進行建設作為配送中心，那么選擇哪些備選點作為配送中心會使得建設費用和運輸費用最小，其中8個配送點的需求量如表1所示，各個備選配送中心的建設費用及容量如表2所示，各配送中心向配送點配送時每單位重量需花費的運輸費用如表3所示。

　采用上述改進遺傳算法對此問題進行仿真測試，其中參數設置為：種群數量NIND=20，最大代數MAXGEN=100，代溝GGAP=0.7，交叉概率Pc=0.7。
程序運行后的最優解的染色體為：21121222，從該染色體可以得出：從6個備選配送中心中選擇1號、2號建設成為配送中心，其中1號配送中心為2號、3號、5號配送點配送服務，2號配送中心為1號、4號、6號、7號、8號配送點配送服務。
　其中遺傳算法進行100代時每代的最優目標值如圖3所示，從圖中可以看出，運行到100代時得出最優解，總的建設和運輸費用是804個單位值，進化時每代的最優目標值從最初的1 655左右逐漸下降到804，說明該算法有很好的尋優能力，能有效地對這類配送中心選址數學模型進行優化。

　科學建立配送中心，不僅可以使企業快速把握和響應市場，而且還能通過優化的配送中心以及相應的配送方案提高企業的市場競爭力。本文針對一類配送中心選址問題出發，對其進行數學建模，并提出一種具有雙重信息的編碼設計方案，使得從染色體編碼上不僅可以體現出哪些備選配送中心被選中，而且還可以體現出這些選出來的配送中心為哪些配送點進行配送。通過仿真測試，證明了該方法在解決這一類模型時的可行性和有效性。
參考文獻
[1] 謝天保，雷西玲，席文玲.物流配送中心配載車輛調度問題研究[J].計算機工程與應用，2010，46（36）：237-240.
[2] 王喆.基于組合遺傳算法的鐵路危險貨物辦理站點整合優化[J].計算機應用，2010，39（9）：2301-2304.
[3] 稅文兵，葉懷珍，張詩波.物流配送中心動態選址模型及算法研究[J].計算機應用研究，2010，27（12）：4476-4479.
[4] 許德剛，肖人彬.基于改進神經網絡的糧食配送中心選址決策研究[J].計算機應用研究，2010，27（3）：887-890.
[5] 朱爽，王東.汽車零部件物流網絡優化設計與實現[J].計算機工程，2011，37（12）：258-261.
[6] 施朝春，王旭，葛顯龍.帶有時間窗的多配送中心車輛調度問題研究[J].計算機工程與應用，2009，45（34）：21-24.
[7] 李凈，袁小華，朱云飛.物流配送系統中車輛路徑問題的實現[J].計算機工程與設計，2009，30（16）：3783-3786.
[8] 張玉芬，齊紅然，劉世普.一類應急服務設施選址問題的模型及算法[J].數學的實踐與認識，2009，39（14）：37-41.