VRPSDP(Vehicle routing problem with simultaneous pickup and delivery,同時(shí)取送貨車輛路徑選擇問題)是學(xué)術(shù)界和物流業(yè)關(guān)注的熱點(diǎn)問題�，F(xiàn)有對同時(shí)取送貨車輛路徑選擇問題的理論成果一般假設(shè)送貨量和取貨量完全已知,建立靜態(tài)優(yōu)化模型,設(shè)計(jì)啟發(fā)式算法進(jìn)行求解,但實(shí)際中取貨量可能是不確定的;對于取貨量不確定的研究,通常假設(shè)取貨量服從某一分布,尋求平均意義上的最優(yōu)方案,這可能給出離實(shí)際最優(yōu)解相距甚遠(yuǎn)的解,無法滿足實(shí)際需求。針對現(xiàn)有研究不足,本文考慮取貨需求不確定的情形,采用在線問題與競爭策略的理論與方法,從取貨需求無法預(yù)知和有限預(yù)知兩個(gè)角度進(jìn)行研究,設(shè)計(jì)在線策略,分析策略的不同情形證明競爭比并分析策略的執(zhí)行效果,為物流運(yùn)輸公司制定路徑選擇方案提供決策依據(jù)。主要工作和創(chuàng)新性成果如下。針對取貨需求不確定的同時(shí)取送貨車輛路徑問題,考慮車輛對需求點(diǎn)取貨量無法預(yù)知且每個(gè)需求點(diǎn)只能服務(wù)一次的情形,在完成送貨任務(wù)的前提下,以取回的貨物盡可能多為目標(biāo),建立在線車輛路徑選擇模型,分析中途不可卸貨和中途可卸貨兩種情形,并針對兩種不同情形分別設(shè)計(jì)先多后少策略和剩余空間可調(diào)策略。證明中途不可卸貨情形下先多后少策略競爭比為1/(β-α-(n-1)λ),已取貨物中途可卸情形下剩余空間可調(diào)策略的競爭比為1/(β-α),比較分析表明已取貨物中途可卸情形下剩余空間可調(diào)策略的執(zhí)行效果要好于中途不可卸貨情形下先多后少策略。最后通過實(shí)例分析驗(yàn)證兩種策略的有效性。針對取貨需求不確定的同時(shí)取送貨車輛路徑選擇問題,考慮車輛對需求點(diǎn)取貨量有限預(yù)知,即車輛從配送中心出發(fā)且在出發(fā)前已知每個(gè)需求點(diǎn)的送貨量,但只有到達(dá)某一需求點(diǎn)時(shí)才能獲知該需求點(diǎn)和下一個(gè)即將到達(dá)需求點(diǎn)的取貨量,在每個(gè)需求點(diǎn)只服務(wù)一次且完成所有需求點(diǎn)送貨任務(wù)回到配送中心的情形下,以取回的貨物總量盡可能地多為目標(biāo),建立取貨需求有限預(yù)知的同時(shí)取送貨車輛在線路徑選擇模型,分析中途不可卸貨和中途可卸貨兩種情形,并針對兩種不同情形分別設(shè)計(jì)Select large策略和PUPI策略并證明策略的競爭比,得到中途不可卸貨情形下Select large策略競爭比為1/(β-α-(n-1)λ),已取貨物中途可卸情形下PUPI策略的競爭比為1/(β-(m+t)θ)。最終將中途不可卸貨情形下Select large策略與已取貨物中途可卸情形下PUPI策略進(jìn)行對分析,發(fā)現(xiàn)已取貨物中途可卸情形下PUPI策略的執(zhí)行效果要好于中途不可卸貨情形下Select large策略。最后通過實(shí)例分析驗(yàn)證策略的有效性。本文設(shè)計(jì)的取貨信息不確定的同時(shí)取送貨在線路徑選擇策略,可為物流運(yùn)輸企業(yè)制定車輛路徑選擇方案提供決策依據(jù)。
【學(xué)位單位】：西安工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2018
【中圖分類】：F274;F724.6
【部分圖文】：

快遞公司將城市中的眾多站點(diǎn)按照其所在地理位置劃分為若干區(qū)域，每個(gè)區(qū)域內(nèi)的站點(diǎn)對應(yīng)著一個(gè)配送中心為其提供取送貨服務(wù)。為提高效率，快遞公司希望在配送中心派出的車輛滿足所有送貨需求的同時(shí)，能夠盡可能多的將站點(diǎn)攬收的包裹帶回配送中心，避免車輛對站點(diǎn)進(jìn)行二次服務(wù)，以提升配送效率。上述問題就是國際學(xué)術(shù)屆以及物流行業(yè)關(guān)注的熱點(diǎn)——同時(shí)取送貨車輛路徑選擇問題，即 VRPSDP（Vehicle routing problem withsimultaneous pickup and delivery）。VRPSDP 是指車輛從配送中心出發(fā)為指定需求點(diǎn)送貨的同時(shí)也需要將該需求點(diǎn)需要帶回配送中心的貨物取回情形下，如何選擇車輛路徑使得車輛在完成送貨的同時(shí)完成取貨服務(wù)請求最多或完成所有取貨服務(wù)請求下運(yùn)輸成本最小。在實(shí)際中，快遞公司從配送中心派出的車輛一般以單次車輛運(yùn)輸成本盡可能小為目標(biāo)，或是按照由近及遠(yuǎn)的原則對站點(diǎn)進(jìn)行服務(wù)，或是按照由遠(yuǎn)及近的原則對站點(diǎn)進(jìn)行服務(wù)。按照這種路徑選擇方式對站點(diǎn)進(jìn)行取送貨服務(wù)時(shí)，由于車輛配送過程中各個(gè)站點(diǎn)依然在進(jìn)行攬件，每個(gè)站點(diǎn)待取回的包裹數(shù)量難于確定，因此會出現(xiàn)車輛剩余較大承載能力但取回的貨物量很少，造成車輛剩余承載能力的浪費(fèi)（如圖 1.1）或者到達(dá)站點(diǎn)后車輛剩余的載貨能力無法滿足站點(diǎn)的取貨需求。（如圖 1.2）。

