簡易檢索 / 詳目顯示

回結果列表
研究生： Budhi Sholeh Wibowo
Budhi - Sholeh Wibowo
論文名稱： 應用蟻群系統求解具模糊服務時間之動態車輛途程問題
Application of Ant Colony System to Solve Dynamic Vehicle Routing Problem with Fuzzy Service Time
指導教授： 郭人介
Ren-Jieh Kuo
口試委員: 田方治
Fang-Chih Tien
喻奉天
Vincent Yu
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2012
畢業學年度： 100
語文別： 英文
論文頁數： 94
中文關鍵詞： 蟻群最佳化 、動態車輛途程規劃 、模糊理論 、有限車輛數 、不確定之服務時間
外文關鍵詞： ant colony optimization, dynamic vehicle routing, fuzzy theory, limited vehicle number, uncertain service time
相關次數： 點閱：232  下載：13 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 近年來資訊科技發展，已使人們在物流管理上可進行即時處理與減少需求之不確定性。然而，服務時間的長短仍存在著不確定性。因此，本研究提出應用蟻群演算法來求解動態車輛途程規劃問題，並考慮服務時間之不確定性。為了能更符合真實狀況，本研究加入車輛數的限制。在模式中，利用模糊理論及可信度衡量來處理不確定之服務時間。此外，本研究在蟻群演算法中加入叢集插入法來產生初始解，以改善演算法之求解品質。蟻群演算法在具有不同動態度的五個標竿問題中進行測試，結果顯示，該演算法針對此問題有非常優良之求解效率。再者，叢集插入法確可強化模糊蟻群演算法的表現。

    Recent advance in information technology has allowed people to do real-time processing and reduced demand uncertainty in logistics management. However, in case of service field, the duration of service time still often cannot be identified in certain. Thus, this study proposes an application of ant colony system (ACS) to solve dynamic vehicle routing problem with uncertainty in service time. The attempt is made to present a more realistic problem by considering a limited number of vehicles. In the model, fuzzy theory and credibility measurement are used to deal with the uncertain service time. In addition, an improved constructive heuristic called clustered-insertion method is applied to generate the initial solution for ACS. The proposed algorithm was tested for five instances with different degrees of dynamism. The computational results show that fuzzy-ACS is an effective method to deal with the problem. Additionally, clustered-insertion method really can improve the performance of fuzzy-ACS.

    Abstract………..………..………..………..………..………..………..………..……….. i Acknowledgment………..………..………..………..………..………..………..……….. ii Contents………..………..………..………..………..………..………..………..……….. iv List of Figures………..………..………..………..………..………..………..………….. vii List of Tables………..………..………..………..………..………..………..…………… ix Chapter 1 Introduction………..………..………..………..………..………..………… 1 1.1 Background………..………..………..………..………..………..……………… 1 1.2 Research Objective………..………..………..………..………..………..………. 5 1.3 Scope and Assumption………..………..………..………..………..…………… 5 1.4 Organization of Thesis………..………..………..………..………..……………. 5 Chapter 2 Literature Review………..………..………..………..………..……………. 7 2.1 Vehicle Routing Problem………..………..………..………..………..………….. 7 2.2 Dynamic Vehicle Routing Problem………..………..………..………..………… 9 2.2.1 Technical requirement………..………..………..………..………..………. 11 2.2.2 Degree of dynamism………..………..………..………..………..………… 12 2.3 DVRP Applications………..………..………..………..………..………..……… 13 2.3.1 Transport of Good………..………..………..………..………..…………… 13 2.3.2 Services………..………..………..………..………..………..……………… 13 2.3.3 Transport of Person………..………..………..………..…………………… 14 2.4 DVRP Solution Methods………..………..………..………..………..…………. 15 2.4.1 Exact solution methods………..………..………..………..………………. 15 2.4.2 Heuristics methods………..………..………..………..………..………….. 15 a) Insert and Improve Algorithm………..………..………..………..……….. 16 b) Tabu Search………..………..………..………..………..………..……….. 17 c) Ant Colony System………..………..………..………..………..………….. 17 d) Genetic Algorithm………..………..………..………..………..………….. 17 e) Hyperheuristics………..………..………..………..………..…………….. 18 2.5 Ant Colony Optimization………..………..………..………..………..……….. 18 2.6 Fuzzy Sets Theory………..………..………..………..………..………..……… 21 2.6.1 Membership Function………..………..………..………..……………….. 21 2.6.2 Logical Operations………..………..………..………..…………………… 22 2.6.3 If-Then Rules………..………..………..………..………..………..………. 23 2.6.4 Credibility Measure Theory………..………..………..………..………….. 23 2.7 Fuzzy Optimization in VRP………..………..………..………..………..……… 24 2.7.1 Fuzzy Demands………..………..………..………..………..…………….. 25 2.7.2 Fuzzy Travel Times………..………..………..………..………..………… 26 Chapter 3 Model Formulation………..………..………..………..………..………… 27 3.1 Problem Description………..………..………..………..………..……………… 27 3.2 Mathematical Model………..………..………..………..………..……………. 28 3.3 System Architecture………..………..………..………..………..……………… 30 3.4 Single Aggregate Objective Function………..………..………..………………. 33 3.5 Fuzzy Approximation………..………..………..………..………..…………… 34 3.5.1 Adaptive Fuzzy Sets………..………..………..………..………………… 34 3.5.2 Fuzzy Logic………..………..………..………..………..………………… 36 3.5.3 Credibility Measure………..………..………..………..………..………… 36 3.5.4 Fuzzy Chance Constrained Programming………..………..……………. 37 3.6 Hybrid Fuzzy-Ant Colony System………..………..………..………..………. 38 3.6.1 Initial Trail………..………..………..………..………..…………………. 38 3.6.2 Solution Construction………..………..………..………..………………. 40 3.6.3 Pheromone Update………..………..………..………..………..………… 42 3.6.4 Local Search………..………..………..………..………..……………….. 43 3.6.5 Fitness Value………..………..………..………..………..……………….. 44 3.6.6 Fuzzy-ACS Procedure………..………..………..………..………..……….. 44 Chapter 4 Computational Experiences….………..………..………..………..…………. 47 4.1 Data and Parameters………..……..…..………..………..………..……………… 47 4.2 ACS Parameter Tuning………..………..………..………..………..…………… 50 4.3 Model Performance………..………..………..………..………..……………….. 54 4.3.1 Clustered-Insertion Method ……………………………...………………… 54 4.3.2 Fuzzy-ACS ……………..………..………..………..………..…………….. 55 4.4 Sensitivity Analysis……………………………………………………………… 57 4.4.1 Number of Time Slices……..………………..………..………..…………… 57 4.4.2 Degree of Dynamism…..…….……..………..………………..…………….. 59 4.4.3 Credibility Preference Index……..………..………..………..………..……. 61 4.5 Graphical Representation of Optimization Result………..………..……………. 65 4.5.1 Case 1 (dod = 0) ………..……………………..………..………..…………….. 65 4.5.2 Case 2 (dod = 0.25) ………..…………....………..………..………..…………. 66 4.5.3 Case 3 (dod = 0. 5) ………..…………....………..………..………..…………. 67 4.5.4 Case 4 (dod = 0. 75) ………..………..…..………..………..………..………… 68 4.5.5 Case 5 (dod = 1) ………..………..………..……….…..………..…………….. 69 Chapter 5 Conclusion and Further Study………………..………..………..…………… 71 5.1 Conclusions………..………..………..………..………..………..………………. 71 5.2 Contributions………..………..………..………..………..………..…..…………. 72 5.3 Further Study….………..………..………..………..………..……..…..……….. 72 References………..………..………..………..………..………..………..……………. 74 Appendix A Basic Dataset………..………..………..………..………..………..……….. 79 Appendix B Problem Variants …………..………..………..………..………..………… 80

    Adenso-Diaz, B. Laguna, M., “Fine tuning of the algorithms using fractional experimental designs and local search,” Operation Research, Vol.54, No.1, pp. 99-114, 2006.
    Bertsimas, J.D. and Ryzin, G.V., “A stochastic and dynamic vehicle routing problem in the Euclidian plane,” Operations Research, Vol.39, No.4, pp. 601-615, 1990.
    Bertsimas, J.D. and Ryzin, G.V., “Stochastic and dynamic vehicle routing with general demand and inter-arrival time distributions,” Advances in Applied Probability, Vol.25, No.4 pp. 947-978, 1993.
    Bianchi, L., “Notes on dynamic vehicle routing: the state of the art,” Technical Report IDSIA-05-01, 2000.
    Brito, J., Martinez FJ., Moreno AJ., Verdegay, JL., “Fuzzy approach for vehicle routing problems with fuzzy travel time.”Fuzzy System (FUZZ). IEEE International Conference, pp.1-8, 2010.
    Brito, J., Moreno, AJ.,Verdegay, J.L., “Fuzzy optimization in vehicle routing problems,” IFSA-EUSFLAT, 2009,
    Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (eds), “Combinatorial Optimization,” John Wiley, Chichester, 1979.
    Colorni, A., Dorigo, M., Maniezzo, V., Trubian, M., “Ant system for job-shop scheduling,” Belgian Journal of Operation Research, Statistics, and Computer Science, Vol 34, No.1, pp. 39–53, 1994.
    Dantzig, G., Ramser J.H., “The truck dispatching problem,” Management Science, Vol. 6, No. 1, pp. 80-91, 1959.
    Dantzig, G., Fulkerson, R., Johnson, S., “Solution of a large-scale travelling salesman problems,” Journal of the Operations Research Society of America, Vol. 2, No. 4, pp. 393-410, 1954.
    Dorigo, M., “Optimization, learning and natural Algorithms,” Ph.D.Thesis, Politecnico di Milano, Italy, 1992.
    Dorigo, M., Gambardella L.M., “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp.53–66, 1997.
    Dorigo, M., Gambardella, L.M., “Ant colonies for the traveling salesman problem,” TR/IRIDIA/1996-3, UniversiteLibre de Bruxelles, Belgium, 1996.
    Dror, M., Laporte, G., Trudeau, P., “Vehicle routing with stochastic demands: properties and solution frameworks,” Transportation Sciences, Vol.23, pp. 166-176, 1989.
    Erbao, C., Mingyong, L., “A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demands,” Journal of Computational and Applied Mathematics, Vol. 231, pp. 302-310, 2009.
    Erbao, C., Mingyong, L., “The open vehicle routing problem with fuzzy system,” Expert System with Applications, Vol. 37, pp. 2405-2411, 2010.
    Fisher, M., Jaikumar, R., Wassenhove, L., “A generalized assignment heuristic for vehicle routing,” Networks, Vol. 11, pp. 109–124, 1981.
    Fleischmann, B., Gnutzmann, S., Sandvos, E., “Dynamic vehicle routing based on online traffic information,” Transportation Science, Vol. 38, No. 4, pp. 420– 433, 2004.
    Gambardella L.M., Taillard E., Dorigo M., “Ant colonies for the quadratic Assignment problem,”Journal of the Operational Research Society, Vol. 50, pp. 167-176, 1999.
    Garrido, P. and Riff, M.C., “DVRP: a hard dynamic combinatorial optimization problem tackled by an evolutionary hyperheuristic,” Journal of Heuristics, Vol. 16, pp.795-834, 2010.
    Gendrau, M., Hertz, A. Laporte, G., “A tabu search heuristic for the vehicle routing problem,” Management Science, Vol. 40, pp.1276-1290, 1994.
    Gendrau, M., Guertin, F. Potvin, J.Y., Taillard, E. “Parallel tabu search for real-time vehicle routing and dispatching,” Transportation Science, Vol. 33, No.4, pp. 381–390, 1999.
    Ghiani, G., Guerriero, F., Laporte., G., Musmanno., R., “Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies,” European Journal of Operational Research, Vol. 151, pp. 1-11, 2003.
    Gupta, R., Singh, B., Pandey, D, “Fuzzy vehicle routing problem with uncertainty in service time,” International Journal Contemporary Mathematics Sciences, Vol.5, No.11, pp. 497-507, 2010.
    Gupta, R., Singh, B., Pandey, D., “Multi-objective fuzzy vehicle routing problem: a case study,” International Journal Contemporary Mathematics Sciences, Vol.5, No.29, pp. 1439-1454, Vol. 2010.
    Hanshar, F.T., Ombuki-Berman, B.M., “Dynamic vehicle routing using genetic algorithms,” Applied Intelligence, Vol. 27, No. 1, pp. 89-99, 2007.
    Harrera, F., Verdegay, J.L., “Three models of fuzzy integer linear programming,” European Journal of Operational Research, Vol. 83, pp. 581-593, 1995.
    Hong, L., Xu, M., “A model of MDVRPTW with fuzzy travel time and time dependent and its solution,” Fifth International Conference on Fuzzy System and Knowledge Discovery, pp. 473-478, 2008.
    Kilby, P., Prosser, P., Shaw. P., “Dynamic VRPs: A study of scenarios,” Report APES-06-1998.
    Kuo, RJ., Chiu, CY, Lin YJ. “Integration of fuzzy theory and ant algorithm for vehicle routing problem with time window,” Fuzzy Information, 2004. Processing NAFIPS '04, IEEE Annual Meeting of the , Vol.2, pp. 925- 930, 2004.
    Larsen, A., “The dynamic vehicle routing problem,” Ph.D thesis, Technical University of Denmark, 2001.
    Larsen, A., Madsen, O., Solomon, M., “Partially dynamic vehicle routing – models and algorithms,” Journal of the Operational Research Society, 53, pp.637-646, 2002.
    Lau, HC., Sim, M., Teo, KW., “Vehicle routing problem with time windows and a limited number of vehicles,” European Journal of Operational Research, 148, pp.559-569. 2003.
    Liu, B., “Uncertainty Theory,” Springer-Verlag, Berlin, 2004.
    Liu, B., “A survey of credibility theory,” Fuzzy Optimization and Decision Making, 5(4), pp. 387-408, 2006.
    Meisel, S., “Anticipatory optimization for dynamic decision making,” 1st Edition, XIV, 182, 2011.
    Montemanni, R., Gambardella L.M., Rizzoli, A.E., Donati A.V., “Ant colony system for a dynamic vehicle routing problem,” Journal of Combinatorial Optimization, Vol.10, pp.327–343, 2005.
    Nanry, WP., Barnes, W.B., “Solving the pickup and delivery problem with time windows using reactive tabu search,” Transportation Research part B, Vol. 34, pp. 107-121, 2000.
    Pankratz, G., “Dynamic vehicle routing by means of a genetic algorithm,” International Journal of Physical Distribution & Logistics Management, Vol. 35, No.5, pp. 362-383, 2005.
    Pillac, V., Gendreau, M., Gueret, C., Medaglia., A., “A review of dynamic vehicle routing problems,” CIRRELT-2011-62, 2011.
    Powell, W.B., Carvalho, T.A., Godfrey, G.A., Simao, H.P., “Dynamic fleet management as a logistics queuing network,” Annals of Operation Research, Vol. 61. pp. 165-188., 1995.
    Psaraftis, H.N., “Dynamic vehicle routing: status and prospect,” Annals of Operations Research, Vol. 61, No.1, pp. 143-164, 1988.
    Psaraftis, H.N., “An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows,” Transportation Science, Vol. 17, No.3., pp. 351-357, 1983.
    Resende, M.G.C., Ribeiro, C.C., “Greedy Randomized Adaptive search procedures,” in F. Glover and G. Kochenberger (eds.), Handbook of Metaheuristics, pp. 219–249, 2003.
    Rizolli, A.E, Montemanni, R., Lucibello, E., Gambardella, L.M., “Ant colony optimization for real world vehicle routing problems,” Swarm Intelligence, Vol. 1, pp. 135-151, 2007.
    Taillard, E., “Parallel iterative search methods for vehicle-routing problems,” Networks, Vol. 3, No. 8, pp. 661–673, 1994.
    Teodorovic, D., Lucic, P., “The fuzzy ant system for the vehicle routing problem when demand at nodes is uncertain,” International Journal on Artificial Intelligence Tools, Vol. 16, No.5, pp. 751-770, 2007.
    Teodorovic, D., Pavkovic, G., “A simulated annealing technique approach to the vehicle routing problem in the case of stochastic,” Transportation Planning Technology, Vol. 16, pp. 261-273, 1992.
    Teodorovic, D., Pavkovic, G., “The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain,” Fuzzy Sets and System, Vol. 82, pp. 307-317, 1995.
    Toth, P., Vigo, D., “An exact algorithm for the vehicle routing problem with backhaul,” Transportation Science, Vol. 31, No. 4, pp. 372-385, 1997.
    Toth, P., Vigo, D., “An overview of vehicle routing problem,” In P. Toth and D. Vigo (Eds), The Vehicle Routing Problem, Philadelphia: Society for Industrial and applied mathematics, 2002.
    Yang, J., Jaillet, P., Mahmassani, H., “Real-time multivehicle truckload pick-up and delivery problems,” Transportation Science, Vol. 38, pp. 135-148, 2004.
    Zadeh, L.A., “Fuzzy sets,” Information and Control, Vol. 8, pp.338-353, 1965.
    Zeimpekis, V.S., “Design and evaluation of a real time fleet management system for dynamic incident handling in urban freight distribution,” Ph.D thesis, Athena University of Economics and Business, 2007.
    Zheng, Y., Liu, B., “Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm,” Applied Mathematics and Computation, Vol. 176, pp. 673-683, 2006.

    QR CODE