本文關(guān)鍵詞：基于生成與選擇模式的公交駕駛員排班問題研究

  更多相關(guān)文章： 公共交通 駕駛員排班 集覆蓋模型 時(shí)間標(biāo)記法 樹枚舉 遺傳算法

【摘要】：本文主要研究了公交駕駛員排班問題,公交駕駛員排班問題是指構(gòu)建合法班次集合滿足行車計(jì)劃的要求。求解目標(biāo)是使班次數(shù)目和班次成本最低。本文基于“生成和選擇”的模式對(duì)駕駛員排班問題進(jìn)行求解。第一階段：生成候選潛在合法班次集合生成階段主要是采用啟發(fā)式算法,根據(jù)約束條件生成一個(gè)大的候選班次集合。首先,根據(jù)集合覆蓋模型的特點(diǎn),集合覆蓋模型中的變量對(duì)應(yīng)于計(jì)劃中班次,約束條件對(duì)應(yīng)工作段。通常,工作段的數(shù)量是非常大的,一方面,大量的工作段會(huì)增加生成合法班次的數(shù)量,在實(shí)際的排班計(jì)劃中,不可能生成所有的合法班次；另一方面,過多的工作段會(huì)增加約束條件的數(shù)量。本文運(yùn)用基于時(shí)間標(biāo)記法的啟發(fā)式算法減少了參與生成班次的工作段數(shù)量。其次,在對(duì)潛在班次分析的基礎(chǔ)上,運(yùn)用樹枚舉算法的思想,生成潛在班次集合。第二階段：班次集合的選擇階段這一部分設(shè)計(jì)了三種不同的遺傳算法,在大量的潛在班次中選擇一個(gè)接近最優(yōu)的解或者最優(yōu)解。運(yùn)用不同的初始化,交叉和變異策略,三種遺傳算法分別求解可行班次集合。本文以實(shí)際的公交運(yùn)營數(shù)據(jù),用生成和選擇的方法求解駕駛員排班問題,并對(duì)三種算法的求解結(jié)果進(jìn)行了比較和分析。對(duì)比結(jié)果表明,算法2中,針對(duì)班次求解改進(jìn)的交叉策略能更快的求解可行班次集合；算法3中,基于班次評(píng)價(jià)的初始化策略,能使遺傳算法在更短時(shí)間內(nèi)求出較好的可行班次集合。
【關(guān)鍵詞】：公共交通 駕駛員排班 集覆蓋模型 時(shí)間標(biāo)記法 樹枚舉 遺傳算法
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：U492.2
【目錄】：

• 致謝5-6
• 摘要6-7
• ABSTRACT7-10
• 1 引言10-14
• 1.1 研究背景和意義10-11
• 1.2 論文結(jié)構(gòu)和主要內(nèi)容11-12
• 1.3 關(guān)鍵技術(shù)12
• 1.4 技術(shù)路線圖12-13
• 1.5 本章小結(jié)13-14
• 2 國內(nèi)外研究的理論和方法綜述14-21
• 2.1 國內(nèi)外研究綜述14-19
• 2.1.1 基本研究階段14-15
• 2.1.2 早期純啟發(fā)式方法15
• 2.1.3 基于生成與選擇模式的方法15-18
• 2.1.4 集成調(diào)度方法18-19
• 2.2 駕駛員排班系統(tǒng)的開發(fā)19-20
• 2.3 本章小結(jié)20-21
• 3 公交駕駛員排班問題分析21-26
• 3.1 公交駕駛員排班的相關(guān)概念21-22
• 3.2 公交駕駛員排班的目標(biāo)22-23
• 3.3 公交駕駛員排班問題的集分割與集覆蓋模型23-25
• 3.3.1 基本模型的闡述23-24
• 3.3.2 目標(biāo)班次數(shù)的計(jì)算24-25
• 3.3.3 改進(jìn)集合覆蓋模型25
• 3.4 本章小結(jié)25-26
• 4 潛在合法班次的生成26-39
• 4.1 換班時(shí)間點(diǎn)的選取方法、26-31
• 4.1.1 選取方法基本原理介紹26-27
• 4.1.2 前后標(biāo)記時(shí)間法27-28
• 4.1.3 時(shí)間標(biāo)記法的實(shí)現(xiàn)和實(shí)例分析28-31
• 4.1.4 可能的風(fēng)險(xiǎn)分析31
• 4.2 初始班次集合的生成31-39
• 4.2.1 潛在班次分析32-34
• 4.2.2 樹枚舉候選班次集合34-36
• 4.2.3 班次結(jié)構(gòu)評(píng)價(jià)36-38
• 4.2.4 本章小結(jié)38-39
• 5 遺傳算法選擇班次39-55
• 5.1 遺傳算法概述及基本原理39-40
• 5.2 遺傳算法求解駕駛員排班問題40-43
• 5.2.1 基于工作段的編碼方式41
• 5.2.2 基于班次的編碼方式41-43
• 5.3 遺傳算法求解班次算法143-47
• 5.3.1 染色體表示43-44
• 5.3.2 初始化策略44
• 5.3.3 適應(yīng)度函數(shù)44
• 5.3.4 交叉操作44-46
• 5.3.5 變異操作46-47
• 5.4 遺傳算法的求解班次算法247-50
• 5.4.1 交叉策略47-50
• 5.5 遺傳算法的求解班次算法350-53
• 5.5.1 初始化策略50-53
• 5.6 本章小結(jié)53-55
• 6 實(shí)例分析55-61
• 6.1 實(shí)驗(yàn)數(shù)據(jù)來源及實(shí)驗(yàn)平臺(tái)55
• 6.2 實(shí)驗(yàn)結(jié)果分析55-60
• 6.3 本章小結(jié)60-61
• 7 總結(jié)和展望61-63
• 7.1 研究工作總結(jié)61
• 7.2 研究工作展望61-63
• 參考文獻(xiàn)63-67
• 附錄A67-73
• 附錄B73-76
• 作者簡歷76-78
• 學(xué)位論文數(shù)據(jù)集78

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前1條

1 沈吟東,倪郁東;基于整數(shù)規(guī)劃的駕駛員調(diào)度系統(tǒng)—TRACSII[J];運(yùn)籌與管理;2005年03期

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前2條

1 劉濤;公交駕駛員排班與輪班問題的模型與算法研究[D];北京交通大學(xué);2013年

2 張學(xué)煒;集成化的公交運(yùn)營計(jì)劃編制方法研究[D];北京交通大學(xué);2008年

，

本文編號(hào)：1011021