數(shù)學(xué)建模論文城市小區(qū)便民服務(wù)點(diǎn)的設(shè)置與調(diào)度優(yōu)化模型

賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)填寫）：2015高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽承諾書我們仔細(xì)閱讀了《全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽章程》和《全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽參賽規(guī)則》（以下簡(jiǎn)稱為“競(jìng)賽章程和參賽規(guī)則”，可從全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽網(wǎng)站下載）。我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）及隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論及賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競(jìng)賽章程和參賽規(guī)則的，如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽章程和參賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽章程和參賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們授權(quán)全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽組委會(huì)，可將我們的論文以任何形式進(jìn)行公開展示（包括進(jìn)行網(wǎng)上公示，在書籍、期刊和其他媒體進(jìn)行正式或非正式發(fā)表等）。我們參賽選擇的題號(hào)（從中選擇一項(xiàng)填寫）： 我們的報(bào)名參賽隊(duì)號(hào)（12位數(shù)字全國(guó)統(tǒng)一編號(hào)）： 參賽學(xué)校（完整的學(xué)校全稱，不含院系名）： 參賽隊(duì)員（打印并簽名）：1. 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）： 日期： 年_月日（此承諾書打印簽名后作為紙質(zhì)論文的封面，注意電子版論文中不得出現(xiàn)此頁(yè)。以上內(nèi)容請(qǐng)仔細(xì)核對(duì)，如填寫錯(cuò)誤，論文可能被取消評(píng)獎(jiǎng)資格。）賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)填寫）：2015高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編號(hào)專用頁(yè)送全國(guó)評(píng)閱統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)填寫）：全國(guó)評(píng)閱隨機(jī)編號(hào)（由全國(guó)組委會(huì)填寫）：（此編號(hào)專用頁(yè)僅供賽區(qū)和全國(guó)評(píng)閱使用，參賽隊(duì)打印后裝訂到紙質(zhì)論文的第二頁(yè)上。注意電子版論文中不得出現(xiàn)此頁(yè)，即電子版論文的第一頁(yè)為標(biāo)題、摘要和關(guān)鍵詞頁(yè)。）城市小區(qū)便民服務(wù)點(diǎn)的設(shè)置及調(diào)度優(yōu)化模型摘要隨著經(jīng)濟(jì)不斷增長(zhǎng)，基礎(chǔ)設(shè)施的需求不斷增加，便民服務(wù)點(diǎn)作為城市基礎(chǔ)化建設(shè)的重要組成部分仍需不斷完善。由于人力、物力和資金等資源是有限的，如何根據(jù)城市的小區(qū)實(shí)際分布情況及需求合理地設(shè)置小區(qū)便民服務(wù)點(diǎn)，分配各服務(wù)點(diǎn)的服務(wù)范圍，充分利用有限資源為全市市民提供一個(gè)生活方便、優(yōu)質(zhì)的服務(wù)，是有關(guān)部門面臨的一個(gè)實(shí)際問題。問題一：分配各便民服務(wù)點(diǎn)的服務(wù)范圍（1）題目要求在全市12個(gè)便民服務(wù)點(diǎn)位置確定的情況下，按照盡量短時(shí)間內(nèi)到達(dá)服務(wù)點(diǎn)和工作量均衡的原則為各便民服務(wù)點(diǎn)分配服務(wù)范圍。對(duì)此問題本文用算法建立最短路徑模型，利用進(jìn)行求解，得到每個(gè)服務(wù)點(diǎn)到居民點(diǎn)的最短路徑。（2）我們對(duì)于120個(gè)居民點(diǎn)在最短時(shí)間到達(dá)服務(wù)點(diǎn)的問題，以所用時(shí)間最小為目標(biāo)，建立0-1整型規(guī)劃模型，借助進(jìn)行求解，得出各條路徑所需最短時(shí)間，結(jié)合（1）最后得到全市現(xiàn)有每個(gè)便民服務(wù)點(diǎn)的服務(wù)范圍如表1。問題二：對(duì)于確定需要增加服務(wù)點(diǎn)的具體個(gè)數(shù)和位置的問題由問題一的分配結(jié)果可知，在現(xiàn)有便民服務(wù)點(diǎn)的設(shè)置下：①還有幾個(gè)居民點(diǎn)不能在平均時(shí)間內(nèi)到達(dá)服務(wù)點(diǎn)，即到達(dá)服務(wù)點(diǎn)時(shí)間過長(zhǎng)②我們根據(jù)便民服務(wù)點(diǎn)工作量的方差定義工作量不均衡度，結(jié)果顯示：此時(shí)服務(wù)點(diǎn)的工作量不均衡度為6.5。為解決到達(dá)服務(wù)點(diǎn)時(shí)間過長(zhǎng)和便民服務(wù)點(diǎn)工作量不均衡的問題。我們建立最優(yōu)化模型，求解結(jié)果表明：在增加三個(gè)服務(wù)點(diǎn)的情況下，可以解決居民點(diǎn)到服務(wù)點(diǎn)時(shí)間過長(zhǎng)的問題。在此基礎(chǔ)上我們優(yōu)化分配方案：在增加幾個(gè)便民服務(wù)點(diǎn)的情況下，使服務(wù)點(diǎn)的工作量不均衡度降為多少。增加的三個(gè)服務(wù)點(diǎn)路口標(biāo)號(hào)見表2。關(guān)鍵詞：最短路徑算法0-1整型規(guī)劃模型最優(yōu)化模型問題重述某市為了方便市民生活，打算在市內(nèi)小區(qū)設(shè)置便民服務(wù)點(diǎn)，為市民就近提供醫(yī)療衛(wèi)生、繳費(fèi)等公共服務(wù)，但由于人力、物力和資金等資源是有限的，如何根據(jù)城市的小區(qū)實(shí)際分布情況及需求合理地設(shè)置小區(qū)便民服務(wù)點(diǎn)，分配各服務(wù)點(diǎn)的服務(wù)范圍，充分利用有限資源為全市市民提供一個(gè)生活方便、優(yōu)質(zhì)的服務(wù)，是有關(guān)部門面臨的一個(gè)實(shí)際問題。問題一：為了提高便民服務(wù)點(diǎn)的服務(wù)效率，同時(shí)考慮每個(gè)服務(wù)點(diǎn)工作量的均衡性，該市打算將居民點(diǎn)劃片服務(wù)，每個(gè)服務(wù)點(diǎn)面向一些居民點(diǎn)服務(wù)；建立數(shù)學(xué)模型，為各便民服務(wù)點(diǎn)分配服務(wù)居民點(diǎn)的范圍，使其在所服務(wù)居民點(diǎn)范圍內(nèi)的居民盡量在最短時(shí)間內(nèi)到達(dá)服務(wù)點(diǎn)，同時(shí)又要使每個(gè)服務(wù)點(diǎn)的工作量盡可能的均衡。問題二：根據(jù)現(xiàn)有便民服務(wù)點(diǎn)的工作量不均衡和有些居民點(diǎn)到達(dá)服務(wù)點(diǎn)時(shí)間過長(zhǎng)的實(shí)際情況，擬在該市內(nèi)再增加1至3個(gè)服務(wù)點(diǎn)，請(qǐng)確定需要增加服務(wù)點(diǎn)的具體個(gè)數(shù)和位置。該市目前有120個(gè)居民點(diǎn)和12個(gè)便民服務(wù)點(diǎn)，居民點(diǎn)和便民服務(wù)點(diǎn)的網(wǎng)絡(luò)分布情況見支持資料1，每個(gè)居民點(diǎn)位置、居民人口數(shù)和道路連接的數(shù)據(jù)信息見支持資料2；支持資料1：該市居民點(diǎn)和便民服務(wù)點(diǎn)的網(wǎng)絡(luò)分布示意圖。支持資料2：該市居民點(diǎn)位置、居民人口數(shù)和道路連接的相關(guān)數(shù)據(jù)表。、問題的分析問題一：?jiǎn)栴}要求在市內(nèi)的12個(gè)便民服務(wù)點(diǎn)位置確定的情況下，按照盡量短時(shí)間內(nèi)到達(dá)服務(wù)點(diǎn)和工作量均衡的原則為各便民服務(wù)點(diǎn)分配服務(wù)范圍。本文引入賦權(quán)圖中任意兩頂點(diǎn)間的最短路理論中的算法和0-1整型規(guī)劃模型進(jìn)行求解。記i€1,2,,120;為市內(nèi)所有居民點(diǎn)的節(jié)點(diǎn)集合，j€1,2,,12;為全市便民服務(wù)點(diǎn)的節(jié)點(diǎn)集合，c(i€1,2,,120;j€1,2,,12)為便民服務(wù)點(diǎn)j到達(dá)居ij??????民點(diǎn)i的最短距離。??? ???引入0T變量x(i€1,2,,120;j€1,2,,12),當(dāng)居民點(diǎn)i分配給便民服務(wù)ij點(diǎn)j管轄是為1,當(dāng)居民點(diǎn)i不分配給便民服務(wù)點(diǎn)管轄是為0。即：??????A第i個(gè)居民點(diǎn)由第j個(gè)服務(wù)點(diǎn)服務(wù)j[0,第i個(gè)居民點(diǎn)不由第j個(gè)服務(wù)點(diǎn)服務(wù)由題目可知當(dāng)c相對(duì)較小時(shí)，居民點(diǎn)i可能分配給便民服務(wù)點(diǎn)j，也可ij能分配給其他可在較短時(shí)間內(nèi)到達(dá)居民點(diǎn)的便民服務(wù)臺(tái)，而不分配給/，故有x€1；當(dāng)c相對(duì)較大時(shí)，居民點(diǎn)i不能在較短時(shí)間內(nèi)到達(dá)服務(wù)點(diǎn)j,故ij ij此時(shí)路口i不能分配給便民服務(wù)點(diǎn)j管轄，故此時(shí)x=0。ij根據(jù)上述的分配原則及每個(gè)路口只由一個(gè)便民服務(wù)點(diǎn)進(jìn)行管轄、每個(gè)便民服務(wù)點(diǎn)至少要管轄一個(gè)路口，可首先利用算法計(jì)算出12個(gè)服務(wù)點(diǎn)到120個(gè)居民點(diǎn)的最短路徑，然后建立0-1規(guī)劃模型，并借助進(jìn)行區(qū)域劃分。問題二：根據(jù)問題一（1）的分配方案可知此時(shí)每個(gè)便民服務(wù)點(diǎn)的工作量分別為：表1按問題一的分配方案12個(gè)便民服務(wù)點(diǎn)的工作量編號(hào)123456工作量21946916編號(hào)789101112工作量412912612此時(shí)便民服務(wù)點(diǎn)的工作量不均衡度為6.3圖1居民點(diǎn)和便民服務(wù)點(diǎn)的網(wǎng)絡(luò)布情況注：圖中圓圈“o*”表示設(shè)置了服務(wù)點(diǎn)；距離單位：公里由問題一可知現(xiàn)有便民服務(wù)點(diǎn)的工作量極其不均衡且有些地方路徑過長(zhǎng)。針上述問題，題目要求再增加1—3個(gè)便民服務(wù)點(diǎn)來解決上述問題。本文建立優(yōu)化模型，然后利用對(duì)模型進(jìn)行增加的平臺(tái)個(gè)數(shù)，可得到初步的分配方案，最后再引入工作量不均衡度，通過計(jì)算求解可確定增加便民服務(wù)點(diǎn)的數(shù)目及位置。三、 模型的假設(shè)假設(shè)每個(gè)便民服務(wù)點(diǎn)的職能和人力配備基本相同假設(shè)每個(gè)路口只由一個(gè)便民服務(wù)點(diǎn)進(jìn)行管轄；假設(shè)每個(gè)便民服務(wù)點(diǎn)至少管轄一個(gè)路口；?假設(shè)居民都按最短路徑到達(dá)各服務(wù)點(diǎn)；?工作量：每個(gè)便民服務(wù)點(diǎn)所管轄范圍內(nèi)的所有居民點(diǎn)人數(shù)之和?時(shí)間：居民到達(dá)服務(wù)點(diǎn)所需時(shí)間；四、符號(hào)說明dij第i個(gè)居民點(diǎn)到第j個(gè)便民服務(wù)點(diǎn)的最短距離ci第i個(gè)居民點(diǎn)人數(shù)j第j個(gè)便民服務(wù)點(diǎn)i第i個(gè)居民點(diǎn)W總總?cè)藬?shù)Q新增點(diǎn)候選集xij居民點(diǎn)i是否分配給便民點(diǎn)jqi工作量li距離pj目標(biāo)值jfc均方差五、模型的建立及求解5.1問題一（1）：服務(wù)范圍的確定——算法最短路徑模型

