車輛途程規劃暨生產配送整合課題探討

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：22

、訪客IP：3.145.175.243

姓名

薛哲夫(Che-Fu Hsueh) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

車輛途程規劃暨生產配送整合課題探討
(Vehicle Routing Problems and the Issues of Integrating Production and Distribution)

相關論文

★ 圖書館系統通閱移送書籍之車輛途程問題	★ 起迄對旅行時間目標下高速公路匝道儀控之研究
★ 結合限制規劃法與螞蟻演算法求解運動排程問題	★ 共同邊界資料包絡分析法在運輸業之應用-以國內航線之經營效率為例
★ 雙北市公車乘客知覺服務品質、知覺價值、滿意度、行為意向路線與乘客之跨層次中介效果與調節式中介效果	★ Investigating the influential factors of public bicycle system and cyclist heterogeneity
★ A Mixed Integer Programming Formulation for the Three-Dimensional Unit Load Device Packing Problem	★ 高速公路旅行時間預測之研究--函數資料分析之應用
★ Behavior Intention and its Influential Factors for Motorcycle Express Service	★ Inferring transportation modes (bus or vehicle) from mobile phone data using support vector machine and deep neural network.
★ 混合羅吉特模型於運具選擇之應用-以中央大學到桃園高鐵站為例	★ Preprocessing of mobile phone signal data for vehicle mode identification using map-matching technique
★ 含額外限制式動態用路人均衡模型之研究	★ 動態起迄旅次矩陣推估模型之研究
★ 動態號誌時制控制模型求解演算法之研究	★ 不同決策變數下動態用路人均衡路徑選擇模型之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

車輛途程規劃問題一直是學術研究及實務界很感興趣且實際遭遇的課題。然而在現實生活中，存在許多不確定性、浮動變化的因素，若在規劃車輛途程時不加以考量，將造成車輛途程規劃與實際操作上的落差，導致成本的提高甚至規劃結果無法執行。這些不確定性、浮動變化因素包括如需求是否會產生、需求量多寡、旅行時間的變化、貨物品質是否會腐敗等。
本研究分成三部份來探討與含時窗限制車輛途程規劃相關的課題，並建立完整的數學模式及演算法進行測試。第一部份探討在顧客需求及旅行時間均可能無預警地產生變化時，如何建立一套即時性、線上反應的車輛派遣導引系統，以充份利用即時最新的交通及顧客需求資訊來重新規劃車輛途程。在該模式中，除了考量即時性的旅行時間及顧客需求資訊外，亦將可預測的旅行時間變化以依時性的函數型式同時納入模式考量。
第二部份則將旅行時間的不確定性以隨機變數的方式納入模式考量，進行行前的路線最佳化求解。在過去的研究中，將旅行時間的隨機性納入車輛途程規劃的文獻並不多見。本模式係一隨機規劃(stochastic programming)模式，並證明目標式具有下限，透過不斷提高下限以求得最佳解。本研究所發展之演算法除可求得真正解外，並有效排除抵達時間受上游所有路段旅行時間隨機性累積影響之問題。
第三部份探討易腐性商品的生產排程與運送路線之整合規劃。由於易腐性商品在生產後到交付顧客為止其品質均持續衰退，進而減少其實際收益，故進行生產排程時即應考量到運送路線所需的運送時間及其貨物所需的生產時間，綜合考量後才能減少品質耗損程度並追求生產者的最大利潤。

摘要(英)

The vehicle routing problem has been and remains a rich topic for researchers and practitioners. In the real world, however, there exist many uncertain or constantly varying factors, which affect the operation of vehicle routing plan and result in the higher cost or failure. These factors may include occurrence of customer, quantity of demand, travel time, deterioration of commodities, etc.
This thesis explores the extensional issues of vehicle routing problem with time windows in three parts. In the first part, the demand of customers and travel times may vary unexpectedly and a real-time, on-line operational vehicle dispatching and guiding system is established, taking the latest information of demand and traffic condition into account. The predictable travel time pattern is also considered as a time-dependent function in this model.
In the second part, the travel time is considered as a random variable and the optimal routes are found in the pre-trip planning. The researches considering the stochasticity of travel time are relatively rare in the past. In this part a stochastic programming model is established, and the objective is proved to have a lower bound. An optimal solution can be found by raising the lower bound. In addition, the stochasticity of the arrival time at a customer will not be affected by the accumulative stochasticity of all previous link travel time in this model.
The third part consists of integration of production scheduling and distribution for perishable goods. The perishable goods deteriorate as soon as they were produced and keep decaying when being delivered, resulting in deduction of revenue. The vehicle route as well as its delivery time and the production time should be considered in the phase of production scheduling, in order to reduce the deterioration and increase the profit.

