An improved fireworks algorithm for the capacitated vehicle routing problem

Abstract

The capacitated vehicle routing problem (CVRP), which aims at minimizing travel costs, is a wellknown NP-hard combinatorial optimization. Owing to its hardness, many heuristic search algorithms have been proposed to tackle this problem. This paper explores a recently proposed heuristic algorithm named the fireworks algorithm (FWA), which is a swarm intelligence algorithm. We adopt FWA for the combinatorial CVRP problem with severalmodifications of the original FWA: it employs a new method to generate “sparks” according to the selection rule, and it uses a new method to determine the explosion amplitude for each firework. The proposed algorithm is compared with several heuristic search methods on some classical benchmark CVRP instances. The experimental results show a promising performance of the proposed method.We also discuss the strengths and weaknesses of our algorithm in contrast to traditional algorithms.

Keywords

fireworks algorithm / vehicle routing problem / computational intelligence

1 1 Introduction

Semi-supervised learning (SSL) is an effective learning paradigm to improve learning performance by attempting to exploit abundant unlabeled data when labels are scarce. It has been reported that, in certain cases, such as image classification, SSL methods can achieve the performance of purely supervised learning even when a substantial portion of the labels in a given data set has been discarded [1].

It is noticeable that the current success of SSL is mostly based on the close environment assumption where important factors between the labeled and unlabeled data are consistent. For example, all the unlabeled instances should belong to the class label set in labeled data, the features describing labeled and unlabeled data should be the same, and all labeled and unlabeled data should be sampled from an identical distribution. Fig.1 illustrates those consistent factors assumed in close environment SSL studies.

Fig.1 Typical consistent factors assumed in close environment semi-supervised learning

Full size|PPT slide

However, many real-world applications involve open environments [2] where class label set, feature space, and data distribution could be inconsistent between labeled and unlabeled data. The main reason lies in the fact that the collection process of unlabeled data is different from labeled data, which lacks human supervision and easily collects data that are inconsistent with the target task. It is also impossible to manually validate the quality of unlabeled data, otherwise it goes against the SSL’s purpose of reducing human labor. It has been widely reported that SSL suffers severe performance degradation problems with inconsistent unlabeled data and could be even worse than the simple supervised learning baseline which does not exploit more unlabeled data [3-8]. Such phenomena undoubtedly violate the expectations of SSL and limit its effectiveness in more practical tasks.

It seems the robust SSL in open environments is relevant to studies like out-of-distribution (OOD) detection [9-12], or open set recognition [13,14]. However, these studies either assume that there is an accurate classification model or sufficient labeled data, which limits their application in SSL. There are also some unsupervised OOD detection studies [15] utilizing the power of the contrastive learning [16] framework to learn better representation for OOD detection. However, although these studies do not require labels, they still need a large amount of in-distribution data for training, while in open environment SSL it is difficult to get the clean in-distribution unlabeled data.

Despite the grand challenges, many research efforts have recently been devoted to robust SSL in open environments. This paper will briefly introduce some advances in this line of research, focusing on approaches concerning inconsistent labels, inconsistent features, and inconsistent distributions between labeled and unlabeled data. Moreover, we introduce the benchmark dataset and performance measures applicable to evaluate the robustness of SSL in open environments and provide a public SSL toolkit for related research. Open research problems are also discussed for reference purposes.

2 2 Robust SSL in open environments

