實用文檔地鐵線路設計規劃問題模型摘要隨著中國城市化進程飛速發展，人們的通勤方式日新月異。人們從以前的步行的交通方式開始發展，出現了自行車，公交車，私家車等。到現在，城市規模越來越大，交通情況越來嚴峻。道路上的嚴重阻塞，導致原來方便快捷的交通方式失去了原有的優點。人們不得不又要去尋找更為方便快捷的交通方式。這時候地鐵出現了。地鐵是交通方式上的變革。和以往的交通方式不一樣，它并不需要占用陸上其他交通方式的線路，它擁有只屬于它自己的交通線路，交通站點。它不影響城市地上事物，它是一條穿梭于地下的一條巨龍。但是，正由于它的方便快捷，它穿梭于地底下，產生了高昂的建造費用，我們因此不得不考慮到各站點的分布問題，以修建最少的地鐵站點減少費用，滿足最多人們的使用需求。本文正是討論城市區域中的地鐵站點、線路建造問題。給出的問題是關于在一個不規則的城市范圍內選地鐵站，然后用最短的路線把各站間地鐵站連通。因此我們得出了以下的思路：每一個地鐵站可以當作一個原點，它的覆蓋范圍為一個圓，然后以某種規律的排布方式使城市被完全覆蓋后每個圓排布后的有效覆蓋面積最大。分析城市的圖形，以1中找到的排布方式，以最少的圖形填滿該城市圖形。圖中排布的點即為所求的地鐵站。根據所找到的地鐵站，按最少生成樹的辦法（prim）尋找最短的路線。關鍵字：prim算法完全覆蓋有效覆蓋面積覆蓋方式標準文案實用文檔一.問題重述地鐵線路設計規劃某城市中心城區（如圖1所示）規劃修建地鐵，要求從該中心城區任意一點出發，到最近的地鐵站的直線距離不超過800米，試通過建立模型解決下列問題：（1）最少要建多少個地鐵站？（2）按最少數量的地鐵站分布，設計出最佳的地鐵線路（要求不同的地鐵線路換乘能互相到達）。圖1：某城市中心城區的簡化圖，其中AGCB為梯形，DEFG為矩形，坐標A(0.5,4.8),B(0,2),BC=7.5,AG=3.5,DE=2.8,EF=7.3。圖中每單位長度表示實際距離3km。標準文案實用文檔二，問題的分析和符號說明本題中規劃的中心城區是一個不規則的圖形，所以地鐵分布時不能簡單的按規律建立。我們設想的是先建造一種擁有最佳有效面積的地鐵站點。首先，我們利用微分的思想，以地鐵站為圓心，800m為半徑畫圓再在圓內畫內接多邊形，希望最后能將兩個圓內內接多邊形重疊之后重疊的面積盡量少。之后，我們又從化學原子排列規律中得到了另一種模型，從中我們再比較選出最佳的模型。之后，我們利用CAD按比例畫出題目的圖與地鐵站點陣進行比較，為了獲取地鐵站間的距離，我們用C語言編了一個程序計算出每個地鐵站的距離矩陣，最后再利用Matlab畫出地鐵站點圖的最小生成樹，從中得出最佳路線。Sa最佳有效面積以一個地鐵站為中心，與其他地鐵站相鄰Y完全覆蓋狀態城市中的每個點都能被地鐵站覆蓋Y*臨界覆蓋狀態城市中的每個點恰好被完全覆蓋N非完全覆蓋狀態城市中存在沒有被地鐵站覆蓋的點S名義覆蓋面積一個地鐵站的所有面積地鐵站點陣以地鐵站為點，最佳有效面積為圖，如圖（1）城市圖題目給出的城市規劃圖1）標準文案實用文檔三，模型假設近似認為地鐵站是不占面積，都是一個質點；城市上的地面是平坦的；認為城市中心內的任意地方都是可以建設站點和線路的。四，模型建立這里，我們用到了兩個模型。模型（一）思路：我們拋開這個城市的圖形，以地鐵站為圓心，800m為半徑畫圓，得圖（a）。圓心Cr=800(a)然后，為了使所有兩個地鐵站能無縫地接在一起，我們把這個圖盡可能多地劃分成內接多邊形。如圖（b）~（e）。....（b） （c） （d） （e）標準文案實用文檔這里，我們又出現一個新的問題，要使內接多邊形能接在一起， 內接多邊形的角度必須能整除360，n邊形內角和為(n2)180，每個內角為(n2)180n。滿足整除360，只有n=3，4，6.現在，我們先假設n=3，則這個點有效面積Sa33r2；4n=4 ，則這個點有效面積 Sa 2r2 ；n=6，則這個點有效面積Sa33r2。2所以可得，取n=6時，有效面積Sa最大，即將地鐵站看成內接六邊形時， 兩個地鐵站之間銜接起來有效面積最大。標準文案實用文檔模型（二）：思路:考慮到每個地鐵站建成后都會覆蓋附近面積為 S的區域。但由思路一可知，Sa<S，所以思路二的基本想法就是允許 S有適當重疊，并得到重疊時的 Y*狀態，然后算出 Y*狀態下的Sa，通過比較各種重合狀態下的 Sa，選得最大的，就是我們要得到的最優設計。具體實現：考慮四個圓的圓心組成矩形的情況A可以看到，中間的A區域沒有被覆蓋，此時有兩種解決方案，一是在A區域的中心在建一個站，覆蓋掉空白的部分；二是直接使四個圓重疊，覆蓋空白部分。一方案：二方案：如果借用化學中晶胞的概念， 那么上兩個圖都可以提煉出各自的 “晶胞”，我標準文案實用文檔們稱之為“排列晶胞” ，如圖：一方案和二方案的排列晶胞圖是相同的：x· ·· ·為正方形，其中 x的值是 2 r ，可計算出該排列晶胞下的有效覆蓋面積Sa 2r2.考慮四個圓的圓心組成菱形的情況：如果組成普通菱形（銳角不是60度），和正方形相比，相同的多的點的有效覆蓋面積Sa減小（相同長度邊的正方形和菱形面積正方形的面積大） 。考慮銳角為60度的菱形：則排列晶胞有所改變，如圖：方案二：x是正六邊形，其中x23r,Sa3r2,3方案二：·x··是正三角形，其中x3r，Sa33。2r2標準文案實用文檔比較三中情況的 Sa，則第三種情況的 Sa是最優的。綜合上述兩種模型，最后得出的最佳有效面積皆為Sa33，因此，接下來，我2r2們就把一個地鐵站覆蓋的面積定為Sa33。2r2五，模型求解以一個地鐵站的有效面積為Sa33。將原題的城市圖按比例畫進地鐵站2r2點陣中，然后再將城市圖平移，旋轉，比較不同情況下，城市圖所含的點最少是多少，下面給出其中的幾種情況（圖內部線段的長度表示圖形所覆蓋的地鐵站數目）。標準文案實用文檔經過多次的比較，我們發現，城市圖中最少包含點陣中32個點，所以得知最少要建32個地鐵站才能完全鋪滿這個城市。標準文案實用文檔我們得出了多個含有32個點的地鐵站圖，我們從中選取了其中一個進行標號，再用C語言計算每個點間的距離（篇末附上了我們的C語言程序）去設計最佳路線。如圖（z）。z）下面是我們用程序算出來每個點到1~32點的距離。（文件中附上算出來的TXT文件）第1點到1~32點的距離是0.001349.002757.001361.412357.303603.672400.942746.803611.733656.104132.414961.394800.264980.595520.566305.556034.367201.696894.907683.757200.287322.907697.0010825.538432.808424.048641.5810819.129706.669600.219692.521453.89第2點到1~32點的距離是1349.000.001408.001392.281379.282374.532786.592400.042753.633669.543663.664150.214999.724800.044993.885526.996041.398026.846339.906921.667337.347200.017329.5611000.758656.598430.218427.4810823.059995.539703.299600.011475.54第3點到1~32點的距離是2757.001408.000.002430.841403.561360.473706.072789.132400.704177.343672.873659.465560.515007.914800.094981.396361.529023.726034.046338.287732.927338.897200.0911352.979100.008663.648431.4911004.9510475.3510005.629704.602474.92第4點到1~32點的距離是1361.411392.282430.840.001386.002755.001394.311385.732380.572400.012771.463665.853666.093664.784159.69標準文案實用文檔4983.464800.006666.325533.946349.856041.516039.896349.659699.547332.197200.007332.199600.008653.218429.628428.542500.01第5點到1~32點的距離是2357.301379.281403.561386.000.001369.002415.211385.731374.372773.962400.002770.964157.193667.423667.044147.724996.107693.124991.135542.426354.586039.896039.779992.207715.187333.527200.009699.549086.218656.598428.542854.63第6點到1~32點的距離是3603.672374.531360.472755.001369.000.003666.912385.761388.743657.542763.002400.054984.854152.203662.003665.725534.448804.504800.005000.566927.156344.436038.0710455.048305.897711.597328.999987.499691.129085.078649.383714.30第7點到1~32點的距離是2400.942786.593706.071394.312415.213666.910.001403.002766.001391.772415.213682.032400.062776.483683.264799.203669.355319.314995.936053.734800.005000.845550.948427.166037.966041.046355.578429.957328.817200.007335.423769.02第8點到1~32點的距離是2746.802400.042789.131385.731385.732385.761403.000.001363.001388.241385.732399.602771.462400.012773.963652.263666.096422.754148.224995.935000.004800.004995.828653.456349.986040.706039.898428.547714.827334.667200.003762.87第9點到1~32點的距離是3611.732753.632400.702380.571374.371388.742766.001363.000.002384.891374.371396.863649.252763.492400.162773.464145.747590.073667.044168.245538.434989.774800.059077.856917.186344.766037.298647.968302.417711.597327.884228.98第10點到1~32點的距離是3656.103669.544177.342400.012773.963657.541391.771388.242384.890.001391.002776.001383.241384.732409.133653.682400.015207.083656.794804.403667.813667.044159.197331.254994.714800.004997.497200.006348.026040.816040.464900.02第11點到1~32點的距離是4132.413663.663672.872771.462400.002763.002415.211385.731374.371391.000.001385.002400.471389.241388.242384.032771.466473.342762.503665.854164.213666.093665.917715.185542.924998.044800.007332.196928.15標準文案實用文檔6354.256039.895090.08第12點到1~32點的距離是4961.394150.213659.463665.852770.962400.053682.032399.601396.862776.001385.000.003665.962405.671382.741376.823665.857776.612400.062771.465005.654156.693666.098313.886349.855545.924995.827714.827714.456934.666349.655625.32第13點到1~32點的距離是4800.264999.725560.513666.094157.194984.852400.062771.463649.251383.242400.473665.960.001379.002777.004139.001385.734111.993649.914996.252400.042771.463665.856039.893666.093664.784157.196039.894995.824800.024996.106140.15第14點到1~32點的距離是4980.594800.045007.913664.783667.424152.202776.482400.012763.491384.731389.242405.671379.000.001398.002760.001382.245445.862390.953672.582774.972400.012774.476347.694153.703666.093667.426039.095538.934997.774800.016137.56第15點到1~32點的距離是5520.564993.884800.094159.693667.043662.003683.262773.962400.162409.131388.241382.742777.001398.000.001362.002404.806816.461374.372395.273680.992773.962400.016931.155000.094163.213667.046351.626353.135551.954997.496443.58第16點到1~32點的距離是6305.555526.994981.394983.464147.723665.724799.203652.262773.463653.682384.031376.824139.002760.001362.000.003648.968160.711385.231394.824796.603652.262762.507703.786025.634988.314147.726919.177318.106346.585533.447002.13第17點到1~32點的距離是6034.366041.396361.524800.004996.105534.443669.353666.094145.742400.012771.463665.851385.731382.242404.803648.960.004626.002754.004157.001392.781385.732399.604996.102771.462400.012771.464800.004156.693668.573666.097300.00第18點到1~32點的距離是7201.698026.849023.726666.327693.128804.505319.316422.757590.075207.086473.347776.614111.995445.866816.468160.714626.000.007380.008783.004098.605452.686810.555791.174032.075205.306473.346666.324410.485322.266422.758646.62第19點到1~32點的距離是標準文案實用文檔6894.906339.906034.045533.944991.134800.004995.934148.223667.043656.792762.502400.063649.912390.951374.371385.232754.007380.000.001403.003663.132384.891377.316338.744785.353658.292762.505533.946025.634993.164148.227799.39第20點到1~32點的距離是7683.756921.666338.286349.855542.425000.566053.734995.934168.244804.403665.852771.464996.253672.582395.271394.824157.008783.001403.000.005009.843665.962400.477332.456040.274806.133665.856349.857199.676050.524995.938396.68第21點到1~32點的距離是7200.287337.347732.926041.516354.586927.154800.005000.005538.433667.814164.215005.652400.042774.973680.994796.601392.784098.603663.135009.840.001400.002785.003663.471378.781389.242412.603668.772763.992400.002778.498530.02第22點到1~32點的距離是7322.907200.017338.896039.896039.896344.435000.844800.004989.773667.043666.094156.692771.462400.012773.963652.261385.735452.682384.893665.961400.000.001385.004157.192400.471389.241385.733666.093665.852777.992400.008527.56第23點到1~32點的距離是7697.007329.567200.096349.656039.776038.075550.944995.824800.054159.193665.913666.093665.852774.472400.012762.502399.606810.551377.312400.472785.001385.000.004995.933665.962405.671385.234156.694799.203675.682770.968748.42第24點到1~32點的距離是10825.5311000.7511352.979699.549992.2010455.048427.168653.459077.857331.257715.188313.886039.896347.696931.157703.784996.105791.176338.747332.453663.474157.194995.930.002400.002767.973666.601386.001385.231379.282400.4712180.03第25點到1~32點的距離是8432.808656.599100.007332.197715.188305.896037.966349.986917.184994.715542.926349.853666.094153.705000.096025.632771.464032.074785.356040.271378.782400.473665.962400.000.001379.002772.002771.461385.231379.282400.479799.65第26點到1~32點的距離是8424.048430.218663.647200.007333.527711.596041.046040.706344.764800.004998.045545.923664.783666.09標準文案實用文檔4163.214988.312400.015205.303658.294806.131389.241389.242405.672767.971379.000.001393.002400.012393.541388.741389.249700.01第27點到1~32點的距離是8641.588427.488431.497332.197200.007328.996355.576039.896037.294997.494800.004995.824157.193667.423667.044147.722771.466473.342762.503665.852412.601385.731385.233666.602772.001393.000.002771.463665.962411.731385.739797.39第28點到1~32點的距離是10819.1210823.0511004.959600.009699.549987.498429.958428.548647.967200.007332.197714.826039.896039.096351.626919.174800.006666.325533.946349.853668.773666.094156.691386.002771.462400.012771.460.002399.601392.281385.7312100.00第29點到1~32點的距離是9706.669995.5310475.358653.219086.219691.127328.817714.828302.416348.026928.157714.454995.825538.936353.137318.104156.694410.486025.637199.672763.993665.854799.201385.231385.232393.543665.962399.600.001372.002771.0011097.81第30點到1~32點的距離是9600.219703.2910005.628429.628656.599085.077200.007334.667711.596040.816354.256934.664800.024997.775551.956346.583668.575322.264993.166050.522400.002777.993675.681379.281379.281388.742411.731392.281372.000.001399.0010923.36第31點到1~32點的距離是9692.529600.019704.608428.548428.548649.387335.427200.007327.886040.466039.896349.654996.104800.014997.495533.443666.096422.754148.224995.932778.492400.002770.962400.472400.471389.241385.731385.732771.001399.000.0010921.50第32點到1~32點的距離是1453.891475.542474.922500.012854.633714.303769.023762.874228.984900.025090.085625.326140.156137.566443.587002.137300.008646.627799.398396.688530.028527.568748.4212180.039799.659700.019797.3912100.0011097.8110923.3610921.500.00接下來，我們再利用Matlab處理上面的數據，利用PRIMF算法（篇末我們附上了Matlab的代碼）得到最小生成樹的數據。T=標準文案實用文檔Columns1through9112565991124563981112Columns10through18121615192323221714161519232227171413Columns19through27132731282430302525103128243029252126Columns28through3110161257203218c=1.0e+003*Columns1through51.3490 1.3614 1.3793 1.3690 1.3605Columns6through101.3744 1.3630 1.3744 1.3850 1.3768Columns11through151.3620 1.3744 1.3773 1.3850 1.3852Columns16through201.3857 1.3822 1.3790 1.3832 1.3857Columns21through25標準文案實用文檔1.3857 1.3860 1.3793 1.3720 1.3793Columns26through301.3788 1.3790 1.3918 1.3948 1.4539Column314.0321>>上述數據T表達意思是，需要將圖中的點1與點2連線，點1與點4連線以此類推，圖中數據c表達的意思是將各點間連線的距離。按上Matlab得出的結論，我們畫出圖。即為最終的設計路線。圖中，我們用六邊形的右上頂點代替了圓心的位置得到的地鐵路線圖。所以等于將城市圖向六邊形的右