A metaheuristic for the min-max windy rural postman problem with K vehicles

被引：13
作者：
Benavent E. [1 ]
Corberán A. [1 ]
Sanchis J.M. [2 ]
机构：
[1] DEIO, Universitat de València, Valencia
[2] DMA, Universidad Politécnica de Valencia, Valencia
来源：
Computational Management Science | 2010年 / 7卷 / 3期
基金：
中国国家自然科学基金;
关键词：
Metaheuristics; Multivehicles; Rural postman problem; Windy rural postman problem;
D O I：
10.1007/s10287-009-0119-2
中图分类号：
学科分类号：
摘要：
In this paper we deal with the min-max version of the windy rural postman problem with K vehicles. For this problem, in which the objective is to minimize the length of the longest tour in order to find a set of balanced tours for the vehicles, we present here a metaheuristic that produces very good feasible solutions in reasonable computing times. It is based on the combination of a multi-start procedure with an Iterated Local Search. Extensive computational results on a large set of instances with up to 50 vertices, 184 edges and 5 vehicles are presented. The results are very good, the average gaps with respect to a known lower bound are less than 0.40% for instances with 2 or 3 vehicles and up to 1.60% when 4 or 5 vehicles are considered. © 2009 Springer-Verlag.
引用
收藏
页码：269 / 287
页数：18
相关论文
共 19 条
  • [1] Ahr D., Reinelt G., New heuristics and lower bounds for the min-max k-Chinese postman problem, Algorithms-ESA 2002, 10th Annual European Symposium, Rome, Italy, September 2002 Proceedings, Lecture Notes in Computer Science, Vol 2461, pp. 64-74, (2002)
  • [2] Ahr D., Reinelt G., A Tabu search algorithm for the min-max k-Chinese postman problem, Comput Oper Res, 33, pp. 3403-3422, (2006)
  • [3] Applegate D., Cook W., Dash S., Rohe A., Solution of a min-max vehicle routing problem, INFORMS J Comput, 14, pp. 132-143, (2002)
  • [4] Assad A., Pearn W.L., Golden B., The capacitated Chinese postman problem: Lower bounds and solvable cases, Am J Math Manag Sci, 7, pp. 63-88, (1987)
  • [5] Barahona F., Grotschel M., On the cycle polytope of a binary matroid, J Comb Theory, 40, pp. 40-62, (1986)
  • [6] Benavent E., Corberan A., Pinana E., Plana I., Sanchis J.M., New heuristic algorithms for the windy rural postman problem, Comput Oper Res, 32, pp. 3111-3128, (2005)
  • [7] Benavent E., Carrotta A., Corberan A., Sanchis J.M., Vigo D., Lower bounds and heuristics for the windy rural postman problem, Eur J Oper Res, 176, pp. 855-869, (2007)
  • [8] Benavent E., Corberan A., Plana I., Sanchis J.M., Min-Max K-vehicles windy rural postman problem, Networks, 54, pp. 216-226, (2009)
  • [9] Christofides N., Campos V., Corberan A., Mota E., An Algorithm for the Rural Postman Problem, Report IC.O.R.81.5, (1981)
  • [10] Christofides N., Campos V., Corberan A., Mota E., An algorithm for the rural postman problem on a directed graph, Math Program Study, 26, pp. 155-166, (1986)
12