In the SSL task, we are given a set of training data which includes labeled data set ${\mathcal{D}}_l$ consists of $n$ labeled instances ${\mathcal{D}}_l=\{({\mathbf{x}}_1,{\mathbf{y}}_1),\dots ,({\mathbf{x}}_n,{\mathbf{y}}_n)\}$ and unlabeled data set ${\mathcal{D}}_u$ consists of $m$ unlabeled instances ${\mathcal{D}}_u=\{{\mathbf{x}}_{n+1},\dots ,{\mathbf{x}}_{n+m}\}$. Usually, $m\gg n$, $\mathbf{x}\in \mathcal{X}\in {\mathbb{R}}^d$, $\mathbf{y}\in \mathcal{Y}=\{1,\dots ,K\}$ where $d$ is the number of feature dimension and $K$ is the number of classes. The goal of SSL is to learn a model $f(\mathbf{x};\theta ):\{\mathcal{X};\mathrm{\Theta }\}\to \mathcal{Y}$ parameterized by $\theta \in \mathrm{\Theta }$ from training data to minimize the generalization risk $R(f)={\mathbb{E}}_{(X,Y)}[\ell (f(X;\theta ),Y)]$, where $\ell :\mathcal{Y}\times \mathcal{Y}\to \mathbb{R}$ refers to certain loss function, e.g., mean squared error or cross-entropy loss.

In open environments, unlabeled data could be inconsistent with labeled data in terms of class label space, feature dimension, and data distribution. We denote the degree of inconsistency as $t\in [0,1]$. A higher $t$ indicates a greater inconsistency, i.e., more unlabeled instances that are inconsistent with the target task. The robust SSL studies in open environments aim to decrease the negative impact of inconsistent unlabeled data, on the one hand, improve the performance via exploiting unlabeled data, and on the other hand, in the worst case, the SSL performance should not be worse than the supervised learning baseline which does not exploit more unlabeled data.

3 3 Label inconsistent

Close-environment SSL studies typically assume that the class label of any unlabeled instances should be a member of the given label space $\mathcal{Y}$. However, this assumption does not always hold. This is because unlabeled data is much easier to collect than labeled data in real-world applications, and the collection process of unlabeled data has less human verification. Thus, it is more likely for unlabeled data to have unseen classes that are irrelevant to the target task. For example, in the image classification task, unlabeled images crawled from Internet/social networking according to keywords usually contain broader category concepts than labeled data [5,6,17,18]. We illustrate label inconsistency in Fig.2 to help understand the problem.

Fig.2 Irrelevant classes occur in the unlabeled dataset

Full size|PPT slide

Many researchers have pointed out that SSL is not robust to irrelevant unseen classes of unlabeled data, and could perform even worse than the simple supervised learning method that uses only a small number of labeled data [4,5].

The straightforward idea to deal with this problem is to detect and remove these irrelevant unseen class unlabeled instances. It is noteworthy that this problem is different from OOD detection since OOD detection approaches typically require a large corpus of in-distribution labeled data and would fail due to the scarcity of labeled data in SSL. Recently, a simple yet effective approach was proposed to tackle the semi-supervised OOD detection issue [19]. This approach learns a new representation space via a novel distance measure in which OOD samples could be separated well with limited labeled data and in-distribution data.

Some approaches try to decrease the negative impact of these unseen class unlabeled instances in the training process. Various scoring mechanisms have been proposed to evaluate how much contribution an unlabeled instance has to the model training [20-22]. If the score is higher than the threshold the instance is retained, otherwise, the instance is discarded. In addition to the hard threshold, some works try to assign soft weight to the unlabeled training instances [5,23].

Instead of treating all irrelevant classes unlabeled instances as harmful, some researchers find these instances could also be helpful for model training. One promising way is to exploit the irrelevant unlabeled instances to help learn better representations via the self-supervised learning paradigm [24].

Robust SSL focuses on how to avoid the negative impact of unseen class unlabeled data. Meanwhile, some studies focus on the setting that the unseen classes in unlabeled data also need to be classified, which is called open-world SSL [25,26]. This line of research is more like class-incremental learning [27], and different from the goal of robust SSL in open environments.

4 4 Feature inconsistent

Close-environment SSL studies typically assume that all unlabeled instances reside in the same feature space with the labeled data. Unfortunately, this does not always hold. For example, in the image classification task, the labeled data are all color images while the unlabeled data could contain grayscale images, resulting in the loss of two color channels. In tasks dealing with tabular data, such as financial analysis tasks or recommendation systems [28], decremental or incremental features in unlabeled data are more common. Fig.3 illustrates the feature inconsistent problem in SSL.

