數(shù)學(xué)建模論文-校園公交車調(diào)度問題

1、西南交通大學(xué)2012年新秀杯數(shù)學(xué)建模競賽題目： A題 組別： 大二組 參賽隊(duì)員1參賽隊(duì)員2參賽隊(duì)員3姓名學(xué)號(hào)學(xué)院專業(yè)電話Email西南交通大學(xué)教務(wù)處西南交通大學(xué)實(shí)驗(yàn)室及設(shè)備管理處西南交通大學(xué)數(shù)學(xué)建模創(chuàng)新實(shí)踐基地21校園通行車路線的設(shè)計(jì)摘 要本文主要研究的是校園交通車的站點(diǎn)設(shè)置、在固定停車和招手即停兩種模式結(jié)合下的運(yùn)載能力、運(yùn)行路線和時(shí)間安排以及相應(yīng)行駛方案的規(guī)劃問題。問題一中，我們對校園通行車現(xiàn)有行車路線網(wǎng)絡(luò)和常停站點(diǎn)進(jìn)行了調(diào)查和分析。首先，在數(shù)據(jù)處理階段，將站點(diǎn)實(shí)體間的線路選擇抽象為圖論最短路模型,用Matlab軟件畫出三條主要的行車線路，然后利用GIS空間分析方法解決單個(gè)交通線路上站點(diǎn)規(guī)劃

2、問題。該方法依據(jù)乘客出行時(shí)間最短確定單個(gè)線路上的站點(diǎn)個(gè)數(shù)，結(jié)合GIS緩沖區(qū)分析和疊合分析，在路線上做站點(diǎn)設(shè)置的適宜性討論，提出基于最優(yōu)化理論和GIS空間分析技術(shù)的站點(diǎn)規(guī)劃方法，確定站點(diǎn)的位置，從而提供一種可行的行駛方案。問題二中，考慮固定停車和招手即停相結(jié)合的方案，我們首先將最佳行駛路線定義為車輛運(yùn)行時(shí)間最短的路線，將圖論中經(jīng)典的Dijkstra算法（單源最短路徑）進(jìn)行改進(jìn)，結(jié)合哈密爾頓圖，以結(jié)點(diǎn)之間的時(shí)間作為權(quán)數(shù)，利用C+編程得到最佳推銷員回路，也就是通行車行駛的最佳路徑?？紤]到招手即停模式具有極大的隨機(jī)性，為了便于調(diào)度，我們首先對乘車人次密度分布進(jìn)行了調(diào)查和分析，并通過隨機(jī)模擬出概率分布值

3、較大的區(qū)域，將其抽象為一假想固定停車點(diǎn)，這樣就將模型簡化為固定停車點(diǎn)最佳行駛路徑的問題。根據(jù)已得到的乘車時(shí)段分布規(guī)律和學(xué)校實(shí)際的作息時(shí)間表，按照模糊聚類分析法將一工作日數(shù)單位時(shí)間段劃分為更概括的高峰期、低潮期和一般期，并應(yīng)用Matlab中的fgoalattain進(jìn)行非線性規(guī)劃求出實(shí)際發(fā)車數(shù)，以及應(yīng)用時(shí)間步長法估計(jì)發(fā)車間隔，從而給出兩種模式結(jié)合下通行車每周運(yùn)行的車輛數(shù)、路線和時(shí)刻表。問題三中，我們首先對校區(qū)師生乘車需求人數(shù)進(jìn)行了描述性統(tǒng)計(jì)，從乘車人數(shù)的均值、方差、峰度以及正態(tài)性四個(gè)角度對樣本進(jìn)行檢測，找到相關(guān)的分布規(guī)律與結(jié)論，即每日在各時(shí)段中的乘車人數(shù)分布相似。隨后，我們以ANOVA方差檢驗(yàn)、組

4、內(nèi)與組間均值比較以及標(biāo)準(zhǔn)誤差分析為手段，進(jìn)一步驗(yàn)證了所得結(jié)論的準(zhǔn)確性。并且以此建立較為理想化的整數(shù)規(guī)劃模型，將全局約束以發(fā)車時(shí)間劃分為幾個(gè)高峰時(shí)段，用Lingo軟件在個(gè)高峰時(shí)段約束中全局最優(yōu)解，從而得到在已知行駛方案下校園通行車的運(yùn)載能力。本文建立的行駛方案模型能與實(shí)際緊密聯(lián)系，結(jié)合校園實(shí)際情況對問題進(jìn)行求解，并在模型擴(kuò)展中利用計(jì)算機(jī)編程和仿真軟件對所得結(jié)果和調(diào)度方案進(jìn)行分析和評價(jià)，使得模型具有很好的通用性和推廣性。關(guān)鍵字：站點(diǎn)選址 最優(yōu)化原理 GIS 模糊聚類 非線性規(guī)劃 圖論1 問題重述西南交通大學(xué)犀浦校區(qū)位于成都市西北郫縣犀浦鎮(zhèn)，緊靠成都市外環(huán)線500米生態(tài)帶，距市中心約12公里，校園占