快遞公司將城市中的眾多站點(diǎn)按照其所在地理位置劃分為若干區(qū)域，每個(gè)區(qū)域內(nèi)的站點(diǎn)對應(yīng)著一個(gè)配送中心為其提供取送貨服務(wù)。為提高效率，快遞公司希望在配送中心派出的車輛滿足所有送貨需求的同時(shí)，能夠盡可能多的將站點(diǎn)攬收的包裹帶回配送中心，避免車輛對站點(diǎn)進(jìn)行二次服務(wù)，以提升配送效率。上述問題就是國際學(xué)術(shù)屆以及物流行業(yè)關(guān)注的熱點(diǎn)——同時(shí)取送貨車輛路徑選擇問題，即 VRPSDP（Vehicle routing problem withsimultaneous pickup and delivery）。VRPSDP 是指車輛從配送中心出發(fā)為指定需求點(diǎn)送貨的同時(shí)也需要將該需求點(diǎn)需要帶回配送中心的貨物取回情形下，如何選擇車輛路徑使得車輛在完成送貨的同時(shí)完成取貨服務(wù)請求最多或完成所有取貨服務(wù)請求下運(yùn)輸成本最小。在實(shí)際中，快遞公司從配送中心派出的車輛一般以單次車輛運(yùn)輸成本盡可能小為目標(biāo)，或是按照由近及遠(yuǎn)的原則對站點(diǎn)進(jìn)行服務(wù)，或是按照由遠(yuǎn)及近的原則對站點(diǎn)進(jìn)行服務(wù)。按照這種路徑選擇方式對站點(diǎn)進(jìn)行取送貨服務(wù)時(shí)，由于車輛配送過程中各個(gè)站點(diǎn)依然在進(jìn)行攬件，每個(gè)站點(diǎn)待取回的包裹數(shù)量難于確定，因此會出現(xiàn)車輛剩余較大承載能力但取回的貨物量很少，造成車輛剩余承載能力的浪費(fèi)（如圖 1.1）或者到達(dá)站點(diǎn)后車輛剩余的載貨能力無法滿足站點(diǎn)的取貨需求。（如圖 1.2）。

圖 3.3 不同坐標(biāo)系中不同( n 1)λ值下的競爭比函數(shù)圖圖 3.4 同一坐標(biāo)系中不同( n 1)λ值下的競爭比函數(shù)圖 3.3 可知，隨著( n 1)λ增長，函數(shù)圖像不會劇烈變化。由圖 3.4 可知，隨著( n 爭比圖像會隨之上升，即競爭比會隨著( n 1)λ變大而變大。

【參考文獻(xiàn)】

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

1 段鳳華;;帶碳費(fèi)約束的同時(shí)取送車輛路徑問題研究[J];湖南師范大學(xué)自然科學(xué)學(xué)報(bào);2015年03期

2 陳妍;單汨源;王秋鳳;;多車型集配貨一體化車輛路徑問題研究[J];中南大學(xué)學(xué)報(bào)(自然科學(xué)版);2015年05期

3 馬軍平;徐寅峰;陳聰;吳騰宇;;具有服務(wù)時(shí)長的在線TSP問題[J];系統(tǒng)工程理論與實(shí)踐;2015年11期

4 馬軍平;徐寅峰;溫新剛;張惠麗;;帶有預(yù)知信息的在線Homing ATSP問題[J];系統(tǒng)工程理論與實(shí)踐;2015年02期

5 趙燕偉;李文;張景玲;任設(shè)東;;多車型同時(shí)取送貨問題的低碳路徑研究[J];浙江工業(yè)大學(xué)學(xué)報(bào);2015年01期

6 王超;穆東;;基于模擬退火算法求解VRPSPDTW問題[J];系統(tǒng)仿真學(xué)報(bào);2014年11期

7 姜啟躍;;基于改進(jìn)蟻群算法的考慮車輛行程約束的逆向物流車輛路徑問題研究[J];物流技術(shù);2014年19期

8 柳毅;余福茂;俞武揚(yáng);;同時(shí)取送貨車輛路徑問題的改進(jìn)人工魚群算法[J];杭州電子科技大學(xué)學(xué)報(bào);2014年03期

9 羅鴻斌;;多車場多車型車輛調(diào)度問題的改進(jìn)粒子群算法[J];計(jì)算機(jī)工程與應(yīng)用;2014年07期

10 楊浩雄;李金丹;張浩;;電商配送中的車輛調(diào)度問題優(yōu)化研究[J];計(jì)算機(jī)工程與應(yīng)用;2015年15期

相關(guān)碩士學(xué)位論文 前2條

1 彭曦;回收需求隨機(jī)的帶時(shí)間窗逆向物流車輛路徑問題研究[D];武漢理工大學(xué);2013年

2 劉晴;隨機(jī)需求同時(shí)取送貨車輛路徑問題建模及優(yōu)化研究[D];南京航空航天大學(xué);2012年

本文編號：2808968