# A Monarch Butterfly Optimization for the Dynamic Vehicle Routing Problem
## 2 Dynamic Vehicle Routing Problem (DVRP)
### Related Work  
The Dynamic Vehicle Routing Problem (DVRP) with capacity and time duration constraints was introduced by [PERSON] et al. [14] and further refined by [PERSON] et al. [15]. These authors proposed some benchmark instances for the DVRP and presented a study on how the degree-of-dynamism affects the final travel costs. [PERSON] et al. [15], who extended [PERSON] et al. 's work [14], considered a DVRP as an extension to the standard VRP, by decomposing a DVRP as a sequence of static VRPs, and then solving them using an ACS algorithm. Other optimization techniques have been applied. [PERSON] et al. [16] presented particle swarm optimization. [PERSON] et al. [17] proposed a hybrid large neighborhood search. In a recent survey, [PERSON] et al. [18] classified routing problems from the perspective of information quality and evolution. They introduced the notion of degree of dynamism, and presented a comprehensive review of applications and solution methods for dynamic vehicle routing problems. [PERSON] et al. [19] provided another survey in this area, which provided a deeper and more detailed analysis. Last but not least, [PERSON] et al. [20] shed more light into work in this area, over more than 3 decades, by developing a taxonomy of DVRP papers according to 11 criteria. Along with advances in technology, improvements to problem-solving methods have been made in order to interact with dynamic environments, and to combine fast responses with quality solutions. Based on the quality of information, [PERSON] et al. [18] classified DVRPs into two categories: deterministic and stochastic. The present work falls under the deterministic category, for which approaches are based on periodic or continuous re-optimization. Periodic re-optimization approaches typically commence at the beginning of the day, with an initial optimization that produces an initial set of routes; then the solution is re-optimized either whenever the available information changes, or at a fixed re-optimization interval. [PERSON] and [PERSON] [4] proposed a dynamic, column generation approach for solving a DVRP, with hard time windows, in which all requests need to be serviced. The authors used the concept of decision epochs over the planning horizon, which indicate the moments of the day when the re-optimization process is executed. [PERSON] et al. [15] employed an ACS to solve the dynamic VRP by dividing the overall planning horizon into periods (time slices), as in [PERSON] et al. [14]. During each time slice, a static problem is solved by considering all requests known at the beginning of this time slice. A similar approach was also employed by [PERSON] et al. [21], [PERSON] et al. [22] and [PERSON] [23]. In contrast, continuous re-optimization approaches commence at the beginning of operations with an initial set of routes, and the vehicles are informed only about their next destination. It keeps high quality solutions within an adaptive memory. A decision procedure is used to update the solutions in the adaptive memory whenever the available information is updated. Updates typically occur due to either a new dynamic customer request service, or the vehicle reaches a customer. [PERSON] et al. [24] were the first to employ continuous re-optimization. These authors proposed a Tabu Search heuristic to address the DVRP arising in a long-distance courier service, in which time windows could be violated at some cost. The approach keeps a pool of good solutions in its adaptive memory, which is used to generate initial solutions for a parallel Tabu Search. Whenever a new customer request arrives, it is checked against all the solutions from the adaptive memory to decide whether it should be accepted or rejected. A fast local search procedure is then applied to select the best solution. When the vehicle reaches a customer, the solution is also updated in the adaptive memory and the next destination of the vehicle is identified, based on the best solution.