校車優(yōu)化配置.doc

隊號：H94校車優(yōu)化配置摘要本文解決的是一個校車配置及運行問題，目的是用盡可能少的車接送教職工，縮短他們的等車時間以及使他們在車上呆的時間盡可能短，同時校車耗油量較少，且不超載，并且要保證家住在不同地方的教職工均能準(zhǔn)時上下班。文中提出了一種解決此問題的模型。通過分析知，一個時刻需要的車數(shù)只與該時刻某一校區(qū)的最大轉(zhuǎn)移教職工數(shù)量有關(guān)，于是我們對題目所給的數(shù)據(jù)進(jìn)行一系列變換處理，求出每個時刻的最大轉(zhuǎn)移教職工數(shù)，得出一組數(shù)據(jù)。根據(jù)最大轉(zhuǎn)移教職工數(shù)量及校車的載客量，求出該時刻所需校車數(shù)量的最小值。綜合考慮等車時間，校車?yán)寐实龋覀兛梢越o出一天中兩個時間段（上午、下午和晚上）(劃分依據(jù)詳見問題分析)分別需要的校車總數(shù)，取這兩個時間段所需校車數(shù)目的最大值，即為全天所需校車的最少輛數(shù)，多次重復(fù)運算，取各天所需校車最少輛數(shù)的平均值作為學(xué)校需購置的最少校車數(shù)。然后將乘車時間、校車耗油量及須接送家住校外的教職工等因素考慮進(jìn)去，制定出一天中校車的分配及運行線路表。用我們構(gòu)造的模型，求出了一個簡單易行的配置計劃，并給出了校車分配及運行線路表。模型1中全天兩個時間段所需40座校車的最大數(shù)量的平均值為9，故學(xué)校需配置的校車最少輛數(shù)為9輛。模型2中需購置40座的校車6輛，20座的校車2輛，6座的校車4輛。一 問題的提出為學(xué)校制定校車的最優(yōu)化配置問題，要綜合考慮各時刻等待登車的教職工人數(shù)，他們的住所以及各趟的耗時、耗油等因素。題目給出了每天大約有450名教職工乘車從沙河校區(qū)到清水河校區(qū)上課，另外有一部分教職工需乘車到清水河校區(qū)上班；往返兩校區(qū)之間有一、二、三這三條線路可供選擇，其路況詳見表1。問題1有如下限制：學(xué)校配置的校車全為40座的大型車；在保證所有等待上車的教職工上車后都有座位的前提下，每個時刻發(fā)出的校車最少；各個時刻發(fā)出的校車必須沿途接送家住在校外的教職工；各趟選擇耗時較短且較節(jié)省油的線路。問題2有如下限制：學(xué)校需配置大型車（40座），中型車（20座），小型車（6座）三種類型的校車各數(shù)輛；根據(jù)各個時刻乘車人數(shù)的不同靈活分配校車的種類和數(shù)量；每個時刻發(fā)出的校車沿途接送家住在校外的教職工；各趟選擇耗時最短且較節(jié)省油的線路。我們的目標(biāo)就是根據(jù)題目所給的已知信息，把校車配置問題抽象成一個清晰完整的數(shù)學(xué)模型，并求解。根據(jù)我們的解，為學(xué)校制定合理的購車方案，并確定一天中（此處僅考慮周一至周五）不同時刻校車的最優(yōu)分配及運行線路，使學(xué)校能有效降低成本，減少開支，但又不犧牲教職工的利益。討論該配置及運行方案的合理性及可行性，并作改進(jìn)。 表1 各線路路況詳表參數(shù)線路總長(Km) 平均耗時(min) 路況第一條 45 3842 不易堵車第二條3040(非交通高峰期)5090(交通高峰期) 適中第三條 20 未知 極易堵車二 模型假設(shè) 1 由于每天從沙河校區(qū)到清水河校區(qū)上班的教職工必然能回到沙河校區(qū)，因此我們可將模型簡化為只考慮一天中教職工在沙河校區(qū)登車的五個時刻（為什么是五個時刻的原因參見表2）的情況； 2 不考慮周六、周日到清水河校區(qū)上課及上班的教職工數(shù)目對所需配置的校車總數(shù)的影響（由于周末到清水河上課的教職工人數(shù)很少，故能滿足周一至周五教職工上下班要求的校車數(shù)一定能滿足周末的需要）； 3上午到達(dá)清水河的校車中午全部回到沙河校區(qū)，下午和晚上到達(dá)清水河校區(qū)的校車在22:20之前也必須全部開往沙河校區(qū); 4忽略到清水河上班的教職工人數(shù)對校車分配的影響。認(rèn)為每天到清水河上班的教職工與上課的教職工相比人數(shù)很少，可以將他們安排在多余的座位上或者站在校車上，不影響實際所需校車數(shù)； 5 在一天中五個時刻登車的教職工數(shù)與全天總登車人數(shù)之比服從01區(qū)間上均勻分布； 6 假設(shè)學(xué)校的校車每天均能正常工作，不出現(xiàn)故障； 7 假設(shè)校車運行時刻表是確定的，車輛高峰期時段也是確定的（7：009：00，12：0013：00，17：3019：00）； 8只考慮夏季工作時間，認(rèn)為冬季各單位工作時間均在夏季的基礎(chǔ)上推遲半小時，故可認(rèn)為影響校車配置和運行的因素(如某時刻的登車人數(shù)、高峰期時間段長度等)不變；9 根據(jù)在網(wǎng)上所查資料（見附錄二），可近似認(rèn)為單位路程汽車的耗油量與座位數(shù)呈正比；10 假設(shè)學(xué)校購置的校車全為新車。三 變量說明 ：一天中沙河校區(qū)的第j個發(fā)車時刻，其中1j5，jN； ：第i天的時刻在沙河校區(qū)的登車的教職工人數(shù)，其中1i 10，iN； ：當(dāng)校車全為40座時,第i天在時刻所需校車數(shù)，N，即對代數(shù)式 = 取整 ：當(dāng)校車全為40座時,第i天所需校車數(shù)量，即第i天兩個時間段所需校車數(shù)的最大值. 四 問題的分析我們應(yīng)該在滿足教職工準(zhǔn)時上下班的前提下，合理安排各時刻車的發(fā)送數(shù)量，使各時刻發(fā)出的校車數(shù)最少，由此得到需要購置校車的最小值。然后綜合考慮運行時間，校車耗油量及須接送家住校外的教職工等因素，制定出一天中校車的分配及運行線路方案。我們的目標(biāo)是求每一時刻發(fā)車的輛數(shù)，發(fā)車數(shù)取決于該時刻要運送的教職工人數(shù)，那么我們就需要求出、五個時刻從沙河校區(qū)（只考慮沙河校區(qū)的原因在模型假設(shè)1中已述）發(fā)出的校車要運送的教職工人數(shù)，鑒于時間比較緊張，要統(tǒng)計一天中各時刻需要登車的教職工人數(shù)較難實現(xiàn)，我們采用數(shù)學(xué)方法對題目所給的數(shù)據(jù)進(jìn)行了變換處理，即認(rèn)為一天中五個時段需要登車的教職工是隨機的，各時刻登車人數(shù)與全天總登車人數(shù)之比服從01區(qū)間上的均勻分布，用計算機模擬產(chǎn)生450個01區(qū)間上的隨機數(shù)，統(tǒng)計出分別落入?yún)^(qū)間(00.2)，(0.20.4)，(0.40.6)，(0.60.8)，(0.81)上的隨機數(shù)個數(shù) (表示第i次模擬落入?yún)^(qū)間j(j取、)上的隨機數(shù)個數(shù))，以此估算出全天五個時刻登車的教職工人數(shù)（具體做法詳見模型1），然后算出各時刻需要分配的校車數(shù)，并采用特定算法計算出某一天所需校車的最小值 (具體算法見模型1).為保證計算結(jié)果的準(zhǔn)確性，我們將十次模擬產(chǎn)生的數(shù)據(jù),用極大似然估計法取平均值，得到較為準(zhǔn)確的校車配置數(shù)。再綜合考慮教職工居住地，投入成本及時間耗費等因素，制定出沙河校區(qū)和清水河校區(qū)校車分配及運行方案。五 模型的建立和求解根據(jù)上課時間，同時保證教職工上班時間最短，制定校車往返時刻表如下：表2 (參照附錄一)校車出發(fā)時間校車開往方向校車到達(dá)時間6:40()沙河校區(qū)至清水河校區(qū)7:408:40()沙河校區(qū)至清水河校區(qū)9:3010:00清水河校區(qū)至沙河校區(qū)11:0011:50清水河校區(qū)至沙河校區(qū)12:5013:20()沙河校區(qū)至清水河校區(qū)14:1015:10()沙河校區(qū)至清水河校區(qū)16:0016:30清水河校區(qū)至沙河校區(qū)17:3018:10()沙河校區(qū)至清水河校區(qū)17:1018:20清水河校區(qū)至沙河校區(qū)19:1022:20清水河校區(qū)至沙河校區(qū)23:10模型1先不考慮各時刻登車的教職工人數(shù)的差異，假設(shè)這450名教職工在全天五個時刻上車是隨機的,令產(chǎn)生的隨機變量X表示各時刻等待登車的教職工，若隨機變量XU（0，1）,即X服從（0，1）區(qū)間上的均勻分布，則有P0X0.2=0.2， P0.2X0.4=0.2， P0.4X0.6=0.2， P0.6X0.8=0.2，P0.8X1=0.2. 用計算機模擬產(chǎn)生450個01區(qū)間上的隨機數(shù)，附錄中的程序中編入了計算機模擬產(chǎn)生的十組在區(qū)間（0，1）區(qū)間上均勻分布的隨機數(shù)的具體算法，統(tǒng)計出分別落入?yún)^(qū)間（00.2），（0.20.4），（0.40.6），（0.60.8），（0.81）上的隨機數(shù)個數(shù) （表示第i次模擬產(chǎn)生的落入?yún)^(qū)間j(j可取、)上的隨機數(shù)個數(shù))我們認(rèn)為某一時刻登車的教職工數(shù)近似等于該時刻X出現(xiàn)的頻數(shù)，即=,表示第i天的時刻需要登車的教職工人數(shù)。由此我們繪出十天中各時刻等待登車的教職工人數(shù)分布表，見表3表3 十天中各時刻登車的教職工人數(shù)分布模擬表時刻登車人數(shù)次數(shù)19885761019028210991769238790839397499859087895931068979836768310299907871038581948781047788103989878994911084809810385根據(jù)模擬產(chǎn)生的表3可算出第i天在時刻所需校車的最少數(shù)量為 = (1i10; 1j5;i,jN)我們規(guī)定上午、時刻校車都到達(dá)清水河校區(qū)后,才有第一批校車回沙河校區(qū),因為在此情況下能夠避免校車空車返回,增大耗油量，并且由于路況因素未知可能使接送教職工的校車晚點,使等車時間延長,若、時刻發(fā)出的校車總數(shù)是當(dāng)日學(xué)校所能調(diào)動的最大校車量,此數(shù)量可能就是學(xué)校配置的校車數(shù),因此將、所在的時段看作一個整體;又由于時刻來上晚自習(xí)的教職工18:10就要在沙河校區(qū)登車,這個時間與下午回沙河的車時間上重疊,故將、所在的時段也看作一個整體,對第一個時段的分析方法對第二個時段同樣也適用。由于要保證所有教職工都能準(zhǔn)時上下班,故在兩個時段所需校車總數(shù)中取最大值即為一天所需校車數(shù)量，也就是學(xué)校應(yīng)配置的校車數(shù)N。為保證計算結(jié)果的準(zhǔn)確性，我們將十次模擬產(chǎn)生的數(shù)據(jù),用極大似然估計方法取平均值，得到較為準(zhǔn)確的校車配置數(shù)。運行程序 得到第i天所需的校車總數(shù)為= max(+),(+) (1i10 i) (見表4) 表4 每天所需校車數(shù)量分布表天次第一天第二天第三天第四天第五天第六天第七天第八天第九天第十天車數(shù)8 8 99899899該十個樣本的樣本均值= =8.6依據(jù)數(shù)理統(tǒng)計中關(guān)于參數(shù)的極大似然估計方法，統(tǒng)計出學(xué)校需購校車數(shù)量的值為，但考慮到實際情況，取實際所需配置的校車數(shù) N= =9此時樣本方差= =0.24方差值很小，故可認(rèn)為各天所需校車數(shù)與學(xué)校購置的校車數(shù)量基本相當(dāng)，即該種購置方案具有合理性。運行方案：為使老師等車時間盡量少,在交通低峰期盡量走路程最短，耗油少的第二條或第三條線路，而在8：40從沙河發(fā)出的校車；11：50從清水河發(fā)出的校車；18：10從沙河發(fā)出的校車；18：20從清水河發(fā)出的校車盡量走不太擁擠，耗時短的第一條線路，但為保證能接送所有教職工準(zhǔn)時上下班，每次往返于兩校區(qū)之間的校車必須至少分配一輛走第三條線路，考慮到實際家住校外的教職工比例不是很大（據(jù)統(tǒng)計占全校教職工總數(shù)的比例不到20%），因此可以認(rèn)為每個時刻分配一輛校車走第三條線路完全能接送完此刻需要登車的家住校外的教職工（假設(shè)各個時刻所有家住校外的教職工都乘坐走第三條線路的校車），因此為簡化模型，將一天中每個高峰期走第三條線路的校車減少為一輛。由此我們得出校車分配和運行方案。模型2與模型1相同,產(chǎn)生450個0到1的隨機數(shù)來模擬教職工在沙河校區(qū)的不同時刻(、)登車人數(shù)(參見表3)。增加變量：第i天的時刻所需40座的校車數(shù)；：第i天的時刻所需20座的校車數(shù)；：第i天的時刻所需6座的校車數(shù)。：統(tǒng)計十次模擬數(shù)據(jù)得到學(xué)校需購置的40座的校車數(shù)量的期望值；：統(tǒng)計十次模擬數(shù)據(jù)得到學(xué)校需購置的20座的校車數(shù)量的期望值；：統(tǒng)計十次模擬數(shù)據(jù)得到學(xué)校需購置的6座的校車數(shù)量的期望值。令、的初始值為0，對第i天的時刻登車人數(shù)求各種類型車的算法規(guī)定如下用除以40，得到的商為p，并求出余數(shù)q，綜合考慮購置校車的成本，各種車型的耗油量及座位利用率等因素，得出寧愿選擇一輛20座的中型車也不選用兩輛6座的小型車的結(jié)論，確定算法如下： 當(dāng)27q39時，再安排一輛40座的車，即=p+1, =0, =0；. 當(dāng)21q25時，再安排一輛20座的車，一輛6座的車，=p，=1，=1； 當(dāng)12q20時，再安排一輛20座的車；=p ，=1，=0； 當(dāng)7q11時，再安排兩輛6座的車；=p， =0，=2； 當(dāng)1q6時，再安排一輛6座的車。=p，=0，=1.（具體算法詳見附錄四）通過此算法,求得各個時刻需要各類車數(shù)量見表5 表5 時刻 車型次數(shù)T1T2T3T4T5402064020640206402064020612102011002112022201300202100202320220220121021042102011022022025210211202100201610020121121020272022112012012108100211100202211920220220221020210201200210211201同樣根據(jù)模型1的分析得：=max(+),(+)， 表示第i次模擬需要40座校車數(shù)量 =max(+),(+)， 表示第i次模擬需要20座校車數(shù)量 =max(+),(+)， 表示第i次模擬需要6座校車數(shù)量得到結(jié)果如表6表6車型座)車數(shù)次數(shù)40座20座6座15132504362446165523662376138513961410622同樣根據(jù)模型1的分析, 采用數(shù)理統(tǒng)計中參數(shù)的極大似然估計方法，統(tǒng)計出學(xué)校需購各類校車數(shù)量的期望值=5.6；=1.3；=3.5.根據(jù)實際情況，可得學(xué)校需配置的40座的校車數(shù)為 X=6；需配置的20座的校車數(shù)為 Y=2；需配置的6座的校車數(shù)為Z=4.通過以上算法確定出了各類校車的配置數(shù)，以下說明校車的運行方案。運行方案： 根據(jù)我們統(tǒng)計的數(shù)據(jù)，住在每次住在市區(qū)的教職工上班人數(shù)不到總教職工上班人數(shù)的20%（在模型1中已作了說明），根據(jù)表5模擬產(chǎn)生的人數(shù)，統(tǒng)計出每次有不到26名家住校外的教職工需要登車。根據(jù)模型1中的思想，為使老師等車時間盡量少,在交通低峰期盡量走路程最短，耗油少的第二或第三條線路，而在8：40從沙河發(fā)出的校車；11：50從清水河發(fā)出的校車；18：10從沙河發(fā)出的校車；18：20從清水河發(fā)出的校車盡量走不太擁擠，耗時短的第一條線路，但為保證能接送所有教職工準(zhǔn)時上下班，每次往返于兩校區(qū)之間的校車在高峰期至多分配一輛20座和一輛6座的走第三號線路，具體分配方案根據(jù)當(dāng)時家住校外的教職工人數(shù)而定,以期達(dá)到校車座位利用率和耗油量達(dá)到最優(yōu)。六 模型評價及改進(jìn)1 在確定校車數(shù)時，用計算機模擬來產(chǎn)生一天中五個時刻在沙河校區(qū)登車的教職工數(shù)，并采用樣本估計總體的思想估計實際值，解決了時間有限從而采集數(shù)據(jù)難的困難，但由于模擬的次數(shù)不夠多（只有十次）,得到結(jié)果與真實值之間存在一定誤差。2 模型1和2只考慮從沙河校區(qū)登車教職工數(shù)，來確定校車數(shù)，忽略從清水河登車教職工數(shù)對校車數(shù)量的影響，簡化了模型。因為在清水河上課的老師可能出現(xiàn)連續(xù)幾節(jié)有課的情況，必然出現(xiàn)某個時刻在沙河校區(qū)不同時刻登車的教職工在清水河校區(qū)的同一時刻登車，使該時刻在清水河登車的教職工數(shù)大于一天中五個時刻分別在沙河登車的教職工人數(shù)的最大值，由于此種情況發(fā)生的概率小于我們假定情況發(fā)生的概率，因此這種簡化方式具有合理性。3 模型1中在對校車制定分配及運行方案時,根據(jù)我們模擬的數(shù)據(jù)推算出各個時刻等待登車且家住校外的教職工人數(shù)少于40人,并假設(shè)他們在交通高峰期乘坐同一輛校車,這只是我們統(tǒng)計的一般情況,但若考慮一些偶然因素,將會帶來校車的不同分配及運行安排.4 模型1簡化了問題的處理,認(rèn)為校車每天都正常工作,一天中各個時刻到清水河上課的教職工人數(shù)服從0450區(qū)間上的均勻分布,但是若某天有校車出現(xiàn)故障不能運行,必然導(dǎo)致所需的校車數(shù)得不到滿足,勢必帶來校車的重新配置.同樣,由于每天各個時刻來上課的教職工人數(shù)在嚴(yán)格意義上并不服從均勻分布,當(dāng)某一天某個時段來上課的教職工人數(shù)過多時,可能造成校車緊缺. 但若我們統(tǒng)計出一天中5個時刻在沙河校區(qū)登車的教職工的準(zhǔn)確概率，計算結(jié)果將更接近真實值，在我們的程序中可以做此修正，在程序運行時輸入改成我們統(tǒng)計的各時刻的概率，算出的校車數(shù)就是更為精確的值。5 模型2中購買座位數(shù)不同的車，購車數(shù)較模型1有所增加，但根據(jù)附錄三中的數(shù)據(jù)可知兩種購車方案實際所需成本相當(dāng)，并且根據(jù)我們的假設(shè)，單位路程校車耗油量與座位數(shù)呈線性關(guān)系，使得模型2在運行時，校車往返與兩個校區(qū)之間總是耗油較模型1少。由于目前石油價格很高，若這些校車的使用年限足夠長，若干年后在汽油耗費上節(jié)約的錢將會很多，那么在這種假設(shè)下，模型2明顯優(yōu)于模型1。若某天需要登車的教職工人數(shù)不是很多，可將兩個模型中當(dāng)天多余的一部分車對外出租或供學(xué)生搭乘。七 參考文獻(xiàn)1 徐全智、呂恕.概率論與數(shù)理統(tǒng)計.北京：高等教育出版社，20072 徐全智、楊晉浩.數(shù)學(xué)建模.北京：高等教育出版社，20043 楊啟帆、何勇、談之奕.數(shù)學(xué)建模競賽:浙江大學(xué)學(xué)生獲獎?wù)撐狞c評1999-2004.浙江：浙江大學(xué)出版社，2006附錄一 電子科技大學(xué)沙河校區(qū)、清水河校區(qū)夏季往返班車運行時刻表一、星期一至星期五沙河校區(qū)至清水河校區(qū)班車時刻表發(fā)車時間及地點到達(dá)時間及地點6:50八里小區(qū)二區(qū)3號門前7:40清水河校區(qū)學(xué)生活動中心6:50沙河校區(qū)學(xué)生活動中心8:40八里小區(qū)二區(qū)3號門前9:30清水河校區(qū)學(xué)生活動中心8:40沙河校區(qū)學(xué)生活動中心13:20八里小區(qū)二區(qū)3號門前14:10清水河校區(qū)學(xué)生活動中心13:20沙河校區(qū)學(xué)生活動中心15:10八里小區(qū)二區(qū)3號門前16:00清水河校區(qū)學(xué)生活動中心15:10沙河校區(qū)學(xué)生活動中心18:10沙河校區(qū)學(xué)生活動中心18:20八里小區(qū)二區(qū)3號門前19:10清水河校區(qū)學(xué)生活動中心二、星期一至星期五清水河校區(qū)至沙河校區(qū)班車時刻表發(fā)車時間及地點到達(dá)時間及地點10:00清水河校區(qū)學(xué)生活動中心11:00沙河校區(qū)學(xué)生活動中心11:50清水河校區(qū)學(xué)生活動中心12:50沙河校區(qū)學(xué)生活動中心16:30清水河校區(qū)學(xué)生活動中心17:30沙河校區(qū)學(xué)生活動中心18:20清水河校區(qū)學(xué)生活動中心19:10沙河校區(qū)學(xué)生活動中心22:20清水河校區(qū)學(xué)生活動