【摘要】：隨著移動(dòng)智能手機(jī)等設(shè)備的不斷發(fā)展和普及,拼車(chē)出行已經(jīng)成為大眾接受并選擇的出行方式之一。在本文解決的拼車(chē)出行場(chǎng)景中,乘客和司機(jī)都有自身行程的約束,還可以在拼車(chē)請(qǐng)求中提出各自的時(shí)間約束和費(fèi)用約束。當(dāng)拼車(chē)過(guò)程中出現(xiàn)多名乘客共同乘車(chē)的情況時(shí),則需要滿足車(chē)上所有乘客和司機(jī)的拼車(chē)約束�？紤]到緩解交通壓力、節(jié)能減排等因素,本文的目標(biāo)是為乘客找到一名能夠滿足雙方拼車(chē)要求并且繞路距離最小的司機(jī),以及其對(duì)應(yīng)的最優(yōu)拼車(chē)路徑�，F(xiàn)有的拼車(chē)算法在解決上述問(wèn)題中,普遍存在如下缺陷。(1)拼車(chē)設(shè)定不夠人性化:僅考慮乘客的拼車(chē)要求,忽略司機(jī)也有拼車(chē)時(shí)間的約束條件。(2)計(jì)費(fèi)方式不合理:直接給所有拼車(chē)乘客予以一定的費(fèi)率折扣,忽視了拼車(chē)對(duì)已有乘客影響更大,應(yīng)該給予更多補(bǔ)償。(3)拼車(chē)路線不夠合理:只查找乘客附近司機(jī)來(lái)提供接送服務(wù),不考慮司機(jī)是否順路。因此,本文需要解決的難點(diǎn)包括以下兩項(xiàng):(1)如何制定合理的拼車(chē)計(jì)費(fèi)模型;(2)如何在大規(guī)模拼車(chē)場(chǎng)景中保證最優(yōu)路徑規(guī)劃算法的實(shí)時(shí)性和高效性;為了解決上述挑戰(zhàn),本文首先提出了一種拼車(chē)計(jì)費(fèi)模型。該模型同時(shí)適用于一名司機(jī)接送一名乘客和接送多名乘客的拼車(chē)場(chǎng)景。除了考慮到需要平衡司機(jī)和乘客的利益之外,還考慮到新乘客拼車(chē)后對(duì)車(chē)上已有乘客產(chǎn)生的行程延誤影響,而設(shè)計(jì)了對(duì)已有乘客的補(bǔ)償機(jī)制。隨后在該計(jì)費(fèi)模型的基礎(chǔ)上,本文設(shè)計(jì)并實(shí)現(xiàn)了相應(yīng)的最優(yōu)路徑規(guī)劃算法URoad。該算法首先采用了出發(fā)時(shí)間篩選和歐氏距離篩選的剪枝技術(shù),在算法前期通過(guò)較小的時(shí)間代價(jià)刪除了大量不滿足要求的司機(jī)。然后在后續(xù)的路徑規(guī)劃中采用了貪心策略,加快了算法的整體運(yùn)行效率。本文最后還設(shè)計(jì)了相應(yīng)的實(shí)驗(yàn)來(lái)驗(yàn)證算法整體和各個(gè)階段的高效性與有效性。實(shí)驗(yàn)表明,在10萬(wàn)名司機(jī)中,為一名乘客查找滿足所有拼車(chē)條件并且產(chǎn)生繞路距離最小的司機(jī)及其對(duì)應(yīng)的最優(yōu)路徑,耗時(shí)不超過(guò)0.5秒。
【圖文】：

第1章 緒 論1.1 研究背景及意義.1.1 研究背景隨著經(jīng)濟(jì)的發(fā)展，城市中私家車(chē)的數(shù)量也不斷地增多[1]，這使得交通壓力日趨增大別是早晚高峰時(shí)期道路更是擁堵不堪[2]，隨之而來(lái)的空氣污染等環(huán)境問(wèn)題也日益嚴(yán)重。近年來(lái)，，作為解決交通問(wèn)題的有效手段之一，拼車(chē)開(kāi)始受到政府等職能部門(mén)的高度[3]。自 2014 年來(lái)，各地政府也出臺(tái)了拼車(chē)出行規(guī)范和指導(dǎo)意見(jiàn)[4,5]。2016 年 12 月 21 日京上海率先落地拼車(chē)新規(guī)，與之前出臺(tái)的《關(guān)于規(guī)范本市私人小客車(chē)合乘出行的實(shí)施(征求意見(jiàn)稿)》[6],[7]相比，落地新規(guī)在車(chē)輛、定價(jià)等方面都進(jìn)行了相應(yīng)調(diào)整，調(diào)整之新規(guī)顯現(xiàn)出更多的對(duì)拼車(chē)的鼓勵(lì)。

邊動(dòng)態(tài)規(guī)劃的優(yōu)化算法和一種精心設(shè)計(jì)的下線剪接送一名乘客的拼車(chē)出行方式在行程體驗(yàn)上會(huì)更解交通壓力而言，一名司機(jī)匹配多名乘客的拼車(chē)的現(xiàn)實(shí)意義。多名乘客24]提出了一種面向大規(guī)模出租車(chē)實(shí)時(shí)拼車(chē)的問(wèn)題。時(shí)間約束，動(dòng)態(tài)地為乘客查找滿足要求的司機(jī)并提服務(wù)。[23]提出了一個(gè)針對(duì)出租車(chē)的大規(guī)模動(dòng)態(tài)拼車(chē)問(wèn)題機(jī)的時(shí)空索引，如圖 2-2 所示。使用該時(shí)空索引從而加快查找最優(yōu)司機(jī)及接送路徑的目的來(lái)解決
【學(xué)位授予單位】：浙江工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類(lèi)號(hào)】：O221

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 劉智琦;李春貴;陳波;;基于交通流量預(yù)測(cè)的動(dòng)態(tài)最優(yōu)路徑規(guī)劃研究[J];廣西工學(xué)院學(xué)報(bào);2012年02期

2 段家鹿;;智能交通中車(chē)輛最優(yōu)路徑規(guī)劃策略的思考[J];科技創(chuàng)新導(dǎo)報(bào);2018年11期

3 史輝;曹聞;朱述龍;朱寶山;;證據(jù)理論在最優(yōu)路徑規(guī)劃中的應(yīng)用[J];計(jì)算機(jī)工程與應(yīng)用;2009年26期

4 薛瑞;張永顯;;校車(chē)最優(yōu)路徑規(guī)劃算法研究[J];重慶科技學(xué)院學(xué)報(bào)(自然科學(xué)版);2015年05期

5 謝民;高利新;;蟻群算法在最優(yōu)路徑規(guī)劃中的應(yīng)用[J];計(jì)算機(jī)工程與應(yīng)用;2008年08期

6 舒翔翔;;多機(jī)器人最優(yōu)路徑規(guī)劃研究[J];信息與電腦(理論版);2017年15期

7 張春平,關(guān)志超,楊東援;深圳應(yīng)急指揮中心的最優(yōu)路徑規(guī)劃技術(shù)研究[J];中山大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年S2期

8 蔡菲;崔健;丁寧;蔡s

本文編號(hào)：2592158