5.1.1模型建立：算法：根據(jù)問題一（1）的分析確定函數(shù)為目標(biāo)函數(shù)：€,￡?約束條件：,12)x={第i個(gè)路口節(jié)點(diǎn)到第j個(gè)服務(wù)平臺(tái) （i€1,2, ,120;j€1,2,,12)ij0第i個(gè)路口節(jié)點(diǎn)不到第j個(gè)服務(wù)平臺(tái)x€1, (i€1,2, ,12)ii,x€1,(i€1,2, ,120)?…ijj€1I二-120cxIva,(j€1,2, ,12)12 iiji€1因cx=q (j=1,2,12)…iijii€1max(xd)=L (j=1,2,,12)1?i?120ijij jI需-,c.x..I=p.,(j.€1,2,,12)12 ii ji€1jfcjfc€5.1.2模型求解1.最短路徑矩陣A的建立本文選用算法確定市內(nèi)任意兩個(gè)路口之間的最短路徑矩陣d。算法ij為：從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能，1是直接從i到j(luò)，2是從i經(jīng)過若干個(gè)節(jié)點(diǎn)x到j(luò)。所以，我們假設(shè)d為節(jié)點(diǎn)i到節(jié)點(diǎn)j的ij最短路徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn)X，我們檢查d€d<d是否成立，如ixxjij果成立，證明從i到X再到j(luò)的路徑比i直接到j(luò)的路徑短，我們便設(shè)置d，d€d，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn)x，d中記錄的便是i到j(luò)ijixxj ij的最短路徑的距離。通過上述算法，利用數(shù)學(xué)軟件計(jì)算出各節(jié)點(diǎn)的最短路徑，組成一個(gè)最短路徑矩陣d 。120—120圖2偏差值及目標(biāo)最優(yōu)解的坐標(biāo)圖0005323332503131值數(shù)函標(biāo)目50010001500200025003000350040004500a的值由圖可看出在1500附近，目標(biāo)函數(shù)值變動(dòng)最小，為此我們選擇1500為偏差限目標(biāo)值：3518.575.1.3最終分配方案的確定從最短路徑矩陣中，我們可以清楚看到如下問題：（1）在僅滿足分配標(biāo)準(zhǔn)時(shí)有些路口可以被多個(gè)路口管轄；（2）在僅滿足分配標(biāo)準(zhǔn)時(shí)個(gè)別居民點(diǎn)離服務(wù)點(diǎn)距離過大；那么此時(shí)并不滿足模型的要求必須對(duì) 進(jìn)行處理，以得到滿足要120-20求的最終分配方案。首先解決（1）中出現(xiàn)的問題，此過程我們利用數(shù)學(xué)軟件進(jìn)行處理，相應(yīng)的程序見附錄。步驟一：由集合覆蓋矩陣A 將120個(gè)居民點(diǎn)分為A、B、C三類：120-20A類：已只由一個(gè)巡警服務(wù)臺(tái)進(jìn)行管轄；B類：可被多個(gè)巡警服務(wù)臺(tái)進(jìn)行管轄；C類；還不能被任何巡警服務(wù)臺(tái)進(jìn)行管轄；步驟二：將A類中的路口直接分配給對(duì)其進(jìn)行管轄的唯一的巡警服務(wù)臺(tái)。步驟三：將B類中的路口按最近原則分配給距離它最近的巡警服務(wù)臺(tái)。然后解決（2）中的問題。將任何服務(wù)點(diǎn)都不能在規(guī)定時(shí)間內(nèi)到達(dá)的居民點(diǎn)按就近原則進(jìn)行分配。表2最后得到最終的分配方案如下：服務(wù)平臺(tái)管轄范圍服務(wù)人數(shù)（人）最長(zhǎng)距離A11,19,64,65,70,71,72,73,74,7,76,77,80,811610056.54864A22,42,43,66,67,68,69,78,791480068.19103A33,18,20,40,44,53,54,6313300115.0042

