High-Level Relay Hybrid Metaheuristic Method for Multi-Depot Vehicle Routing Problem with Time Windows
详细信息    查看全文
  • 作者：Siamak Noori (1) snoori@iust.ac.ir
    S. Farid Ghannadpour (1) ghannadpour@rail.iust.ac.ir
  • 关键词：Multi ; Depot vehicle routing and scheduling – ; Hybrid metaheuristic – ; Genetic algorithm – ; Tabu search
  • 刊名：Journal of Mathematical Modelling and Algorithms
  • 出版年：2012
  • 出版时间：June 2012
  • 年：2012
  • 卷：11
  • 期：2
  • 页码：159-179
  • 全文大小：657.7 KB
  • 参考文献：1. Dondo, R., Cerda, J.: A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. Eur. J. Oper. Res. 176, 1478–1507 (2007)
    2. Ho, W., Ho, G.T.S., Ji, P., Lau, H.C.W.: A hybrid genetic algorithm for the multi-depot vehicle routing problem. Eng. Appl. Artif. Intell. 21, 548–557 (2008)
    3. Pepin, A.S., Desaulniers, G., Herts, A., Huisman, D.: A comparison of rive heuristics for the multiple depot vehicle scheduling problem. J. Sched. 12, 17–30 (2009)
    4. Achutan, N., Caccettal, L., Hill, S.: An improved branch-and-cut algorithm for the capacitated vehicle routing problem. Transp. Sci. 37, 153–169 (2003)
    5. Larsen, J.: Parallelization of the vehicle routing problem with time windows. Ph.D. thesis, IMM-PHS-1999-62, Department of Mathematical Modelling, Technical University of Denmark, Lynghy, Denmark (1999)
    6. Kohl, N.: Exact methods for time constrained routing and related scheduling problems. Ph.D. Thesis, Department of Mathematical Modeling, Technical University of Denmark (1995)
    7. Tan, K.C., Lee, L.H., Zhu, K.Q., Qu, K.: Heuristic methods for vehicle routing problem with time windows. Artif. Intell. Eng. 15, 281–295 (2001)
    8. Thangiah, S.R.: A hybrid genetic algorithms, simulated annealing and tabu search heuristic for vehicle routing problems with time windows. In: Chambers, L. (ed.) Practical Handbook of Genetic Algorithms, Complex Structures, vol. 3, pp. 347–381 (1999)
    9. Czech, Z.J., Czarnas, P.: Parallel simulated annealing for the vehicle routing problem with time windows. In: 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, pp. 376–383. Spain (2002)
    10. Chiang, W.C.: Russell: simulated annealing metaheuristic for the vehicle routing problem with time windows. Ann. Oper. Res. 63, 3–27 (1996)
    11. Jemai, J., Mellouli, Kh: A neural-tabu search heuristic for the real time vehicle routing problems. J. Math. Model. Algorithm. 7, 161–176 (2008)
    12. Taillard, E.D., Badeau, P., Gendreau, M., Gueritin, F., Potvi, J.-Y.: A tabu search heuristic for the vehicle routing problem with soft time windows. Transp. Sci. 31, 170–186 (1997)
    13. Cordeau, J.F., Larporte, G., Mercier, A.: A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. 52, 928–936 (2001)
    14. Gambardella, L.M., Taillard, E., Agazzi, G.: MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows. In: Corne, D., Dorigo, M., Glover, F. (eds.) New Ideas in Optimization, pp. 63–76. London (1999)
    15. Ombuki, B., Ross, B., Hanshar, F.: Multi-Objective genetic algorithm for vehicle routing problem with time windows. Appl. Intell. 24, 17–30 (2006)
    16. Braysy, O., Dullaert, W., Gendreau, M.: Evolutionary algorithm for the vehicle routing problem with time windows. J. Heuristic 10, 587–611 (2005)
    17. Salhi, S., Petch, R.J.: A GA based heuristic for the vehicle routing problem with multiple trips. J. Math. Model. Algorithm. 6, 591–613 (2007)
    18. Berger, J., Barkaoui, M.: A hybrid genetic algorithm for the capacitated vehicle routing problem. In: Cant煤-Paz, E. (ed.) GECCO03. LNCS, 2723, Chicago (2003)
    19. Tan, K.C., Chew, Y.H., Lee, L.H.: A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Comput. Optim. Appl. 34, 115–151 (2006)
    20. Ghoseiri, K., Ghannadpour, S.F.: Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm. Appl. Soft Comput. 4, 1096–1107 (2010)
    21. Tan, K.C., Hay, L.L., Ke, O.: A hybrid genetic algorithm for solving vehicle routing problems with time window constraints. Asia Pac. J. Oper. Res. 18, 121–130 (2001)
    22. Ghoseiri, K., Ghannadpour, S.F.: Hybrid genetic algorithm for vehicle routing and scheduling problem. J. Appl. Sci. 9, 79–87 (2009)
    23. Majumdar, J., Bhunia, A.K.: Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times. J. Comput. Appl. Math. 235, 3063–3078 (2011)
    24. Marinakis, Y., Marinaki, M., Dounias, G.: A hybrid particle swarm optimization algorithm for the vehicle routing problem. Eng. Appl. Artif. Intell. 23, 463–472 (2010)
    25. Garcia-Najera, A., Bullinaria, J.A.: An improved multi-objective evolutionary for the vehicle routing problem with time windows. Comput. Oper. Res. 38, 287–300 (2011)
    26. Ursani, Z., Essam, D., Cornforth, D., Stocker, R.: Localized genetic algorithm for vehicle routing problem with time windows. Appl. Soft Comput (2011). doi:10.1016/j.asoc.2011.05.021
    27. Nagata, Y., Braysy, O., Dullaret, W.: A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Comput. Oper. Res. 37, 724–737 (2010)
    28. Li, F., Golden, B., Wasil, E.: Very large scale vehicle routing: new test problems algorithms and results. Comput. Oper. Res. 32, 1165–1179 (2005)
    29. Kim, B.I., Kim, S., Sahoo, S.: Waste collection vehicle routing problem with time windows. Comput. Oper. Res. 33, 3624–3642 (2006)
    30. Tan, K.C., Cheong, C.Y., Goh, C.K.: Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. Eur. J. Oper. Res. 177, 813–139 (2007)
    31. Irnich, S., Funke, B., Grunert, T.: Sequential search and its application to vehicle routing problems. Comput. Oper. Res. 33, 2405–2429 (2006)
    32. Sumichrast, R.T., Markham, I.S.: A heuristic and lower bound for the multi-depot routing problem. Comput. Oper. Res. 22, 1047–1056 (2002). References and further reading may be available for this article. To view references and further reading you must purchase this article.
    33. Yucenur, G.N., Demirel, N.C.: A new geometric shape-based genetic clustering algorithm for the multi-depot vehicle routing problem. Expert Syst. Appl. (2011). doi:10.1016/j.eswa.2011.03.077
    34. Salhi, S., Sari, M.: A multi-level composite heuristic for the multi-depot vehicle fleet mix problem. Eur. J. Oper. Res. 103, 95–112 (1997)
    35. Wu, T.H., Low, C., Bai, J.W.: Heuristic solutions to multi-depot location-routing problem. Comput. Oper. Res. 29, 1393–1415 (2002)
    36. Lim, A., Zhu, W.: A Fast and Effective Insertion Algorithm for Multi-Depot Vehicle Routing Problem with Fixed Distribution of Vehicles and a New Simulated Annealing Approach, pp. 282–291. Springer-Verlag Berlin, Heidelberg (2006)
    37. Polacek, M., Harlt, R.F., Doerner, K.: A variable neighborhood search for the multi depot vehicle routing problem with time windows. J. Heuristics 10, 613–627 (2004)
    38. Tansini, L., Viera, O.: Adapted Clustering Algorithm for the Assignment Problem in the MDVRPTW. Technical Report, RT04-13 (2004)
    39. Dondo, R.G., Creda, J.: A hybrid local improvement algorithm for large-scale multi-depot vehicle routing problems with time windows. Comput. Chem. Eng. 33, 513–530 (2009)
    40. Mirabi, M., Fatemi Ghomi, S.M.T., Jolai, F.: Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem. Robot Comput. Integrated Manuf. 26, 564–569 (2010)
    41. Liu, R., Jiang, Z., Fung, R.Y.K., Chen, F., Liu, X.: Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration. Comput. Oper. Res. 37, 950–959 (2010)
    42. Ghoseiri, K., Ghannadpour, S.F.: A hybrid genetic algorithm for multi-depot homogenous locomotive assignment with time windows. Appl. Soft Comput. 10, 53–65 (2010)
    43. Holland, J.H.: Adaptation in Natural and Artificial System. Ann Arbor, Michigan (1975)
    44. Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35, 254–265 (1987)
    45. Ishibashi, H., Aguirre, H., Tanaka, K., Sugimura, T.: Multi-objective optimization with improved genetic algorithm. IEEE International Conference on Systems, Man, and Cybernetics (SMC), Nashville, pp. 3852–3857 (2000)
    46. http://neo.lcc.uma.es/radi-aeb/WebVRP/index.html?/Problem_Instances/instances.html
    47. Cordeau, J.F., Laporte, G., Mercier, A.: An improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows. J. Oper. Res. Soc. 55, 542–546 (2004)
    48. Derrac, J., Garcia, S., Molina, D., Herrera, F.: A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol. Comput. 1, 3–18 (2011)
  • 作者单位：1. Department of Industrial Engineering, Iran University of Science and Technology, 16846-13114 Tehran, Iran
  • 刊物类别：Mathematics and Statistics
  • 刊物主题：Mathematics
    Mathematical Modeling and IndustrialMathematics
    Optimization
    Numeric Computing
    Theory of Computation
    Algorithms
  • 出版者：Springer Netherlands
  • ISSN：1572-9214
文摘
This paper presents an efficient hybrid metaheuristic solution for multi-depot vehicle routing with time windows (MD-VRPTW). MD-VRPTW involves the routing of a set of vehicles with limited capacity from a set of depots to a set of geographically dispersed customers with known demands and predefined time windows. The present work aims at using a hybrid metaheuristic algorithm in the class of High-Level Relay Hybrid (HRH) which works in three levels and uses an efficient genetic algorithm as the main optimization algorithm and tabu search as an improvement method. In the genetic algorithm various heuristics incorporate local exploitation in the evolutionary search. An operator deletion- retrieval strategy is executed which shows the efficiency of the inner working of the proposed method. The proposed algorithm is applied to solve the problems of the standard Cordeau’s Instances. Results show that proposed approach is quite effective, as it provides solutions that are competitive with the best known in the literature.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址：北京市海淀区学院路29号 邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700