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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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