5、地約3000畝。犀浦校區(qū)的規(guī)劃和建設(shè)都強(qiáng)調(diào)和突出“自然、人文”的先進(jìn)理念，按照“一軸二帶三環(huán)六區(qū)”的規(guī)劃骨架，由南至北，逐步展開的。從2004年第一批學(xué)生入住以來，犀浦校區(qū)的規(guī)模日漸擴(kuò)大并趨于成熟。但是由于校區(qū)面積過大，出現(xiàn)了師生出行難，上課、回寢室、出校等所花時(shí)間較多等問題。為解決這一問題，校園內(nèi)出現(xiàn)了便捷通行車，師生只用花費(fèi)一元錢就可以在校內(nèi)往返。 目前，這種通行車采取招手即停的方式，校園內(nèi)的任意地點(diǎn)都基本可以到達(dá)，但是當(dāng)規(guī)模進(jìn)一步擴(kuò)大，管理更加規(guī)范后，可能需要考慮固定班次和行車路線。 題圖2給出了交大犀浦校區(qū)的平面地圖，利用數(shù)學(xué)模型研究以下問題：1、請?jiān)谛@內(nèi)設(shè)置一些固定停車點(diǎn)，并說明其

6、合理性；2、將固定停車和招手即停兩種模式結(jié)合起來，給出每周通行車從上午7點(diǎn)到晚上10點(diǎn)的運(yùn)行車輛數(shù)、運(yùn)行路線及時(shí)刻表；3、預(yù)測校園通行車在您安排的行駛方案下的運(yùn)載能力。2 問題分析問題一：影響固定停車點(diǎn)分布的主要因素有通行車的數(shù)量、乘客人數(shù)分布與到站規(guī)律、交通流量及線路上的其他隨機(jī)因素對車輛運(yùn)行的干擾。一般來說，站點(diǎn)安排應(yīng)考慮到以下兩點(diǎn)：1) 使乘客的出行總時(shí)間降到最低2) 固定停車點(diǎn)附近的所有乘客到達(dá)站點(diǎn)的總路程最短本節(jié)就此問題僅對最短通行時(shí)間路徑進(jìn)行討論，即在所用時(shí)間最短的前提下，求解所經(jīng)過的道路點(diǎn)。問題二：考慮固定停車和招手即停兩種模式結(jié)合，該情況的影響因子很多，且各因素都是隨機(jī)的。因此

7、，必須對模型做一定的簡化。首先，我們搜集了北區(qū)第一講課之前乘車高峰時(shí)間段及乘車人數(shù)的統(tǒng)計(jì)數(shù)據(jù)并進(jìn)行了描述性統(tǒng)計(jì)，由對樣本的分析結(jié)果找到相關(guān)的人流密度分布規(guī)律，且通過模糊聚類分析對時(shí)間段進(jìn)行劃分，假設(shè)每日各時(shí)段的乘車人數(shù)分布相似。隨后，通過檢驗(yàn)與誤差分析進(jìn)一步驗(yàn)證所得結(jié)論的準(zhǔn)確性，為以后的分析和建模做好準(zhǔn)備。之后，結(jié)合圖論中的Dijkstra算法和哈密爾頓圈問題分析，得出適合該問題求解的最佳路徑模型，根據(jù)已得到的乘車時(shí)段分布規(guī)律和學(xué)校實(shí)際的作息時(shí)間表，應(yīng)用Matlab進(jìn)行多目標(biāo)規(guī)劃并結(jié)合時(shí)間步長法估計(jì)發(fā)車間隔和發(fā)車數(shù)，從而給出兩種模式結(jié)合下通行車每周運(yùn)行的車輛數(shù)、路線和運(yùn)行時(shí)刻表。問題三：根據(jù)問

8、題一、二得出的行駛方案，利用計(jì)算機(jī)仿真對模型進(jìn)行模擬和檢驗(yàn)。根據(jù)已有數(shù)據(jù)建立多目標(biāo)規(guī)劃模型，考慮時(shí)間、車輛數(shù)、路線等對目標(biāo)函數(shù)的約束，分析影響通行車運(yùn)載能力的因素，求出全局最優(yōu)解，并對所得結(jié)論進(jìn)行實(shí)際合理性分析和驗(yàn)證。3 模型假設(shè)(1) 通行車在行駛過程中以的速度勻速運(yùn)行，在停車點(diǎn)前后各m內(nèi)為加減速距離，平均車速為一般車速的一半；不考慮每一站停車延遲及其他因素的影響(2) 考慮各站上下車以“先下后上”方式，每位乘客上下車時(shí)間都相等(3) 通行車的運(yùn)行時(shí)間只包括乘客上下車時(shí)間和必要的運(yùn)行時(shí)間，不考慮其他時(shí)間(4) 乘客候車時(shí)間一般不超過10分鐘，早高峰時(shí)一般不超過5分鐘(5) 如果候車人數(shù)多于座