Fig.3 Feature inconsistent in SSL

Full size|PPT slide

As pointed out by [18], close environment SSL methods could suffer severe performance degradation when facing the feature inconsistent between labeled and unlabeled data.

Compared with the label inconsistent problem, detecting which unlabeled instances have inconsistent features with the target task is much easier since validating the feature $\mathbf{x}$ is irrelevant to the label. Therefore, the straightforward method to address the feature inconsistent problem is to detect and remove all inconsistent unlabeled instances.

However, this baseline method cannot effectively utilize the information behind these unlabeled data, resulting in limited performance improvement. Another approach that readily comes to mind is to remove all incremental features and fill in decremental features, whereas how to fill the missing feature to ensure the SSL performance will not degrade is still a challenging problem [18].

There are also studies focusing on the adversarial feature inconsistency unlabeled examples, which can be categorized into two aspects: Attack and Defense. Semi-supervised attack techniques study how to generate adversarial unlabeled examples that cause SSL predictions to be incorrect. The major techniques can be categorized as misleading sequence injection, which aims to inject a sequence of synthetically unlabeled examples into the unlabeled training data and cause the model to make wrong predictions [29] and adversarial perturbation generation, which aims to learn a feature perturbation generator for the training examples and making the model output wrong predictions when training with these perturbed examples [30,31]. The defense techniques study how to make the SSL robust to adversarial unlabeled examples. The major techniques can be categorized as robust regularization, which aims to design regularization terms to the objective of SSL directly [32,33] and the combination with classical distribution robust optimization methods [34].

Recent studies of robust SSL with feature inconsistency mainly focus on the image classification task. It is noteworthy that tabular data is also commonly encountered in real scenarios [28]. Compared with image data, the feature inconsistent problem is more commonly occurring in tabular data. Robust SSL with inconsistent features on tabular data is an important yet understudied problem.

5 5 Distribution inconsistent

Close-environment SSL studies typically assume that all labeled and unlabeled data are independent samples from an identical distribution (i.e., $i.i.d.$ samples). Unfortunately, this does not always hold. Taking the image classification as an example again, the labeled data may sampled from natural images. In contrast, the unlabeled data may be selected from the internet according to some keywords and may include cartoon images [35]. These problems also commonly happen in scenarios like sentiment analysis [5], remote sensing [36], legal judgment [37], etc. Fig.4 illustrates that ignoring the data distribution inconsistent mismatch may lead to seriously downgraded performance.

Fig.4 Distribution inconsistent between labeled and unlabeled data in SSL

Full size|PPT slide

There have been plentiful studies concerning distribution shifts such as prior probability shifts, covariate shifts, and concept shifts. However, the relevant studies mainly focus on the training/testing distribution change and are conducted under the umbrella of domain adaptation or transfer learning [38]. In SSL studies the distribution occurs within the training data. To be able to handle various kinds of data distribution inconsistent between labeled and unlabeled data is an important requirement for robust SSL in open environments.

The straightforward method is to treat labeled data as the target domain and unlabeled data as the source domain and then apply domain adaptation techniques to learn new representations for all training instances to eliminate the distribution mismatch [39-41]. However, due to the label scarcity in SSL, these methods can only consider the adaptation in an unsupervised manner and ignore task-related label information.

Recent work presented a theoretical framework that presents three main reasons why SSL algorithms can not perform well with inconsistent distributions: coupling between the pseudo-label predictor and the target predictor, biased pseudo labels, and restricted instance weights [42]. To address these challenges, they provided a new method called bidirectional adaptation that can adapt to the distribution of unlabeled data for debiased pseudo-label prediction and to the target distribution for debiased target prediction, thereby mitigating the above shortcomings.

Moreover, some works focus on the problem that unlabeled data distribution is long-tailed and report that SSL suffers performance degradation on tail classes [43-47]. Conventional long-tailed techniques can not be applied directly due to the label scarcity in SSL. The general principle is to design distribution alignment techniques to calibrate the distribution of pseudo-labels to align with the target distribution [43,44,46].