A44,49,52,56,57,58,59,60,61,62,991560052.10555A55,22,30,47,4&50,51,55,1340052.50731A66,32,33,34,35,36,37,45,46,891630040.04293A77,15,2&29,31,106,1091440098.17466A8&13,21,23,24,25,26,27,82,1460050.93686A99,14,83,84,85,86,87,88,90,921540055.85048A1010,16,38,39,91,93,94,95,9&100,103,1470047.01612All11,96,97,101,102,104,10&113,115,117,1201330072.03523A1212,17,41,105,107,110,111,112,114,116,11&1191560074.349544圖3居民點(diǎn)和便民服務(wù)點(diǎn)的最短路徑網(wǎng)絡(luò)用設(shè)計(jì)增加的平臺(tái)個(gè)數(shù)5.2問題二：確定增加平臺(tái)的個(gè)數(shù)及位置用設(shè)計(jì)增加的平臺(tái)個(gè)數(shù)5.2.1模型的建立及求解優(yōu)化模型建立：根據(jù)問題一確定函數(shù)為：=為120i€1j€1約束條件：1選擇第個(gè)路口節(jié)點(diǎn)到第 個(gè)服務(wù)平臺(tái)不選擇第 個(gè)路口節(jié)點(diǎn)到第 個(gè)服務(wù)平臺(tái)i€1,2,_,12j€1,2, ,120)X=1 (i=1,2, ,12)ii??????C€1,2,,12)(j，1,2, ,120)( ) (i，1,2, ,12j，1,2, ,120)ijij2當(dāng)x三0時(shí),至否則為jj??????a<13533 得到的最優(yōu)目標(biāo)函數(shù)值要小于1353321133?120<(1,2,???，12)1，1根據(jù)平局工作量公式及工作量不均衡度公式，利用分別對(duì)分配方案中巡警服務(wù)臺(tái)的工作量不均衡度進(jìn)行計(jì)算。從49至64范圍內(nèi)取出若干個(gè)偏差限及所對(duì)應(yīng)的目標(biāo)函數(shù)值，得坐標(biāo)圖如下：圖4偏差值及目標(biāo)最優(yōu)解的坐標(biāo)圖