9、位數(shù)，假設(shè)等待的乘客不離開(6) 通行車運(yùn)行過程中處于良好狀態(tài)，即不出現(xiàn)中途因電量不足或其他故障臨時(shí)停車或換乘情況(7) 通行車按時(shí)刻表順次發(fā)車，在同一時(shí)間段內(nèi)相鄰兩輛車發(fā)車時(shí)間間隔相同，且準(zhǔn)時(shí)到達(dá)每個(gè)站點(diǎn)(8) 通行車在每個(gè)固定站點(diǎn)停留時(shí)間均為4 符號(hào)說明:通行車運(yùn)行過程中行駛速度：最短時(shí)間下從固定停車點(diǎn)到固定停車點(diǎn)之間的距離:表示從頂點(diǎn)到的經(jīng)過一條路所用時(shí)間的權(quán):表示最佳的路線，的父親點(diǎn)：第時(shí)間點(diǎn)需要乘車的人數(shù)(=1,2,k):控制參數(shù):某時(shí)段運(yùn)載能力其中為通行車單程總運(yùn)行距離5 校園通行車固定停車點(diǎn)選擇模型（問題一）由于校園交通車行車網(wǎng)絡(luò)受到道路狀況、交通流量、道路長度、人流分布等多種因

10、素的制約，但考慮諸多因素建立起來的模型必然很復(fù)雜且難以求解。我們經(jīng)分析取舍，考慮主要的影響因子，建立了一個(gè)用于解決固定停車點(diǎn)規(guī)劃問題的方法。該方法主要基于最優(yōu)化理論和GIS適宜性分析技術(shù)，首先通過建立一個(gè)優(yōu)化的數(shù)學(xué)模型確定固定停車點(diǎn)的總數(shù)目，同時(shí)同這個(gè)數(shù)學(xué)模型得到各影響因子和站點(diǎn)個(gè)數(shù)之間關(guān)系的函數(shù)表達(dá)式，該表達(dá)式說明在什么地方適宜建固定停車點(diǎn)，從而為GIS適應(yīng)性分析提供依據(jù)。停車點(diǎn)數(shù)目確定后，在確定站點(diǎn)的空間布局。該方法采用了GIS適宜性分析技術(shù)，對人流分布、交通流量、道路狀況等因素進(jìn)行量化，通過疊合分析和緩沖區(qū)分析，找到最適宜的地方建立站點(diǎn)，用GIS的方法彌補(bǔ)了確定站點(diǎn)數(shù)目的優(yōu)化數(shù)學(xué)模型的引

11、入因素少的不足，使建立GIS輔助規(guī)劃系統(tǒng)成為現(xiàn)實(shí)。5.1 固定停車點(diǎn)選址的優(yōu)化模型5.1.1 影響固定停車點(diǎn)選址的相關(guān)因素模型中選址問題的影響因子有人流分布、交通流量、交通起訖點(diǎn)、一般車速、道路狀況等，我們主要考慮以下四點(diǎn)：1) 兩相鄰?fù)＼圏c(diǎn)間的距離；2) 人流分布。根據(jù)實(shí)際情況，固定停車點(diǎn)應(yīng)設(shè)置在人流密度相對較大的地方；3) 道路狀況。考慮交叉口和不同路段寬度、車道數(shù)對設(shè)站的影響：停車點(diǎn)越靠近交叉口對乘客越方便，但考慮安全和交通流暢，一般應(yīng)離開交叉口3050米。為減少通行車行駛對學(xué)生步行以及騎自行車的影響，道路路段寬度大的地點(diǎn)比寬度窄的地點(diǎn)更適宜設(shè)置固定停車點(diǎn)；4) 交通流量。路段上公交流量

12、的分布狀況是通行車停車點(diǎn)選址的重要依據(jù)。通行車的停駛會(huì)給其他學(xué)生帶來一定的干擾，因此，若路段交通狀況原本就比較擁擠，則不宜設(shè)置停車點(diǎn)。5.1.2 通行車行駛線路規(guī)劃設(shè)置固定停車點(diǎn)的原則為方便乘客和節(jié)省乘客出行時(shí)間。首先，我們根據(jù)校園車現(xiàn)今大體行駛路線，用Matlab軟件畫出假設(shè)的三條主要行車路線（如圖5-1），該路線覆蓋了學(xué)校已建成大部分地區(qū)的主干道。圖5-1其中，:南門南區(qū)體育場一食堂西二門北區(qū)體育場15號(hào)天佑齋:南門虹橋X橋體育館15號(hào)天佑齋北區(qū)校車站:南門南區(qū)校車站一教二教圖書館八教北區(qū)校車站15號(hào)天佑齋5.1.2.1 最佳站距公式利用乘客步行到站與離站時(shí)間、乘車時(shí)間之和最短的原理，得到

