本文選題：物流　切入點(diǎn)：路由　出處：《哈爾濱工業(yè)大學(xué)》2016年碩士論文

【摘要】：隨著互聯(lián)網(wǎng)的快速發(fā)展,我們步入了一個(gè)快速消費(fèi)的時(shí)代�，F(xiàn)在互聯(lián)網(wǎng)越來(lái)越普及,更多的消費(fèi)者通過(guò)網(wǎng)絡(luò)在全球動(dòng)態(tài)市場(chǎng)中購(gòu)買(mǎi)商品,這就給物流配送公司提出了迫切要求,必須以顧客為中心,及時(shí)完成配送。調(diào)度問(wèn)題是許多物流系統(tǒng)面臨的重大難題。大量研究一直致力于找到好的方案,進(jìn)行調(diào)度優(yōu)化。其中最有挑戰(zhàn)性的組合優(yōu)化研究課題之一就是車(chē)輛路徑問(wèn)題。車(chē)輛路徑問(wèn)題是指有一定數(shù)量的、地理位置分散的客戶(hù),各自有不同的貨物需求,由一個(gè)車(chē)隊(duì)負(fù)責(zé)從配送中心分送貨物,組織適當(dāng)?shù)男熊?chē)安排,目標(biāo)是使得顧客的需求得到滿(mǎn)足,并保證路程最短。車(chē)輛路徑問(wèn)題是配送管理的主要內(nèi)容之一。盡管大量研究已經(jīng)對(duì)幾種類(lèi)型的車(chē)輛路徑問(wèn)題提出了解決方案,但是都是針對(duì)一些相對(duì)簡(jiǎn)單的問(wèn)題采用用精準(zhǔn)算法解決。然而,一些近似算法在解決車(chē)輛路徑問(wèn)題上顯示出了良好的效果。本文是針對(duì)動(dòng)態(tài)的取送貨路徑優(yōu)化問(wèn)題進(jìn)行研究,該問(wèn)題由于其承諾的可能性,值得更多的關(guān)注。物流和快遞公司為了使服務(wù)更加高效,對(duì)取送貨路徑優(yōu)化的需求會(huì)不斷增加。如今,配送系統(tǒng)需要運(yùn)輸要求實(shí)時(shí)到達(dá),所以需要對(duì)如何更好地安排動(dòng)態(tài)需求進(jìn)行更多研究。動(dòng)態(tài)取送貨的例子有:貨幣收藏、食品飲料配送、銀行與自動(dòng)存款機(jī)之間的交付、醫(yī)療樣本的運(yùn)輸以及最常見(jiàn)的基于互聯(lián)網(wǎng)的交付等。取送貨問(wèn)題是車(chē)輛路徑問(wèn)題的擴(kuò)展,每一個(gè)取送貨請(qǐng)求包含兩個(gè)位置:一個(gè)是取貨的地點(diǎn),一個(gè)是送貨的地點(diǎn)。無(wú)論哪一個(gè)地點(diǎn),應(yīng)該只被訪(fǎng)問(wèn)一次,而且應(yīng)該先取貨后送達(dá)各自的貨物交付地點(diǎn)。同時(shí)也需要考慮車(chē)的容量以及可以裝載的貨物數(shù)量。最后的限制條件就是復(fù)雜的優(yōu)化過(guò)程。本研究的主要目標(biāo)之一就是提供一個(gè)完整的關(guān)于帶時(shí)間窗的動(dòng)靜態(tài)取送貨問(wèn)題的文獻(xiàn)綜述。第二個(gè)目標(biāo)是對(duì)帶時(shí)間窗取送貨問(wèn)題的解決方法進(jìn)行大量分析,從而建立模型。本文共包括六個(gè)章節(jié)。第一章為緒論,概述了研究背景、研究意義、研究問(wèn)題以及研究目標(biāo)。第二章分析了不同國(guó)家的電子商務(wù)現(xiàn)狀,電子商務(wù)與送貨到家服務(wù)的現(xiàn)狀以及送貨到家服務(wù)存在的主要問(wèn)題。本文討論了物流服務(wù)中的配送問(wèn)題,并提出了前瞻性的解決方案,可以更好地提高配送能力。第三章對(duì)車(chē)輛路徑問(wèn)題以及分類(lèi)、帶時(shí)間窗的取送貨問(wèn)題的相關(guān)文獻(xiàn)進(jìn)行了全面深入的回顧分析。第四章是動(dòng)靜態(tài)取送貨問(wèn)題的模型的發(fā)展。首先,對(duì)動(dòng)靜態(tài)取送貨問(wèn)題的解決方法進(jìn)行了分析;然后,提供了方法、模型的選取、模型的描述和計(jì)算。第五章提供了實(shí)驗(yàn)結(jié)果,說(shuō)明數(shù)據(jù)收集及分析過(guò)程并給出設(shè)計(jì)以及仿真結(jié)果分析。第六章為結(jié)論。雖然帶時(shí)間窗的取送貨問(wèn)題在實(shí)際生活中可以被廣泛運(yùn)用,但是對(duì)該問(wèn)題的研究還是相對(duì)較少。在運(yùn)籌學(xué)領(lǐng)域,帶時(shí)間窗的取送貨問(wèn)題給出了正在發(fā)展的各種情況。改善目前的算法,對(duì)這樣復(fù)雜的優(yōu)化問(wèn)題進(jìn)行更多的研究是很重要的。在動(dòng)態(tài)車(chē)輛路徑問(wèn)題中,當(dāng)配送車(chē)輛已經(jīng)開(kāi)始服務(wù)后,還會(huì)不斷接收到新的服務(wù)請(qǐng)求。如今,在世界各地的大大小小的城市中,有很多快遞公司提供服務(wù),每天完成數(shù)百個(gè)取送貨請(qǐng)求。這些服務(wù)請(qǐng)求只有一小部分是提前知道的,大部分是在服務(wù)的過(guò)程中動(dòng)態(tài)接收到的。之前的研究主要是針對(duì)靜態(tài)車(chē)輛問(wèn)題,即在路徑優(yōu)化之前,知道所有的服務(wù)請(qǐng)求。動(dòng)態(tài)取送貨問(wèn)題的布線(xiàn)方法需要對(duì)動(dòng)態(tài)顯示的信息作出反應(yīng)。最近幾年,很多現(xiàn)代的實(shí)時(shí)技術(shù)被研制出來(lái),例如全球定位系統(tǒng)(gps)、先進(jìn)的車(chē)隊(duì)管理系統(tǒng)(afms)和智能轉(zhuǎn)換系統(tǒng)(its)。這使得動(dòng)態(tài)車(chē)輛路徑問(wèn)題成為一個(gè)比較熱門(mén)的研究領(lǐng)域,雖然這方面的文獻(xiàn)還是較少。車(chē)輛路徑問(wèn)題是np難題,取送貨問(wèn)題是比車(chē)輛路徑問(wèn)題更復(fù)雜的np難題。一些研究人員已經(jīng)研究出了精確的算法,但它們通常只能解決簡(jiǎn)單的問(wèn)題。一方面由于取送貨問(wèn)題的復(fù)雜性,另一方面由于該問(wèn)題大量的計(jì)算需求,使得這些精確算法不適用。通過(guò)分析不同的可以應(yīng)用于取送貨問(wèn)題的相關(guān)方法,本文決定選用元啟發(fā)式方法。在解決取送貨問(wèn)題上,元啟發(fā)式算法相對(duì)于傳統(tǒng)算法更加有效。它是一個(gè)結(jié)合不同的程序?qū)饪臻g進(jìn)行探索以至于找到更好的解。本文提出了在帶時(shí)間窗的取送貨問(wèn)題上應(yīng)用元啟發(fā)式算法的優(yōu)勢(shì)。本文將取送貨問(wèn)題轉(zhuǎn)化為整數(shù)線(xiàn)性規(guī)劃模型。整數(shù)線(xiàn)性規(guī)劃模型是一個(gè)數(shù)學(xué)優(yōu)化方法,它要求變量必須是整數(shù)型,目標(biāo)函數(shù)和約束條件是線(xiàn)性的。該模型被應(yīng)用在不同的情境中,包括時(shí)間調(diào)度問(wèn)題。目標(biāo)函數(shù)就是使總的運(yùn)行距離最小化。為了對(duì)提出的模型進(jìn)行仿真,必須先產(chǎn)生數(shù)據(jù)集。六種問(wèn)題分別有不同長(zhǎng)度的調(diào)度地平線(xiàn),不同數(shù)據(jù)類(lèi)型對(duì)地理位置的請(qǐng)求是不同的。為了對(duì)取送貨的問(wèn)題進(jìn)行仿真,本文將位置與解決方案的路線(xiàn)進(jìn)行隨機(jī)配對(duì)。該模型是以彈射鏈鄰域(ecn)和迭代搜索為框架。具體方法如下:1)一個(gè)請(qǐng)求(包括取貨和送貨兩個(gè)位置)需要從一個(gè)路線(xiàn)移動(dòng)到另一個(gè)路線(xiàn)。2)這導(dǎo)致另一個(gè)請(qǐng)求從一個(gè)路線(xiàn)移動(dòng)到另一個(gè)路線(xiàn),等等。3)外鏈可能包含任何數(shù)量的請(qǐng)求,可能是循環(huán)的,也可能不是。在這個(gè)過(guò)程中有一些遵循的基本規(guī)則:1)首先,確定取貨的最佳插入位置;然后,當(dāng)取貨位置移動(dòng)后,再確定送貨的最佳插入位置。2)在插入取貨或送貨位置之后,使用目標(biāo)函數(shù)的近似值來(lái)預(yù)估該位置的調(diào)整對(duì)成本函數(shù)的影響。3)將尋找最佳的插入移動(dòng)鏈以超過(guò)當(dāng)前設(shè)定的路線(xiàn)的任務(wù),建模為一個(gè)最短路徑問(wèn)題,試探性地解決問(wèn)題。4)在某些情況下,當(dāng)送貨位置不能改變時(shí),新的請(qǐng)求只是簡(jiǎn)單地被安排在相同的路線(xiàn)上。這是因?yàn)閷?duì)應(yīng)的取貨位置已經(jīng)被服務(wù)過(guò)。應(yīng)該使用適當(dāng)?shù)母聶C(jī)制對(duì)計(jì)劃路線(xiàn)進(jìn)行跟蹤,處理動(dòng)態(tài)環(huán)境的響應(yīng)時(shí)間必須足夠快,而且可以根據(jù)新的請(qǐng)求對(duì)當(dāng)前路線(xiàn)進(jìn)行優(yōu)化。本文提供了三個(gè)實(shí)驗(yàn):場(chǎng)景1,場(chǎng)景2,場(chǎng)景3。場(chǎng)景1的模擬時(shí)間是8.5小時(shí),使用20輛車(chē)輛,請(qǐng)求到達(dá)率不太頻繁(平均每小時(shí)24次請(qǐng)求)。在場(chǎng)景1中,每輛車(chē)平均每小時(shí)服務(wù)1.2個(gè)服務(wù)請(qǐng)求�？紤]到其中有5分鐘的服務(wù)時(shí)間與每個(gè)服務(wù)點(diǎn)聯(lián)系,12分鐘用于此目的,所以行程時(shí)間是48分鐘。在場(chǎng)景1的參數(shù)設(shè)置的比較寬松,為優(yōu)化留下空間。相比靜態(tài)解的問(wèn)題,旅行時(shí)間和距離不會(huì)受到影響的附表。場(chǎng)景2將模擬時(shí)間設(shè)置為4.5小時(shí),車(chē)輛從20輛減少到10輛,服務(wù)請(qǐng)求到達(dá)率保持在每小時(shí)28次。模擬結(jié)果為每輛車(chē)平均每小時(shí)服務(wù)2.4個(gè)服務(wù)請(qǐng)求。在更現(xiàn)實(shí)的環(huán)境中,在應(yīng)用動(dòng)態(tài)解決方案后,減少了21%的距離和18%的旅行時(shí)間。這提供了一個(gè)積極的結(jié)果。場(chǎng)景3比場(chǎng)景2更加動(dòng)態(tài),模擬時(shí)間是7小時(shí),使用10輛車(chē)輛,請(qǐng)求到達(dá)率由平均每小時(shí)28次上升到平均每小時(shí)33次。在場(chǎng)景3中,每輛車(chē)平均每小時(shí)服務(wù)3.3個(gè)服務(wù)請(qǐng)求。所以一旦服務(wù)時(shí)間被減掉,每個(gè)小時(shí)只剩下27分鐘可以行使。請(qǐng)求數(shù)量的增加對(duì)方案質(zhì)量有顯著的影響。幾乎總成本的33%都是由于在顧客的位置超時(shí)或者遲到。一開(kāi)始,看起來(lái)是每條路線(xiàn)上請(qǐng)求越多,優(yōu)化機(jī)會(huì)就越多;然而,我們忽略了在事件發(fā)生之間缺乏計(jì)算時(shí)間。當(dāng)獲得更多的計(jì)算時(shí)間時(shí),本文的算法是有效的。本文已證明禁忌搜索啟發(fā)式算法可以應(yīng)對(duì)復(fù)雜的動(dòng)態(tài)環(huán)境,例如同城的取送貨服務(wù)。當(dāng)有足夠的計(jì)算能力時(shí),該算法優(yōu)化了簡(jiǎn)單啟發(fā)式算法的結(jié)果(即使是對(duì)已知請(qǐng)求的優(yōu)化)。本文的主要結(jié)論是:1)靜態(tài)取送貨問(wèn)題可以用動(dòng)態(tài)的方法來(lái)解決,即靜動(dòng)態(tài)取送貨問(wèn)題的推廣。2)禁忌搜索的啟發(fā)式算法可以應(yīng)付復(fù)雜的動(dòng)態(tài)環(huán)境,例如,在本地的取貨和送貨服務(wù)。3)取得的結(jié)果,20%大于通過(guò)靜態(tài)算法實(shí)現(xiàn)。因此,通過(guò)應(yīng)用適于動(dòng)態(tài)問(wèn)題的方法,可以實(shí)現(xiàn)大規(guī)模靜態(tài)問(wèn)題的合理解決方案。本文的算法還存在以下不足:1)不能將車(chē)輛從當(dāng)前位置轉(zhuǎn)移到附近位置來(lái)服務(wù)一個(gè)新的請(qǐng)求,這是因?yàn)榕汕仓行呐c司機(jī)的溝通只在服務(wù)地點(diǎn)進(jìn)行。所以,可以考慮對(duì)該方法進(jìn)行改進(jìn),使得車(chē)輛在行駛過(guò)程中也可與派遣中心進(jìn)行聯(lián)系。2)該算法沒(méi)有考慮意外事故的情況(例如,車(chē)輛發(fā)生故障)。
[Abstract]:With the rapid development of Internet , we have entered a era of rapid consumption . Now the Internet is becoming more and more popular , more consumers buy goods in the global dynamic market through the network . In recent years , many modern real - time technologies have been developed , such as global positioning system ( gps ) , advanced fleet management system ( afms ) and intelligent conversion system . The new request is simply arranged on the same route . This is because the corresponding pick - up location has been serviced . The response time for the dynamic environment must be fast enough to track the planned route using an appropriate update mechanism . This provides a positive result . In Scenario 1 , the travel time and distance will not be affected . In Scenario 3 , the algorithm optimizes the results of a simple heuristic algorithm ( even for known requests ) . In scenario 3 , the algorithm optimizes the results of simple heuristic algorithms ( even for known requests ) . The vehicle has failed ) .

【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：F724.6;F252
，

本文編號(hào)：1702825