配送過程中提貨送貨問題的靜態(tài)動(dòng)態(tài)方法的應(yīng)用效果研究.pdf

1、隨著互聯(lián)網(wǎng)的快速發(fā)展，我們步入了一個(gè)快速消費(fèi)的時(shí)代?，F(xiàn)在互聯(lián)網(wǎng)越來越普及，更多的消費(fèi)者通過網(wǎng)絡(luò)在全球動(dòng)態(tài)市場中購買商品，這就給物流配送公司提出了迫切要求，必須以顧客為中心，及時(shí)完成配送。
　　調(diào)度問題是許多物流系統(tǒng)面臨的重大難題。大量研究一直致力于找到好的方案，進(jìn)行調(diào)度優(yōu)化。其中最有挑戰(zhàn)性的組合優(yōu)化研究課題之一就是車輛路徑問題。車輛路徑問題是指有一定數(shù)量的、地理位置分散的客戶，各自有不同的貨物需求，由一個(gè)車隊(duì)負(fù)責(zé)從配送中心分送貨物

2、，組織適當(dāng)?shù)男熊嚢才?，目?biāo)是使得顧客的需求得到滿足，并保證路程最短。車輛路徑問題是配送管理的主要內(nèi)容之一。盡管大量研究已經(jīng)對幾種類型的車輛路徑問題提出了解決方案，但是都是針對一些相對簡單的問題采用用精準(zhǔn)算法解決。然而，一些近似算法在解決車輛路徑問題上顯示出了良好的效果。本文是針對動(dòng)態(tài)的取送貨路徑優(yōu)化問題進(jìn)行研究，該問題由于其承諾的可能性，值得更多的關(guān)注。物流和快遞公司為了使服務(wù)更加高效，對取送貨路徑優(yōu)化的需求會(huì)不斷增加。如今，配送系統(tǒng)需

3、要運(yùn)輸要求實(shí)時(shí)到達(dá)，所以需要對如何更好地安排動(dòng)態(tài)需求進(jìn)行更多研究。動(dòng)態(tài)取送貨的例子有：貨幣收藏、食品飲料配送、銀行與自動(dòng)存款機(jī)之間的交付、醫(yī)療樣本的運(yùn)輸以及最常見的基于互聯(lián)網(wǎng)的交付等。
　　取送貨問題是車輛路徑問題的擴(kuò)展，每一個(gè)取送貨請求包含兩個(gè)位置：一個(gè)是取貨的地點(diǎn)，一個(gè)是送貨的地點(diǎn)。無論哪一個(gè)地點(diǎn)，應(yīng)該只被訪問一次，而且應(yīng)該先取貨后送達(dá)各自的貨物交付地點(diǎn)。同時(shí)也需要考慮車的容量以及可以裝載的貨物數(shù)量。最后的限制條件就是復(fù)雜的優(yōu)

4、化過程。
　　本研究的主要目標(biāo)之一就是提供一個(gè)完整的關(guān)于帶時(shí)間窗的動(dòng)靜態(tài)取送貨問題的文獻(xiàn)綜述。第二個(gè)目標(biāo)是對帶時(shí)間窗取送貨問題的解決方法進(jìn)行大量分析，從而建立模型。
　　本文共包括六個(gè)章節(jié)。第一章為緒論，概述了研究背景、研究意義、研究問題以及研究目標(biāo)。
　　第二章分析了不同國家的電子商務(wù)現(xiàn)狀，電子商務(wù)與送貨到家服務(wù)的現(xiàn)狀以及送貨到家服務(wù)存在的主要問題。本文討論了物流服務(wù)中的配送問題，并提出了前瞻性的解決方案，可以更好地

5、提高配送能力。
　　第三章對車輛路徑問題以及分類、帶時(shí)間窗的取送貨問題的相關(guān)文獻(xiàn)進(jìn)行了全面深入的回顧分析。
　　第四章是動(dòng)靜態(tài)取送貨問題的模型的發(fā)展。首先，對動(dòng)靜態(tài)取送貨問題的解決方法進(jìn)行了分析；然后，提供了方法、模型的選取、模型的描述和計(jì)算。
　　第五章提供了實(shí)驗(yàn)結(jié)果，說明數(shù)據(jù)收集及分析過程并給出設(shè)計(jì)以及仿真結(jié)果分析。
　　第六章為結(jié)論。
　　雖然帶時(shí)間窗的取送貨問題在實(shí)際生活中可以被廣泛運(yùn)用，但是對該問

