研究生: |
陳宛吟 Wan-yin Chen |
---|---|
論文名稱: |
以混合塔布搜尋法求解變動週期車輛途程問題 A hybrid tabu search algorithm for the variable periodic vehicle routing problem |
指導教授: |
廖慶榮
Ching-Jong Liao |
口試委員: |
郭人介
Ren-Jieh Kuo 鄭元杰 Yuan-Jye Tseng |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2013 |
畢業學年度: | 101 |
語文別: | 英文 |
論文頁數: | 52 |
中文關鍵詞: | 精實生產 、週期車輛途程問題 、裝載成本 、混合塔布搜尋法 |
外文關鍵詞: | Lean production, Periodic vehicle routing problem, Loading cost, Hybrid tabu search |
相關次數: | 點閱:197 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
汽車製造廠的物流配送系統,多以特定週期指派車輛的方式,將零件運回廠內進行組裝為主,然而汽車業本身是以精實生產的方式製造產品,其中零件配送的收貨物流方式是推行精實生產的關鍵。在實務上,載貨數量會隨著週期時間改變而改變。因此在本篇論文中,我們將討論變動週期車輛途程問題且設計兩個決策進行求解。首先,設計車輛收貨路徑來取得運輸時間,接著安排每個零件的收貨週期頻率及數量。藉由決定收貨路徑達到一天總運輸成本最小化之目標。而總運輸成本考量包括了距離成本、裝載成本、調度成本及運送頻率成本。由於此問題為週期車輛途程問題的一個特例,我們發展初始解演算法及混合塔布搜尋法 (hybrid tabu search, HTS)。混合塔布搜尋法具有從鄰域解中隨機選取十個可行解、考慮所有可行解、多樣化策略、強化策略、交換機制與塔步搜尋法 (tabu search, TS) 的結合等特性。實驗結果證明,我們發展的初始解演算法及混合塔布搜尋法對問題改善成效明顯優於現行汽車組裝廠使用的調度方法。
In general, the distribution for the auto parts manufacturer in the real-life system must pick-up raw materials periodically by vehicles. However, the idea of lean production is applied in the production of the auto parts manufacturer. The key of raw materials distribution is to implement lean production. The quantity of cargo will be changed as a vehicle transport cycle time changes. Therefore, the objective of the variable periodic vehicle routing problem (VPVRP) is to minimize the total transportation cost in this thesis. There are two decisions must be design to solve this problem. First, the daily routes have to be designed to obtain the transport times. Then, the pick-up cycle time and the quantity of each raw material have to assign in the planning horizon. The objective of the problem is to determine pick-up routes so as to minimize the total transportation cost in one day. The transportation cost includes distance cost, loading cost, dispatching cost, and frequency cost. Since the problem is a special case of the periodic vehicle routing problem (PVRP), we develop initial algorithms and the hybrid tabu search (HTS) for solving the problem. There are several distinctive features in the HTS, including randomly generating ten feasible solutions in a neighborhood, considering all feasible solutions in a neighborhood, the intensification strategy, the diversification strategy, and combination of tabu search (TS) with the switch mechanism. The computational results show that the proposed initial algorithms and the HTS outperform the current scheduling method used by the case plant with a significant improvement.
Alegre, J., Laguna, M., and Pacheco, J. (2007). Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts. European Journal of Operational Research, 179,736-746.
Alinaghian, M., Ghazanfari, M., Salamatbakhsh, A. and Norouzi, N. (2011). A new competitive approach on multi-objective periodic vehicle routing problem. International Journal of Applied Operational Research, 1,33-43.
Alonso, F., Alvarez, M. J., and Beasley, J. E. (2007). A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions. Journal of the Operational Research Society, 59, 969-976.
Al-Turki, U., Fedjki, C. and Andijani, A. (2001). Tabu search for a class of single-machine scheduling problems. Computers & Operations Research, 28, 1223-1230.
Angelelli, E. and S peranza, M. G. (2002). The periodic vehicle routing problem with intermediate facilities. European Journal of Operational Research, 137, 233-247.
Baptista, S., Oliveira, R. C. and Zuquete, E. (2002). A period vehicle routing case study. European Journal of Operational Research, 139, 220-229.
Beltrami, E. J. and Bodin, L. D. (1974). Networks and vehicle routing for municipal waste collection. Networks, 4, 65-74.
Blakeley, F., Bozkaya, B., Cao, B., Hall, W. and Knolmajer, J. (2003). Optimizing periodic maintenance operations for schindler elevator corporation. Interfaces, 33, 67-79.
Bouthillier, A. L. and Crainic, T. G. (2005). A cooperative parallel meta-heuristic for the vehicle routing problem with time windows. Computers & Operations Research, 32, 1685-1708.
Cacchiania, V., Hemmelmayrb, V. C. and Tricoireb, F. (2012). A set-covering based heuristic algorithm for the periodic vehicle routing problem. Discrete Applied Mathematics, article in press.
Chao, I. M., Golden, B. L. and Wasil, E. A. (1995). A new heuristic for the period traveling salesman problem. Computers & Operations Research, 22, 553-565.
Christofides, N. and Beasley, J. E. (1984). The period routing problem. Networks, 14, 237-256.
Coene, S., Arnout, A. and Spieksma, F. (2010). On a periodic vehicle routing problem. Journal of the Operational Research Society, 61, 1719-1728.
Cordeau, J. F. and Maischberger, M. (2012). A parallel iterated tabu search heuristic for vehicle routing problems. Computers & Operations Research, 39, 2033-2050.
Cordeau, J. F., Gendreau, M. and Laporte, G. (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30, 105-119.
Crainic, T. G., Toulouse, M. and Farvolden, J. M. (1996). Simplex-based Tabu Search for the Multicommodity Capacitated Fixed Charge Network Design Problem, Vol. 96, No. 7,Universite de Montreal, Centre for Research Transportation.
Dror, M. and Ball, M. (1987). Inventory routing: reduction from an annual to a short‐period problem. Naval Research Logistics (NRL), 34, 891-905.
Drummond, L. M. A., Ochi, L. S. and Vianna, D. S. (2001). An asynchronous parallel metaheuristic for the period vehicle routing problem. Future Generation Computer Systems, 17, 379-386.
Gaudioso, M. and Paletta, G. (1992). A heuristic for the periodic vehicle routing problem. Transportation Science, 26, 86-92.
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.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13, 533-549.
Golden, B. L. and Wasil, E. A. (1987). Operations research practice—computerized vehicle routing in the Soft Drink Industry. Operations Research, 35, 6-17.
Goncalves, L. B., Ochi, L. S. and Martins, S. L. (2005, November). A grasp with adaptive memory for a period vehicle routing problem. Computational Intelligence for Modelling, Control and Automation, 2005 and International Conference on Intelligent Agents, Web Technologies and Internet Commerce, International Conference on IEEE, 1, 721-727.
Hadjiconstantinou, E. and Baldacci, R. (1998). A multi-depot period vehicle routing problem arising in the utilities sector. Journal of the Operational Research Society, 49, 1239-1248.
Hemmelmayr, V., Doerner, K. and Hartl, R. (2009). A variable neighborhood search heuristic for periodic routing problems. European Journal of Operational Research, 195, 791-802.
Hemmelmayr, V., Doerner, K. F., Hartl, R. F. and Rath, S. (2011). A heuristic solution method for node routing based solid waste collection problems. Journal of Heuristics, 19, 129-156.
Laguna, M., Marti, R. and Campos, V. (1998), Intensification and diversification with elite tabu search solutions for the linear ordering problem. Computers and Operations Research, 26, 1217-1230.
Liaw, C. F. (2003). An efficient tabu search approach for the two-machine preemptive open shop scheduling problem. Computers & Operations Research, 30, 2081-2095.
Maya, P., Sorensen, K. and Goos, P. (2012). A metaheuristic for a teaching assistant assignment-routing problem. Computers & Operations Research, 39, 249-258.
Mitchell, M. (1999). An introduction to genetic algorithms, Fifth Edition, Massachusetts Institute of Technology, England.
Pirkwieser, S. and Raidl, G. (2010). Multilevel variable neighborhood search for periodic routing problems. Evolutionary Computation in Combinatorial Optimization, Lecture Notes in Computer Science, 6022, 226-238.
Russel, R. A. and Gribbin, D. (1991). A multiphase approach to the period routing problem. Networks, 21, 747-765.
Russell, R. A. and Igo, W. (1979). An assignment routing problem. Networks, 9, 1-17.
Skorin-Kapov, J. (1990). Tabu search applied to the quadratic assignment problem. ORSA Journal on Computing, 2, 33-45.
Tan, C. C. R. and Beasley, J. E. (1984). A heuristic algorithm for the periodic vehicle routing problem. Omega, 12, 497-504.
Tang, J., Zhang, J. and Pan, Z. (2010). A scatter search algorithm for solving vehicle routing problem with loading cost. European Journal of Operational Research, 37, 4073-4083.
Vahed, A. R., Crainic, T. G., Gendreau, M. and Rei, W. (2012). Fleet-Sizing for Multi-Depot and Periodic Vehicle Routing Problems Using a Modular Heuristic Algorithm, 51, 1-27.