13、最佳站距公式為：式中，為站距； 為乘客到停車點(diǎn)的平均速度； 為乘客距離固定乘車點(diǎn)的平均距離；為站點(diǎn)?？繒r(shí)間。求出最佳停車點(diǎn)站距后，在具體設(shè)置站點(diǎn)時(shí)，還應(yīng)根據(jù)沿線用地性質(zhì)進(jìn)行合理布置。5.1.2.2 基于最優(yōu)理論的通行車優(yōu)化模型實(shí)際情況表明，當(dāng)停車點(diǎn)很多時(shí)，每位乘客在線路上的行程會(huì)因?yàn)橹型就＼嚧螖?shù)較多而導(dǎo)致總出行時(shí)間增大；而當(dāng)停車點(diǎn)很少時(shí)，乘客平均到最近一個(gè)停車點(diǎn)的時(shí)間會(huì)加長，可能超過在路上形成部分所節(jié)省的時(shí)間，從而導(dǎo)致總出行時(shí)間還是很大?？梢?，當(dāng)停車點(diǎn)間距很小或很大時(shí)，總出行時(shí)間都會(huì)較大，而在此間存在著某個(gè)最優(yōu)站點(diǎn)數(shù)目，使總的行程時(shí)間最小。總行程時(shí)間最小的通行車優(yōu)化模型為 (1)式中：為總出行

14、時(shí)間；為停車點(diǎn)的個(gè)數(shù)；為公交車輛在公交站點(diǎn)停留的時(shí)間；為乘客到最近停車點(diǎn)的平均距離；為乘客到停車點(diǎn)的平均速度; 為通行車路線的總里程數(shù)；為一般車速運(yùn)行的公里數(shù)，這樣為在站點(diǎn)總的停靠時(shí)間；為在站點(diǎn)前后加減速的運(yùn)行時(shí)間；是以速度運(yùn)行的時(shí)間。在式(1)中，除了與站點(diǎn)距離有關(guān)，和屬于因變量外，都可做自變量，對于特定的值，可以得出一個(gè)最佳的值來。以（經(jīng)驗(yàn)值），代入式(1)的第一個(gè)式子得令得 (2)式(2)即為最優(yōu)停車點(diǎn)數(shù)的公式根據(jù)式(2)，在其他變量一定的情況下，人流越密集，那么?？繒r(shí)間越大，則站點(diǎn)應(yīng)建的越少；同樣，人們到達(dá)停車點(diǎn)的速度越小，站點(diǎn)應(yīng)建的越多；公交車輛在路上可達(dá)到的加速度越大，則越小，停車

15、點(diǎn)應(yīng)建的越多。這些都是進(jìn)行GIS適宜性分析的依據(jù)。5.1.3 基于GIS適宜性分析的停車點(diǎn)選址當(dāng)站點(diǎn)數(shù)目確定后，利用GIS空間適宜性分析技術(shù)實(shí)現(xiàn)站點(diǎn)的空間定位，主要步驟為1、對人流分布，交通流量，道路狀況進(jìn)行量化。量化過程中采用下面的規(guī)則：1道路上的人流分布采用以10m的步長逐點(diǎn)做100m范圍緩沖區(qū)的方法，在緩沖區(qū)內(nèi)的人數(shù)就是對應(yīng)道路上的人流分布值（或者采用克里金插值生成人流密度表面，一般口越密集，站點(diǎn)應(yīng)建的越少；反之人口過于稀少，也不應(yīng)設(shè)置過多站點(diǎn)）；2交通流量以實(shí)地采集的日平均數(shù)據(jù)為準(zhǔn)；3校園中道路狀況大體相當(dāng)，可看作相同忽略不計(jì)說明：為了便于說明模型的思路，以下的圖表都是示意性的，實(shí)際系

16、統(tǒng)中將量化成灰度圖，以下是經(jīng)量化獲得的各影響因子的值。表1 線路人口分布、交通流量度量指標(biāo)南門南體育場一食堂三食堂北體育場四食堂15天佑齋人流分布3455445交通流量4533321Q7988766表2 線路人口分布、交通流量度量指標(biāo)南門玻璃橋虹橋X橋北區(qū)體育館15天佑齋人流分布244622交通流量543332Q787954表3 線路人口分布、交通流量度量指標(biāo)南門一教二教圖書館八教北區(qū)校車站15天佑齋人流分布2445432交通流量4113322Q6558754注：表中人流分布按照很稀疏、稀疏、一般稀疏、中等、一般密集、密集、很密集分別對應(yīng)量化值2、3、4、5、4、3、2；交通流量從量很小過渡到

17、很多分別對應(yīng)60的量化值；道路狀況取較好狀態(tài)度量值5.2、按照上面的規(guī)則生成對交通路徑的交通流量、人流分布的灰度圖，結(jié)果分別如圖1、2，再對兩個(gè)圖層進(jìn)行疊合分析，對量化指標(biāo)柵格化得到柵格圖（圖略） 圖1 交通流量圖 圖2 人流分布圖 圖3 在疊加結(jié)果上做緩沖區(qū)3、根據(jù)固定停車點(diǎn)數(shù)，在交通路徑上等間距取個(gè)點(diǎn)。對每個(gè)點(diǎn)在步驟2、得到的柵格圖上做半徑為10m的點(diǎn)緩沖區(qū)（圖3）4、在緩沖區(qū)內(nèi)交通流量、人流分布量化值最大的位置設(shè)置固定停車點(diǎn)5.1.4 固定停車點(diǎn)選擇方案以起點(diǎn)南門處為中心，沿前行方向分別以200m和500m繪制圓弧，形成環(huán)形緩沖區(qū)，選取緩沖區(qū)內(nèi)量化值最大的點(diǎn)作下一個(gè)站點(diǎn)；若緩沖區(qū)內(nèi)出現(xiàn)最

