武漢理工大學(xué)校車調(diào)度問題

1、標(biāo)題：校車調(diào)度問題,作者：工業(yè)gc1102班,目錄,1.1問題概述,隨著高校招生比例的逐年增加，全國各大高校都面臨著擴(kuò)建、發(fā)展的問題。武漢理工大學(xué)在合并后，各校區(qū)比較分散，教師以及學(xué)生如何在各校區(qū)便捷的通行，是一個值得去探究的問題。就教職工而言，由于他們基本都居住在老校區(qū)，因此往返于新老校區(qū)之間，便成為教職員工一大棘手的問題。對于學(xué)生來說，也有令他們頭疼的地方。對于武漢理工大學(xué)而言，由于行車路線、距離以及課程安排的變化，學(xué)生們一般選擇坐校車來往返各校區(qū)，而由于存在許多動態(tài)因素，出現(xiàn)了有老師或?qū)W生上下課趕不上校車的現(xiàn)象。因此，等候校車成為了很多師生經(jīng)常面臨的問題。由此可見，本為師生提供方便的校車

2、，不時成為困擾師生正常工作學(xué)習(xí)的問題?？偟膩碚f，候車時間與上、下課時間的協(xié)調(diào)是針對老師首要解決的問題。根據(jù)實(shí)際情況，我們了解到，現(xiàn)在校車周一到周五是根據(jù)上課、下課時刻表來決定發(fā)車時間的。基于以上校車調(diào)度方面存在的問題，本文試圖建立模型，設(shè)計(jì)校車調(diào)度的優(yōu)化方案，從而實(shí)現(xiàn)對校車調(diào)度方面問題的解決及優(yōu)化。,1.2校車調(diào)度優(yōu)化問題解析 校車調(diào)度工作除了要考慮學(xué)校后勤集團(tuán)的收益 ，還要考慮乘客利益 ，并且乘客利益優(yōu)先于企業(yè)利益。本模型從校車乘客和后勤集團(tuán)雙方利益最大化 出發(fā) ，根據(jù) 校車 在 實(shí) 際運(yùn) 營 時 乘 客 流 量在時間上 的不 均衡 規(guī) 律 ，以極小 化 后勤集團(tuán)和 出行者費(fèi)用總和為目標(biāo)進(jìn)行

3、建模和優(yōu)化。,如何優(yōu)化校車調(diào)度？,2.1數(shù)學(xué)模型 的假設(shè) 數(shù)學(xué)建模要對現(xiàn)實(shí)世界的特定對象作一些重要 的簡化和 假設(shè) ，把 實(shí) 際 問題 抽象 為一 個 數(shù) 學(xué) 問題 本 文做 如下 假 設(shè) ： 各校車為 同種車 型 ； 同一時段相鄰 的兩車發(fā)車時間間隔相等； 校車的運(yùn)能能滿足運(yùn)量要求 ； 校車有兩個車門，可同時上下車； 各 時段 內(nèi)，各站客流到達(dá)分布服從均勻分布； 站間區(qū)間內(nèi)車輛運(yùn)行 速度為恒定值，且途中無特殊事件發(fā)生 ； 出行者消耗的單位時間費(fèi)用是固定值u2 ； 校車單位 乘次營運(yùn)成本是固定值u1。,2.2相關(guān)數(shù)據(jù),3.1建立模型,以后勤集團(tuán)和 出行 者 費(fèi)用 最 小 為 目標(biāo) ，以發(fā)車間隔

4、為待求變量 ，建立模型 1) 營運(yùn)成本 C1 車輛營運(yùn)成本可以表示為線路總乘次與單位乘次營運(yùn)成本積的形式： 式 中：C1為車輛營運(yùn)成本 ，元h ；將一天劃分為 K 個時段 ，個；Tk為第 k 時段校車營運(yùn)時間，h ；Hk為第 k 時段的發(fā)車間隔，h ；u1為車輛的單車營運(yùn)成本 ，元h/乘次。 2) 出行者費(fèi)用 C 2 出行者費(fèi)用 C2由乘客候車消耗的時間費(fèi)用 Ca與不下車乘客 由于站點(diǎn)停車所消耗的時間費(fèi)用 Cb 組成 ，可以表示為： C2=Ca+ Cb (2 ) 乘客候車消耗的時間費(fèi)用 Ca,以此將校車的運(yùn)營時間劃分為10個時間段，即K=10，并對人流量的大小進(jìn)行定性分類。問題在于無論以平峰或

