Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking

被引：23

作者：

Prins C. ^{[1
]}

Prodhon C. ^{[1
]}

Calvo R.W. ^{[1
]}

机构：

[1] Institute Charles Delaunay, University of Technology of Troyes, 10010 Troyes Cedex

来源：

4OR | 2006年 / 4卷 / 3期

关键词：

GRASP; Heuristic; Location routing problem; Path relinking;

D O I：

10.1007/s10288-006-0001-9

中图分类号：

学科分类号：

摘要：

As shown in recent researches, the costs in distribution systems may be excessive if routes are ignored when locating depots. The location routing problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. This paper presents a new metaheuristic to solve the LRP with capacitated routes and depots. A first phase executes a GRASP, based on an extended and randomized version of Clarke and Wright algorithm. This phase is implemented with a learning process on the choice of depots. In a second phase, new solutions are generated by a post-optimization using a path relinking. The method is evaluated on sets of randomly generated instances, and compared to other heuristics and a lower bound. Solutions are obtained in a reasonable amount of time for such a strategic problem. Furthermore, the algorithm is competitive with a metaheuristic published for the case of uncapacitated depots.

引用

页码：47 / 64

页数：17

共 26 条

[1]

Albareda-Sambola M., Diaz J.A., Fernandez E., A compact model and tight bounds for a combined location-routing problem, Comput Oper Res, 32, 3, pp. 407-428, (2005)

[2]

Barreto S.S., Análise e Modelização de Problemas de Localização-distribuição (Analysis and Modelization of Location-routing Problems)(in Portuguese), pp. 3810-4193, (2004)

[3]

Bruns A., Klose A., An iterative heuristic for location-routing problems based on clustering, Proceedings of the 2nd International Workshop on Distribution Logistics, (1995)

[4]

Chan Y., Carter W.B., Burnes M.D., A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands, Comput Oper Res, 28, pp. 803-826, (2001)

[5]

Chien T.W., Heuristic procedures for practical-sized uncapacitated location-capacitated routing problems, Decis Sci, 24, 5, pp. 995-1021, (1993)

[6]

Clarke G., Wright J.W., Scheduling of vehicles from a central depot to a number of delivery points, Oper Res, 12, pp. 568-581, (1964)

[7]

Cordeau J.F., Gendreau M., Hertz A., Laporte G., Sormany J.S., New heuristics for the vehicle routing problem, Technical Report, G-2004-33, (2004)

[8]

Feo T.A., Resende M.G.C., Greedy randomized adaptive search procedures, J Glob Optim, 2, pp. 1-27, (1995)

[9]

Fleurent C., Glover F., Improved constructive multistart strategies for the quadratic assignment problem using adaptative memory, INFORMS J Comput, 11, pp. 198-204, (1999)

[10]

Ghiani G., Laporte G., Location-arc routing problems, OPSEARCH, 38, pp. 151-159, (2001)

← 1 2 3 →