18、大量化值相等的點(diǎn)，那么就取距離上一個(gè)點(diǎn)為300m的點(diǎn)為站點(diǎn)；再以尋找到的站點(diǎn)為新的起點(diǎn)，重復(fù)上述步驟，直到線路終點(diǎn)，如圖5-2為設(shè)計(jì)總圖圖5-25.3 模型的評價(jià)由圖可以觀察到，利用該方法設(shè)計(jì)的校園通行車固定停車點(diǎn)個(gè)數(shù)為11個(gè)，這些站點(diǎn)在道路交叉口附近和人流密集的教學(xué)區(qū)、住宿區(qū)都有分布，非常方便學(xué)生上下課以及出入校園的情況。而且比較現(xiàn)有的通行情況，固定線路和停車點(diǎn)減少了乘客總的出行時(shí)間，提高了運(yùn)載效率。因此，利用該方法進(jìn)行選址是比較合理的。當(dāng)然，為了模型方便求解，我們對于交通流量、道路狀況、人流分布等因素的相關(guān)關(guān)系，以及它們在站點(diǎn)選擇時(shí)所占的權(quán)重并沒有多加考慮。另外，如果考慮到學(xué)校未來的規(guī)劃（

19、如圖5-3），則需增加一條線路圖5-3:南門七教一五教?hào)|門行政大樓北區(qū)校車站研究生小高樓教師公寓給出其量化指標(biāo)分布表：南門七教五教?hào)|門北區(qū)校車站教師公寓人流分布244622交通流量543332Q787954該線路可方便教師出行及上下課的情況。6 將固定停車和招手即停相結(jié)合的通行車行駛方案模型（問題二）結(jié)合問題一我們可定義通行車最佳行駛路線為：在所用時(shí)間最短的前提下所經(jīng)過的道路點(diǎn)。為了求出最短時(shí)間下的優(yōu)化路徑從而給出合理的行車路線的方案，我們采用了圖論中最佳推銷員回路以及Dijkstra算法建立相關(guān)模型。6.1 招手即停模式的概率抽象模型對于學(xué)生來說，每天乘車的人數(shù)為隨機(jī)變量，因此為了探討交通車

20、運(yùn)行數(shù)據(jù)的規(guī)律，首先要對每天乘坐校車的學(xué)生的人數(shù)的分布情況進(jìn)行統(tǒng)計(jì)分析。我們實(shí)地調(diào)查了一周每天早晨北區(qū)宿舍樓附近的候車情況，高峰期大致出現(xiàn)在7：458:00之間(如圖6-1所示)圖6-1對總體學(xué)生乘車人數(shù)的樣本總體進(jìn)行描述性分析，得到下表(表6-1)：表6-1：描述性統(tǒng)計(jì)量總乘車人數(shù)均值標(biāo)準(zhǔn)差極小值極大值為了更直觀的了解分布情況，畫出如下散點(diǎn)圖(圖1)：6.2 最佳行駛路線模型的建立如圖6-3為問題一中確定的固定停車點(diǎn)的抽象線圖，編號(hào)分別表示各站點(diǎn)，兩點(diǎn)間連線表示可通行。圖 6-36.2.1最佳推銷員回路問題的哈密爾頓圖首先考慮運(yùn)行線路為環(huán)線的情況。在加權(quán)圖中,給出最佳H圖定義：1.權(quán)最小的哈

21、密爾頓圖成為最佳H圖2.經(jīng)過每個(gè)頂點(diǎn)至少一次且權(quán)最小的閉通路成為最佳銷售回路由定義可知，本題可以轉(zhuǎn)化為最佳推銷員回路問題。有給定的構(gòu)造一個(gè)以為頂點(diǎn)集的完備圖,中的每條邊的權(quán)等于頂點(diǎn)X與Y在圖G中最短路徑的權(quán)，即根據(jù)哈密爾頓回路，由C+語言編寫程序和相應(yīng)解釋見附件（附錄二）。下面給出程序運(yùn)行結(jié)果：以該方法可給出37種不同的行車路線，其中最短路徑為：19108761154321，總行駛里程6.2.2 根據(jù)Dijstra算法的最佳路徑根據(jù)所學(xué)圖論知識(shí)，我們將圖采用鄰接矩陣的形式描述，表示在最短時(shí)間下從道路點(diǎn)到道路點(diǎn)之間的距離，如果沒有直接連通，則為無窮大，計(jì)算機(jī)可以用一個(gè)很大的數(shù)據(jù)代替（如matla

