跳到主要內容

臺灣博碩士論文加值系統

(44.200.194.255) 您好!臺灣時間:2024/07/15 01:27
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:林信彥
研究生(外文):Hsin-Yen Lin
論文名稱:有時窗限制的收送貨問題之研究
論文名稱(外文):The Study of Pickup and Delivery Problem with Time Window Constraints
指導教授:王晉元王晉元引用關係
指導教授(外文):Jin-Yuan Wang
學位類別:碩士
校院名稱:國立交通大學
系所名稱:運輸科技與管理學系
學門:運輸服務學門
學類:運輸管理學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:36
中文關鍵詞:收送貨問題時窗限制時窗切割
外文關鍵詞:Pickup and Delivery ProblemTime Window ConstraintsTime Window Partitioning
相關次數:
  • 被引用被引用:1
  • 點閱點閱:202
  • 評分評分:
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
對於貨運業者來說,有效率且有效的車輛派遣有許多優點。首先,有效率的車輛派遣可以減少派遣所需的時間,使得人力資源可以有更充分的利用;而縮減車輛的旅行距離可以減少車輛的維修成本;另外,貨運業者可以因為較好的車輛利用率而去服務更多的顧客以增加利潤。因此,發展一個最佳化模式來協助貨運業者進行車輛派遣的決策是相當重要的。
本研究針對有時窗限制的收送貨問題構建了數學規劃的模式,並且針對非線性的時窗限制式做放鬆與緊縮,使得模式成為兩個線性的混合整數規劃(MIP)模型。放鬆時窗限制式使我們得到一個最佳解的下界,而緊縮時窗限制式可得到最佳解的上界(亦為一可行解),由於兩種模式都為線性規劃,因此可利用一般的數學規劃解題軟體來分別求解以得到上下界。另外,本研究亦使用切割時窗(Time Window Partitioning)的方式來縮減上界與下界之間的差距,當兩者收斂至重合時,代表已經獲得最佳解,然而切割時窗雖然會減小上下界的差距,也會增加問題的規模,因此使用切割時窗法必須在解的品質與求解時間當中做取捨。
本研究利用一個自行設計的小範例來驗證模式的正確性與合理性。此外,由於在文獻上並沒有發現適合本研究的標竿題庫,因此本研究擷取Solomon於1987年針對有時窗限制的車輛路線問題(VRPTW)所設計的題庫,做部分的修正來產生所需的測試範例,以用來觀察使用不同的切割時窗寬度時,問題規模成長以及上下界收斂的情形。測試結果顯示本研究的模式及所使用的求解方法適用於求解此問題。
It is important for cargo carriers to dispatch their vehicles efficiently and effectively. There are several advantages for efficient and effective dispatches. First, shortening the dispatching time could save the personnel expenses and make better human resources utilization. Secondly, shortening the travel distance of vehicles can reduce the operation and maintenance costs of vehicles. Moreover, the cargo carrier could serve more customers and increase their revenues due to higher utilization rate. Therefore, it is important to develop optimization models and algorithms for such decision making.
We construct an optimization model for pickup and delivery problem with time windows in this research. This model is based on the dispatching rule, and takes current operation status into account. We apply the over-constrained and under-constrained method to deal with the nonlinear time window constraint. The over-constrained method offer an upper bound (a feasible solution) while the under-constrained method provides a lower bound for the solution. In order to approximate the optimal solution, we use the time window partitioning method to narrow the gap between the upper bound and lower bound.
In addition, we use a small example to verify the accuracy and rationality of our model. We also generate our test instances from Solomon’s benchmark test samples for VRPTW to evaluate our solving method. The testing results show that our proposed model and solution techniques are suitable for solving this problem.
Content i
List of Tables ii
List of Figures iii
Chapter1 Introduction 1
1.1 Motivation 1
1.2 Objectives 1
1.3 Scope 2
1.4 Study Flowchart 3
Capter2 Literature Review 5
2.1 Review of Characteristics of Pickup and Delivery Problem with Time Windows 5
2.1.1 Transportation Requests 6
2.1.2 Time constraints 6
2.1.3 Objective Functions 7
2.2 Review of Solving Techniques for Pickup and Delivery Problem 8
2.2.1 The Static Pickup and Delivery Problem 8
2.2.2 The Dynamic Pickup and Delivery Problem 10
Chapter3 Model Building 12
3.1 Definitions and Assumptions 12
3.2 Problem Formulation 13
3.3 Modifications of the Model 15
3.3.1 Variable Redefinition 16
3.3.2 Over-constrained and Under-constrained Methods [15] 17
3.3.3 Time Window Partitioning [15] 19
Chapter4 Model Testing and Analysis 23
4.1 Accuracy and Rationality Analysis 23
4.2 Test Instance Generation 28
4.3 Performance Evaluation 30
4.3.1 Performance without Using Time Window Partitioning Method 30
4.3.2 Performance of Time Window Partitioning Method 31
Chapter5 Conclusions and Suggestions 35
5.1 Conclusions 35
5.2 Suggestions 35
References 37
References
1. Warren B. Powell, “Optimization models and algorithms: an emerging technology for the motor carrier industry,” IEEE Transactions on Vehicle Technology, vol. 40, No. 1, February 1991.
2. M.W.P Savelsbergh, “Local Search for Routing Problems with Time Windows”, Annals of Operations Research 4, 285-305, (1985).
3. J. Desrosiers (1995), “Time Constrained Routing and Scheduling,” Chapter 2 in M.Ball, T.Magnanti, C.Monma and G..Nemhauser (eds.), Network Routing, Hand Books in Operations Research and Management Science Volume 8, pp.102-116.
4. M. Solomon, “The general Pickup and Delivery problem,” Transportation Science, No. 1, February 1995.
5. F. H. Cullen, J. J. Jarvis and H. D. Ratliff, “Set partitioning based heuristics for interactive routing,” Networks 11, 125-143 (1981).
6. Y. Dumas, J. Desrosiers and F. Soumis, “The pickup and delivery problem with time windows,” European Journal of Operational Research, 54, 7-22(1991).
7. Haibing Li and Andrew Lim, “A metaheuristic for the pickup and delivery problem with time windows”, 13th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'01) , November 2001.
8. William P. Nanry and J. Wesley Barnes, “Solving the pickup and delivery problem with time windows using reactive tabu search,” Transportation Research Part B, 34(2000) 107-121.
9. H. Psaraftis, “A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem,” Transportation Science, 14, 130-154(1980).
10. H. Psaraftis, “Dynamic vehicle problems,” in Vehicle Routing: Methods and Studies, B. L. Golden and A. A. Assad (eds), North-Holland, Amsterdam, 1988.
11. L. F. Frantzeskakis and W. B. Powell, “A successive linear approximation procedure for for stochastic, dynamic vehicle allocation problems,” Transportation Science, 20B, 243-257(1990)
12. Hoong Chuin Lau and Zhe Liang, “Pickup and delivery with time windows: algorithms and test case generation,” 13th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'01) , November 2001.
13. Stefan Irnich, “A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles,” European Journal of Operational Research, 122(2000) 310-328.
14. H. Onal, B. M. Jaramillo and M. A. Mazzocco, ”Two formulations of the vehicle routing problem: an empirical application and computational experience,” Logistics and Transportation Review, January 1996.
15. Xiubin Wang and Amelia C. Regan, “Local truck load pickup and delivery with hard time window constraints,” Transportation Research Part B, 36(2002) 97-112.
16. M.M.Solomon, “Algorithms for the vehicle routing and scheduling problem with time window constraints”, Operations Research, 41, 469-488, (1987).
電子全文 電子全文(限國圖所屬電腦使用)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top