6、題的研究還是相對較少。在運(yùn)籌學(xué)領(lǐng)域，帶時(shí)間窗的取送貨問題給出了正在發(fā)展的各種情況。改善目前的算法，對這樣復(fù)雜的優(yōu)化問題進(jìn)行更多的研究是很重要的。
　　在動(dòng)態(tài)車輛路徑問題中，當(dāng)配送車輛已經(jīng)開始服務(wù)后，還會(huì)不斷接收到新的服務(wù)請求。如今，在世界各地的大大小小的城市中，有很多快遞公司提供服務(wù)，每天完成數(shù)百個(gè)取送貨請求。這些服務(wù)請求只有一小部分是提前知道的，大部分是在服務(wù)的過程中動(dòng)態(tài)接收到的。之前的研究主要是針對靜態(tài)車輛問題，即在路徑優(yōu)化之

7、前，知道所有的服務(wù)請求。動(dòng)態(tài)取送貨問題的布線方法需要對動(dòng)態(tài)顯示的信息作出反應(yīng)。最近幾年，很多現(xiàn)代的實(shí)時(shí)技術(shù)被研制出來，例如全球定位系統(tǒng)（GPS）、先進(jìn)的車隊(duì)管理系統(tǒng)（AFMS）和智能轉(zhuǎn)換系統(tǒng)（ITS）。這使得動(dòng)態(tài)車輛路徑問題成為一個(gè)比較熱門的研究領(lǐng)域，雖然這方面的文獻(xiàn)還是較少。
　　車輛路徑問題是NP難題，取送貨問題是比車輛路徑問題更復(fù)雜的NP難題。一些研究人員已經(jīng)研究出了精確的算法，但它們通常只能解決簡單的問題。一方面由于取送貨

8、問題的復(fù)雜性，另一方面由于該問題大量的計(jì)算需求，使得這些精確算法不適用。
　　通過分析不同的可以應(yīng)用于取送貨問題的相關(guān)方法，本文決定選用元啟發(fā)式方法。在解決取送貨問題上，元啟發(fā)式算法相對于傳統(tǒng)算法更加有效。它是一個(gè)結(jié)合不同的程序?qū)饪臻g進(jìn)行探索以至于找到更好的解。本文提出了在帶時(shí)間窗的取送貨問題上應(yīng)用元啟發(fā)式算法的優(yōu)勢。
　　本文將取送貨問題轉(zhuǎn)化為整數(shù)線性規(guī)劃模型。整數(shù)線性規(guī)劃模型是一個(gè)數(shù)學(xué)優(yōu)化方法，它要求變量必須是整數(shù)型，

9、目標(biāo)函數(shù)和約束條件是線性的。該模型被應(yīng)用在不同的情境中，包括時(shí)間調(diào)度問題。目標(biāo)函數(shù)就是使總的運(yùn)行距離最小化。
　　為了對提出的模型進(jìn)行仿真，必須先產(chǎn)生數(shù)據(jù)集。六種問題分別有不同長度的調(diào)度地平線，不同數(shù)據(jù)類型對地理位置的請求是不同的。為了對取送貨的問題進(jìn)行仿真，本文將位置與解決方案的路線進(jìn)行隨機(jī)配對。
　　該模型是以彈射鏈鄰域（ECN）和迭代搜索為框架。具體方法如下：
　　1）一個(gè)請求（包括取貨和送貨兩個(gè)位置）需要從一個(gè)

10、路線移動(dòng)到另一個(gè)路線。
　　2）這導(dǎo)致另一個(gè)請求從一個(gè)路線移動(dòng)到另一個(gè)路線，等等。
　　3）外鏈可能包含任何數(shù)量的請求，可能是循環(huán)的，也可能不是。
　　在這個(gè)過程中有一些遵循的基本規(guī)則：
　　1）首先，確定取貨的最佳插入位置；然后，當(dāng)取貨位置移動(dòng)后，再確定送貨的最佳插入位置。
　　2）在插入取貨或送貨位置之后，使用目標(biāo)函數(shù)的近似值來預(yù)估該位置的調(diào)整對成本函數(shù)的影響。
　　3）將尋找最佳的插入移動(dòng)鏈以超