22、b中的inf）。由于Dijkstra算法只能求從結(jié)點(diǎn)到其他各結(jié)點(diǎn)的最短路徑，對每個(gè)頂點(diǎn)，定義兩個(gè)標(biāo)記（，），其中：表從頂點(diǎn)到的經(jīng)過一條路所用時(shí)間的權(quán)。表示的父親點(diǎn)，用以確定最佳的路線。算法的過程就是在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終為從頂點(diǎn)到的最時(shí)間的權(quán)。輸入 的帶權(quán)鄰接矩陣。算法步驟：1）賦初值：令 ， 令=，= 2）更新、：,若>則令=，=3）設(shè)是使取最小值的中的頂點(diǎn)，則令S=S，4）若，轉(zhuǎn)步驟2，否則停止用上述算法求出的就是到的最短時(shí)間的權(quán)，從的父親標(biāo)記追溯到, 就得到到的最佳路線（程序用C語言編寫，具體代碼見附錄一，源程序見附件）程序運(yùn)行結(jié)果如下：給定問題一求解出的11個(gè)固定停車點(diǎn)之

23、間的連通關(guān)系，根據(jù)算法和已知相鄰的點(diǎn)的距離，選擇具有11個(gè)節(jié)點(diǎn)的有向圖6-2，我們可以得到其各邊權(quán)重及拓?fù)浣Y(jié)構(gòu)。 圖6-4上述程序選取了節(jié)點(diǎn)7為目的節(jié)點(diǎn)，程序中采用鄰接矩陣表示一個(gè)有向圖，輸入為該圖的鄰接矩陣以及目的節(jié)點(diǎn)，輸出為圖中各點(diǎn)的鄰接關(guān)系，依照次鄰接關(guān)系可得到到達(dá)目的節(jié)點(diǎn)的最短路徑。如從節(jié)點(diǎn)2到達(dá)節(jié)點(diǎn)7，需順次經(jīng)過第3點(diǎn)、第4點(diǎn)和第5點(diǎn)，最優(yōu)路徑為23457，路程總長度為1482m.該方法可以求出最短路徑以及所對應(yīng)的路程，在車速假設(shè)一定的前提下，所對應(yīng)的行車時(shí)間最短，也就是說減少了乘客的總出行時(shí)間，提高了運(yùn)行效率。6.3 非線性規(guī)劃分析法求解通行車線路安排及時(shí)刻表首先通過數(shù)據(jù)的分析，考

24、慮到方案的可操作性，根據(jù)學(xué)校實(shí)際的作息時(shí)間表，我們對時(shí)間段按照模糊聚類分析法劃分為不同時(shí)間段高峰期、低潮期和一般期。引入乘客利益6.3.1 符號(hào)約定：某一時(shí)段發(fā)車次數(shù)（注：由于數(shù)據(jù)給定為平均客流量只需考慮在一個(gè)完整的周期內(nèi)的車次，即從始發(fā)站到終點(diǎn)站的這段時(shí)間）：該時(shí)段的平均滿載率（一般情況下，車輛滿載率不應(yīng)超過100%，也不要低于50%）：一輛通行車走完全程的時(shí)間：第站上車平均客流量:供求匹配比：控制參數(shù):某時(shí)段運(yùn)客能力6.3.2 發(fā)車次數(shù)的確定依據(jù)前面的分析，兼顧乘客出行時(shí)間與線路利用效率最大化，對6.2中求解出的最佳路線建立如下的多目標(biāo)規(guī)劃模型：目標(biāo)函數(shù)1： 供求的最優(yōu)匹配 各時(shí)段的發(fā)車車

25、次均最小 約束條件：各時(shí)段的平均滿載率限制 供求匹配比限制目標(biāo)函數(shù)使某一時(shí)段的運(yùn)客能力 與運(yùn)輸需求(實(shí)際客運(yùn)量)達(dá)到最優(yōu)匹配，反映滿載率高低的影響；目標(biāo)函數(shù)使所需的最大發(fā)車次，在滿足約束條件下盡可能少，以使總車輛數(shù)較少。約束條件是限制滿載率滿足運(yùn)營調(diào)度要求，條件是限制供求匹配比；為使始發(fā)站車場每天起始時(shí)刻的車輛數(shù)保持不變，需使總發(fā)車次數(shù)與總收車次數(shù)相等,即必須使單程車次總數(shù)達(dá)到匹配() ,而受滿載率限制，不能減少，因此用二次規(guī)劃可求得各時(shí)段發(fā)車次數(shù)目標(biāo)函數(shù)2： 約束條件：滿足每一個(gè)時(shí)刻點(diǎn)的乘車人數(shù)即可，即 6.3.3 發(fā)車數(shù)量及發(fā)車間隔的確定對于這個(gè)問題，我們采用上時(shí)間步長法，根據(jù)假設(shè)一個(gè)時(shí)段

