簡易檢索 / 詳目顯示

回結果列表
研究生： 林韵函
Yun-han Lin
論文名稱： 以粒子群最佳化演算法求解具時間窗之開放式車輛途程問題
A particle swarm optimization for the open vehicle routing problem with time windows
指導教授： 喻奉天
Vincent F. Yu
口試委員: 郭人介
Ren-Jieh Kuo
林詩偉
Shih-Wei Lin
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2012
畢業學年度： 100
語文別： 英文
論文頁數： 60
中文關鍵詞： 粒子群最佳化演算法 、具時間窗之開放式車輛途程問題 、具時間窗之車輛途程問題 、車輛途程問題
外文關鍵詞： Open Vehicle Routing Problem with Time windows, Vehicle Routing Problem with Time Windows, Vehicle Routing Problem, Particle Swarm Optimization
相關次數： 點閱：277  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  •  上一筆

    • This research considers the open vehicle routing problem with time windows (OVRPTW), a new variant of the well-known vehicle routing problem (VRP) and an extension of the vehicle routing problem with time windows (VRPTW). The objective of this study is to describe the problem and develop an effective algorithm for solving the problem. VPR as well as VRPTW belong to the class of NP-hard problem. When the problem scale gets larger, the difficulty and time for finding an optimum solution also increase. Therefore, heuristic algorithms are often developed for solving VRP and VRPTW problems. The OVRPTW in this study is also an NP-hard problem. Thus the goal of this study aims at developing a heuristic algorithm to solve OVRPTW.
    The results of computational study show that the proposed algorithm is effective in solving the OVRPTW within a reasonable amount of time. The obtained solutions reduce travel distance while using more vehicles. However, this increase in vehicle use is still acceptable. This study indicates that it is possible to reduce the operating costs of third party logistics (3PL) companies while satisfying the rigid constraints from customers and logistics operations.

    ABSTRACT I ACKNOWLEDGE II CONTENTS III LIST OF TABLES V LIST OF FIGURES VI CHAPTER 1 INTRODUCTION 1 1.1 Research background and motivation 1 1.2 Purpose of research 2 1.3 Research scopes and constraints 2 1.4 Research framework 3 CHAPTER 2 LITERATURE REVIEW 5 2.1. Vehicle routing problem 5 2.2. Open vehicle routing problem with time windows (OVRPTW) 6 2.3. Meta-heuristics 7 CHAPTER 3 OPEN VEHICLE ROUTING PROBLEM WITH TIME WINDOWS 11 3.1 Problem definition 11 3.2 Mathematical model 12 CHAPTER 4 SOLUTION METHODOLOGY 17 4.1 PSO framework 17 4.2 Initialize 19 4.3 Iteration procedure 19 4.3.1 Route decoding method 20 4.3.1.1 Decode continuous value to discrete nodes 21 4.3.2 Route construction 24 4.4 Neighborhood improvement 26 4.5 Thorough local search 29 CHAPTER 5 COMPUTATIONAL STUDY 30 5.1 Benchmark instances 30 5.2 Parameter setting 30 5.3 Computational results 32 CHAPTER 6 CONCLUSION AND FUTURE RESEARCH 36 6.1 Conclusion 36 6.2 Future Research 36 REFERENCES 39 APPENDIX 43

    Ai, T. J. and V. Kachitvichyanukul (2009). A particle swarm optimisation for vehicle routing problem with time windows. International Journal of Operational Research,6(4),519-537.
    Akjiratikarl, C., P. Yenradee and P. R. Drake (2007). PSO-based algorithm for home care worker scheduling in the UK. Computers & Industrial Engineering,53(4),559-583.
    Aksen, D., Z. zyurt and N. Aras (2006). Open vehicle routing problem with driver nodes and time deadlines. Journal of the Operational Research Society,58(9),1223-1234.
    Bell, J. E. and P. R. McMullen (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics,18(1),41-48.
    Bent, R. and P. Van Hentenryck (2004). A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science,38(4),515-530.
    Braysy, O., W. Dullaert and M. Gendreau (2004). Evolutionary algorithms for the vehicle routing problem with time windows. Journal of Heuristics,10(6),587-611.
    Bullnheimer, B., R. F. Hartl and C. Strauss (1999). An improved ant System algorithm for thevehicle Routing Problem. Annals of Operations Research,89,319-328.
    Christofides, N., A. Mingozzi and P. Toth (1979). The vehicle routing problem. Combinatorial optimization,11,315-338.
    Cordeau, J. F., G. Desaulniers, J. Desrosiers, M. M. Solomon and F. Soumis (2002). VRP with time windows. The vehicle routing problem,9,157-193.
    Desrochers, M., J. Desrosiers and M. Solomon (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research,342-354.
    Desrochers, M., J. K. Lenstra, M. W. P. Savelsbergh and F. Soumis (1988). Vehicle Routing with Time Windows: Optimization and Approximation. Vehicle Routing: Methods and Studies. B. L. Golden and A. A. Assad. Amsterdam, North-Holland: 65-84.
    Desrosiers, J., Y. Dumas, M. M. Solomon and F. Soumis (1995). Time constrained routing and scheduling. Handbooks in operations research and management science,8,35-139.
    Donati, A. V., R. Montemanni, N. Casagrande, A. E. Rizzoli and L. M. Gambardella (2008). Time dependent vehicle routing problem with a multi ant colony system. European Journal of Operational Research,185(3),1174-1191.
    Dorigo, M. and C. Blum (2005). Ant colony optimization theory: A survey. Theoretical Computer Science,344(2-3),243-278.
    Fleszar, K., I. H. Osman and K. S. Hindi (2009). A variable neighbourhood search algorithm for the open vehicle routing problem. European Journal of Operational Research,195(3),803-809.
    Fu, Z., R. Eglese and L. Y. O. Li (2005). A new tabu search heuristic for the open vehicle routing problem. Journal of the Operational Research Society,267-274.
    Gambardella, L. M., Taillard and G. Agazzi (1999). Macs-vrptw: A multiple colony system for vehicle routing problems with time windows. New Ideas in Optimization, McGraw-Hill: 63-76.
    Ge, H., T. Zhen, Y. Jiang and Y. Che (2010). An Intelligent Solution for Open Vehicle Routing Problem in Grain Logistics. Advances in Wireless Networks and Information Systems,389-396.
    Gong, Y.-J., et al. (2012). Optimizing the Vehicle Routing Problem With Time Windows: A Discrete Particle Swarm Optimization Approach. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on,42(2),254-267.
    Kant, G., M. Jacks and C. Aantjes (2008). Coca-Cola enterprises optimizes vehicle routes for efficient product delivery. Interfaces,38(1),40.
    Kennedy, J. and R. Eberhart (1995). Particle swarm optimization, IEEE. 4: 1942-1948 vol. 1944.
    Kennedy, J. and R. Eberhart (1995). Particle swarm optimization. Neural Networks, 1995. Proceedings., IEEE International Conference on. 4: 1942-1948 vol.1944.
    Kuo, R. J., C. M. Chao and Y. T. Chiu (2011). Application of particle swarm optimization to association rule mining. Applied Soft Computing,11(1),326-336.
    Li, H. and A. Lim (2003). Local search with annealing-like restarts to solve the VRPTW. European Journal of Operational Research,150(1),115-127.
    Lin, S. W., V. F. Yu and C. C. Lu (2010). A simulated annealing heuristic for the truck and trailer routing problem with time windows. Expert Systems with Applications.
    MirHassani, S. A. and N. Abolghasemi (2011). A particle swarm optimization algorithm for open vehicle routing problem. Expert Systems with Applications.
    Qing, Z., Q. Limin, L. Yingchun and Z. Shanjun (2006). An Improved Particle Swarm Optimization Algorithm for Vehicle Routing Problem with Time Windows. Evolutionary Computation, 2006. CEC 2006. IEEE Congress on: 1386-1390.
    Repoussis, P. P., C. D. Tarantilis and G. Ioannou (2006). The open vehicle routing problem with time windows. Journal of the Operational Research Society,58(3),355-367.
    Salhi, S. and G. K. Rand (1993). Incorporating vehicle routing into the vehicle fleet composition problem. European Journal of Operational Research,66(3),313-330.
    Sariklis, D. and S. Powell (2000). A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society,564-573.
    Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research,254-265.
    Solomon, M. M. and J. Desrosiers (1988). Survey Paper: Time Window Constrained Routing and Scheduling Problems. Transportation Science,22(1),1-13.
    Song, M. P. and G. C. Gu (2004). Research on particle swarm optimization: a review, IEEE. 4: 2236-2241 vol. 2234.
    Syslo, M., N. Deo and J. S. Kowalik (1983). Discrete optimization algorithms with Pascal programs, Prentice Hall Professional Technical Reference.
    Tan, K. C., L. H. Lee, Q. L. Zhu and K. Ou (2001). Heuristic methods for vehicle routing problem with time windows. Artificial Intelligence in Engineering,15(3),281-295.
    Tasgetiren, M. F., M. Sevkli, Y. C. Liang and G. Gencyilmaz (2004). Particle swarm optimization algorithm for single machine total weighted tardiness problem, IEEE. 2: 1412-1419 Vol. 1412.
    Tasgetiren, M. F., M. Sevkli, L. Yun-Chia and G. Gencyilmaz (2004). Particle swarm optimization algorithm for single machine total weighted tardiness problem. Evolutionary Computation, 2004. CEC2004. Congress on. 2: 1412-1419 Vol.1412.
    Thangiah, S. R., K. E. Nygard and P. L. Juell (1991). Gideon: A genetic algorithm system for vehicle routing with time windows, IEEE. 1: 322-328.
    Toth, P. and D. Vigo (2002). The vehicle routing problem, Society for Industrial Mathematics.
    Wang, K.-P., L. Huang, C.-G. Zhou and W. Pang (2003). Particle swarm optimization for traveling salesman problem. Machine Learning and Cybernetics, 2003 International Conference on. 3: 1583-1585 Vol.1583.
    Wang, K. P., L. Huang, C. G. Zhou and W. Pang (2003). Particle swarm optimization for traveling salesman problem, IEEE. 3: 1583-1585 Vol. 1583.
    Wang, W., B. Wu, Y. Zhao and D. Feng (2006). Particle swarm optimization for open vehicle routing problem. Computational Intelligence,999-1007.
    Xia, W. and Z. Wu (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering,48(2),409-425.
    Yu, B., Z. Z. Yang and B. Yao (2009). An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research,196(1),171-176.
    Zhu, Q., L. Qian, Y. Li and S. Zhu (2006). An improved particle swarm optimization algorithm for vehicle routing problem with time windows, IEEE: 1386-1390.

    QR CODE