由圖可看出在1500附近，目標(biāo)函數(shù)值變動(dòng)最小，為此我們選擇1500為偏差限最優(yōu)目標(biāo)函數(shù)值2618.287增加3個(gè)服務(wù)點(diǎn)，標(biāo)號(hào)及坐標(biāo)分別為20（244,134）109（19,56）116（248,76）最后，利用運(yùn)用搜索法得到：至少?gòu)暮蜻x集Q中選出3個(gè)路口來設(shè)置便民服務(wù)點(diǎn)，才能解決到服務(wù)點(diǎn)時(shí)間過長(zhǎng)的問題。此時(shí)共有1938種可能

的分配方案。表2滿足題目二要求的3個(gè)便民服務(wù)點(diǎn)的路口標(biāo)號(hào)表3方案一中15個(gè)服務(wù)點(diǎn)的管轄范圍服務(wù)平臺(tái)管轄范圍服務(wù)人數(shù)（人）取長(zhǎng)距離Al1,19,64,65,70,71,72,73,74,76,77,80,811310056.54864A22,42,43,66,67,68,69,751330060.79228A33,1&40,44,53,54,631310069.64803A44,49,52,56,57,5&59,60,61,62,99980052.10554A55,22,30,47,48,50,511350052.50731A66,32,33,34,35,36,37,45,461330040.04293A77,15,2&29,31,106,1091040084.98434A8&13,21,23,24,25,26,27,821160050.93683A99,14,85,86,87,88,90,921070034.13871A1010,16,3&39,94,93,91,95,9&100,1031310046.08345All11,96,97,101,102,104,10&113,115,117,1201040072.03523A1212,41,105,107,110,111,1121310032.949472018,20,75,76,77,7&79,80,81,1320036.779439922,48,99690052.8131610625,26,27,28,82,1061200027.26469五、模型的評(píng)價(jià)及推廣優(yōu)點(diǎn)：采用離散定位模型作為城區(qū)巡警服務(wù)臺(tái)優(yōu)化布局方法的應(yīng)基礎(chǔ),結(jié)合相關(guān)的影響因素，能很好地解決實(shí)際問題。本文把實(shí)際問題抽象成集合模型、規(guī)劃和圖論，完整準(zhǔn)確的描述了實(shí)際問題。本文所用算法，效率好精度高解決實(shí)際問題方便快捷。缺點(diǎn)：本文對(duì)工作量的定義只考慮路口發(fā)案率，沒有不同區(qū)人密度對(duì)便民服務(wù)點(diǎn)工作量的影響。本文較少考慮不同區(qū)的路口發(fā)案率相差加大，導(dǎo)致服務(wù)點(diǎn)工作量難以均衡。模型推廣：本模型不僅對(duì)便民服務(wù)點(diǎn)適用，而且可以廣泛運(yùn)于消防站、醫(yī)院等應(yīng)急服務(wù)設(shè)施的布局。六、參考文獻(xiàn)謝金星，優(yōu)化模型及軟件，北京：清華大學(xué)出版社，2006年。王沫然，及科學(xué)，北京：電子工業(yè)出版社，2008年。方世昌，離散數(shù)學(xué)，西安：西安電子科技大學(xué)出版社，2009年吳美文，基于離散定位模型的城市消防站優(yōu)化布局方法*，系統(tǒng)仿真技術(shù)，2006年1月第2卷第一期：58-62頁(yè)。陳馳任愛珠，消防站布局優(yōu)化的計(jì)算機(jī)方法[J],清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2003,43(10)：1390~1393。陳艷艷郭國(guó)旗，城市消防站的優(yōu)化布局[J].消防科技，1999,(1)：26?28吳軍，消防站優(yōu)化布局方法及技術(shù)研究，消防科學(xué)及技術(shù)2006年1月第25卷第1期七、附錄附錄1(算法求最短路徑及距離)建立帶權(quán)鄰接矩陣A：('C:\\\\1');(:,1);(:,2);(:,3);(