1、考慮混合分批送貨和取貨之車輛途程問題研 究 生：盧柏翔指導教授：駱景堯教授報告日期：2008/1/61考慮混合分批送貨和取貨之車輛途程問題研 究 生：盧柏翔1摘要本研究的基本假設(shè)是建立在需求點可能同時需要送貨及取貨的情況，且允許分批送貨和取貨，加上不違背車容量限制、時窗限制和有限行駛距離限制內(nèi)，來求解最小總路線成本的規(guī)劃。本研究的目的為建構(gòu)一個符合本研究的數(shù)學模式，並且利用禁忌搜尋法進行求解，期望在問題規(guī)模變大的時候，能夠快速獲得近似最佳解。 2摘要本研究的基本假設(shè)是建立在需求點可能同時需要送貨及取貨的情大綱緒論研究背景與動機研究目的 研究範圍 研究流程文獻探討車輛途程問題 車輛途程問題含時窗

2、限制 車輛途程問題含回程取貨 車輛途程問題含混合送貨和取貨 車輛途程問題含分批送貨車輛途程問題彙整小結(jié)數(shù)學模式建立 問題描述 數(shù)學規(guī)劃模式 未來研究進度和預期結(jié)果 3大綱緒論3緒論-研究背景與動機(1/5)隨著時代進步與社會的發(fā)展，物流中心的出現(xiàn)，漸漸地改變傳統(tǒng)流通管道的方式。 製造商大批發(fā)商中批發(fā)商小批發(fā)商零售商製造商零售商傳統(tǒng)流通方式現(xiàn)代流通方式4緒論-研究背景與動機(1/5)隨著時代進步與社會的發(fā)展，物流緒論-研究背景與動機(2/5)車輛途程問題(Vehicle Routing Problem, VRP)是物流議題當中最受到重視的，因為現(xiàn)今的油價居高不下，若可以改善其配送路線規(guī)劃，有效的

