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

5.1.1模型建立：算法：根據問題一（1）的分析確定函數為目標函數：€,￡?約束條件：,12)x={第i個路口節點到第j個服務平臺 （i€1,2, ,120;j€1,2,,12)ij0第i個路口節點不到第j個服務平臺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的建立本文選用算法確定市內任意兩個路口之間的最短路徑矩陣d。算法ij為：從任意節點i到任意節點j的最短路徑不外乎2種可能，1是直接從i到j，2是從i經過若干個節點x到j。所以，我們假設d為節點i到節點j的ij最短路徑的距離，對于每一個節點X，我們檢查d€d<d是否成立，如ixxjij果成立，證明從i到X再到j的路徑比i直接到j的路徑短，我們便設置d，d€d，這樣一來，當我們遍歷完所有節點x，d中記錄的便是i到jijixxj ij的最短路徑的距離。通過上述算法，利用數學軟件計算出各節點的最短路徑，組成一個最短路徑矩陣d 。120—120圖2偏差值及目標最優解的坐標圖0005323332503131值數函標目50010001500200025003000350040004500a的值由圖可看出在1500附近，目標函數值變動最小，為此我們選擇1500為偏差限目標值：3518.575.1.3最終分配方案的確定從最短路徑矩陣中，我們可以清楚看到如下問題：（1）在僅滿足分配標準時有些路口可以被多個路口管轄；（2）在僅滿足分配標準時個別居民點離服務點距離過大；那么此時并不滿足模型的要求必須對 進行處理，以得到滿足要120-20求的最終分配方案。首先解決（1）中出現的問題，此過程我們利用數學軟件進行處理，相應的程序見附錄。步驟一：由集合覆蓋矩陣A 將120個居民點分為A、B、C三類：120-20A類：已只由一個巡警服務臺進行管轄；B類：可被多個巡警服務臺進行管轄；C類；還不能被任何巡警服務臺進行管轄；步驟二：將A類中的路口直接分配給對其進行管轄的唯一的巡警服務臺。步驟三：將B類中的路口按最近原則分配給距離它最近的巡警服務臺。然后解決（2）中的問題。將任何服務點都不能在規定時間內到達的居民點按就近原則進行分配。表2最后得到最終的分配方案如下：服務平臺管轄范圍服務人數（人）最長距離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居民點和便民服務點的最短路徑網絡用設計增加的平臺個數5.2問題二：確定增加平臺的個數及位置用設計增加的平臺個數5.2.1模型的建立及求解優化模型建立：根據問題一確定函數為：=為120i€1j€1約束條件：1選擇第個路口節點到第 個服務平臺不選擇第 個路口節點到第 個服務平臺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當x三0時,至否則為jj??????a<13533 得到的最優目標函數值要小于1353321133?120<(1,2,???，12)1，1根據平局工作量公式及工作量不均衡度公式，利用分別對分配方案中巡警服務臺的工作量不均衡度進行計算。從49至64范圍內取出若干個偏差限及所對應的目標函數值，得坐標圖如下：圖4偏差值及目標最優解的坐標圖

由圖可看出在1500附近，目標函數值變動最小，為此我們選擇1500為偏差限最優目標函數值2618.287增加3個服務點，標號及坐標分別為20（244,134）109（19,56）116（248,76）最后，利用運用搜索法得到：至少從候選集Q中選出3個路口來設置便民服務點，才能解決到服務點時間過長的問題。此時共有1938種可能

的分配方案。表2滿足題目二要求的3個便民服務點的路口標號表3方案一中15個服務點的管轄范圍服務平臺管轄范圍服務人數（人）取長距離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五、模型的評價及推廣優點：采用離散定位模型作為城區巡警服務臺優化布局方法的應基礎,結合相關的影響因素，能很好地解決實際問題。本文把實際問題抽象成集合模型、規劃和圖論，完整準確的描述了實際問題。本文所用算法，效率好精度高解決實際問題方便快捷。缺點：本文對工作量的定義只考慮路口發案率，沒有不同區人密度對便民服務點工作量的影響。本文較少考慮不同區的路口發案率相差加大，導致服務點工作量難以均衡。模型推廣：本模型不僅對便民服務點適用，而且可以廣泛運于消防站、醫院等應急服務設施的布局。六、參考文獻謝金星，優化模型及軟件，北京：清華大學出版社，2006年。王沫然，及科學，北京：電子工業出版社，2008年。方世昌，離散數學，西安：西安電子科技大學出版社，2009年吳美文，基于離散定位模型的城市消防站優化布局方法*，系統仿真技術，2006年1月第2卷第一期：58-62頁。陳馳任愛珠，消防站布局優化的計算機方法[J],清華大學學報：自然科學版，2003,43(10)：1390~1393。陳艷艷郭國旗，城市消防站的優化布局[J].消防科技，1999,(1)：26?28吳軍，消防站優化布局方法及技術研究，消防科學及技術2006年1月第25卷第1期七、附錄附錄1(算法求最短路徑及距離)建立帶權鄰接矩陣A：('C:\\\\1');(:,1);(:,2);(:,3);(