11、過當(dāng)前設(shè)定的路線的任務(wù)，建模為一個(gè)最短路徑問題，試探性地解決問題。
　　4）在某些情況下，當(dāng)送貨位置不能改變時(shí)，新的請求只是簡單地被安排在相同的路線上。這是因?yàn)閷?yīng)的取貨位置已經(jīng)被服務(wù)過。
　　應(yīng)該使用適當(dāng)?shù)母聶C(jī)制對計(jì)劃路線進(jìn)行跟蹤，處理動(dòng)態(tài)環(huán)境的響應(yīng)時(shí)間必須足夠快，而且可以根據(jù)新的請求對當(dāng)前路線進(jìn)行優(yōu)化。
　　本文提供了三個(gè)實(shí)驗(yàn)：場景1，場景2，場景3。場景1的模擬時(shí)間是8.5小時(shí)，使用20輛車輛，請求到達(dá)率不太頻

12、繁（平均每小時(shí)24次請求）。在場景1中，每輛車平均每小時(shí)服務(wù)1.2個(gè)服務(wù)請求?？紤]到其中有5分鐘的服務(wù)時(shí)間與每個(gè)服務(wù)點(diǎn)聯(lián)系，12分鐘用于此目的，所以行程時(shí)間是48分鐘。在場景1的參數(shù)設(shè)置的比較寬松，為優(yōu)化留下空間。相比靜態(tài)解的問題，旅行時(shí)間和距離不會(huì)受到影響的附表。
　　場景2將模擬時(shí)間設(shè)置為4.5小時(shí)，車輛從20輛減少到10輛，服務(wù)請求到達(dá)率保持在每小時(shí)28次。模擬結(jié)果為每輛車平均每小時(shí)服務(wù)2.4個(gè)服務(wù)請求。在更現(xiàn)實(shí)的環(huán)境中，在

13、應(yīng)用動(dòng)態(tài)解決方案后，減少了21％的距離和18%的旅行時(shí)間。這提供了一個(gè)積極的結(jié)果。
　　場景3比場景2更加動(dòng)態(tài)，模擬時(shí)間是7小時(shí),使用10輛車輛，請求到達(dá)率由平均每小時(shí)28次上升到平均每小時(shí)33次。在場景3中，每輛車平均每小時(shí)服務(wù)3.3個(gè)服務(wù)請求。所以一旦服務(wù)時(shí)間被減掉，每個(gè)小時(shí)只剩下27分鐘可以行使。請求數(shù)量的增加對方案質(zhì)量有顯著的影響。幾乎總成本的33%都是由于在顧客的位置超時(shí)或者遲到。一開始，看起來是每條路線上請求越多，優(yōu)化

14、機(jī)會(huì)就越多；然而，我們忽略了在事件發(fā)生之間缺乏計(jì)算時(shí)間。當(dāng)獲得更多的計(jì)算時(shí)間時(shí)，本文的算法是有效的。
　　本文已證明禁忌搜索啟發(fā)式算法可以應(yīng)對復(fù)雜的動(dòng)態(tài)環(huán)境，例如同城的取送貨服務(wù)。當(dāng)有足夠的計(jì)算能力時(shí)，該算法優(yōu)化了簡單啟發(fā)式算法的結(jié)果（即使是對已知請求的優(yōu)化）。
　　本文的主要結(jié)論是：
　　1）靜態(tài)取送貨問題可以用動(dòng)態(tài)的方法來解決，即靜動(dòng)態(tài)取送貨問題的推廣。
　　2）禁忌搜索的啟發(fā)式算法可以應(yīng)付復(fù)雜的動(dòng)態(tài)環(huán)境，例

15、如，在本地的取貨和送貨服務(wù)。
　　3)取得的結(jié)果，20%大于通過靜態(tài)算法實(shí)現(xiàn)。因此，通過應(yīng)用適于動(dòng)態(tài)問題的方法，可以實(shí)現(xiàn)大規(guī)模靜態(tài)問題的合理解決方案。
　　本文的算法還存在以下不足：
　　1）不能將車輛從當(dāng)前位置轉(zhuǎn)移到附近位置來服務(wù)一個(gè)新的請求，這是因?yàn)榕汕仓行呐c司機(jī)的溝通只在服務(wù)地點(diǎn)進(jìn)行。所以，可以考慮對該方法進(jìn)行改進(jìn)，使得車輛在行駛過程中也可與派遣中心進(jìn)行聯(lián)系。
　　2）該算法沒有考慮意外事故的情況（例如，車