校車調(diào)度問題建模與仿真 武漢理工大學(xué)

武漢理工大學(xué)校車調(diào)度優(yōu)化模型——制作者：工業(yè)gc1102班——主講人：錢文家韋鈰雙目錄

3.模型的假設(shè)

4.模型的建立及其求解

5.結(jié)束語

6.結(jié)束語

2.問題的提出的背景1.摘要1.摘要

以武漢理工大學(xué)南湖教學(xué)區(qū)師生校車站點及發(fā)車時間安排為對象,首先針對乘車站點建立了目標(biāo)非線性

規(guī)劃模型。其中目標(biāo)函數(shù)為所有乘客到達(dá)站點的總的距離最小;站點確定后針對車輛數(shù)最少，車輛行駛的總距離最短，各輛車的運行距離均衡及各輛車的負(fù)荷均衡這4個目標(biāo)建立針對線路優(yōu)化的多目標(biāo)非線性規(guī)劃模型,并給出了解決這類問題的啟發(fā)式優(yōu)化算法。該模型與一般算法更實際,更具體的給出了問題的解答。關(guān)鍵詞:校車問題;最優(yōu)化;非線性規(guī)劃;啟發(fā)式算法2.問題提出1.1.現(xiàn)狀隨著高校招生比例的逐年增加，全國各大高校都面臨著擴建、發(fā)展的問題。武漢理工大學(xué)在合并后，各校區(qū)比較分散，教師以及學(xué)生如何在各校區(qū)便捷的通行，是一個值得去探究的問題。就教職工而言，由于他們基本都居住在老校區(qū)，因此往返于新老校區(qū)之間，便成為教職員工一大棘手的問題。對于學(xué)生來說，也有令他們頭疼的地方。對于武漢理工大學(xué)而言，由于行車路線、距離以及課程安排的變化，學(xué)生們一般選擇坐校車來往返各校區(qū)，而由于存在許多動態(tài)因素，出現(xiàn)了有老師或?qū)W生上下課趕不上校車的現(xiàn)象。因此，等候校車成為了很多老師經(jīng)常面臨的問題。由此可見，本為師生提供方便的校車，不時成為困擾師生正常工作學(xué)習(xí)的問題?？偟膩碚f，候車時間與上、下課時間的協(xié)調(diào)是針對老師首要解決的問題。根據(jù)實際情況，我們了解到，現(xiàn)在校車周一到周五是根據(jù)上課、下課時刻表來決定發(fā)車時間的。基于以上校車調(diào)度方面存在的問題，本文試圖建立模型，設(shè)計校車調(diào)度的優(yōu)化方案，從而實現(xiàn)對校車調(diào)度方面問題的解決及優(yōu)化。如何優(yōu)化校車調(diào)度？乘客離站點的距離最短乘客滿意度最優(yōu)的校車數(shù)目最優(yōu)的行車路線校車的利益1.2.現(xiàn)有的路線3.模型假設(shè)假設(shè)一：校車在行駛過程中，不存在堵車現(xiàn)象,且途中無特殊事件發(fā)生，且校車從南湖校區(qū)到達(dá)東院所需要的時間為15min；假設(shè)二：每輛校車只能容納C=45人，不存在嚴(yán)重超載行為；假設(shè)三：將南湖教學(xué)區(qū)的可以作為校車停靠點的地方等效成教學(xué)區(qū)分為：新一教學(xué),新二教學(xué)樓，新三教學(xué)樓，食宿生活區(qū)分為：食堂，南舍區(qū)和北舍區(qū)；假設(shè)四：南湖教學(xué)區(qū)要求建立兩個校車?？奎c，分別在教學(xué)區(qū)和食宿區(qū)各一個;假設(shè)五：南湖教學(xué)區(qū)的師生從所在地到達(dá)最近的校車站點所用的時間最多為4min.4.模型的建立及其求解一.符號說明新一教學(xué)樓，新二教學(xué)樓，新三教學(xué)樓，食堂，南舍，北舍代號分別為：S1,S2,S3,S4,S5,S6;時間7:30,9:40,11:50,13:30,15:40,17:40代號分別為：T1,T2,T3,T4,T5,T6;另外Smn：表示Sm到Sn的距離；Nij：表示在校車停靠地點Si，時間點Tj時乘車去東院的學(xué)生人數(shù)。4.模型的建立及其求解4.1?？空军c的選取符號說明S1

,S2,S3,S4,S5,S6：分別表示新一，新二，新三，食堂，南舍區(qū)，北舍區(qū)；T1,