6 6 Evaluation benchmark

Conventional SSL studies mainly evaluate performance on standard image classification datasets and report classification accuracy. How to fair evaluate the robustness of SSL methods in open environments is under-considered. In this section, we briefly introduce some datasets, applicable performance measures, and an open-sourced SSL toolkit.

6.1 6.1 Datasets

Constructing open environment SSL benchmarks that contain different extents of inconsistency between labeled and unlabeled data is important for the evaluation of robust SSL algorithms. Recently, a more realistic SSL benchmark included both label, feature, and distribution inconsistent has been provided [18]. The benchmark involves various data types in machine learning, including tabular datasets from the UCI dataset, widely applied image datasets, and text datasets. Specifically, to simulate the inconsistent labels, they construct inconsistent labeled space by randomly selecting some classes and discarding the labeled data belonging to these classes. To simulate the inconsistent features, they randomly mask features for tabular data and convert the images to grayscale, resulting in the loss of two color channels for image datasets. For the text datasets, they employ text truncation, and truncated portions are filled with “$<pad>$”. To simulate the data distribution, for image and text datasets, they adopt the Image-CLEF [48] and the IMDA/Amazon [49,50] to construct the labeled and unlabeled data which are natural distribution shifts. For tabular datasets, they calculate the centroids of each class and use the distance between instances and class centroids to filter instances, thus constructing an environment with inconsistent data distribution.

6.2 6.2 Performance measures

To achieve a fair and comprehensive evaluation of robust SSL in open environments, only reporting the classification accuracy or error is not enough. A series of performance metrics tailored for robust SSL in open environments have been proposed recently [18]. These metrics begin by defining a function $Acc(t)$, which quantifies the change in classification accuracy as a function of the inconsistency level $t$. This function is used to construct the Robustness Analysis Curve (RAC) that maps the inconsistency level $t$ to the corresponding accuracy $Acc(t)$. Unlike conventional SSL evaluations that focus solely on $Acc(0)$ or a specific $Acc(t)$, various performance metrics are proposed based on the RAC that include Area Under the RAC Curve (AUC) which captures the overall robustness of SSL approaches; Expected Accuracy (EA) which describes the average performance across all inconsistency levels; Worst-Case Accuracy (WA) which identifies the lowest accuracy level, representing performance in the worst-case scenario; Expected Variation Magnitude (EVM) which captures the average magnitude of performance variation; Variation Stability (VS) which quantifies the stability of the performance variation; Robust Correlation Coefficient (RCC) which captures the overall trend of performance variation. The detailed formulation of these metrics is presented in Tab.1.

Tab.1 Performance metrics for robust SSL in open environments. $Acc(t)$ describe the change in classification accuracy with the inconsistency extent $t$, $P_T(t)$ is the distribution for $t$, $Ac{c}^{\prime }(\cdot )$ indicate the first derivative

Area Under the Curve (AUC)	$\text{AUC}(Acc)={\int }_0^{1}Acc(t)\mathrm{d}t$
Expected Accuracy (EA)	$\text{EA}(P_T,Acc)={⟨P⟩}_T,Acc⟨=⟩{\int }_0^1{P}_T(t)Acc(t)\mathrm{d}t$
Worst-Case Accuracy (WA)	$\text{WA}(Acc)=\underset{t\in [0,1]}{min}Acc(t)$
Expected Variation Magnitude (EVM)	$\text{EVM}(Acc)={\int }_0^1|Ac{c}^{\prime }(t)|\mathrm{d}t$
Variation Stability (VS)	$\text{VS}(Acc)={\int }_0^1[Ac{c}^{\prime }(t)-({\int }_0^{1}Ac{c}^{\prime }(t)\mathrm{d}t){]}^2\mathrm{d}t$
Robust Correlation Coefficient (RCC)	$\text{RCC}(Acc)=\frac{{\int }_0^{1}Acc(t)\cdot t\mathrm{d}t-{\int }_0^{1}Acc(t)\mathrm{d}t}{\sqrt{{\int }_0^1{t}^2\mathrm{d}t-1}\cdot \sqrt{{\int }_0^{1}Ac{c}^2(t)\mathrm{d}t-({\int }_0^{1}Acc(t)\mathrm{d}t{)}^2}}$

