簡易檢索 / 詳目顯示

回結果列表
研究生： 張家鳳
CHIA-FENG CHANG
論文名稱： 利用物件導向程式架構開發啟發式演算法-考慮加油點車輛途程問題
Using object-oriented programming framework to develop an effective meta-heuristic for the vehicle routing problem with refueling
指導教授： 喻奉天
Vincent F. Yu
口試委員: 林詩偉
Shih-Wei Lin
郭人介
Ren-Jieh Kuo
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2011
畢業學年度： 99
語文別： 英文
論文頁數： 60
外文關鍵詞： Greedy Randomized Adaptive Search Procedure, Path-relinking, Object-Oriented Programming
相關次數： 點閱：1403  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • This research considers the vehicle routing problem with refueling (VRPR), a new variant of the well-known vehicle routing problem (VRP). It happens quite often that a vehicle needs refueling while making deliveries. Thus, comparing to the traditional approach, including the considering of refueling point in the route planning decision is more practical. This research develops an effective algorithm for solving the VRPR problem using object-oriented framework. The algorithms are tested on CVRP instances. The impact of the number of refueling points and tank size are discussed based on extensive experiments.

    ABTRACT I ACKNOWLEDGE II CONTENTS III LIST OF FIGURES V LIST OF TABLES VI CHAPTER 1 INTRODUCTION 1 1.1 RESEARCH BACKGROUND AND MOTIVATION 1 1.2 PURPOSE OF RESEARCH 2 1.3 RESEARCH SCOPES AND CONSTRAINTS 3 1.4 RESEARCH FRAMEWORK 3 CHAPTER 2 LITERATURE REVIEW 5 2.1 VEHICLE ROUTING PROBLEM 5 2.2 META-HEURISTIC 6 2.3 OBJECT-ORIENTED FRAMEWORK 6 CHAPTER 3 THE VEHICLE ROUTING PROBLEM WITH REFUELING 7 3.1 PROBLEM DEFINITION 7 3.2 MATHEMATICAL MODEL 8 3.3 VALIDATION OF THE MATHEMATICAL MODEL BY AMPL 11 3.4 ILLUSTRATION OF SOLUTION REPRESENTATION 12 CHAPTER 4 SOLUTION METHODOLOGY 13 4.1 GENERATING THE INITIAL SOLUTION BY GRASP 13 4.2 NEIGHBORHOOD STRUCTURE 15 4.2.1 Relocation 16 4.2.2 Exchange 17 4.2.3 2-opt 18 4.3 TABU SEARCH 19 4.4 PATH-RELINKING PROCEDURE 21 4.5 LOCAL SEARCH PROCEDURE 22 4.6 IMPROVEMENT MECHANISM 23 4.7 SIMULATED ANNEALING 24 CHAPTER 5 OBJECT-ORIENTED PROGRAMMING FRAMEWORK 26 5.1 CLASS AND OBJECT DIAGRAM 26 5.2 SEQUENCE DIAGRAM 27 5.3 CRC CARD 27 CHAPTER 6 EXPERIMENTAL DESIGN 31 6.1 GENERATION OF REFUELING POINT FROM VRP INSTANCES 31 6.2 TAGUCHI PARAMETER DESIGN 32 CHAPTER 7 COMPUTATIONAL RESULTS 35 7.1 EXPERIMENTS ON CVRP INSTANCES 35 7.2 EXPERIMENTS ON VRPR INSTANCE 38 CHAPTER 8 CONCLUSION AND FUTURE RESEARCH 40 8.1 CONCLUSION 40 8.2 FUTURE RESEARCH 40 REFERENCES 45 APPENDIX 48

    Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30, 787-800.
    Bard, J. F., Huang, L., Dror, M., & Jaillet, P. (1998a). A branch and cut algorithm for the VRP with satellite facilities. IIE Transactions, 30(9), 821-834.
    Bard, J. F., Huang, L., Jaillet, P., & Dror, M. (1998b). A decomposition approach to the inventory routing problem with satellite facilities. Transportation Science, 32(2), 189-203.
    Bastian, C., & Rinnooy Kan, A. H. G. (1992). The stochastic vehicle routing problem revisited. European Journal of Operational Research, 56(3), 407-412.
    Bräysy, O., & Gendreau, M. (2005a). Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation Science, 39(1), 104-118.
    Bräysy, O., & Gendreau, M. (2005b). Vehicle routing problem with time windows, Part II: Metaheuristics. Transportation Science, 39(1), 119-139.
    Chen, A. L., Yang, G. K., & Wu, Z. M. (2006). Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. Journal of Zhejiang University: Science, 7(4), 607-614.
    Christofides, N., Mingozzi, A., & Toth, P. (1979). The vehicle routing problem. Combinatorial Optimization.
    Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91.
    Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M. M., & Soumis, F. (2002). VRP with pickup and delivery. In P. Toth & D. Vigo (Eds.), The vehicle routing problem. (pp. 225-242). Philadelphia, PA: SIAM Monographs on Discrete Mathematics and Applications.
    Desrochers, M., & Verhoog, T. W. (1991). A new heuristic for the fleet size and mix vehicle routing problem. Computers and Operations Research, 18(3), 263-274.
    Dror, M., & Trudeau, P. (1986). Stochastic vehicle routing with modified savings algorithm. European Journal of Operational Research, 23(2), 228-235.
    Du, T. C., & Wu, J. L. (2001). Using object-oriented paradigm to develop an evolutional vehicle routing system. Computers in Industry, 44(3), 229-249.
    Eksioglu, B., Vural, A. V., & Reisman, A. (2009). The vehicle routing problem: A taxonomic review. Computers and Industrial Engineering, 57(4), 1472-1483.
    El-Sherbeny, N. A. (2010). Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods. Journal of King Saud University - Science, 22(3), 123-131.
    Feo, T. A., & Resende, M. G. C. (1995). Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization, 6(2), 109-133.
    Funke, B., Grünert, T., & Irnich, S. (2005). Local search for vehicle routing and scheduling problems: Review and conceptual integration. Journal of Heuristics, 11(4), 267-306.
    Glover, F. (1989). Tabu search - part I. ORSA Journal on Computing, 1(3), 190-206.
    Glover, F. (1990). Tabu search - part II. ORSA Journal on Computing, 2(1), 4-32.
    Glover, F., & Laguna, M. (1997). Tabu search. Boston: Kluwer Academic Publishers.
    Hansen, P., & Mladenovic, N. (1999). An introduction to variable neighborhood search. Proceedings of the 2nd International Conference on Metaheuristics-MIC97.
    Ho, S. C., & Gendreau, M. (2006). Path relinking for the vehicle routing problem. Journal of Heuristics, 12(1-2), 55-72.
    Jerne, N. K. (1974). Towards a network theory of the immune system. COLLECT.ANN.INST.PASTEUR, 125 C(1-2), 373-389.
    Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.
    Laporte, G. (1992). The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59, 345-358.
    Lenstra, J. K., & Rinnooy Kan, A. H. G. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221-227.
    Lim, A., & Wang, F. (2005). Multi-depot vehicle routing problem: A one-stage approach. IEEE Transactions on Automation Science and Engineering, 2(4), 397-402.
    Lin, S.-W., Yu, V. F., & Chou, S.-Y. (2009). Solving the truck and trailer routing problem based on a simulated annealing heuristic. Computers & Operations Research, 36(5), 1683-1492.
    Mazzeo, S., & Loiseau, I. (2004). An ant colony algorithm for the capacitated vehicle routing. Electronic Notes in Discrete Mathematics, 18, 181-186.
    Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers and Operations Research, 24(11), 1097-1100.
    Mohri, H., Kubo, M., Yajima, Y., & Mori, M. (1996). A split delivery vehicle routing problem. Journal of the Operations Research Society of Japan, 39(3), 372-387.
    Rego, C. (1998). A subpath ejection method for the vehicle routine problem. Management Science, 44(10), 1447-1459.
    Resende, M. G. C., & Ribeiro, C. C. (2005). GRASP with path-relinking: Recent advances and applications. Metaheuristics: Progress as Real Problem Solvers, 29-63.
    Sun, Z. Y., Guan, Z. L., He, S. E., & Guo, Z. G. (2010). Vehicle routing problem based on object-oriented discrete event simulation. Jiaotong Yunshu Xitong Gongcheng Yu Xinxi/Journal of Transportation Systems Engineering and Information Technology, 10(4), 148-154.
    Toth, P., & Vigo, D. (2003). The Granular Tabu Search and Its Application to the Vehicle-Routing Problem. INFORMS J. on Computing, 15(4), 333-346.
    Toth, P., & Vigo, D. (2002). The vehicle routing problem. Philadelphia, PA: SIAM Monographs on Discrete Mathematics and Applications.
    Villegas, J. G., Prins, C., Prodhon, C., Medaglia, A. L., & Velasco, N. (2011). A GRASP with evolutionary path relinking for the truck and trailer routing problem. Computers and Operations Research, 38(9), 1319-1334.
    Wu, B., Zhao, Y., Ma, Y., Dong, H., & Wang, W. (2004). Particle Swarm Optimization method for vehicle routing problem (Vol. 3, pp. 2219-2222). Hangzhou.
    Yu, V. F., Lin, S. W., Lee, W., & Ting, C. J. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers and Industrial Engineering, 58(2), 288-299.

    QR CODE