# A Monarch Butterfly Optimization for the Dynamic Vehicle Routing Problem
## 1 Introduction  
The dynamic vehicle routing problem (DVRP) is a hard combinatorial optimization problem which is advanced by information and communication technologies that allow information to be obtained and processed in real time, typically used in distribution logistics and transportation systems. This system facilitates quick updating of transportation system plans in unexpected or uncertain events, for example if roads between two customers are blocked off, customers can modify their orders, or when the travel time for some routes is increased due to bad weather conditions or traffic congestion, etc. On the other hand, customers in the e-market place increasingly expect quicker and more flexible fulfilment of their transportation requests. In this context, the DVRP is becoming increasingly interesting and important. The DVRP is a variant of the VRP--the well-known NP-hard problem which is used in general cases. Because VRPs can be regarded as special cases of dynamic VRPs, dynamic VRPs are at least as hard as VRPs; therefore, research efforts mainly focus on metaheuristics and intelligent optimization algorithms. For example, [PERSON] [1] designed a hybrid GA and Tabu Search heuristic to solve the DVRP. [PERSON] et al. [2] applied ant colony system (ACS) techniques to solve the DVRP with time window constraints and a capacitated fleet. [PERSON] and [PERSON] [3] proposed a scatter search (SS) approach to deal with real-life heterogeneous fleet vehicle routing with time windows and split deliveries in Brazil. [PERSON] and [PERSON] [4] proposed a dynamic column generation algorithm for the DVRP with time windows. [PERSON] et al. [5] presented a general variable neighborhood search algorithm to solve a real-world application of the DVRP. In this paper, a monarch butterfly optimization (MBO) approach is proposed for the DVRP. Although MBO has been successfully applied to a great variety of hard combinatorial optimization problems ([PERSON] et al. (2015); [PERSON] et al. (2015); [PERSON] et al. (2015); [PERSON] et al. (2015)), this paper, as far as we know, proposes the first MBO-based algorithm for the DVRP. Biologically-inspired computation is a field focusing on the development of computational tools, modeled on the principles that exist in natural systems. The results presented in recent publications show that bio-inspired approaches are now highly competitive with other state-of-the-art heuristics. MBO was proposed by [PERSON] et al. [PERSON] et al. (2015) in 2015. Preliminary studies indicated that MBO is a very competitive metaheuristic algorithm [PERSON] et al. (2015), when compared with ant colony optimization (ACO) [PERSON] et al. (2015), biogeography-based optimization (BBO) [PERSON] et al. (2015) and differential evolution (DE) [PERSON] et al. (2015), is very easy to implement because it only needs to fine-tune migration and adjusting operators. In addition, MBO is very capable of finding the shortest paths [PERSON] et al. (2015). However, MBO may fail to reach optimal performance on average and standard values in certain test cases [PERSON] et al. (2015). This paper considers a version of the DVRP in which some of the customers' locations and associated demands are unknown at the start of the working day and arrive gradually as time passes. All vehicles start from the depot to serve yesterday's remaining customers after opening time and must return to the depot by the closing time. A similar problem was first introduced by [PERSON] et al. [PERSON] et al. (2015). In order to overcome the MBO shortcoming, a greedy algorithm is incorporated into the migration operation and butterfly adjusting operator, and a later perturbation procedure is applied after the butterfly adjusting operator, to maintain a balance between global diversification and local intensification. To the best of our knowledge, this is the first MBO implementation for the DVRP. It is tested using data sets introduced in [PERSON] et al. [PERSON] et al. (2015) and [PERSON] et al. [PERSON] et al.