6.3 6.3 Open-sourced toolkit

To provide easier evaluation and implementation of SSL algorithms, an open-sourced SSL toolkit: LAMDA-SSL is released [51]. LAMDA-SSL incorporates more than 30 SSL algorithms, supports various data types, and is compatible with other popular machine learning toolkits such as “scikit-learn” and “pytorch”. The toolkit is available at the website of ygzwqzd.github.io/LAMDA-SSL.

7 7 Open challenges

Though robust SSL in open environments has attracted much attention, it is still in its infancy. We hope to propose new research directions to broaden and boost robust SSL research.

Theoretical issues. Many theoretical problems about robust SSL have not been addressed yet. For example, when the inconsistent unlabeled data is helpful or harmful, how the generalization performance varies with different inconsistent extents, etc. More efforts are desired to be devoted.

General data types. SSL studies mainly focus on homogeneous data, especially image data. Tabular data is also a commonly occurring data in practical tasks [28,52,53]. The heterogeneous property of tabular data causes the failure of SSL algorithms. For example, consistency regularization, which is the most important technique in SSL, encourages the model to have similar output distribution on an instance and its augmented variants. The notion of augmentation simply does not exist in tabular data. Therefore, there is an urgent need to develop robust SSL techniques for more general data types.

Exploiting pre-trained models. With the success of the “pre-train and fine-tune” paradigm, more and more pre-trained models have been released. Similar to the goal of SSL, selecting and adapting helpful pre-trained models can also decrease the labeled data requirement for the target task [54,55]. Thus, how to bridge the pre-trained model with SSL is a promising direction. Recently, there have been some studies that try to exploit SSL techniques with large language models [56] and vision-language models [57]. However, the robustness of these methods after exploiting more unlabeled data is still an unaddressed problem.

From perception to decision-making. Current SSL studies mainly focus on perceptual tasks such as image classification, while practical tasks often encounter decision-making tasks that involve interaction with the environment. The dynamic of environments poses significant challenges to robustness, meanwhile, high-quality data is expensive in decision-making tasks, posing a great need for SSL. Many researchers have been exploring how to utilize unlabeled data for reinforcement learning [58,59] on these tasks, including reward-free or action-free data [60,61]. Therefore, it is important to broaden robust SSL studies into decision-making tasks with interactive environments.

8 8 Conclusions

This paper introduces open environments SSL. We present a definition of this problem, in which unlabeled data could contain label/feature/distribution inconsistent with the target task, and briefly introduce some research advances in this line of research. Although we consider these inconsistent problems separately, in practice they often occur simultaneously. It can hardly be a thorough review of all the relevant work and is mostly a brief review of general principles and strategies rather than specific learning algorithms. The quality of unlabeled data is hard to validate and it is fundamentally important to enable SSL to achieve excellent performance in the usual case while keeping satisfactory performance no matter what unexpected unfortunate issues occur in unlabeled data. This is crucial for achieving robust SSL in practical tasks.

References

[1] Dantzig G B, Ramser J H. The truck dispatching problem. Management Science, 1959, 6(1): 80–91

[2] Fukasawa R, Longo H, Lysgaard J, de Aragão M P, Reis M, Uchoa E, Werneck R F. Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming, 2006, 106(3): 491–511

[3] Baldacci R, Christofides N, Mingozzi A. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming, 2008, 115(2): 351–385

[4] Clarke G, Wright J W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 1964, 12(4): 568–581

[5] Golden B L, Magnanti T L, Nguyen H Q. Implementing vehicle routing algorithms. Networks, 1977, 7(2): 113–148

