搬家公司的選址問(wèn)題

【摘要】選址問(wèn)題研究的是如何選定一個(gè)或多個(gè)設(shè)施的地理位置，使得所考慮的目標(biāo)達(dá)到最優(yōu).本文主要研究了搬家公司選址問(wèn)題的模型建立和求解，以開設(shè)店面的費(fèi)用和行車費(fèi)用總和最小為目標(biāo)，根據(jù)搬家公司各個(gè)店面之間的聯(lián)系情況和車輛調(diào)度方法的不同，提出了三種不同的數(shù)學(xué)模型，并利用遺傳算法對(duì)三個(gè)模型進(jìn)行求解，最后進(jìn)行算例應(yīng)用和敏感度分析，以驗(yàn)證本文所構(gòu)建的模型的合理性及可行性.

【關(guān)鍵詞】搬家公司;選址;遺傳算法

一、引 言

國(guó)內(nèi)外物流配送中心選址問(wèn)題的研究已有幾十年的歷史，對(duì)各種類型物流配送中心的選址問(wèn)題在理論和實(shí)踐方面都取得了令人矚目的成就，形成了許多可行的模型和方法.但是對(duì)于具體的搬家公司選址問(wèn)題卻沒(méi)有相應(yīng)的資料和文獻(xiàn)，為了更好地為居民服務(wù)，也為了實(shí)現(xiàn)搬家公司節(jié)省費(fèi)用，實(shí)現(xiàn)利益最大化，店面的選址就成為一個(gè)值得深入研究的問(wèn)題.對(duì)于搬家公司來(lái)說(shuō)，利潤(rùn)的最大化是其追求的目標(biāo)，為實(shí)現(xiàn)這一目標(biāo)，搬家公司最關(guān)心的問(wèn)題是在何處建店面才能實(shí)現(xiàn)利潤(rùn)的最大化，也即是實(shí)現(xiàn)搬家公司成本最小化.

二、搬家公司選址模型

從長(zhǎng)遠(yuǎn)觀點(diǎn)看，影響搬家公司選址問(wèn)題的因素主要有：

1.在不同居民區(qū)建立一個(gè)店面的費(fèi)用以及相應(yīng)的運(yùn)營(yíng)維護(hù)成本.

2.運(yùn)輸費(fèi)用，分為三個(gè)方面：

（1）店面到搬遷居民所處地址的距離；

（2）搬遷居民所處位置到目的搬遷地址的距離；

（3）目的搬遷地址回到店面的距離.

3.居民區(qū)間人口流動(dòng)數(shù)量.

在模型的建立過(guò)程中，綜合考慮選擇建立店面數(shù)目的不同、各店面之間的聯(lián)系情況以及搬家公司車輛不同的調(diào)度方法分別建立了如下模型：

首先針對(duì)店面數(shù)目不唯一且各店面之間相互獨(dú)立的情況，根據(jù)搬家公司可能的追求目標(biāo)給出了兩種不同的策略：

(1)最快響應(yīng)策略：要求離請(qǐng)求顧客最近的店面完成，使得響應(yīng)盡可能快；

(2)最少運(yùn)輸費(fèi)用策略：要求與搬家起點(diǎn)、搬家終點(diǎn)兩地的距離和最短的店面響應(yīng)請(qǐng)求.

如果各個(gè)店面之間是相互聯(lián)系的，從這個(gè)店面駛出的搬運(yùn)車輛可以不必回到原店面，而是選擇一個(gè)離它最近的店面停靠.

符號(hào)說(shuō)明：

n：居民區(qū)數(shù)目；

mn：開設(shè)店面的數(shù)目；

λ：行車單位里程的花費(fèi)；

Lij：居住區(qū)i與居住區(qū)j之間的人口流動(dòng)戶數(shù)；

ck：在k點(diǎn)開設(shè)店面的費(fèi)用；

xk：xk=0，不在k開設(shè)店面，

1，在k開設(shè)店面；

dij：居住區(qū)i到居住區(qū)j的最短距離.

模型一 最快響應(yīng)策略——即當(dāng)居民區(qū)i發(fā)出搬家請(qǐng)求時(shí)，選擇距離節(jié)點(diǎn)i最近的店面派車執(zhí)行本次搬遷任務(wù).

min∑nk=1ckxk+λ∑ni=1∑nj=1Lij×dij+λ∑ni=1∑nj=1Lij×cij，

s.t. ∑nk=1xk=m，xk∈{0，1}，

cij=min{dik}+dkj|xk=1，k=1，…，m.

模型二 最少運(yùn)輸費(fèi)用策略：要求與搬家起點(diǎn)、搬家終點(diǎn)兩地的距離和最短的店面響應(yīng)請(qǐng)求.對(duì)于節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的所有搬遷，選擇一家到兩節(jié)點(diǎn)距離之和最短的店面進(jìn)行本次搬家任務(wù)，當(dāng)任務(wù)完成后，車輛返回本店面.

min∑nk=1ckxk+λ∑ni=1∑nj=1Lij×dij+λ∑ni=1∑nj=1Lij×cij，

s.t. ∑nk=1xk=m，xk∈{0，1}，

cij=min{dik+dkj|xk=1，k=1，…，m}.

模型三 公司的車輛全地區(qū)范圍內(nèi)流通，即某車輛在完成搬遷任務(wù)后不一定回到出發(fā)時(shí)的店面，對(duì)于搬遷起點(diǎn)i就近選擇店面，完成搬遷任務(wù)后在節(jié)點(diǎn)j處就近選擇店面歸隊(duì).

min∑nk=1ckxk+λ∑ni=1∑nj=1Lij×dij+λ∑ni=1∑nj=1Lij×cij，