關鍵字(中)

★ 即時
★ 隨機
★ 旅行時間
★ 車輛途程規劃
★ 生產排程

關鍵字(英)

★ stochastic
★ travel time
★ vehicle routing
★ real time
★ production scheduling

論文目次

摘要 I
Abstract II
Acknowledgement III
Table of Contents IV
List of Tables VII
List of Figures VIII
Chapter 1 Introduction 1
1.1 Research Motivation 1
1.2 Research Purposes and Methods 1
1.3 An Overview of this Dissertation 2
Chapter 2 The Real-Time Time-Dependent Vehicle Routing Problem With Time
Windows 5
2.1 Introduction 5
2.2 Literature Review 6
2.2.1 Dynamic Vehicle Routing Problem 6
2.2.2 Real-Time Vehicle Routing Problem 6
2.2.3 Time-Dependent Vehicle Routing Problem 7
2.3 Model Formulation 7
2.3.1 Problem Description 7
2.3.2 Notations 10
2.3.3 Mathematical Model 11
2.3.4 Time-Space Network 15
2.4 Solution Algorithm 16
2.4.1 Calculation of Insertion Cost and Choice of Departure Time 17
2.4.2 Unified Framework of Solution Procedure 21
2.4.3 Method for Route Construction 22
2.5 Computational Results 27
2.5.1 Test Problem Set 27
2.5.2 Test Results 28
2.5.3 Real Application 33
2.6 Remarks 38
Chapter 3 The Vehicle Routing Problem with Stochastic Travel Times and Time
Windows 39
3.1 Introduction 39
3.2 Literature Review 39
3.3 Model Formulation 41
3.3.1 Notations 42
3.3.2 Mathematical Models 44
3.4 Solution Algorithm 47
3.4.1 Framework of Solution Procedure 47
3.4.2 Lower Bounds of 52
3.4.3 Proof of Lower Bounds of 58
3.4.4 Proof of Convergence of the Proposed Algorithm 68
3.5 Computational Results 69
3.5.1 Input Data 69
3.5.2 Testing Results 70
3.5.3 Sensitivity Analysis of Vehicle Fleet Size 73
3.5.4 Improvement of Computational Efficiency by Adding Hard Time
Window Constraints 74
3.5.5 Number of Discrete States of Stochastic Travel Time versus
Computational Time 74
3.6 Remarks 75
Chapter 4 The Production Scheduling and Vehicle Routing Problem for Perishable
Goods 76
4.1 Introduction 76
4.2 Literature Review 77
4.3 Model Formulation 78
4.3.1 Problem Description 78
4.3.2 Notations 79
4.3.3 Mathematical Model 80
4.4 Solution Algorithm 83
4.4.1 Solving Production Scheduling Problem (Upper Level Model) 84
4.4.2 Solving Vehicle Routing Problem with Time Windows (Lower Level Model) 88
4.4.3 Enhancing the Algorithm 89
4.5 Computational Results 91
4.5.1 Numerical Examples 91
4.5.2 Sensitivity Analysis 91
4.6 Remarks 93
Chapter 5 Conclusions and Suggestions 94
5.1 Conclusions 94
5.2 Suggestions 96
References 97

參考文獻