[6] Altinkemer K, Gavish B. Parallel savings based heuristics for the delivery problem. Operations Research, 1991, 39(3): 456–469

[7] Gillett B E, Miller L R. A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 1974, 22(2): 340–349

[8] Beasley J E. Route first-cluster second methods for vehicle routing. Omega, 1983, 11(4): 403–408

[9] Lin S. Computer solutions of the traveling salesman problem. The Bell System Technical Journal, 1965, 44(10): 2245–2269

[10] Kindervater G A, Savelsbergh M W. Vehicle routing: handling edge exchanges. In: Aarts E, Lenstra J, eds. Local Search in Combinatorial Optimization. Chichester: Wiley, 1997, 337–360

[11] Toth P, Vigo D. The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002

[12] Alba E, Dorronsoro B. Computing nine new best-so-far solutions for capacitated VRP with a cellular genetic algorithm. Information Processing Letters, 2006, 98(6): 225–230

[13] Mester D, Bräysy O. Active-guided evolution strategies for large-scale capacitated vehicle routing problems. Computers & Operations Research, 2007, 34(10): 2964–2975

[14] Nagata Y, Bräysy O. Edge assembly-based memetic algorithm for the capacitated vehicle routing problem. Networks, 2009, 54(4): 205–215

[15] Bullnheimer B, Hartl R F, Strauss C. An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research, 1999, 89: 319–328

[16] Bell J E, McMullen P R. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 2004, 18(1): 41–48

[17] Reimann M, Doerner K, Hartl R F. D-ants: savings based ants divide and conquer the vehicle routing problem. Computers & Operations Research, 2004, 31(4): 563–591

[18] Yu B, Yang Z Z, Yao B. An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research, 2009, 196(1): 171–176

[19] Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 2004, 31(12): 1985–2002

[20] Baker B M, Ayechew M. A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 2003, 30(5): 787–800

[21] Thangiah S R, Osman I H, Sun T. Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows. Technical Report SRU CpSc-TR-94-27, 1994

[22] Vidal T, Crainic T G, Gendreau M, Lahrichi N, Rei W. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 2012, 60(3): 611–624

[23] Marinakis Y, Marinaki M, Dounias G. A hybrid particle swarm optimization algorithm for the vehicle routing problem. Engineering Applications of Artificial Intelligence, 2010, 23(4): 463–472

[24] Ai T J, Kachitvichyanukul V. Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering, 2009, 56(1): 380–387

[25] Szeto W, Wu Y, Ho S C. An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 2011, 215(1): 126–135

[26] Alfa A S, Heragu S S, Chen M. A 3-opt based simulated annealing algorithm for vehicle routing problems. Computers & Industrial Engineering, 1991, 21(1–4): 635–639

[27] Osman I H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 1993, 41(4): 421–451

[28] Tavakkoli-Moghaddam R, Safaei N, Gholipour Y. A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation, 2006, 176(2): 445–454

[29] Taillard É. Parallel iterative search methods for vehicle routing problems. Networks, 1993, 23(8): 661–673

[30] Gendreau M, Hertz A, Laporte G. A tabu search heuristic for the vehicle routing problem. Management Science, 1994, 40(10): 1276–1290

[31] Toth P, Vigo D. The granular tabu search and its application to the vehicle-routing problem. INFORMS Journal on Computing, 2003, 15(4): 333–346

[32] Lai D S, Demirag O C, Leung J M. A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transportation Research Part E: Logistics and Transportation Review, 2016, 86: 32–52

[33] Prins C. A GRASP × evolutionary local search hybrid for the vehicle routing problem. In: Pereira F B, Tavares J, eds. Bio-inspired algorithms for the Vehicle Routing Problem. Berlin: Springer-Verlag, 2009, 35–53

[34] Penna P H V, Subramanian A, Ochi L S. An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 2013, 19(2): 201–232

[35] Bräysy O. A reactive variable neighborhood search for the vehiclerouting problem with time windows. INFORMS Journal on Computing, 2003, 15(4): 347–368

