典型優(yōu)化問題的遺傳算法求解—8選址分配問題

《典型優(yōu)化問題的遺傳算法求解—8選址分配問題》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、典型問題選址－分配問題(LocationAllocationProblem)東北大學系統(tǒng)工程研究所2014.09典型優(yōu)化問題的模型與算法-R03選址－分配問題?選址－分配(location-allocation)問題?也稱作多韋伯(multi-Weber)問題或P中位(P-median)問題。?單韋伯(singleWeber)問題?在歐幾里德空間上典型的單韋伯(singleWeber)問題是尋找一個位置，使從代表顧客位置的一些固定點到它的距離和最小。?問題描述：?有m個“設施”需要選址，n個已知位置的“顧客”分配給不同的設施，每個顧客的需求為b，j=1,2,…,nj；每個

2、設施具有的能力為a，i=1,2,…,mi?我們需要找到?設施的位置（選址）?顧客對設施的分配?使顧客和服務他們的設施間的距離總和最小。典型優(yōu)化問題的模型與算法-R032圖形描述(u,v)nn(u,v)11CC3Cbn11bn(x1,y1)…F1aFmma1(xm,ym)C2m:設施總數a:第i個設施的能力in:顧客總數b:第j個顧客的需求jF:第i個設施,i=1,2,…,mF=(x,y):設備i的未知位置，決策變量iiiiC:第j個顧客,j=1,2,…,nC=(u,v):顧客j的已知位置jjjj典型優(yōu)化問題的模型與算法-R033數學模型mnminf(F,z)???t(Fi

3、,Cj)?ziji??11j保證不超過每個設施的服務能力ns.t.gi(z)??bjzij?ai,i?1,2,?,mj?1保證每個顧客只m由一個設施服務gm?j(z)??zij?1,j?1,2,?,ni?1z?0or1,i?1,2,?,m,j?1,2,?,nij?變量:C(uj,vj)jzij:0-1決策變量bjz=1,顧客j由設施i服務；否則z=0ijijF=(x,y):設施i的未知位置，決策變量iiiaFii?參數：(xi,yi)……t(F,C):由設施i到顧客j的歐幾里得距離。ij22t(F,C)?(x?u)?(y?v)ijijij典型優(yōu)化問題的模型與算法-R034

4、特點?非線性規(guī)劃問題?既有0-1變量，又有實數變量?分配子問題是一個一般的指派問題?NP-難的問題?Cooper是正式認識并描述多韋伯問題的第一位學者。他證明目標函數既不是凹的也不是凸的，并存在許多局部最優(yōu)解。典型優(yōu)化問題的模型與算法-R035分類?按能力分類：?有能力約束的LAP?無能力約束的LAP?按階段分類：?單階段LAP?多階段LAP?其它分類：?有障礙的LAP?平衡的LAP典型優(yōu)化問題的模型與算法-R036問題的擴展?一般的選址-分配模型致力于為這樣一些基礎設施尋找最佳選址，如：?學校、消防站、公園等，?此類基礎設施對于“最佳選址”理解的共同點在于，使供需點之間

5、的“總距離”或者“平均距離”最小。?除此以外，這個基本模型經過擴展還可以有更廣泛的應用范圍，如：?優(yōu)化城市零售商業(yè)網點空間分布(通過最大化惠顧人流量來實現)、?優(yōu)化制造業(yè)場所空間分布(通過最小化運輸成本實現)、?優(yōu)化公共服務設施空間分布(通過最優(yōu)化服務質量實現)、?……典型優(yōu)化問題的模型與算法-R037應用?物流配送中心選址問題?物流網絡設計中首先必須要解決的問題?物流中心?設施；零售商?顧客；運費或距離最C3短F1?城市醫(yī)院空間布局優(yōu)化?醫(yī)院?設施；街區(qū)?顧客；服務質量,距離最小等C1?城市郵政局所空間布局?郵局?設施；建筑物的中心?顧客；郵政服務的…平均出行距離最短C

6、?城市電網變電站選址問題2?變、配電站?設施；小區(qū)?顧客；輸電線（距離F）最短m?海上溢油應急點選址優(yōu)化C?應急服務點?設施；發(fā)生溢油較高的區(qū)域?顧客n；到達發(fā)生事故點的距離之和最小?公路養(yǎng)護資源的選址和配置問題?養(yǎng)護點?設施；路段?顧客；目標是工作量均衡典型優(yōu)化問題的模型與算法-R038應用?社會考試考場選擇問題?例如英語等級考試、公務員考試等涉及的人數很多；C3?考場?設施；生源地?顧客；距離最短、最F1便利等C?零售商業(yè)點的選址問題1?商業(yè)點?設施；小區(qū)（街區(qū)）?顧客；惠顧人流量最大或距離最短…?公共設施的最優(yōu)選址問題C2?如公園、學校、圖書館、加油站、污水處理廠、

7、城市垃圾填埋場、消防設施等Fm?突發(fā)事件的應急資源配置問題C?如地震、海嘯、流行病、n?設備選址?如電力、通信、交通系統(tǒng)中相關設備或站址的選取和定位典型優(yōu)化問題的模型與算法-R039一般求解方法?Cooper提出了一種稱作選擇選址－分配(alternativelocation-allocation)的啟發(fā)式，這是一種最好的啟發(fā)方法?隨著非線性規(guī)劃技術的發(fā)展，通過松弛整數分配約束，同時考慮選址變量和分配變量，產生了一些新的方法。?Murtagh和Niwattisyawong提出一種松弛0-1分配約束的方法。允許在[0,1]區(qū)間上