key: cord-0047512-51ax0erq authors: Liu, Mingde; Shen, Yang; Shi, Yuhui title: A Hybrid Brain Storm Optimization Algorithm for Dynamic Vehicle Routing Problem date: 2020-06-22 journal: Advances in Swarm Intelligence DOI: 10.1007/978-3-030-53956-6_23 sha: 8c1e9d4823f89c3b86f739fb913afb2f267c0c16 doc_id: 47512 cord_uid: 51ax0erq The Dynamic Vehicle Routing Problem (DVRP) has many real-world applications and practical values. The objective of DVRP is to find the optimal routes for a fleet of vehicles to service the given customer requests, without violating the vehicle capacity constraint. In this paper, a hybrid algorithm is proposed for solving the DVRP with the objective to minimize the total distance of the vehicles. The Brain Storm Optimization in objective space (BSO-OS) is applied to guide the choice of different strategies for the periodic reoptimization of routes. In the BSO-OS procedure, Adaptive Large Neighborhood Search (ALNS) and Ant Colony System (ACS) are used to generate new solutions. The experiments on the DVRP benchmark and comparative studies are conducted, from which 12 out of 21 new best solutions are obtained by the proposed algorithm, and the other nine solutions are also very competitive. The experimental results show that the proposed algorithm is very effective and competitive. In recent years, logistics has drawn considerable attention in both research and industry. The Vehicle Routing Problem (VRP) is a classic logistics problem that seeks to find the optimal set of routes for a fleet of vehicles to service a given set of customers. Generally, the objective function of the VRP is to minimize the total travel distance. The VRP is proved NP-hard [10] , when the size of the problem increases, exact algorithms become very time consuming and maybe invalid [5] . Therefore, researchers tend to use heuristics to solve VRPs. In real-world scenarios, logistics companies or ride-hailing companies are facing the Dynamic Vehicle Routing Problems (DVRPs) [9] . For DVRPs, new customer requests arrive dynamically when the vehicles have already started servicing existing customer requests. Therefore, the routes of the vehicles have to be replanned at run time to minimize the cost, i.e, the routes have to be reoptimized. The reoptimization of DVRPs can be classified into two categories: periodic reoptimization and continuous reoptimization [14] . Generally, periodic reoptimization methods start with a first optimization of the initially known customer requests, then an optimization procedure solves the static VRP periodically with a fixed time interval [8] . For continuous reoptimization, whenever the new customer requests arrive, the reoptimization procedure starts to solve the new incoming data to update the routes [20] . Continuous reoptimization requires extensive computational resources. Also, if the new customer requests arrive very frequently, continuous reoptimization methods may repeat running and fail to update the routes. The advantages of periodic reoptimization are: 1) it transforms DVRPs to static VRPs to solve, and there exists extensive research on static VRPs; 2) the reoptimization is run independently during each time interval; 3) computational resources would be enough for each time interval; 4) it is more similar to practical applications. In this paper, we address the periodic reoptimization of DVRPs. Many researches have been carried out based on the benchmark for DVRPs proposed by Kilby et al. [8] and extended by Montemanni et al. [12] . An algorithm based on Ant Colony System (ACS) was first proposed by Montemanni et al. [12] for the DVRPs. The ACS makes use of the pheromone to track the good components of a good solution. When the next time interval comes, the good components can be used by the reoptimization procedure. In addition, Hanshar et al. applied Genetic Algorithm (GA) to solve the DVRP and compared it with Tabu Search (TS) [6] . The proposed DVRP-GA algorithm used inversion operator [11] for mutation and a problem-specific operator Best-Cost Route Crossover (BCRC) for crossover. Moreover, a comparative study was carried out between the Dynamic Adapted Particle Swarm Optimization (DAPSO) algorithm and the Variable Neighborhood Search (VNS) algorithm for the DVRPs [7] . In the comparative study, the proposed DAPSO algorithm uses adaptive memory to reuse the information from the previous solutions, and the VNS algorithm systematically changes neighborhoods to escape from local optima. Additionally, an enhanced GA-based system [1] for DVRP was proposed to improve the DVRP-GA. The main modifications include the initial population of the time slices, the selection process, swap mutation, and a Local Optimal Condition (LOC) detection and escape strategy. Brain Storm Optimization (BSO) [16, 18] was first proposed in 2011, which is inspired by the human brainstorming process. In DVRPs, choosing different strategies to optimize the current state is similar to the brainstorming process. In the BSO procedure, different strategies were applied for simulating the problem owners to choose good solutions that they believe in the brainstorming process. To reduce the computational cost, an enhanced BSO algorithm in objective space named BSO-OS [17] was proposed in 2015. In this paper, we applied the BSO-OS algorithm and proposed a hybrid BSO algorithm named BSO-DVRP for solving DVRPs. The overall frame of the algorithm is BSO, and in the BSO procedure, two popular VRP heuristics are applied to generate new solutions, which are Adaptive Large Neighborhood Search (ALNS) [15] and ACS [3] . The rest of this paper is organized as follows. Section 2 illustrates the definition and model of DVRP. Section 3 introduces the proposed BSO-DVRP algorithm. Section 4 first describes the benchmark and then evaluates the proposed algorithm. Section 5 concludes the paper. In this paper, we explore a DVRP model based on the benchmark proposed by Kilby et al. [8] and Montemanni et al. [12] , i.e., the DVRP model is a periodic reoptimization model. A DVRP model has a sequence of static VRP instances which contain all the customer requests known at each particular time, the periodic reoptimization needs to process the unserved customer requests. In the DVRP model, all vehicles depart from the same depot to service customer requests. A vehicle is allowed to return to the depot when all customer requests have been serviced or the capacity of the vehicle has exceeded. The DVRP has three parameters which are different from static VRP [1] , which are: 1) the available time indicating that when the customer request appeared; 2) the duration for each customer request; 3) the working day, which determines the available time to service the customer requests. For periodic reoptimization, the working day is divided into time slices. When new customer requests arrive during a time slice, these requests are delayed to the end of the time slice. Similar to static VRP, the objective function of DVRP is to minimize the total distance of all the routes. To better understand the DVRPs, Fig. 1 shows an example of DVRP. At time t0, the routes of the vehicles were planned based on the initially known customer requests. At time t1, when vehicles were executing their routes, some new customer requests arrived, then the reoptimization procedure was executed to process the remaining unserved customers. At time t2, when all the customers were serviced, the vehicles returned to the depot. For static VRPs, population based methods and local search or neighborhood search have been widely used. In the DVRPs, a difficult problem is when and how to choose good strategies to optimize the current state (time slice). A good strategy can not only avoid local optima, but also make use of the solutions obtained from previous time slice. In this paper, we choose BSO [17] as a framework to determine when and what strategy to choose, and choose ALNS [15] and ACS [3] from extensive heuristics for VRPs reported in literature as two good strategies to choose from. [3] is the most popular one among population based heuristics for VRP. The procedure of ACS is as the following: the ants depart from depot and select customers to service by pheromone one by one. When the ants can not service more customers, i.e., the vehicle capacity constraint can not be satisfied, the ants will return to the depot. Then, the ants will restart from the depot to service remained customers. The pheromone is updated after the ants completed their tours. ALNS [15] is the most popular algorithm among neighborhood search for VRP. There are some heuristics to remove customer requests and some other heuristics to insert removed requests into routes in ALNS. The adaptive method is used to select the removal heuristics and inserting heuristics according to the history information. BSO [16, 18] is inspired by the human brainstorming process. In the BSO procedure, different strategies were applied for simulating the problem owners to choose good solutions that they believe in the brainstorming process. Since the clustering operation in the BSO algorithm is very time consuming, an enhanced version of BSO algorithm in objective space named BSO-OS [17] is proposed. In the BSO-OS algorithm, solutions are sorted according to their fitness values, and the top perc e percentage are set as elitists, while the remaining are set as normals. New solutions are generated in four ways: 1) generate a new solution based on one randomly selected elitist; 2) generate a new solution based on two randomly selected elitists; 3) generate a new solution based on one randomly selected normal; 4) generate a new solution based on two randomly selected normals. To guide the choice of strategies, we applied the BSO-OS algorithm to choose different strategies, i.e., ALNS or ACS for the periodic reoptimization. In this paper, we propose a hybrid BSO algorithm named BSO-DVRP for solving the DVRPs. The pseudocode of the proposed algorithm is shown in Algorithm 1. The overall frame of the algorithm is BSO-OS, in which ALNS and ACS are applied to generate new solutions. The new solutions are generated based on one solution or two solutions, either in elitists or in normals. If one solution S i is selected, then ALNS is applied to perform a neighborhood search to generate a new solution. If two solutions S i , S j are selected, then these two solutions are sent to the ACS as the initial solution. By updating the pheromones, a new solution will be generated by ACS. In our experiments, we used the benchmarks proposed by Kilby et al. [8] and extended by Montemanni et al. [12] , which were designed based on popular static VRP benchmarks proposed by Taillard [19] , Christofides and Beasley [2] , and Fisher [4] . There are three datasets in the benchmark: the first dataset has 12 instances with 75 to 150 customers; the second dataset consists of seven instances with 50 to 199 customers; and the third dataset contains two instances with 71 and 134 customers. In the DVRP instances, three types of data were introduced: 1) available time indicating that when the request first appeared; 2) duration for each request; 3) working day, which is the length of the day. According to [13] , when the number of time slices n ts is set as 25, the tradeoff between the total distance and the computational cost is well balanced. In addition, the working day is set as 16 × 25 = 400. The parameter settings of the BSO-OS algorithm are listed in Table 1 . In Table 1 , perc e is the percentage of elitists, p elitists is the probability of choosing elitists, p one is the probability of choosing one solution, and max iter is the maximum number of iterations. The proposed algorithm was programmed in Python, and the DVRP experiments were conducted on an Intel Xeon E5-2650 CPU@2.30 GHz PC with 16 GB RAM. To evaluate the proposed algorithm, a comparative study has been conducted. The compared algorithms for DVRP are ACS [12] , DVRP-GA and TS [6] , DAPSO and VNS [7] , and the GA-based DVRP [1] . The experimental results are given in Table 2 , in which the best result for each instance is highlighted with bold fonts. The gap of the total distance (TD) is computed according to Eq. (1). where T D ours is the total distance obtained by the proposed algorithm, and T D best is the best total distance among all the compared algorithms for DVRP. A negative gap illustrates that the proposed algorithm outperforms all the other algorithms for DVRP, while a positive gap shows that the proposed algorithm is worse than the best result obtained by other algorithms. As is observed from Table 2 , 12 out of 21 new best solutions were found by the proposed algorithm, and the gap between our solutions and the previously best solutions ranges from −8.85% to −0.27%. From Table 2 , the other nine solutions obtained by the proposed algorithm have a gap range from 0.11% to 6.91%, which are also competitive. All these results showed that the proposed algorithm is effective to generate high quality solutions for the DVRPs. In this paper, we proposed a BSO algorithm named BSO-DVRP for solving DVRPs. By cutting the working day into a certain number of time slices, the DVRP was transformed into static VRP to solve. To guide the choice of strategies for the periodic reoptimization, the BSO-OS algorithm was applied. In addition, two popular heuristics, ALNS and ACS were selected for generating new solutions in the proposed BSO procedure. The experiments were conducted on the DVRP benchmark, and a comparative study with six algorithms for DVRP was carried out. A total of 12 out of 21 new best solutions were found by the proposed algorithm, and the other solutions obtained by the proposed algorithm were also competitive, which illustrated the effectiveness of the proposed algorithm. On solving periodic re-optimization dynamic vehicle routing problems The period routing problem Ant colony system: a cooperative learning approach to the traveling salesman problem A generalized assignment heuristic for vehicle routing The Vehicle Routing Problem: Latest Advances and New Challenges Dynamic vehicle routing using genetic algorithms A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests Dynamic VRPs: a study of scenarios The dynamic vehicle routing problem Complexity of vehicle routing and scheduling problems An Introduction to Genetic Algorithms A new algorithm for a dynamic vehicle routing problem based on ant colony system Ant colony system for a dynamic vehicle routing problem A review of dynamic vehicle routing problems An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows Brain storm optimization algorithm Brain storm optimization algorithm in objective space An optimization algorithm based on brainstorming process Parallel iterative search methods for vehicle routing problems Adaptive memory programming: a unified view of metaheuristics