资源描述
*,*,按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,Department of Industrial Engineering and Management,National Yunlin University of Science and Technology,按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,*,考慮混合分批送貨和取貨之車輛途程問題,研 究 生：盧柏翔,指導教授：駱景堯教授,報告日期：2008/1/6,1,考慮混合分批送貨和取貨之車輛途程問題研 究 生：盧柏翔1,摘要,本研究的基本假設是建立在需求點可能同時需要送貨及取貨的情況，且允許分批送貨和取貨，加上不違背車容量限制、時窗限制和有限行駛距離限制內，來求解最小總路線成本的規劃。,本研究的目的為建構一個符合本研究的數學模式，並且利用禁忌搜尋法進行求解，期望在問題規模變大的時候，能夠快速獲得近似最佳解。,2,摘要本研究的基本假設是建立在需求點可能同時需要送貨及取貨的情,大綱,緒論,研究背景與動機,研究目的,研究範圍,研究流程,文獻探討,車輛途程問題,車輛途程問題含時窗限制,車輛途程問題含回程取貨,車輛途程問題含混合送貨和取貨,車輛途程問題含分批送貨,車輛途程問題彙整,小結,數學模式建立,問題描述,數學規劃模式,未來研究進度和預期結果,3,大綱緒論3,緒論,-研究背景與動機(1/5),隨著時代進步與社會的發展，物流中心的出現，漸漸地改變傳統流通管道的方式。,製造商,大批發商,中批發商,小批發商,零售商,製造商,零售商,傳統流通方式,現代流通方式,4,緒論-研究背景與動機(1/5)隨著時代進步與社會的發展，物流,緒論,-研究背景與動機(2/5),車輛途程問題,(Vehicle Routing Problem,VRP)是物流議題當中最受到重視的，因為現今的油價居高不下，若可以改善其配送路線規劃，有效的減少運輸成本，將可以提升貨運業的競爭能力。,車輛途程含回程取貨問題,(Vehicle Routing Problem with Backhauls,VRPB)是典型VRP的延伸。在VRPB中，顧客需求分為送貨和取貨兩種，車輛完成送貨作業之後，在回程時可以進行取貨的作業。,5,緒論-研究背景與動機(2/5)車輛途程問題(Vehicle,緒論,-研究背景與動機(3/5),若需求點同時具有送貨和取貨兩種性質時，以VRPB的假設而言，會造成此需求點被拜訪兩次的情況，而增加運輸成本。因此本研究考慮需求點,同時具有送貨和取貨,。,另外考量單純送貨模式時，當顧客需求大於車容量時，沒辦法一次送貨就滿足需求點，因此就需要,分批送貨,。,根據Archetti等人(2008)提到當需求量大於或小於車容量時，分批送貨會有較好的效益；所以本研究考慮需求點有兩種情況：一為需求量大於車容量，另一為需求輛小於車容量。,6,緒論-研究背景與動機(3/5)若需求點同時具有送貨和取貨兩種,緒論,-研究背景與動機(4/5),除此之外，在實際配送的過程中，為了增加顧客的滿意度，每一個需求點都會有時窗限制。時窗限制可分為硬時窗和軟時窗，所謂的硬時窗就是車輛必須在指定的時間內到達並開始服務，不允許遲到，如果提早到達必須等到時窗開起才可以開始服務；軟時窗是指可允許不在指定的時間內到達，但是必須給予一個懲罰值。,另外在考慮車輛行駛距離的條件下，會給予一個上限值，也就是最大行駛距離的限制，期望能在有限的資源下，可以完成所有配送作業。,7,緒論-研究背景與動機(4/5)除此之外，在實際配送的過程中，,緒論,-研究背景與動機(5/5),綜合以上的敘述，為了能更符合現實配送作業的情況，本研究考慮需求點同時具有單一送貨、單一取貨和同時具有送貨和取貨三種作業型態，而此三種作業型態也都加入分批送(取)貨的考慮，而車輛必須考慮有限的行駛距離，同時考慮軟時窗的限制，來求解總路線成本最小的規劃。,8,緒論-研究背景與動機(5/5)綜合以上的敘述，為了能更符合現,緒論,-研究目的,VRP屬於NP-hard(Nondeterministic Polynomial Time Hard)問題，也就是當需求點增加的時候，求解的時間會成指數倍增加。本研究是基於VRP再加上諸多限制條件，複雜度可想而知。,因此本研究的目的如下：,針對本研究的問題，提出數學模式，並利用LINGO驗證其正確性。,發展啟發式演算法求解，期望在問題範圍變大時，能快速求得近似最佳解。,9,緒論-研究目的VRP屬於NP-hard(Nondetermi,緒論,-研究範圍,項目,性質,場站,單一場站,車輛種類,單一車種,產品種類,同種產品,顧客需求,已知固定需求，需求點的需求量有可能大於車容量或小於車容量，並且可允許分批送貨和取貨。,作業型態,單一送貨、單一取貨和同時具有送貨和取貨,限制,行駛距,離、車容量、軟時窗,衡量指標,總路線成本最小化,10,緒論-研究範圍項目性質場站單一場站車輛種類單一車種產品種類同,緒論,-研究流程,11,緒論-研究流程11,文獻探討,-車輛途程問題(1/7),車輛途程問題的定義如下：有個場站總共有k輛貨車，車容量皆為Q，有n個需求點需要被服務，每個需求點的需求量為q，貨車從需求點i到需求點j的運送成本為c,ij,，在不違反車容量的限制條件下，車輛自場站出發且滿足所有需求點的需求後返回場站，其目標為路徑成本最小化。,：,Depot,：,Deliveries,12,文獻探討-車輛途程問題(1/7)車輛途程問題的定義如下：有,文獻探討,-車輛途程問題(2/7),基本假設如下：,場站和需求點的位置固定且已知。,需求點的需求量固定且已知。,每個需求點到另一個需求點的距離成本為已知。,另外必須滿足下列限制，以求得總路線成本最小化：,每個需求點只能被一輛車服務一次。,每輛車皆由場站出發，服務完後必須回到原場站。,每輛車所服務的需求點，其需求量總和不能超過車容量。,每個需求點的需求量必需都被滿足。,每輛車只服務一條路徑。,13,文獻探討-車輛途程問題(2/7)基本假設如下：13,文獻探討,-車輛途程問題(3/7),車輛途程問題之相關啟發式解法,依據Fisher(1995)將VRP的相關解法可分為三類,簡易啟發式演算法,數學規劃模式,萬用啟發式演算法,模擬退火法(Simulated Annealing,SA),禁忌搜尋法(Tabu Search,TS),14,文獻探討-車輛途程問題(3/7)車輛途程問題之相關啟發式解法,文獻探討,-車輛途程問題(4/7),模擬退火法,是,否,是,否,15,文獻探討-車輛途程問題(4/7)模擬退火法是否是否15,文獻探討,-車輛途程問題(5/7),作者,方法,結果,Osman(1993),利用途程間單一個節點的交換改善法來對總途程做改善，並加入了禁忌搜尋法和模擬退火法的混合搜尋法,使改善的解能夠跳脫局部最佳解,Van Breedam(1995),String Relocation、String Exchange和String Mix三種途程間的改善法，再加入模擬退火法的機制來做改善,得到的解比單純用這三種改善法的結果來的較佳,16,文獻探討-車輛途程問題(5/7)作者方法結果Osman(19,文獻探討,-車輛途程問題(6/7),禁忌搜尋法,是,是,否,否,17,文獻探討-車輛途程問題(6/7)禁忌搜尋法是是否否17,文獻探討,-車輛途程問題(7/7),作者,方法,結果,Potvin等人(1996),以平插入的線求得起始解，再以Or-opt與2-opt*為核心的禁忌搜尋法求解VRPHTW,結果與Solomon例題進行比較，所有問題可明顯的改善，但平均求解時間過長。,18,文獻探討-車輛途程問題(7/7)作者方法結果Potvin等人,文獻探討,-車輛途程問題含時窗限制(1/2),車輛途程問題含時窗限制(Vehicle Routing Problem with Time Windows,VRPTW)，就是每個需求點都有不同送貨時間為限制，基本上可分為硬時窗和軟時窗兩種。,在硬時窗中，所找到的解一定要符合時間範圍內的限制，不然就是不可行解，可是在現實生活中，除非很特殊的情況，否則很少顧客會如此嚴格的要求。因此本研究探討較為符合現實生活的情況，也就是軟時窗限制。,19,文獻探討-車輛途程問題含時窗限制(1/2)車輛途程問題含時窗,文獻探討,-車輛途程問題含時窗限制(2/2),車輛途程問題含時窗限制之相關啟發式解法,作者,方法,結果,Fisher等人(1997),提出K-Tree Approach和拉氏鬆弛/變數分割方法,以Solomon例題去測試，可以求解到100個需求點至最佳解,Taillard等人(1997),以Tabu Search為主體，利用Cross exchange，和Cross exchange的兩個特例2-opt*以及Or-opt求解VRPSTW,結果與Solomon例題進行比較，可以獲得較佳的解,敖君瑋(1999),以Tabu Search為主體，利用最鄰近法、掃描法和節省法求得起始解，再利用途程內Swap、Or-opt，途程間Swap，Cross exchange以及2-opt*求解VRPSTW,結果與Solomon例題進行比較，結果以最鄰近解法所建構的起始解經改善後最佳,20,文獻探討-車輛途程問題含時窗限制(2/2)車輛途程問題含時窗,文獻探討,-車輛途程問題含回程取貨(1/3),傳統的車輛途程問題，若將需求點分成取貨和或兩種，且在完成送貨服務之後，開始進行取貨的服務，這就是車輛途程問題含回程取貨。,：,Depot,：Deliveries,：,Pickup,21,文獻探討-車輛途程問題含回程取貨(1/3)傳統的車輛途程問題,文獻探討,-車輛途程問題含回程取貨(2/3),車輛途程問題含回程取貨之相關啟發式解法,作者,方法,結果,Goetschalckx和Jacobs-Blecha(1989),提出一個啟發式解法，分成建構和改善兩個階段，建構部份是利用空間填滿取線求得起始解，改善部份則是利用數學模式中分解成子問題最佳的觀念，當作改善的基礎，再以貪心法(greedy method)和K-median兩個方法當做改善的依據,結果顯示貪心法和K-median的運送距離相等，但貪心法的車輛利用率較高，使用的車輛數較少。,Toth和Vigo(1997),提出數學規劃法求解，並利用拉氏鬆弛法得到一個有效的下限值,結果與Solomon例題進行比較，發現與最佳解誤差2.2%,22,文獻探討-車輛途程問題含回程取貨(2/3)車輛途程問題含回程,文獻探討,-車輛途程問題含回程取貨(3/3),作者,方法,結果,Duhamel等人(1997),利用禁忌搜尋法來求解VRPBTW，利用貪心插入法獲得起始解，接著在禁忌搜尋法裡，是先隨機選取2-opt*、Or-opt、swap三種交換改善法的其中一種來改善原來的可行解,結果與Solomon例題進行比較，並設定取貨的比率加以求解，有不錯的結果,23,文獻探討-車輛途程問題含回程取貨(3/3)作者方法結果Duh,文獻探討,-車輛途程問題含混合送貨和取貨(1/3),本問題對需求點的限制加以寬放，需求點可同時具有送貨和取貨的條件，並且未限制送貨和取貨的先後順序。,D P,D P,：,Both,D P,：,Depot,：Deliveries,：,Pickup,24,文獻探討-車輛途程問題含混合送貨和取貨(1/3)本問題對需求,文獻探討,-車輛途程問題含混合送貨和取貨(2/3),車輛途程問題含混合送貨和取貨之相關啟發式解法,作者,方法,結果,Min(1989),先將節點依地理鄰近度分群，然後再分派車輛到各分群中，轉換成TSP問題利用數學規劃法求解,能有效的節省行駛距離,Dethloff(2001),先分群再安排路線，接著在利用4種插入法，插入的準則分別為travel distance、residual capacity、radial surchar
展开阅读全文