s.t. ∑nk=1xk=m，xk∈{0，1}，xr∈{0，1}，

cij=min{dik}+min{drj}|xk=1，xr=1；k，r=1，…，m.

三、模型的算法實(shí)現(xiàn)

1.遺傳算法

遺傳算法的運(yùn)行過(guò)程中，由于選擇、交叉、變異等遺傳操作的隨機(jī)性可能破壞當(dāng)前群體中適應(yīng)度最好的個(gè)體，所以，使用最優(yōu)保存策略進(jìn)化模型(Elitist Model)來(lái)進(jìn)行優(yōu)勝劣汰操作，即當(dāng)前群體中適應(yīng)度最高的個(gè)體不參與交叉運(yùn)算和變異運(yùn)算，而是用它來(lái)替換掉當(dāng)代群體中經(jīng)過(guò)交叉、變異等遺傳操作后所產(chǎn)生的適應(yīng)度最低的個(gè)體.在本文的算法中，是使用最優(yōu)保存策略的推廣，即在每一代的進(jìn)化過(guò)程中保留最優(yōu)個(gè)體，不參加交叉、變異等遺傳運(yùn)算，而直接將它們復(fù)制到下一代群體中.

算法步驟：

Step1：初始化店鋪數(shù)m，種群個(gè)體數(shù)n，繁衍代數(shù)G，交叉、變異、精英選擇概率pc，pm，pj.

Step2：令loop=0，開始循環(huán)直到loop=G.

（1）對(duì)于每一代個(gè)體，計(jì)算并比較cost值，選取cost值最小的一個(gè)個(gè)體selected；

（2）隨機(jī)地為得到的種群分配一種繁殖方式：

①若隨機(jī)方式為精英選擇，則next=Append［next，selected］，count++；

②若隨機(jī)方式為交叉繁殖，則在0.5的概率下selected的各個(gè)基因（店鋪位置）與其地理位置附近的某一數(shù)字交換，count++；

③若隨機(jī)方式為變異繁殖，隨機(jī)選擇selected中的k(k=Random Prime［m］)個(gè)基因并用Random Prime［n］來(lái)替換，此后count++；

（3）若“下一代種群”集合中元素?cái)?shù)量

Step3：若loop=G，停止，輸出cost最小的個(gè)體，否則跳至（1）.

2.模型的實(shí)例結(jié)果分析

下列數(shù)據(jù)為某市53個(gè)居住區(qū)之間的最短路徑矩陣，不同居住區(qū)的人口以及任意兩個(gè)居住區(qū)之間的人口流動(dòng)數(shù)量矩陣.

該市不同居住區(qū)的人口（單位：千人）

{28.8，25.4，21.6，37.8，24.8，41.0，23.3，9.5，18.9，23.3，33.3，43.3，15.2，4.7，40.7，43.2，17.3，10.5，27.4，30.2，16.2，21.2，4.9，10.8，41.7，24.1，12.2，40.8，5.7，30.5，35.1，38.，41.5，22.8，7.8，107.5，81.5，53.3，67.3，114.9，109.6，102.2，137.8，81.6，116.1，44.4，109.1，48.9，75.0，179.6，87.8，87.3，111.6}表示居住區(qū)1，2，…，53的人口數(shù).

結(jié)果分析說(shuō)明：

(1)當(dāng)采用比較實(shí)際的最快響應(yīng)時(shí)，結(jié)果中店面的分布是盡可能分散，而且偏向搬家人口較多的地方，這點(diǎn)是符合比較經(jīng)典的重心法原則.

(2)對(duì)比三種建模策略，發(fā)現(xiàn)差距還是存在的，所以就要求各個(gè)店面能夠相互協(xié)調(diào)，建店的時(shí)候盡量將這作為一個(gè)重要的因素考慮.

四、總 結(jié)

在模型的建立過(guò)程中，模型的側(cè)重點(diǎn)是選址，側(cè)重于考查選址地點(diǎn)的開設(shè)店面的費(fèi)用以及由搬家任務(wù)帶來(lái)的車費(fèi)支出.在本文中的模型都是基于假設(shè)此地區(qū)沒(méi)有其他的搬家公司，如果考慮在這家公司進(jìn)入之前已有其他的搬家公司，那就要考慮競(jìng)爭(zhēng)的問(wèn)題.考慮競(jìng)爭(zhēng)，就必須提及市場(chǎng)占有率的計(jì)算，可以按照用戶光顧每個(gè)搬家公司的概率分布的簡(jiǎn)明計(jì)算規(guī)則：用戶在選擇某個(gè)搬家公司為其服務(wù)時(shí)，選擇某個(gè)搬家公司的概率與該公司的吸引力成正比，而與其距搬家公司的距離成反比.這樣會(huì)使得模型更接近現(xiàn)實(shí)，更具有實(shí)用性.

【參考文獻(xiàn)】

［1］Aikens C H.Facility Location Models for Distribution Planning.European Journal of Operational Research.1985.

［2］Barahona F，Jensen D.Plant Location with Minimum Inventory.Mathematical Programming，1998.

［3］王丹.物流配送中心選址問(wèn)題研究.大連海事大學(xué)，2007.

［4］楊波.多品種隨機(jī)數(shù)學(xué)模型的物流配送中心選址問(wèn)題.中國(guó)管理科學(xué)，2003.

［5］蔡臨寧.物流系統(tǒng)規(guī)劃——建模及實(shí)例分析.機(jī)械工業(yè)出版社，2003.

［6］陳照輝.配送中心選址問(wèn)題模型及算法研究.鞍山科技大學(xué)理學(xué)院.