1. Abad, P.L., 1996, Optimal Pricing and Lot-sizing under Conditions of Perishability and Partial Backordering, Management Science 42, 1093-1104.
2. Arbib, C., Pacciarelli, D. and Smriglio, S., 1999, A Three-dimensional Matching Model for Perishable Production Scheduling, Discrete Applied Mathematics 92, 1-15.
3. Bastian, C. and Rinnooy Kan, A.H.G., 1992, The Stochastic Vehicle Routing Problem Revisited, European Journal of Operational Research 56, 407-412.
4. Bertsimas, D. and Ryzin, G.V., 1991, A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane, Operations Research 39, 601-615.
5. Bertsimas, D. and Ryzin, G.V., 1993, Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated Vehicles, Operations Research 41, 60-76.
6. Bertsimas, D. and Simchi-Levi, D., 1996, A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty, Operations Research 44, 286-303.
7. Birge, J.R. and Louveaux, F., 1997, Introduction to Stochastic Programming. Springer-Verlag, New York.
8. Bräysy O. and Gendreau M., 2005a, Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. Transportation Science, 39, 104–118.
9. Bräysy O. and Gendreau M., 2005b, Vehicle Routing Problem with Time Windows, Part II: Metaheuristics. Transportation Science, 39, 119–139.
10. Carraway, R.L., Morin, T.L. and Moskowitz, H., 1989, Generalized Dynamic Programming for Stochastic Combinatorial Optimization, Operation. Research 37, 819-829.
11. Chang, M.S., Chen, S.R. and Hsueh, C.F., 2003, Real-Time Vehicle Routing Problem with Time Windows and Simultaneous Delivery/Pickup Demands, Journal of the Eastern Asia Society for Transportation Studies 5, 2273-2286.
12. Chang, Y.C. and Lee, C.Y., 2004, Machine Scheduling with Job Delivery Coordination, European Journal of Operational Research 158, 470-487.
13. Cheng, T.C.E., Gordon, V.S. and Kovalyov, M.Y., 1996, Single Machine Scheduling with Batch Deliveries, European Journal of Operational Research 94, 277-283.
14. Cheng, T.C.E., Kovalyov, M.Y. and Lin, B.M.T., 1997, Single Machine Scheduling to Minimize Batch Delivery and Job Earliness Penalties, SIAM Journal on Optimization 7, 547-559.
15. Chen, H.K., Hsueh C.F. and Chang, M.S., 2002, An Efficient Algorithm for the Time-Dependent Vehicle Routing Problem with Time-Windows, The International Conference on Intercity Transportation, Beijing, China, Nov 5-7, 370-379.
16. Clarke, G., and Wright, J.W., 1964, Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operation Research 12, 568-581.
17. Dror, M., and Trudeau, P., 1986, Stochastic Vehicle Routing with Modified Savings Algorithm, European Journal of Operational Research 23, 228-235.
18. Fox, K.R., Gavish, B. and Graves, S.C., 1980, An N-Constraint Formulation of the Time-Dependent Traveling Salesman Problem, Operations Research 28, 1018-1021.
19. García, J.M., Sánchez, Lozano S., Guerrero F, Calle M. and Smith, K., 2001, Production and Vehicle Scheduling for Ready-Mix Operations, Proceedings of the 29th International Conference on Computers and Industrial Engineering, 70-76, Montreal, Canada. (http://Www.umoncton.ca/CIE/Conferences/Index.htm)
20. Gendreau, M., Guertin, F., Potvin, J.Y. and Taillard, E., 1999, Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching, Transportation Science 33, 381-390.
21. Gendreau, M., Laporte, G., and Séguin, R., 1996, Stochastic Vehicle Routing, European Journal of Operational Research 88, 3-12.
22. Gendreau, M. and Potvin, J.Y., 1998, Fleet Management and Logistics, Kluwer Academic Publishers, 115-126.
23. Hoogeveen, J.A. and Vestjens, A.P.A., 2000, A Best Possible Deterministic On-line Algorithm for Minimizing Maximum Delivery Time on a Single machine, SIAM Journal on Discrete mathematics 13, 56-63.
24. Lee, C.Y. and Chen, Z.L., 2001, Machine Scheduling with Transportation Considerations, Journal of Scheduling 4, 3-24.
25. Li, C.L., Vairaktarakis, G. and Lee, C.Y., 2005, Machine Scheduling with Deliveries to Multiple Customer Locations, European Journal of Operational Research 164, 39-51.
26. ILOG CPLEX, 2001, ILOG CPLEX 7.1 User’s Manual, ILOG S.A, Gentilly, France.
27. Kao, E.P.C., 1978, A Preference Order Dynamic Program for a Stochastic Traveling Salesman Problem, Operational Research 26, 1033-1045.
28. Kenyon, A.S. and Morton, D.P., 2003, Stochastic Vehicle Routing with Random Travel Times, Transportation Science 37, 69-82.
29. Lambert, V., Laporte, G. and Louveaux, F., 1993, Designing Collection Routes through Bank Branches, Computer and Operation Research 20, 793-791.
30. Laporte, G. and Louveaux, F., 1990, Formulations and Bounds for the Stochastic Capacitated Vehicle Routing Problem with Uncertain Supplies, Economic Decision Making: Games, Econometrics and Optimization (eds. By Gabzewicz, J., Richard ,J.-F., and Wolsey, L.), North Holland, Amsterdam, The Netherlands, 443-455.
31. Laporte, G. and Louveaux, F., 1993, The Integer L-Shaped Method for Stochastic Integer Programs with Complete Recourse, Operation Research Letter 13, 133-142.
32. Laporte, G., Louveaux, F. and Mercure, H., 1989, Models and Exact Solutions for a Class of Stochastic Location-Routing Problems, European Journal of Operational Research 39, 71-78.
33. Laporte, G., Louveaux, F. and Mercure, H., 1992, The Vehicle Routing Problem with Stochastic Travel Times, Transportation Science 26, 161-170.
34. Larsen A., 2001, The Dynamic Vehicle Routing Problem, Ph.D. Thesis, Technical University of Denmark, Denmark.
35. LINGO, 2004, LINGO user’s guide, LINDO Systems Inc., Chicago.
36. Liu, C.W., 2000, Study on Time Dependent Vehicle Route Problem with Time Window, Ph.D. Thesis, National Central University, Taiwan. (In Chinese)
37. Lucena, A., 1990, Time-Dependent Traveling Salesman Problem – The Deliveryman Case, Networks 20, 753-763.
38. Malandraki, C. and Daskin, M.S., 1992, Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms, Transportation Science 26, 185-200.
39. Malandraki, C. and Dial, R.B., 1996, A Restricted Dynamic Programming Heuristic Algorithm for the Time Dependent Traveling Salesman Problem. European Journal of Operational Research 90, 45-55.
40. Nelder, J.A. and Mead, R., 1965, A Simplex for Function Minimization, Computer Journal 7, 308–313.
41. Or, I., 1976, Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Blood Banking, Ph.D. Thesis, Northwestern University, Evanston, IL. USA.
42. Picard, J.C. and Queyranne, M., 1978, The Time-Dependent Traveling Salesman Problem and Its Applications to the Tardiness Problem in One-Machine Scheduling, Operations Research 26, 86-110.
43. Powell, W.B., 1996, A Stochastic Formulation of the Dynamic Assignment Problem, with an Application to Truckload Motor Carriers, Transportation Science 30, 195-219.
44. Powell, W.B., Jaillet, P. and Odoni, A., 1995, Stochastic and Dynamic Network and Routing, Handbooks in Operations Research and Management Science 8, 141-295.
45. Psaraftis, H.N., 1995, Dynamic Vehicle Routing: Status and Prospects, Annuals of Operations Research 61, 143-164.
46. Pasternack, B.A., 1985, Optimal Pricing and Return Policies for Perishable Commodities, Marketing Science 4, 166-176.
47. Raafat, F., 1991, Survey of Literature on Continuously Deterioration Inventory Models, Journal of Operational Research Society 42, 27-37.
48. Sana, S. and Chaudhuri, K.S., 2004, On a Volume Flexible Production Policy for a Deteriorating Item with Time-Dependent Demand and Shortages, Advanced Modeling and Optimization 6, 57-74.
49. Shieh, H.M. and May, M.D., 1998, On-Line Vehicle Routing with Time Windows: Optimization-Based Heuristics Approach for Freight Demands Requested in Real-Time, Transportation Research Record 1617, 171-178.
50. Sniedovich, M., 1981, Analysis of a Preference Order Traveling Salesman Problem, Operation Research 29, 1234-1237.
51. Solomon, M.M., 1987, Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows Constraints, Operations Research 35, 254-265.
52. Stewart, W.R. and Golden, B.L., 1983, Stochastic Vehicle Routing: a Comprehensive Approach, European Journal of Operational Research 14, 371-385.
53. Teng J.T. and Ouyang, L.Y., 2005, An EOQ Model for Deteriorating Items with Power-Form Stock-Dependent Demand, Information and Management Sciences 16, 1-16.
54. Zdrzalka, S. 1995, Analysis of Approximation Algorithms for Single-Machine Scheduling with Delivery Times and Sequence Independent Batch Setup Times. European Journal of Operational Research 80, 371-380.

指導教授

陳惠國(Huey-Kuo Chen)

審核日期

2005-7-1

推文