26、內(nèi)發(fā)車間隔時(shí)間相等，則可由確定，從而得到發(fā)車時(shí)刻表。按此發(fā)車時(shí)刻表模擬實(shí)際運(yùn)行過程，目標(biāo)是確定能滿足時(shí)刻表的最小車輛數(shù),統(tǒng)計(jì)各項(xiàng)運(yùn)營指標(biāo)，搜索最優(yōu)調(diào)度方案解。6.3.3.1 模擬子程序一：確定最小車輛數(shù)根據(jù)“按流發(fā)車”和“先進(jìn)先出”的原則，對起點(diǎn)站,在發(fā)車時(shí)刻應(yīng)至少有一輛車可以發(fā)出(處于等待發(fā)車狀態(tài))。若有多輛車,則先進(jìn)站者先發(fā)車,其余車輛“排隊(duì)”等候；若無車可發(fā)，則出現(xiàn)“間斷”。完整的運(yùn)營過程應(yīng)保證車輛嚴(yán)格按時(shí)刻表發(fā)車,不發(fā)生間斷。設(shè)圖6-3中的站點(diǎn)5有車場A，從車場中不斷有車發(fā)出，同時(shí)接受車進(jìn)場，則車場中的車的數(shù)目是隨時(shí)間變化的狀態(tài)量。用來描述車場A中要滿足車流不間斷所需的最小數(shù)目，分別搜

27、索其在運(yùn)行過程中的最大值，則所需最小車量數(shù)目6.3.3.2 模擬子程序二：統(tǒng)計(jì)各項(xiàng)運(yùn)營指標(biāo)確定各項(xiàng)運(yùn)營指標(biāo)采用模擬統(tǒng)計(jì)的計(jì)算方法，對不同的運(yùn)營指標(biāo)進(jìn)行定量計(jì)算，主要功能是通過定量分析運(yùn)營指標(biāo)來檢驗(yàn)方案的可行性，以確定方案調(diào)整。由于車次與發(fā)車時(shí)刻一一對應(yīng),而車輛的隊(duì)列順序不發(fā)生改變,因而對所需車輛進(jìn)行統(tǒng)一編號(hào),則對每一車次,與其對應(yīng)的車輛編號(hào)是確定的,故我們直接對第次車進(jìn)行考察。統(tǒng)計(jì)的指標(biāo)及其定義如下:平均滿載率 平均候車時(shí)間 符號(hào)說明:：第次車到第站時(shí)上車與下車的人數(shù)之差：第次車離開第站時(shí)站臺(tái)上的滯留人數(shù)：第次車離開第站時(shí)車上的人數(shù); 為第次車離開第站時(shí)站臺(tái)上滯留者的滯留時(shí)間：第次車離開第站時(shí)

28、的滿載率：一天單程所發(fā)的車次總數(shù)：單程站臺(tái)總數(shù)6.3.3.3 模擬結(jié)果及統(tǒng)計(jì)指標(biāo)分析通過谷歌地圖測出校園通行車全程長度為L=4830m，車平均速度為，假設(shè)站點(diǎn)間的距離6.3.4 其他模型及求解設(shè)決策變量：每個(gè)發(fā)車點(diǎn)的調(diào)運(yùn)車輛為目標(biāo)函數(shù)：設(shè)總運(yùn)營成本為當(dāng)為奇數(shù)時(shí)，車輛要空跑一個(gè)單程，以滿總的乘車需求。約束條件：使調(diào)運(yùn)的車數(shù)可以滿足全部需要乘車的人數(shù)，設(shè)為，即若車在時(shí)間不發(fā)車，則。綜上所述：可建立如下模型：6.3.5調(diào)度方案6.4 模型的評價(jià)7 校園車運(yùn)載能力預(yù)測模型（問題三）交通系統(tǒng)的運(yùn)載能力一般可定義為：某股道上，某一方向一小時(shí)內(nèi)所能運(yùn)載的總旅客數(shù)，運(yùn)載能力是交通系統(tǒng)中最重要的參數(shù)。一般情況下

29、，運(yùn)載能力區(qū)分為：通過能力。在一定運(yùn)輸線路、方向和區(qū)段上，在一定運(yùn)輸組織方法條件下，運(yùn)輸固定設(shè)備所擁有的能力；輸送能力。在運(yùn)輸線路、方向和區(qū)段上，在配備一定職工條件下，運(yùn)輸活動(dòng)工具所具有的能力通過能力和輸送能力均以單位時(shí)間內(nèi)（通常是一晝夜或一年）所能通過的列車數(shù)、汽車數(shù)、船舶數(shù)或運(yùn)輸量來計(jì)量。一般公路校園車運(yùn)載能力分為：基本通行能力、可能通行能力和實(shí)際通行能力。其中，實(shí)際通行能力是單位時(shí)間內(nèi)公路上能實(shí)際順利通過的最大車輛數(shù)，需要考慮車道寬度、側(cè)向凈空、行車視距和氣候條件等因素加以折減?；就ㄐ心芰Φ挠?jì)算公式為8 模型的評價(jià)與改進(jìn)8.1模型的評價(jià)我們通過一些合理的假設(shè) ,針對校園通行車輛調(diào)度問題