T2,T3,T4,T5,T6分別表示時刻：7:30,9:40,11:50,13:30,15:40,17:40；Smn：表示Sm到Sn的距離；Nij：表示在校車?？康攸cSi，時間點為Tj時，乘車去東院的學(xué)生人數(shù)。將南湖分為兩個區(qū)域（住宿生活區(qū)、教學(xué)區(qū)），并在兩個區(qū)中選擇各選一個校車?？空军c；現(xiàn)分別在兩個區(qū)中各擬定三個候選?？空军c，然后通過進(jìn)一步計算確定南湖校區(qū)最終的兩個?？空军c；初選站點見以下地圖（南湖中紅色三角標(biāo)記）；相關(guān)數(shù)據(jù)分別見表一、表二；初選站點教學(xué)區(qū)、生活區(qū)各初選站點間的距離（單位：m）S1S2S3S16050S260110S350110S4S5S6S410080S5100180S680180表一教學(xué)區(qū)各初選站點間的距離表二生活區(qū)各初選站點間的距離各時刻各點需要到東院的人數(shù)（單位：人）新一新二新三食堂南舍北舍7:30——————1520309:40603010——101011:50804010——————13:30————————808015：40402010——101017:4020101052010構(gòu)造目標(biāo)函數(shù)MinZ1=MinZ2=約束條件：1.校車容量限制：k=1,2,...,L每輛車的乘客數(shù)不超過其載客量2.可行性限制：LC>=n所有校車的載客能力大于等于總的載客數(shù)3.乘客限制：i=1,...n每位乘客只能做一輛車輸出結(jié)果：站點一新一站點二北舍7:34——兩輛校車9:44三輛校車一輛校車11:54三輛校車——13:34——四輛校車15:44兩輛校車一輛校車17:44一輛校車一輛校車

對于校車線路優(yōu)化,應(yīng)從車輛數(shù)最少，車輛行駛的總距離最短，各輛車的運行距離均衡及各輛車的負(fù)荷均衡這4個目標(biāo)進(jìn)行最優(yōu)化。4.2校車線路確定的數(shù)學(xué)模型目標(biāo)函數(shù)：l.車輛數(shù)最少M1=min{L|L*C>=n};其中:L表示校車的總數(shù),C表示校車的容量(假設(shè)均是標(biāo)準(zhǔn)大客車),n表示乘客的總數(shù).2.車輛行駛的總距離最短M2=min若校車直接從Si站到Sj站否則3.各輛車的運行距離均衡(不同乘客相對公平）M3=min(max-min)4.各輛車的負(fù)荷均衡(不同乘客相對公平)M4=min(max)綜合以上四個因素，目標(biāo)函數(shù)可建立為：F=min其中ak為權(quán)重系數(shù)ak>=0,k=1,2,3,4約束條件：1.校車容量限制：k=1,2,...,L每輛車的乘客數(shù)不超過其載客量2.可行性限制：LC>=n所有校車的載客能力大于等于總的載客數(shù)3.乘客限制：i=1,...n每位乘客只能做一輛車4.校車經(jīng)過站點的限制

j=1...m,k=1,...L任意站點一輛校車最多通一次任意站點至少一輛校車通過5.每輛校車的終點必須是學(xué)校，終點站學(xué)校可以看作是虛擬的第m+1個站點6.非負(fù)約束，0-1約束已經(jīng)整數(shù)約束算法設(shè)計(啟發(fā)式算法)：l)輸入:校車的容量C,權(quán)重系數(shù)ak,k=1,2,3,4(根據(jù)實際偏重可人為調(diào)整);2)循環(huán)輸入校車的總數(shù)L,取L=[n/C],[n/C]+1,[n/C]+2,...,因為校車總數(shù)L與M1以及整個目標(biāo)函數(shù)有關(guān),如果看做一變量的話會使問題求解變得非常困難,而L最多可取有限多個(n個),而實際上我們的第一優(yōu)化目標(biāo)就是車輛數(shù)最少,所以可行的L會更少;3)在給定校車數(shù)L下,首先確定出距離學(xué)校最遠(yuǎn)的L個站點,利用這些站點與學(xué)校分別作直線,確定出L條線段,定義為L條初始線路,記最長線路的長度為S;4)對每條初始線路進(jìn)行站點補充:在剩余的站點中,把離自己最近(即點到直線距離最最小)的站點并入該路線中,若此時新的線路長度依然小于最長初始線路的長度S,則繼續(xù)重復(fù)補充站點;否則停止補充轉(zhuǎn)(5);5)若所有站點已考慮,則轉(zhuǎn)(6).否則從初始線路出發(fā),首先將離最長初始線路最近的點加入到該線路中,計算其長度記為S',令S=S',轉(zhuǎn)(4);6)在站點補充完畢后,計算每條線路上乘客的人數(shù),安排校車,若校車的載客量滿足均衡要求,則停止,否則對相鄰線路上距離最近的站點上的乘客進(jìn)行互補交換,直到滿足要求.最后通過比較不同的校車的總數(shù)L下的有效解(與權(quán)重系數(shù)占ak,