數(shù)學建模 電梯調度問題19.doc

建模第31小組李騰飛楊苗青張云飛電梯的調度問題一、摘要本文針對上下班高峰期電梯的調度問題進行了研究，對上、下班人群采用顧客的滿意度（與電梯的運行總時間成正相關）和電梯行駛的總長度作為評價指標，運用啟發(fā)式算法，對結果進行了優(yōu)化，并將結果與傳統(tǒng)的算法得出結果進行比較。由于現(xiàn)在社會人們對居住環(huán)境的需求差異較大，導致一個公司職工居住地分散，直接引起了職工到達公司的時間差異，雖然每個人到公司的時間有一定的差異，但是在一個相對較短的時間段里到達，再加上電梯運行時間的消耗，可看成每次電梯啟動打開電梯門的人數(shù)都滿足下面算法對電梯的需求，即人可看成在同一點到達，從而減少了計算量。針對這個算法編寫c語言程序，帶入題中給定的數(shù)據(jù)進行求解。同樣對于下班高峰期的的計算為上班的逆運算，直接用上班的計算數(shù)據(jù)即可。再將所得的優(yōu)化解與傳統(tǒng)解以各自的評價指標進行比較，證明了該算法的可靠性.二、問題的提出商業(yè)中心的寫字樓有二十二層地上建筑樓層和兩層地下停車場，六部電梯，每部電梯的最大載重是20個正常成人的載重和，要求在電梯的運行期間，電梯的搭載乘客不能多于20人。工作日里每天早晚高峰期均是非常擁擠，導致乘客平均等待時間明顯增加，而在高峰期外人流密度相對較小，可以近似忽略人員的流動?？紤]到公司員工以中等收入為主（忽略高收入人停車在地下樓層等待）均從一樓開始等待乘電梯上樓。每層樓的平均辦公人數(shù)經(jīng)調查已知。假設每層樓之間的電梯平均隱形時間是3秒，在滿足電梯在各層相應的停留時間內乘梯人員能夠完成出入電梯最底層人員出入量較大平均停留時間定為20秒，其他各層人員流動量較小，平均停留時間定為10秒，題中給出了該寫字樓個樓層的平均辦公人數(shù)（見附表一）針對該問題給出一個最優(yōu)的電梯調度方案，從題設中可以看出，要求電梯的調度最優(yōu)，以電梯的行駛總長度為評價指標，就要盡可能的減少電梯的停留期時間，同樣也要提高電梯的吞吐率（電梯停留一次所進出乘客的數(shù)量），想辦法降低這兩個的時間消耗是本題的關鍵。三、問題的分析由于上下班相對于本題的模型可看成是一個逆問題，因此僅考慮上班電梯調度的最優(yōu)解即可根據(jù)逆運算得出下班的最優(yōu)解?？偟碾娞菪旭偟拈L度等于各個電梯運行長度之和，減少總長度的關鍵在于提高電梯運行效率（電梯的載客人數(shù)/電梯的運行長度）。減小電梯的運行時間關鍵在于減小電梯的停留次數(shù)，這就要求電梯在工作時間內必須盡可能多的滿載運行。提高電梯的吞吐率關鍵在于電梯運行時電梯內的乘客應盡量多的有相同的目的地即樓層。四、符號代表意義/ 電梯總的工作時間（i=1、2、3、4、5、6） 電梯i總的運行時間 / 上班高峰期時各個電梯運行時間之和（j=2、320）（i=1、2、3、4、5、6） 電梯i從底層到j層的運行樓層數(shù) （i=1、2、3、4、5、6）（j=2、320）（k=1、2、3.）電梯i運行k次時從地上一層到j層的載客人數(shù) （i=1、2、3、4、5、6）電梯i總的停留時間 電梯的吞吐率 （i=1、2、3、4、5、6）電梯i的吞吐率 電梯運行效率 （i=1、2、3、4、5、6）（k=1、2、3.）電梯i第k次運行的效率/ 總的運行路程H 一層樓的高度五、模型的假設1、上下班高峰期時職工均可看成在同一時間到達電梯口。2、上班時在電梯啟動前電梯處在地上一層，下班時電梯啟動前處在頂層。3、電梯在上下樓時在各層的運行速度相等即電梯的運行時間與經(jīng)過的樓層數(shù)成正比（不考慮電梯停留的前提下）即各個樓層的高度相等。4、假設此樓層沒有樓梯，各個乘客必須乘坐電梯上下樓。5、乘客進出樓梯服從安排，不依據(jù)自己的意愿，運行期間不出現(xiàn)電梯擁堵現(xiàn)象延長停留時間。6、各個電梯獨立正常運行，相互之間沒有干擾且均聽從調度，每個服務響應均由一個電梯控制器調度各部電梯來完成每個服務任務，命令時間可忽略不計。7、運行時間不出現(xiàn)停電和一切影響電梯正常運行的故障，電梯按照指揮者的意愿可靠運行。8、假設題設條件真實可靠。9、假設公司職工體重大體相等，不出現(xiàn)過輕過重的人，變化電梯的最大搭載人數(shù)。六、模型的建立1、電梯運行效率=（+）/62、電梯的運行時間S=max+，+3、電梯的吞吐率=4、電梯的總的運行路程=(-)*H5、電梯總的工作時間=+七、模型的分析該模型的目的是去得最優(yōu)的電梯調度發(fā)，而主要的解決問題在于電梯運行效率的提高，同樣我們不難理解電梯的運行時間越短電梯的運行效率越高，并且有電梯的吞吐率越高電梯的運行效率越高，則求解該模型的關鍵在于如何縮短電梯的運行時間和提高電梯的吞吐率上面。電梯的運行時間有兩部分組成（電梯的運動時間和電梯在各層的停留時間）因此我們可以從兩方面著手。減少可以看成是減少電梯的運行次數(shù)，必須做到使電梯每次上升前能做到盡可能多的搭載乘客，為此我們得出當?shù)匾粚邮Ｓ嗳藬?shù)大于二十人之前電梯的載客量應均為二十。要增加即使在滿足電梯滿載的情況之下使電梯的中乘客盡可能前往少的樓層，這就要求電梯的乘客類別盡可能的單一（即在前往某一樓層的人數(shù)大于二十的前提這下，該電梯僅在一個樓層停留然后返回一層）。而這些這表最終反映在電梯總的運行路程和工作時間上，通過比較運行路程和工作時間進行優(yōu)化與否的判定。八、數(shù)據(jù)的分析和模型的求解表1：該寫字樓各層辦公人數(shù)樓層人數(shù)樓層人數(shù)樓層人數(shù)12345678無208177222130181191236910111213141516236139272272272270300264171819202l22200200200200207207當電梯運行一段時間后，開始層剩余各層人數(shù)樓層人數(shù)樓層人數(shù)樓層人數(shù)123456780817210111169101112131415161619121212004171819202l22000077通過excel計算六部電梯在完全搭載同樓層乘客停留的總時間=30*（0+10+8+11+6+9+9+11+11+6+13+13+13+13+15+13+10+10+10+10+10+10）=6630s六部電梯在完全搭載同樓層乘客運行的總時間=8205s當搭載不同層的顧客是計算方法與最短路問題類似，通過編寫C語言程序實現(xiàn)經(jīng)運算得到的結果：電梯運行一個來回在樓層停留兩次數(shù)：6電梯運行一個來回在樓層停留一次數(shù)：3搭載剩余乘客運行樓層：148搭載剩余乘客運行時間：148*3=444s帶入數(shù)據(jù)可得到總的停留時間之和=30*3+40*6+=6960s運行的總時間=8250+444=8694s總的運行路程=(-)*H=1734H同理也可得出下樓時電梯的運行時間=6960s總的運行路程=1734H八、模型的評價倘若采用傳統(tǒng)的算法，各樓層乘客搭載電梯隨機，不妨采用折中算法。=（max+min）/2=(max+min)/2有max130*(20+10*21) 很容易證明即結果進行了一定的優(yōu)化。九、模型的改進該模型沒有考慮乘客的意愿，如果附帶平息一下乘客的不滿心理，我們可以采用另外一種電梯搭載乘客方案。題設部分和上面模型一樣，但運送乘客順序有所調整，可以采用當電梯運送完一批乘客之后回到底層讓他們搭載等待上樓中的乘客人數(shù)最多的樓層，直至各個樓層的剩余乘客量均小于二十，載接著采用上述的運送方法，可以驗證總的運行時間和總的運行路程和上面方法一樣，但在顧客的滿意度會有所上升，更加的符合實際、貼近現(xiàn)實。同樣該模型還有不完善的地方，如對于剩余各層乘客的處理僅運用了一個和兩個樓層的搭配組合，并不能達到最優(yōu)結果，可以進一步的擴展樓層的搭配個數(shù)，使結果進一步的優(yōu)化，但由于時間限制，未能給出改造。十、參考文獻【1】堵丁柱 .k車服務問題與競爭算法 J.數(shù)學的實踐與認識，1991（4）：36-40.附錄 C語言程序#includevoid main()int a21,i,j,k,s,m=20,p,q,b=0,c=0,t,r=0,x=0,v=0; for(i=0;i=21;i+)scanf(%d,&ai);for(i=0;i=21;i+)if(i%5=0)printf(n);printf(%4d,ai);printf(n);do x+;for(i=1;i=21;i+) for(j=i;j0)k=20-s;printf(%4d,k);else continue; m=m+k; if(k(m*1.0)/2)m=k;p=i;q=j; if(ap+aq)q)