5、高峰的人流量來確定運(yùn)行車輛的數(shù)量和發(fā)車時間間隔都是不合理的，故應(yīng)進(jìn)行優(yōu)化。 2.3行車路線,東院 西院 鑒湖 南湖,總站點(diǎn)數(shù)J=4。,式中：u2為乘客的單位時間價值 ，元h人次 ；Ukj 為 k 時段 、第j 站 的乘 客到 站密度 ，假設(shè) 服從 均 勻分布 ;J為公交站點(diǎn)數(shù)。 不下車乘客由于公交站點(diǎn)停車所消耗 的時間費(fèi)用Cb。,式中Dkj為k 時段J 站點(diǎn)的不下車乘客數(shù) ，人次h。,式 中 ：Bkj 為 k 時段 J 站點(diǎn) 的上 車乘客 數(shù) ，人 次h；Akj為k 時段 站點(diǎn)的下車乘客數(shù) ，人次h。,3.2優(yōu)化模 型,后勤集團(tuán)的營運(yùn)成本 C1 與出行者費(fèi)用 C2 二者處于對立的關(guān)系，因此本文

6、屬于典型的多目標(biāo)優(yōu)化問題依據(jù)本文特點(diǎn)，選取權(quán)重和方法作為多 目標(biāo)函數(shù)優(yōu)化算法，得到 目標(biāo) 函數(shù) ，待求變量為發(fā)車間隔 H。以 f作為校車調(diào)度的 目標(biāo) ，兼顧 了乘客和后勤集團(tuán)的成本 ，有利于實(shí)現(xiàn)乘客與后勤集團(tuán)的共同利益，對 于調(diào)度優(yōu)化來說是一個適當(dāng)?shù)哪繕?biāo)。,約束條件：,（1）,（2）,（3）,式中:p,q為權(quán)重系數(shù) ，取正數(shù) ；Hmax為最大發(fā) 車間隔 ，h ；Hmin為最小發(fā)車間隔 ，h ；Qd 為公 交車輛額定載客量 ，人；Nk為k時段 是所需車輛數(shù)。Nmax為所能提供的最大的車輛數(shù)。當(dāng)滿座率達(dá)到80%時準(zhǔn)許發(fā)車。,4.利用遺傳算法解決校車調(diào)度問題,4.1編碼 （1）本文建立分 時段等 間

7、隔 的模 型 ，即把 一天 劃分 為 K 個 時段 ，每個時段的發(fā)車間隔相 等考慮通過 染色體表示各個時段的發(fā)車間隔，進(jìn)而得到發(fā)車時刻表。：假設(shè) 最 大發(fā) 車間 隔為 15 min ，最 小 發(fā) 車間隔為 1 min ，則可供選擇的區(qū)間為14min=840s,將此 區(qū)間分成 100 等份，所以表示每個時段發(fā) 車 間 隔 的 基 因 二 進(jìn) 制 串 長 度 至 少 需 要 7位。我們把一天劃分為 K=10個時段 ，那么染色體的長度為 l=70位。 （2）編碼精度： = 4.2適應(yīng)度函數(shù)計(jì)算 適應(yīng)度 函數(shù)是用來度量群體中各個體的適應(yīng)能力的。在群體中，適應(yīng)度大的個體遺傳到下一代的概率較大，否則較小。

8、,本 文引入 P aul L Stoffa 提 出的適值模 擬退 火拉 伸 方 法 ，通 過 設(shè) 置 可 變 的適 應(yīng) 度 函數(shù)來 解決 這一 問題 。,式中： Fi為第 i 個染色體 的適配值 ；f 為第 i 個染色體 的 目標(biāo) 值 ；C 為 一 個 較 大 的 正值 ，如 果C-f 0 ，取 Fi=0；g 為遺傳迭代數(shù)序號；Tc，T 分別 為初始 溫度 和 當(dāng)代 溫度 ；k 為 降溫 速率 ，取值 為 099。,4.3選擇運(yùn)算 采用輪盤賭注的方法，將當(dāng)前群體中適應(yīng)度較高的個體按某種規(guī)則或模型遺傳到下一代。本文中后代產(chǎn)生的概率為 其中，個體適應(yīng)度為 ，個體適應(yīng)度總和 4.4交叉運(yùn)算 （1）隨機(jī)配對 （2）隨機(jī)設(shè)置交叉點(diǎn) （3）交叉部分基因,4.4變異運(yùn)算 遺傳算法實(shí)現(xiàn)變異是賦予每個基因一個相對較小的變異概率 P ，通過 隨機(jī)模擬決定該基因是否變異。 4.5解碼，輸出結(jié)果 使用以下公式解碼：,得出結(jié)果。,結(jié)束語,本文針對極