Feature Construction for Meta-heuristic Algorithm Recommendation of Capacitated Vehicle Routing Problems
ACM Transactions on Evolutionary Learning and Optimization · 2021
DOI: 10.1145/3447540 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Evolutionary Learning and Optimization, 2021. Verfasst von Hao Jiang und 4 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 75 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Anhui Provincial Natural Science Foundation.
Abstract (Originalsprache)
The algorithm recommendation is attracting increasing attention in solving real-world capacitated vehicle routing problems (CVRPs), due to the fact that existing meta-heuristic algorithms often show different performances on different CVRPs. To effectively perform algorithm recommendation for CVRPs, it becomes vital to extract suitable features to characterize the CVRPs accurately. To this end, in this article three groups of penetrating features are proposed to capture the characteristics of CVRPs. The first group consists of some basic features of CVRPs, where several features are suggested to capture the distribution of customer demand, the relationship between customer demand and vehicle capacity, besides some common attributes widely used in CVRPs. The second group is composed of the features extracted from some CVRP solutions generated by local search, where in addition to the feasible and better solutions, the worse solutions and the distribution of travel cost are also used to measure the sensitivity of CVRPs to local search operations. The third group is made up of image features obtained by depicting CVRP instances through images, which is first introduced by us to enhance the generalization of algorithm recommendation. Furthermore, based on the three groups of features, an algorithm recommendation method called ARM-I is built on the basis of a KNN classifier to recommend suitable algorithm for CVRPs. Experimental results on several selected benchmarks demonstrate the effectiveness of the designed features. More interestingly, the proposed ARM-I shows high generalization on real-world instances.
Förderung
- National Natural Science Foundation of China
- Anhui Provincial Natural Science Foundation
Zitieren
APA
Jiang, H., Wang, Y., Tian, Y., Zhang, X., & Xiao, J. (2021). Feature Construction for Meta-heuristic Algorithm Recommendation of Capacitated Vehicle Routing Problems. ACM Transactions on Evolutionary Learning and Optimization. https://doi.org/10.1145/3447540
Vancouver
Jiang H, Wang Y, Tian Y, Zhang X, Xiao J. Feature Construction for Meta-heuristic Algorithm Recommendation of Capacitated Vehicle Routing Problems. ACM Transactions on Evolutionary Learning and Optimization. 2021. doi:10.1145/3447540
BibTeX
@article{Jiang2021,
author = {Jiang, Hao and Wang, Yuhang and Tian, Ye and Zhang, Xingyi and Xiao, Jianhua},
title = {Feature Construction for Meta-heuristic Algorithm Recommendation of Capacitated Vehicle Routing Problems},
journal = {ACM Transactions on Evolutionary Learning and Optimization},
year = {2021},
doi = {10.1145/3447540}
}
EUVIMED