面向大規(guī)模拼車出行的最優(yōu)路徑規(guī)劃算法研究
發(fā)布時間:2020-03-20 20:32
【摘要】:隨著移動智能手機等設備的不斷發(fā)展和普及,拼車出行已經(jīng)成為大眾接受并選擇的出行方式之一。在本文解決的拼車出行場景中,乘客和司機都有自身行程的約束,還可以在拼車請求中提出各自的時間約束和費用約束。當拼車過程中出現(xiàn)多名乘客共同乘車的情況時,則需要滿足車上所有乘客和司機的拼車約束?紤]到緩解交通壓力、節(jié)能減排等因素,本文的目標是為乘客找到一名能夠滿足雙方拼車要求并且繞路距離最小的司機,以及其對應的最優(yōu)拼車路徑,F(xiàn)有的拼車算法在解決上述問題中,普遍存在如下缺陷。(1)拼車設定不夠人性化:僅考慮乘客的拼車要求,忽略司機也有拼車時間的約束條件。(2)計費方式不合理:直接給所有拼車乘客予以一定的費率折扣,忽視了拼車對已有乘客影響更大,應該給予更多補償。(3)拼車路線不夠合理:只查找乘客附近司機來提供接送服務,不考慮司機是否順路。因此,本文需要解決的難點包括以下兩項:(1)如何制定合理的拼車計費模型;(2)如何在大規(guī)模拼車場景中保證最優(yōu)路徑規(guī)劃算法的實時性和高效性;為了解決上述挑戰(zhàn),本文首先提出了一種拼車計費模型。該模型同時適用于一名司機接送一名乘客和接送多名乘客的拼車場景。除了考慮到需要平衡司機和乘客的利益之外,還考慮到新乘客拼車后對車上已有乘客產生的行程延誤影響,而設計了對已有乘客的補償機制。隨后在該計費模型的基礎上,本文設計并實現(xiàn)了相應的最優(yōu)路徑規(guī)劃算法URoad。該算法首先采用了出發(fā)時間篩選和歐氏距離篩選的剪枝技術,在算法前期通過較小的時間代價刪除了大量不滿足要求的司機。然后在后續(xù)的路徑規(guī)劃中采用了貪心策略,加快了算法的整體運行效率。本文最后還設計了相應的實驗來驗證算法整體和各個階段的高效性與有效性。實驗表明,在10萬名司機中,為一名乘客查找滿足所有拼車條件并且產生繞路距離最小的司機及其對應的最優(yōu)路徑,耗時不超過0.5秒。
【圖文】:
第1章 緒 論1.1 研究背景及意義.1.1 研究背景隨著經(jīng)濟的發(fā)展,城市中私家車的數(shù)量也不斷地增多[1],這使得交通壓力日趨增大別是早晚高峰時期道路更是擁堵不堪[2],隨之而來的空氣污染等環(huán)境問題也日益嚴重。近年來,,作為解決交通問題的有效手段之一,拼車開始受到政府等職能部門的高度[3]。自 2014 年來,各地政府也出臺了拼車出行規(guī)范和指導意見[4,5]。2016 年 12 月 21 日京上海率先落地拼車新規(guī),與之前出臺的《關于規(guī)范本市私人小客車合乘出行的實施(征求意見稿)》[6],[7]相比,落地新規(guī)在車輛、定價等方面都進行了相應調整,調整之新規(guī)顯現(xiàn)出更多的對拼車的鼓勵。
邊動態(tài)規(guī)劃的優(yōu)化算法和一種精心設計的下線剪接送一名乘客的拼車出行方式在行程體驗上會更解交通壓力而言,一名司機匹配多名乘客的拼車的現(xiàn)實意義。多名乘客24]提出了一種面向大規(guī)模出租車實時拼車的問題。時間約束,動態(tài)地為乘客查找滿足要求的司機并提服務。[23]提出了一個針對出租車的大規(guī)模動態(tài)拼車問題機的時空索引,如圖 2-2 所示。使用該時空索引從而加快查找最優(yōu)司機及接送路徑的目的來解決
【學位授予單位】:浙江工業(yè)大學
【學位級別】:碩士
【學位授予年份】:2018
【分類號】:O221
【圖文】:
第1章 緒 論1.1 研究背景及意義.1.1 研究背景隨著經(jīng)濟的發(fā)展,城市中私家車的數(shù)量也不斷地增多[1],這使得交通壓力日趨增大別是早晚高峰時期道路更是擁堵不堪[2],隨之而來的空氣污染等環(huán)境問題也日益嚴重。近年來,,作為解決交通問題的有效手段之一,拼車開始受到政府等職能部門的高度[3]。自 2014 年來,各地政府也出臺了拼車出行規(guī)范和指導意見[4,5]。2016 年 12 月 21 日京上海率先落地拼車新規(guī),與之前出臺的《關于規(guī)范本市私人小客車合乘出行的實施(征求意見稿)》[6],[7]相比,落地新規(guī)在車輛、定價等方面都進行了相應調整,調整之新規(guī)顯現(xiàn)出更多的對拼車的鼓勵。
邊動態(tài)規(guī)劃的優(yōu)化算法和一種精心設計的下線剪接送一名乘客的拼車出行方式在行程體驗上會更解交通壓力而言,一名司機匹配多名乘客的拼車的現(xiàn)實意義。多名乘客24]提出了一種面向大規(guī)模出租車實時拼車的問題。時間約束,動態(tài)地為乘客查找滿足要求的司機并提服務。[23]提出了一個針對出租車的大規(guī)模動態(tài)拼車問題機的時空索引,如圖 2-2 所示。使用該時空索引從而加快查找最優(yōu)司機及接送路徑的目的來解決
【學位授予單位】:浙江工業(yè)大學
【學位級別】:碩士
【學位授予年份】:2018
【分類號】:O221
【相似文獻】
相關期刊論文 前10條
1 劉智琦;李春貴;陳波;;基于交通流量預測的動態(tài)最優(yōu)路徑規(guī)劃研究[J];廣西工學院學報;2012年02期
2 段家鹿;;智能交通中車輛最優(yōu)路徑規(guī)劃策略的思考[J];科技創(chuàng)新導報;2018年11期
3 史輝;曹聞;朱述龍;朱寶山;;證據(jù)理論在最優(yōu)路徑規(guī)劃中的應用[J];計算機工程與應用;2009年26期
4 薛瑞;張永顯;;校車最優(yōu)路徑規(guī)劃算法研究[J];重慶科技學院學報(自然科學版);2015年05期
5 謝民;高利新;;蟻群算法在最優(yōu)路徑規(guī)劃中的應用[J];計算機工程與應用;2008年08期
6 舒翔翔;;多機器人最優(yōu)路徑規(guī)劃研究[J];信息與電腦(理論版);2017年15期
7 張春平,關志超,楊東援;深圳應急指揮中心的最優(yōu)路徑規(guī)劃技術研究[J];中山大學學報(自然科學版);2003年S2期
8 蔡菲;崔健;丁寧;蔡s
本文編號:2592158
本文鏈接:http://www.sikaile.net/kejilunwen/yysx/2592158.html
最近更新
教材專著