3、減少運輸成本，將可以提升貨運業(yè)的競爭能力。車輛途程含回程取貨問題(Vehicle Routing Problem with Backhauls, VRPB)是典型VRP的延伸。在VRPB中，顧客需求分為送貨和取貨兩種，車輛完成送貨作業(yè)之後，在回程時可以進行取貨的作業(yè)。 5緒論-研究背景與動機(2/5)車輛途程問題(Vehicle 緒論-研究背景與動機(3/5)若需求點同時具有送貨和取貨兩種性質(zhì)時，以VRPB的假設(shè)而言，會造成此需求點被拜訪兩次的情況，而增加運輸成本。因此本研究考慮需求點同時具有送貨和取貨。另外考量單純送貨模式時，當顧客需求大於車容量時，沒辦法一次送貨就滿足需求點，因此就需要分批

4、送貨。根據(jù)Archetti等人(2008)提到當需求量大於或小於車容量時，分批送貨會有較好的效益；所以本研究考慮需求點有兩種情況：一為需求量大於車容量，另一為需求輛小於車容量。 6緒論-研究背景與動機(3/5)若需求點同時具有送貨和取貨兩種緒論-研究背景與動機(4/5)除此之外，在實際配送的過程中，為了增加顧客的滿意度，每一個需求點都會有時窗限制。時窗限制可分為硬時窗和軟時窗，所謂的硬時窗就是車輛必須在指定的時間內(nèi)到達並開始服務(wù)，不允許遲到，如果提早到達必須等到時窗開起才可以開始服務(wù)；軟時窗是指可允許不在指定的時間內(nèi)到達，但是必須給予一個懲罰值。另外在考慮車輛行駛距離的條件下，會給予一個上限值

5、，也就是最大行駛距離的限制，期望能在有限的資源下，可以完成所有配送作業(yè)。7緒論-研究背景與動機(4/5)除此之外，在實際配送的過程中，緒論-研究背景與動機(5/5)綜合以上的敘述，為了能更符合現(xiàn)實配送作業(yè)的情況，本研究考慮需求點同時具有單一送貨、單一取貨和同時具有送貨和取貨三種作業(yè)型態(tài)，而此三種作業(yè)型態(tài)也都加入分批送(取)貨的考慮，而車輛必須考慮有限的行駛距離，同時考慮軟時窗的限制，來求解總路線成本最小的規(guī)劃。8緒論-研究背景與動機(5/5)綜合以上的敘述，為了能更符合現(xiàn)緒論-研究目的VRP屬於NP-hard(Nondeterministic Polynomial Time Hard)問題，也

6、就是當需求點增加的時候，求解的時間會成指數(shù)倍增加。本研究是基於VRP再加上諸多限制條件，複雜度可想而知。 因此本研究的目的如下：針對本研究的問題，提出數(shù)學模式，並利用LINGO驗證其正確性。發(fā)展啟發(fā)式演算法求解，期望在問題範圍變大時，能快速求得近似最佳解。9緒論-研究目的VRP屬於NP-hard(Nondetermi緒論-研究範圍項目性質(zhì)場站單一場站車輛種類單一車種產(chǎn)品種類同種產(chǎn)品顧客需求已知固定需求，需求點的需求量有可能大於車容量或小於車容量，並且可允許分批送貨和取貨。 作業(yè)型態(tài)單一送貨、單一取貨和同時具有送貨和取貨限制行駛距離、車容量、軟時窗衡量指標總路線成本最小化10緒論-研究範圍項目性

7、質(zhì)場站單一場站車輛種類單一車種產(chǎn)品種類同緒論-研究流程11緒論-研究流程11文獻探討-車輛途程問題(1/7)車輛途程問題的定義如下：有個場站總共有k輛貨車，車容量皆為Q，有n個需求點需要被服務(wù)，每個需求點的需求量為q，貨車從需求點i到需求點j的運送成本為cij，在不違反車容量的限制條件下，車輛自場站出發(fā)且滿足所有需求點的需求後返回場站，其目標為路徑成本最小化 。：Depot：Deliveries12文獻探討-車輛途程問題(1/7)車輛途程問題的定義如下：有文獻探討-車輛途程問題(2/7)基本假設(shè)如下：場站和需求點的位置固定且已知。需求點的需求量固定且已知。每個需求點到另一個需求點的距離成本為已

8、知。另外必須滿足下列限制，以求得總路線成本最小化：每個需求點只能被一輛車服務(wù)一次。每輛車皆由場站出發(fā)，服務(wù)完後必須回到原場站。每輛車所服務(wù)的需求點，其需求量總和不能超過車容量。每個需求點的需求量必需都被滿足。每輛車只服務(wù)一條路徑。13文獻探討-車輛途程問題(2/7)基本假設(shè)如下：13文獻探討-車輛途程問題(3/7)車輛途程問題之相關(guān)啟發(fā)式解法依據(jù)Fisher(1995)將VRP的相關(guān)解法可分為三類簡易啟發(fā)式演算法數(shù)學規(guī)劃模式萬用啟發(fā)式演算法模擬退火法(Simulated Annealing, SA)禁忌搜尋法(Tabu Search, TS)14文獻探討-車輛途程問題(3/7)車輛途程問題之相

9、關(guān)啟發(fā)式解法文獻探討-車輛途程問題(4/7)模擬退火法是否是否15文獻探討-車輛途程問題(4/7)模擬退火法是否是否15文獻探討-車輛途程問題(5/7)作者方法結(jié)果Osman(1993) 利用途程間單一個節(jié)點的交換改善法來對總途程做改善，並加入了禁忌搜尋法和模擬退火法的混合搜尋法 使改善的解能夠跳脫局部最佳解Van Breedam(1995) String Relocation、String Exchange和String Mix三種途程間的改善法，再加入模擬退火法的機制來做改善 得到的解比單純用這三種改善法的結(jié)果來的較佳16文獻探討-車輛途程問題(5/7)作者方法結(jié)果Osman(19文獻探討

10、-車輛途程問題(6/7)禁忌搜尋法是是否否17文獻探討-車輛途程問題(6/7)禁忌搜尋法是是否否17文獻探討-車輛途程問題(7/7)作者方法結(jié)果Potvin等人(1996) 以平插入的線求得起始解，再以O(shè)r-opt與2-opt*為核心的禁忌搜尋法求解VRPHTW 結(jié)果與Solomon例題進行比較，所有問題可明顯的改善，但平均求解時間過長。 18文獻探討-車輛途程問題(7/7)作者方法結(jié)果Potvin等人文獻探討-車輛途程問題含時窗限制(1/2)車輛途程問題含時窗限制(Vehicle Routing Problem with Time Windows, VRPTW)，就是每個需求點都有不同送貨時

11、間為限制，基本上可分為硬時窗和軟時窗兩種。在硬時窗中，所找到的解一定要符合時間範圍內(nèi)的限制，不然就是不可行解，可是在現(xiàn)實生活中，除非很特殊的情況，否則很少顧客會如此嚴格的要求。因此本研究探討較為符合現(xiàn)實生活的情況，也就是軟時窗限制。19文獻探討-車輛途程問題含時窗限制(1/2)車輛途程問題含時窗文獻探討-車輛途程問題含時窗限制(2/2)車輛途程問題含時窗限制之相關(guān)啟發(fā)式解法作者方法結(jié)果Fisher等人(1997) 提出K-Tree Approach和拉氏鬆弛/變數(shù)分割方法 以Solomon例題去測試，可以求解到100個需求點至最佳解 Taillard等人(1997)以Tabu Search為主

12、體，利用Cross exchange，和Cross exchange的兩個特例2-opt*以及Or-opt求解VRPSTW 結(jié)果與Solomon例題進行比較，可以獲得較佳的解 敖君瑋(1999) 以Tabu Search為主體，利用最鄰近法、掃描法和節(jié)省法求得起始解，再利用途程內(nèi)Swap、Or-opt，途程間Swap，Cross exchange以及2-opt*求解VRPSTW 結(jié)果與Solomon例題進行比較，結(jié)果以最鄰近解法所建構(gòu)的起始解經(jīng)改善後最佳 20文獻探討-車輛途程問題含時窗限制(2/2)車輛途程問題含時窗文獻探討-車輛途程問題含回程取貨(1/3)傳統(tǒng)的車輛途程問題，若將需求點分成

13、取貨和或兩種，且在完成送貨服務(wù)之後，開始進行取貨的服務(wù)，這就是車輛途程問題含回程取貨 。：Depot：Deliveries：Pickup21文獻探討-車輛途程問題含回程取貨(1/3)傳統(tǒng)的車輛途程問題文獻探討-車輛途程問題含回程取貨(2/3)車輛途程問題含回程取貨之相關(guān)啟發(fā)式解法作者方法結(jié)果Goetschalckx和Jacobs-Blecha(1989) 提出一個啟發(fā)式解法，分成建構(gòu)和改善兩個階段，建構(gòu)部份是利用空間填滿取線求得起始解，改善部份則是利用數(shù)學模式中分解成子問題最佳的觀念，當作改善的基礎(chǔ)，再以貪心法(greedy method)和K-median兩個方法當做改善的依據(jù) 結(jié)果顯示貪心

14、法和K-median的運送距離相等，但貪心法的車輛利用率較高，使用的車輛數(shù)較少。 Toth和Vigo(1997) 提出數(shù)學規(guī)劃法求解，並利用拉氏鬆弛法得到一個有效的下限值 結(jié)果與Solomon例題進行比較，發(fā)現(xiàn)與最佳解誤差2.2%22文獻探討-車輛途程問題含回程取貨(2/3)車輛途程問題含回程文獻探討-車輛途程問題含回程取貨(3/3)作者方法結(jié)果Duhamel等人(1997) 利用禁忌搜尋法來求解VRPBTW，利用貪心插入法獲得起始解，接著在禁忌搜尋法裡，是先隨機選取2-opt*、Or-opt、swap三種交換改善法的其中一種來改善原來的可行解結(jié)果與Solomon例題進行比較，並設(shè)定取貨的比率

15、加以求解，有不錯的結(jié)果 23文獻探討-車輛途程問題含回程取貨(3/3)作者方法結(jié)果Duh文獻探討-車輛途程問題含混合送貨和取貨(1/3)本問題對需求點的限制加以寬放，需求點可同時具有送貨和取貨的條件，並且未限制送貨和取貨的先後順序。 D PD P：BothD P：Depot：Deliveries：Pickup24文獻探討-車輛途程問題含混合送貨和取貨(1/3)本問題對需求文獻探討-車輛途程問題含混合送貨和取貨(2/3)車輛途程問題含混合送貨和取貨之相關(guān)啟發(fā)式解法作者方法結(jié)果Min(1989) 先將節(jié)點依地理鄰近度分群，然後再分派車輛到各分群中，轉(zhuǎn)換成TSP問題利用數(shù)學規(guī)劃法求解 能有效的節(jié)省行

16、駛距離 Dethloff(2001) 先分群再安排路線，接著在利用4種插入法，插入的準則分別為travel distance、residual capacity、radial surcharge和combination 結(jié)果發(fā)現(xiàn)利用combination的方法比其他3種方法來的較佳，再用combination的方法和文獻去比較，可以獲得較佳的結(jié)果 25文獻探討-車輛途程問題含混合送貨和取貨(2/3)車輛途程問題文獻探討-車輛途程問題含混合送貨和取貨(3/3)作者方法結(jié)果Alfred(2006) 利用禁忌搜尋法來求解VRPSDP，利用途程間Relocation、 Interchange和Cros

17、sover Movements三種方法和途程內(nèi)2-opt方法 和Dethloff(2001)的問題去比較可以改善8.82%；和Salhi and Nagy(1999)的問題(without distance constraints)可以改善13.43%；和Salhi and Nagy(1999)的問題(with distance constraints)去比較，可以改善27.76%。 徐俊誠(2000) 以最鄰近解法和掃描法分別加上改良型插入法作為模擬退火法之起始解，接著途程間利用2-exchange、2-swap或插入法與途程內(nèi)利用2-opt*和OR-opt 其結(jié)果都比傳統(tǒng)模式來的好 26文

18、獻探討-車輛途程問題含混合送貨和取貨(3/3)作者方法結(jié)果文獻探討-車輛途程問題含分批送貨(1/4)車輛途程問題含分批送貨(Vehicle Routing Problem with Split Deliveries, VRPSD)就是考慮需求點可以被兩臺車以上服務(wù)。21A32B13：Depot：Deliveries27文獻探討-車輛途程問題含分批送貨(1/4)車輛途程問題含分批文獻探討-車輛途程問題含分批送貨(2/4)車輛途程問題分批送貨之相關(guān)啟發(fā)式解法Dror和Trudeau(1989)提出成本矩陣Cij滿足triangular inequality，沒有兩條路線在最佳解的時候，共同擁有超過

19、一個可分割的需求點。 28文獻探討-車輛途程問題含分批送貨(2/4)車輛途程問題分批送文獻探討-車輛途程問題含分批送貨(3/4)作者方法結(jié)果Frizzell和Giffin(1995) 利用Dynamic Urgency Classification的方法加上MOVECUSTOMER的改善方法 和Solomon所提出的VRPTW比較，可以得到較佳的解 郭維凌(1999)求解多車種車輛途程問題含分批送貨，利用節(jié)線間交換和節(jié)線內(nèi)交換改善路線成本 可以快速求得近似解 Ho和Haugland(2004) 以Tabu Search為主體，加上relocate、exchange、2-opt*和relocat

20、e split四種途程間交換方式和Solomon所提出的VRPTW比較，可以得到較佳的解，但因為此問題比VRPTW複雜，所以在計算時間上會花較多的時間 29文獻探討-車輛途程問題含分批送貨(3/4)作者方法結(jié)果Fri文獻探討-車輛途程問題含分批送貨(4/4)Archetti等人(2008)提出分批送貨有以下三個好處：分批送貨可以節(jié)省送貨的路線。當需求點的需求大於車容量的一半但小於車容量的四分之三，且變異很小的時候，可獲得較大的效益。分批送貨的效益主要取決於需求點的需求輛和車容量，跟需求點的位置沒有太大的關(guān)係。作者方法結(jié)果Archetti等人(2006) 以Tabu Search為主體，先利用G

21、ENIUS algorithm產(chǎn)生起始解，再利用ORDER ROUTES和BEST NEIGHBOR的方法改善 和Dror和Trudeau的方法比較，可以得到較佳的解 30文獻探討-車輛途程問題含分批送貨(4/4)作者方法結(jié)果Arc車輛途程問題彙整問題類型衡量指標需求點型態(tài)資源限制VRP總路線成本最小化固定需求單一送貨或單一取貨單一場站單一車種有容量限制VRPTW總路線成本最小化固定需求單一送貨或單一取貨時窗限制單一場站單一車種有容量限制VRPB總路線成本最小化固定需求先送貨後取貨單一場站單一車種有容量限制VRPSDP總路線成本最小化固定需求同時具有送貨和取貨單一場站單一車種有容量限制VRPS

22、D總路線成本最小化固定需求分批送貨單一場站單一車種有容量限制31車輛途程問題彙整問題類型衡量指標需求點型態(tài)資源限制VRP總路小結(jié)車輛途程問題已經(jīng)廣泛的被討論，目前對於分批送貨的文獻並不多，而且大部份都只考慮時窗限制，因此引發(fā)一個新的構(gòu)想作為本研究的主體，主要是根據(jù)Archetti等人(2008)所發(fā)表的文章裡提到分批送貨的三個優(yōu)點，再加上其他相關(guān)的限制條件，例如：時窗限制、混合送貨和取貨有限行駛距離，期望能得到相同的結(jié)果。另外在啟發(fā)式演算法的部份，對於求解VSPSD，禁忌搜尋法可以獲得不錯的效果，因此本研究將以禁忌收尋法為主體，作為本研究的演算法。32小結(jié)車輛途程問題已經(jīng)廣泛的被討論，目前對於

23、分批送貨的文獻並不數(shù)學模式建立-問題描述(1/2) 本研究問題是將傳統(tǒng)車輛途程問題加以延伸，其需求點可分為單一送貨、或單一取貨或同時送貨和取貨的作業(yè)型態(tài)，且可以允許分批送貨和取貨，另外同時考慮軟時窗的限制；而每一輛車都有車容量的限制，且都有行駛距離的限制，其基本假設(shè)和限制如下：單一場站且位置已知。需求點的位置已知，作業(yè)型態(tài)可分為單一送貨、單一取貨或同時送貨和取貨，其需求量固定且已知。車容量和最大行駛距離皆為已知且固定。每個需求點至少被一輛車服務(wù)一次，即可分批送貨或取貨。 33數(shù)學模式建立-問題描述(1/2) 本研究問題是將傳統(tǒng)車輛途程數(shù)學模式建立-問題描述(2/2)每個需求點可同時接受多輛車服務(wù)。每個需求點都有軟時窗限制。每輛車皆由場站出發(fā)，服務(wù)完後必須回到原場站。車輛服務(wù)需求點i結(jié)束後，必須從需求點i離開。每輛車所服務(wù)的需求點，其需求量總和不能超過車容量。每個需求點的需求量必須都被滿足。車輛