臺灣人文及社會科學引文索引資料庫系統

:::

詳目顯示

回上一頁
第 1 筆 / 總合 1 筆   第一頁 上一頁 下一頁 最後一頁
/1頁
題名：應用時窗分割與整數化策略簡化時窗收卸貨問題之研究
書刊名：運輸學刊
作者：李泰琳／張靖 引用關係
作者(外文)：Li, Tai-lin／Chang, Ching
出版日期：2008
卷期：20:3
頁次：頁313-350
主題關鍵詞：時窗收卸貨問題；時窗分割策略；巨集啟發式演算法；Pickup and delivery problem with time windows；Time window partitioning strategy；Meta-heuristic algorithm
原始連結：連回原系統網址new window
相關次數：
  • 被引用次數被引用次數:期刊(2) 博士論文(0) 專書(0) 專書論文(0)
  • 排除自我引用排除自我引用:1
  • 共同引用共同引用:21
  • 點閱點閱:17
本研究利用時窗分割與整數化策略將時窗收卸貨問題(PDPTW)轉換為無時窗的近似PDP(SPDP)，即得以求解PDPTW時不用考慮時窗。在轉換過程中進一步提出問題規模精簡策略與關連式旅行網路結構表，大量減少轉換過程中所衍生出新的限制式與決策變數的數量。研究中利用Lau and Liang (2002)的方法，修改國際標準題庫VRPTW例題，產生具有相同最適解之PDPTW例題進行測試。本研究首先提出SPDP之數學規劃模式，利用小規模例題，透過LINGO來驗證，當時窗切割夠細的話，轉換所得之SPDP與原PDPTW之最適解是相同的，即求解時窗切割夠細的SPDP即可求得原PDPTW之最適解；其次利用較大規模問題，透過啟發式演算法來驗證，顯示求解SPDP較直接求解原PDPTW，其解的精確度平均提升7.88％，求解時間大幅減少達88.10％，因此本研究確定先將PDPTW轉換為SPDP求解較直接求解PDPTW，確實可以在較短的時間內求出品質較佳的近似最佳解。
The goal of this paper is to provide a new concept to solve a Pickup and Delivery Problem with Time Windows (PDPTW) efficiently and accurately. In order to achieve this goal, a PDPTW is transferred into a new Similar PDP (SPDP) without time window by adopting the Time Window Partitioning and Discretization Strategy.Every time window of each pickup or delivery point is partitioned as many equal-length sub time windows. Besides, only one of all sub time windows of the pickup or delivery point can be served. The SPDP is formulated as a 0-1 integer programming model in this paper. The optimal solution obtained by LINGO of the transferred SPDP is equal to the optimal solution of the original PDPTW when the time window is partitioned small enough, i.e. the SPDP is the same as PDPTW when the length of the sub time window is short enough. However, the size of the transferred SPDP is much bigger than the original PDPTW because a lot of new decision variables and constraints are produced. Since these additional derived decision variables and constraints make computation inefficient, we also design a preprocessing procedure to reduce problem size of the SPDP, e.g. the redundant decision variables and constraints, and a relation structured asymmetric travel cost matrix to avoid searching the infeasible solutions. There are 18 Solomon benchmark VRP problems transferred to PDPTW by using the method developed by Lau and Liang (2002). In order to show our contribution, we developed a simple Meta-Heuristic algorithm to solve both PDPTW and SPDP. According to the computation results, we can improve the accuracy by about 7.88% and save the computation time by about 88.1%.
期刊論文
1.Mitrovic-Minic, S.、Laporte, Gilbert(2004)。Waiting Strategies for the Dynamic Pickup and Delivery Problem with Time Windows。Transportation Research Part B: Methodological，38(7)，635-655。  new window
2.Dueck, G.、Scheuer, T.(1990)。Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing。Journal of Computational Physics，90(1)，161-175。  new window
3.Dumas, Y.、Desrosiers, J.、Soumis, F.(1991)。Pickup and Delivery Problem with Time Windows。European Journal of Operational Research，54(1)，7-22。  new window
4.Lu, Q.、Dessouky, M.(2004)。An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem。Transportation Science，38(4)，503-514。  new window
5.Nanry, W. P.、Barnes, J. W.(2000)。Solving the Pickup and Delivery Problem with Time Windows Using Reactive Tabu Search。Transportation Research Part B，34(2)，107-121。  new window
6.Psarafis, H.(1983)。An Exact Algorithm for the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem。Transportation Science，17(4)，351-361。  new window
7.Toussaint, K. J.、Golden, B. L.(1994)。Heuristics to Improve the Clarity of Base/Time Plots。Computers and Operations Research，21(5)，573-586。  new window
8.Psaraftis, Harilaos N.(1980)。A Dynamic Programming Solution to the Single Vehicle Many-to-many Immediate Request Dial-a-ride Problem。Transportation Science，14(2)，130-154。  new window
9.韓復華、王國琛(20020600)。巨集啟發式解法在求解大規模旅行推銷員問題之應用。運輸學刊，14(2)，1-14。new window  延伸查詢new window
10.韓復華、楊智凱(19960600)。門檻接受法在TSP問題上之應用。運輸計劃，25(2)，163-187。new window  延伸查詢new window
11.韓復華、楊智凱、卓裕仁(19970600)。應用門檻接受法求解車輛路線問題之研究。運輸計劃，26(2)，253-280。new window  延伸查詢new window
12.Savelsbergh, M. W. P.、Sol, M.(1995)。The General Pickup and Delivery Problem。Transportation Science，29(1)，17-29。  new window
13.Desrosiers, J.、Dumas, Y.、Solomon, M. M.、Sournis, E.(1995)。Time Constrained Routing and Scheduling。Operations Research and Management Science，8，35-139。  new window
14.Lau, H. C.、Liang, Z.(2002)。Pickup and Delivery with Time Windows - Algorithms and Test Case Generation。International Journal on Artificial Intelligence Tools，11(3)，455-472。  new window
15.Haibing, L.、Andrew, L.(2003)。A Metaheuristic for the Pickup and Delivery Problem with Time Windows。International Journal on Artificial Intelligence Tools，12(2)，173-186。  new window
16.Nagy, G.、Salhi, S.(2005)。Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Delivery。European Journal of Operational Research，162(4)，126-142。  new window
17.Sexton, T. R.、Bodin, L. D.(1985)。Optimizing Single Vehicle Many-to-many Dial-a-ride Problem with Desired Delivery Time: I Scheduling。Transportation Science，19(4)，378-410。  new window
18.Sexton, T. R.、Bodin, L. D.(1985)。Optimizing Single Vehicle Many-to-many Dial-a-ride Problem with Desired Delivery Time: II Routing。Transportation Science，19(4)，411-435。  new window
19.Graham, D.、Nuttle, H. L. W.(1986)。A Comparison of Heuristics for a School Bus Scheduling Problem。Transportation Research Part B，20(3)，175-182。  new window
20.Appelgren, L. H.(1969)。A Column Generation Algorithm for a Ship Scheduling Problem。Transportation Science，3(1)，53-68。  new window
21.Swersey, A.、Ballard, W.(1984)。Scheduling School Buses。Management Science，30(7)，844-853。  new window
22.Bent, R.、Van Hentenryck, P.(2006)。A Two-stage Hybrid Algorithm for Pickup and Delivery Vehicle Routing Problems with Time Windows。Computers and Operations Research，33(4)，875-893。  new window
23.Kolen, A. W. J.、Rinnooy Kan, A. G. H.、Trienekens, H. W. J. M.(1987)。Vehicle Routing with Time Windows。Operations Research，35(2)，266-273。  new window
24.Dror, M.(1994)。Note on the Complexity of the Shortest Path Models for Column Generations in the VRPTW。Operations Research，42(5)，977-978。  new window
25.Appelgren, L. H.(1971)。Integer Programming Methods for a Vessel Scheduling Problem。Transportation Science，5(1)，62-74。  new window
26.Levin, A.(1971)。Scheduling and Fleet Routing Methods for Transportation System。Transportation Science，5(3)，232-255。  new window
27.Penna, T. J. P.(1995)。Traveling Salesman Problem and Tsallis Statistics。Physical Review E，51(1)，1-3。  new window
會議論文
1.韓復華、王國琛(2000)。巨集啓發式解法在求解大規模旅行推銷員問題之研究。臺北：逢甲大學。195-204。  延伸查詢new window
2.Fabián, J.、Pérez, L.(2005)。A Meta-heuristic Applied for a Topologic Pickup and Delivery Problem with Time Windows Constraints。0。924-928。  new window
學位論文
1.Kohl, N.(1995)。Exact Methods for Time Constrained Routing and Related Scheduling Problems(博士論文)。Technical University of Denmark。  new window
2.楊智凱(1995)。以門檻接受法改善TSP及VRP路網成本之研究(碩士論文)。國立交通大學。  延伸查詢new window
3.劉佩玲(2006)。在考量資源限制下國際快遞業服務中心位置選擇，0。  延伸查詢new window
 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top
QR Code
QRCODE

臺灣人文及社會科學引文索引資料庫

目前上線人數：1191（臺灣：1189，外國：2） ／ 本年度總使用人次：2096089 ／ 訪客人次（自102年09月）：67895785
國家圖書館著作權聲明 Copyright © 2013 All rights reserved.
本館地址: 100201臺北市中山南路20號． 本館地圖及交通資訊．
總機：(02)23619132．最佳瀏覽解析度為1024x768以上