A hybrid genetic algorithm with perturbation for the multi-depot capacitated arc routing problem

被引：5

作者：

Hu, Hongtao ^{[1
]}

Liu, Tiantang ^{[2
]}

Zhao, Ning ^{[1
]}

Zhou, Yiting ^{[1
]}

Min, Dequan ^{[3
]}

机构：

[1] Logistics Engineering College, Shanghai Maritime University, Shanghai

[2] School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai

[3] Transportation Management College, Dalian Maritime University, Dalian

来源：

Journal of Applied Sciences | 2013年 / 13卷 / 16期

关键词：

Hybrid genetic algorithm; Local search; Multi-depot capacitated arc routing problem; Perturbation;

D O I：

10.3923/jas.2013.3239.3244

中图分类号：

学科分类号：

摘要：

The Capacitated Arc Routing Problem (CARP) is a difficult vehicle routing problem, where given an undirected graph, the objective is to minimize the total cost of all vehicle tours that serve all required edges under vehicle capacity constraints. In this study, a Hybrid Genetic Algorithm with Perturbation (HGAP) is proposed to solve the multi-depot CARP (MDCARP) which generalizes the CARP by extending the single-depot to the multi-depot. The proposed HGAP incorporates a Genetic Algorithm (GA), a local search, a new replacement method and a perturbation mechanism. The proposed HGAP is evaluated on the MDCARP benchmark instances and computational results show that the HGAP is very competitive. © 2013 Asian Network for Scientific Information.

引用

页码：3239 / 3244

页数：5

共 18 条

[1]

Benavent E., Campos V., Corberan A., Mota E., The capacitated arc routing problem, A Heuristic Algorithm. Questiio, 14, pp. 107-122, (1990)

[2]

Beullens P., Muyldermans L., Cattrysse D., van Oudheusden D., A guided local search heuristic for the capacitated arc routing problem, Eur. J. Operat. Res, 147, pp. 629-643, (2003)

[3]

Brandao J., Eglese R., A deterministic tabu search algorithm for the capacitated arc routing problem, Comput. Operat. Res, 35, 111, pp. 2-1126, (2008)

[4]

Chapleau L., Ferland J.A., Lapalme G., Rousseau J.M., A parallel insert method for the capacitated arc routing problem, Operat. Res. Lett, 3, pp. 95-99, (1984)

[5]

Corberan A., Prins C., Recent results on arc routing problems: An annotated bibliography, Networks, 56, pp. 50-69, (2010)

[6]

Eglese R.W., Routeing winter gritting vehicles, Discrete Applied Math, 48, pp. 231-244, (1994)

[7]

Frederickson G.N., Approximation algorithms for some postman problems, J. ACM, 26, pp. 538-554, (1979)

[8]

Golden B.L., Wong R.T., Capacitated arc routing problems, Networks, 11, pp. 305-315, (1981)

[9]

Golden B.L., Dearmon J.S., Baker E.K., Computational experiments with algorithms for a class of routing problems, Comput. Operat. Res, 10, pp. 47-59, (1983)

[10]

Hertz A., Mittaz M., A variable neighborhood descent algorithm for the undirected capacitated arc routing problem, Transport. Sci, 35, pp. 425-434, (2001)

← 1 2 →