30、建立了一般模型。先對模型進(jìn)行了合理的簡化，采用由簡單到復(fù)雜逐步深入的方法，建立了針對車輛調(diào)度問題的一般規(guī)劃模型，然后充分利用C+、SPSS、Matlab與Lingo等軟件，并應(yīng)用Dijstra算法和深度優(yōu)先算法進(jìn)行求解與優(yōu)化，從而得到一個(gè)整體最優(yōu)解以及最佳車輛調(diào)配方案。通過對通行車路徑優(yōu)化問題進(jìn)行研究分析，可以得到較合理的校車路徑，一方面可以減少學(xué)校投入通行車數(shù)量，節(jié)約成本；另一方面可以縮短學(xué)生等待時(shí)間和校車總行駛時(shí)間，提高運(yùn)載能力和服務(wù)質(zhì)量；除此之外，對于校園通行車路徑優(yōu)化問題的研究能為其他企業(yè)職工通勤車、公交車調(diào)度、物流企業(yè)車輛線路優(yōu)化等提供相關(guān)的理論指導(dǎo)和方法，起到一定的推廣與借鑒作用。

31、8.2模型的改進(jìn)(l)從模型構(gòu)造角度來看，本文雖然嘗試性的進(jìn)行了數(shù)學(xué)規(guī)劃模型的構(gòu)建，但是只考慮了在一定假設(shè)條件下的站點(diǎn)選擇和路徑安排問題。由于實(shí)際情況中，通行車的發(fā)車時(shí)間是關(guān)于期望準(zhǔn)點(diǎn)發(fā)車的正態(tài)分布，對應(yīng)的時(shí)點(diǎn)概率為；在各個(gè)時(shí)間點(diǎn)上來乘車的人數(shù)也是隨機(jī)的，經(jīng)過重新數(shù)據(jù)搜集，并運(yùn)用聚類分析等統(tǒng)計(jì)工具，可將人數(shù)的分布分為，所以，第個(gè)時(shí)間點(diǎn)可載人數(shù)進(jìn)而目標(biāo)函數(shù)可修正為：實(shí)際問題可能會(huì)涉及到更多的隨機(jī)因素，如時(shí)間窗的引入，以及學(xué)生、車輛、路況等不確定信息的考慮，這些問題將有待于今后進(jìn)一步研究。(2)在設(shè)計(jì)車輛調(diào)度方案時(shí) ,并未充分考慮學(xué)生的乘車需求，在進(jìn)行模型改進(jìn)時(shí)，可以試著想其它辦法找到一些更好的規(guī)

32、則來進(jìn)行對比與評價(jià)，從而得到更加優(yōu)化的方案，使各方利益達(dá)到充分均衡，這也是模型改進(jìn)的方向。參考文獻(xiàn)1姜啟源,謝金星,葉俊,數(shù)學(xué)模型(第三版)M,北京:清華大學(xué)出版社,2010.2黃杏元,馬勁松,湯勤等,地理信息系統(tǒng),北京:高等教育出版社,2002.3周義倉,赫孝良,數(shù)學(xué)建模實(shí)驗(yàn)M,西安:西安交通大學(xué)出版社,1999.4謝華,都金康,基于優(yōu)化理論和GIS空間分析技術(shù)的公交站點(diǎn)規(guī)劃方法,武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),第28卷:第6期,2004.附錄附錄一：#include <stdio.h>#include <stdlib.h>#define N 7 /*節(jié)點(diǎn)個(gè)數(shù)*

33、/int main() double eNN,dN; int v; /*目的節(jié)點(diǎn)*/ int i,j,min,x; long p=0;int pathN;for(i=0;i<N;i+) /*節(jié)點(diǎn)從0開始計(jì)數(shù)*/ printf("Input the weights to node %dn",i+1);for(j=0;j<N;j+) scanf("%lf",&eij); /*不相鄰節(jié)點(diǎn)間邊權(quán)用負(fù)數(shù)表示*/ if(eij<0)eij=32767; printf("Input destination noden");

34、 scanf("%d",&v); /*輸入目的節(jié)點(diǎn)*/ v-=1; /*初始化*/ for(i=0;i<N;i+) di=eiv;pathi=v; p|=1<<v; while(1) min=32767;for(j=0;j<N;j+) if(p&(1<<j)continue; if(min>dj) i=j;min=dj; p|=1<<i;if(p>=(1<<N)-1) break;for(j=0;j<N;j+) if(p&(1<<j)continue; min=

35、32767; for(i=0;i<N;i+)if(min>di+eji) min=di+eji; x=i; if(dj>min) dj=min;pathj=x; printf("*result:*n"); for(i=0;i<N;i+) if(i=v) continue;printf("P%d->P%dn",i+1,pathi+1); exit(EXIT_SUCCESS附錄二：#include<iostream>using namespace std;int road1111=0,673,0,0,0,0,0,1200,609,673,0,527,0,0,0,0,0,677,0,527,300,0,0,300,0,300,721,694,0,0,806,0,0,0,300,0,385,355,0,0,513,274,0,0,0,0,385,0,444,0,0,0