A monarch butterfly optimization for the dynamic vehicle routing problem

被引：39

作者：

Chen S. ^{[1
]}

Chen R. ^{[1
]}

Gao J. ^{[1
]}

机构：

[1] Department of Information Science and Technology, Dalian Maritime University, Dalian

来源：

Algorithms | 2017年 / 10卷 / 03期

基金：

中国国家自然科学基金;

关键词：

Dynamic vehicle routing problem; Greedy strategy; Local search; Monarch butterfly optimization;

D O I：

10.3390/a10030107

中图分类号：

学科分类号：

摘要：

The dynamic vehicle routing problem (DVRP) is a variant of the Vehicle Routing Problem (VRP) in which customers appear dynamically. The objective is to determine a set of routes that minimizes the total travel distance. In this paper, we propose a monarch butterfly optimization (MBO) algorithm to solve DVRPs, utilizing a greedy strategy. Both migration operation and the butterfly adjusting operator only accept the offspring of butterfly individuals that have better fitness than their parents. To improve performance, a later perturbation procedure is implemented, to maintain a balance between global diversification and local intensification. The computational results indicate that the proposed technique outperforms the existing approaches in the literature for average performance by at least 9.38%. In addition, 12 new best solutions were found. This shows that this proposed technique consistently produces high-quality solutions and outperforms other published heuristics for the DVRP. © 2017 by the authors.

引用

共 30 条

[1]

Ismail Z., Solving the vehicle routing problem with stochastic demands via hybrid genetic algorithm-tabu search, J. Math. Stat., 4, (2008)

[2]

Oliveira S., de Souza S.R., Silva M.A.L., A solution of dynamic vehicle routing problem with time window via ant colony system metaheuristic, Proceedings of the 10th Brazilian Symposium on Neural Networks, pp. 21-26, (2008)

[3]

Belfiore P.C., Yoshizaki H.T.Y., Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in brazil, Eur. J. Oper. Res., 199, pp. 750-758, (2009)

[4]

Chen Z.L., Xu H., Dynamic column generation for dynamic vehicle routing with time windows, Transp. Sci., 40, pp. 74-88, (2006)

[5]

De Armas J., Melian-Batista B., Moreno-Perez J.A., Restricted Dynamic Heterogeneous Fleet Vehicle Routing Problem with Time Windows, Advances in Computational Intelligence, Part II, Proceedings of the 12th International Work-Conference on Artificial Neural Networks (IWANN 2013), pp. 36-45, (2013)

[6]

Wang G.G., Zhao X., Deb S., A novel monarch butterfly optimization with greedy strategy and self-adaptive, Proceedings of the 2015 Second International Conference on Soft Computing and Machine Intelligence (ISCMI), pp. 45-50, (2015)

[7]

Ghetas M., Yong C.H., Sumari P., Harmony-based monarch butterfly optimization algorithm, Proceedings of the 2015 IEEE International Conference on Control System, Computing and Engineering (ICCSCE), pp. 156-161, (2015)

[8]

Feng Y., Yang J., Wu C., Lu M., Zhao X.J., Solving 0-1 knapsack problems by chaotic monarch butterfly optimization algorithm with gaussian mutation, Memet. Comput., pp. 1-16, (2016)

[9]

Wang G.G., Hao G.S., Cheng S., Qin Q., A discrete monarch butterfly optimization for chinese TSP problem., Advances in Swarm Intelligence, Part I

[10]

Proceedings of the 7th International Conference (ICSI 2016), pp. 165-173, (2016)

← 1 2 3 →