[36] Kytöjoki J, Nuortio T, Bräysy O, Gendreau M. An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Computers & Operations Research, 2007, 34(9): 2743–2757

[37] Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 2006, 40(4): 455–472

[38] Tan Y, Zhu Y. Fireworks algorithm for optimization. In: Proceedings of International Conference on Swarm Intelligence. 2010, 355–364

[39] Pei Y, Zheng S, Tan Y, Takagi H. An empirical study on influence of approximation approaches on enhancing fireworks algorithm. In: Proceedings of IEEE International Conference on Systems, Man, and Cybernetics. 2012, 1322–1327

[40] Zheng S, Janecek A, Tan Y. Enhanced fireworks algorithm. In: Proceedings of IEEE Congress on Evolutionary Computation. 2013, 2069–2077

[41] Zheng S, Janecek A, Li J, Tan Y. Dynamic search in fireworks algorithm. In: Proceedings of IEEE Congress on Evolutionary Computation. 2014, 3222–3229

[42] Zheng Y J, Xu X L, Ling H F, Chen S Y. A hybrid fireworks optimization method with differential evolution operators. Neurocomputing, 2015, 148: 75–82

[43] Janecek A, Tan Y. Swarm intelligence for non-negative matrix factorization. International Journal of Swarm Intelligence Research, 2011, 2(4): 12–34

[44] He W, Mi G, Tan Y. Parameter optimization of local-concentration model for spam detection by using fireworks algorithm. In: Proceedings of International Conference on Swarm Intelligence. 2013, 439–450

[45] Zheng Y J, Song Q, Chen S Y. Multiobjective fireworks optimization for variable-rate fertilization in oil crop production. Applied Soft Computing, 2013, 13(11): 4253–4263

[46] Pholdee N, Bureerat S. Comparative performance of meta-heuristic algorithms for mass minimisation of trusses with dynamic constraints. Advances in Engineering Software, 2014, 75: 1–13

[47] Reddy K S, Panwar L K, Kumar R, Panigrahi B K. Distributed resource scheduling in smart grid with electric vehicle deployment using fireworks algorithm. Journal of Modern Power Systems and Clean Energy, 2016, 4(2): 188–199

[48] Saravanan B, Kumar C, Kothari D. A solution to unit commitment problem using fire works algorithm. International Journal of Electrical Power & Energy Systems, 2016, 77: 221–227

[49] Liu Z, Feng Z, Ke L. Fireworks algorithm for the multi-satellite control resource scheduling problem. In: Proceedings of IEEE Congress on Evolutionary Computation. 2015, 1280–1286

[50] Abdulmajeed N H, Ayob M. A firework algorithm for solving capacitated vehicle routing problem. International Journal of Advancements in Computing Technology, 2014, 6(1): 79–86

[51] Tan Y. Discrete firework algorithm for combinatorial optimization problem. In: Tang Y, eds. Fireworks Algorithm. Berlin: Springer- Verlag, 2015, 209–226

[52] Stützle T, Hoos H H. Max–min ant system. Future Generation Computer Systems, 2000, 16(8): 889–914

[53] Bräysy O, Gendreau M. Vehicle routing problem with time windows, part I: route construction and local search algorithms. Transportation Science, 2005, 39(1): 104–118

[54] Christofides N, Mingozzi A, Toth P. The vehicle routing problem. In: Christofides N, Mingozzi A, Toth P, et al., eds. Combinatorial Optimization. Chichester: Wiley, 1979, 315–338

[55] Golden B L, Wasil E A, Kelly J P, Chao I M. The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results. In: Crainic T G, Laporte G, eds. Fleet Management and Logistics. Springer US, 1998, 33–56

[56] Lee C, Lee Z, Lin S, Ying K. An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem. Applied Intelligence, 2010, 32(1): 88–95

[57] Lysgaard J, Letchford A N, Eglese R W. A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 2004, 100(2): 423–445

RIGHTS & PERMISSIONS

2018 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature