基于遺傳算法的配送中心選址問題研究

孫元鵬，孫欽國，蘇強盛，楊毓玲（西南科技大學，四川 綿陽 621000）

0 引言

在社會經濟迅速發(fā)展的今天，每一條能夠提高經濟效益的措施都會為競爭者在激烈的市場競爭中取得一定的優(yōu)勢，增加一定的籌碼。如何降低生產成本，減少從生產到銷售中各個環(huán)節(jié)的費用，進而提高整體的經濟效益[1]，成為了擺在我們面前的首要問題。而在經濟發(fā)展的環(huán)節(jié)中，如何降低運輸成本，縮減運輸費用就變得尤為重要，物流也隨之變成一個決不可忽略的產業(yè)，一個城市的物流水平將直接影響到城市的經濟發(fā)展，也是判斷一個城市經濟發(fā)展?jié)撃艿臉藴手?。能不能在最小費用、最短時間的情況下將物品運到銷售地將直接決定著經濟效益的提升。而在整個運輸環(huán)節(jié)中，配送點的選取就顯得尤為重要。選取配送點時不僅要考慮到配送點的建設費用、運輸費用、覆蓋面積，還要考慮到客戶的要求。能不能滿足客戶及時的需求、拉動整體經濟的上漲才是我們最終的目的。因此，配送點的選取將直接影響到整個運輸網絡的效率[2]。本文將通過遺傳算法對配送點的選取進行一個綜合的、合理的計算。本文目的很純粹，就是為了減少物品在運輸環(huán)節(jié)中的費用，從小環(huán)節(jié)入手，提高經濟效益增長的空間。

1 配送中心選址問題描述

配送中心選址問題是一個多目標優(yōu)化問題，其宗旨是在滿足配送需求的前提下將配送網絡的運營成本降到最低。通過對當地經濟區(qū)域內需求點的需求量、路況、以及配送中心建設成本等因素的分析，合理地選擇配送中心的建設地點，合理地分配配送中心的配送資源，調整配送路徑，以降低配送成本。在確定配送中心建設規(guī)模時，還要考慮該配送中心的配送車輛優(yōu)化調度問題。要考慮的因素包括需求點、運輸網絡、車輛、貨物，約束條件以及目標函數[3]。

2 數學建模

綿陽市配送網絡構建滿足以下條件：綿陽市有充足的資金建設配送中心，且配送中心數量大于1。配送成本與運量、運距成正相關[4]。一個配送中心可以對多個需求點提供服務，但是一個需求點只能由一個配送中心的車輛配送貨物。配送任務不考慮貨源不足的情況，不考慮天氣、路況、車況等因素的影響[5]。各需求點的需求量一致，且隨時間增長變化不大。每次配送任務由單車次完成。

目標函數：

Qn——綿陽市的配送中心的車型相同，每臺車的載貨量

Xj1j2——客戶J1、J2之間的距離

Mn——第N輛車配送的客戶數

Jn——第N條路徑

Jnz——客戶J在第N條路徑中第Z個被服務

a——運送單位質量的貨物每公里所需的費用

約束條件：

式中：Gj——需求點j的需求量

Xij——配送中心i到需求j的距離

Ai——配送中心在i的造價，L代表需求點數量

Di為0——在i點不設置配送中心，不會選擇i點，Di為1則代表在i點建設配送中心，此時i點選上

Hij為0——配送中心i的車輛不負責對需求點j配送貨物，Hij為1則代表需求點j由配送中心i的車輛配送貨物編碼方法：將需求點隨機排列，數字1-j在數列中互不重復，生成j個自然數列。例如：用2輛車向7個需求點配送貨物，隨機生成數列5426371，代表第五個需求點作為第一輛車的服務對象，然后評價此項配送任務是否符合約束條件，判斷此項任務行車距離是否超出第一輛車的經濟運距，配送數量是否超出第一輛車的載貨量。如果符合約束條件，則將第4個需求點作為第一輛車的第二服務對象，然后評價該項配送任務是否滿足約束條件，如果滿足，則將第2個需求點作為其第三服務對象，假如第三項配送任務不滿足約束條件，則將第2個需求點作為第2輛車的第一服務對象，然后評價其是否符合約束條件。以此類推，n輛車，j個需求點[7]。

個體評價：先將已經編碼的個體解碼，得出其表現型。然后根據計算公式計算出目標函數值，最后把目標函數值轉換成個體的適應度。適應度越大說明個體越好，留到最后的幾率也越大[8]。適應度計算公式為H為適應度，f為目標函數值，r為不可行路徑數，p為懲罰項。

選擇方法：把得出的所有個體的適應度從大到小排列，擁有最大適應度的個體替換本代群體中適應度最低的個體，直接進入下一代，其他個體則參與遺傳運算。

交叉算子：類OX法。例如父代為A=12（34）567，B=7（65）4321，括號內為隨機產生的交配區(qū)域。運算后為A=6512347，B=3476521。

變異算子：多次采用交換變異，例如：序列1234567，交換第四位和第五位，則序列變?yōu)?235467。終止運行條件：當運算進行到一定的程度時，在K步內，解并沒有發(fā)生變化，則終止運算。

3 結束語

本文以綿陽的配送現狀為例，在綜合考慮各種因素的情況下，對綿陽的配送現狀做一個定性的分析和總體的評估。依照分析和根據將物流網絡建設成本和客戶雙方的利益最大化的基本原則來構造一個模型，并通過遺傳算法對模型進行求解，來求得選取配送中心的最佳方案。然后對方案的可行性進行一個科學的分析并反過來驗證算法的科學性，但是，模型畢竟是模型，與實際還是有一些差異，具體情況還需具體分析。但這不能否定算法的重要性，算法的存在對以后求解類似的問題具有極其重要的意義。經濟還在發(fā)展之中，算法也一樣，也在逐步的完善當中。通過本次對遺傳算法的運用，感覺到它在經濟發(fā)展當中重要作用，對促進城市的經濟結構調整和優(yōu)化市場資源配置，加快我國城市經濟現代化物流建設有著積極的意義[6]。

[1] 孫會軍，高自友.供應鏈分銷系統(tǒng)雙層優(yōu)化模型[J].管理科學學報，2003,6(3):66-70.

[2] FELLOWSA M R,FERNAU H.Facility location problem:a parame-terized view[J].Discrete Applied Mathematics,2011,159(11):1118-1130.

[3] 李昌兵，杜茂康，曹慧英.基于層次遺傳算法的物流配送中心選址策略[J].計算機應用研究，2012,29(1):57-59,78.

[4] 王燕，蔣笑梅.配送中心全程規(guī)劃[M].北京：機械管理出版社，2003.

[5] 郎茂祥.配送車輛優(yōu)化調度模型與算法[M].北京：電子工業(yè)出版社，2009.

[6] 王戰(zhàn)權，楊東媛，汪超.配送中心選址的遺傳算法研究[J].物流技術，2001(3):11-14.

[7] Young H A.On the optimum location of checking station[J].Operations Research,1963,11(5):721-731.

[8] B.L.Mac Carthy,W.Atthirawong.Factors Affecting Location Decision in international Operations-a Delphi Study[J].International Journal of Operation&Production Management,2003,23(7):25-30.