# A Monarch Butterfly Optimization for the Dynamic Vehicle Routing Problem
## 2 Dynamic Vehicle Routing Problem (DVRP)  
### Problem Description  
To allow better understanding of the DVRP, Figure 1 shows a simple example of a dynamic vehicle routing problem. In the example, two uncapacitated vehicles must service both advance- and immediate-request customers. The static customers are represented by white nodes, while those that are immediate requests are depicted by black nodes. The dashed lines represent the two routes that the dispatcher has planned prior to the vehicles leaving the depot (Figure 1A). The two dash-dotted lines indicate the vehicle positions at the time the dynamic requests appear. Ideally, the dispatcher routes should be adjusted to fulfill the dynamic customers' requests (Figure 1B). Finally, the vehicles deliver the demands of all customers and return to the depot (Figure 1C). The study problem concerns routing a fleet of capacitated vehicles in real time to deliver goods ordered by a partially-known set of customers. There is a fleet of \(K\) homogenous vehicles, each with an identical capacity (\(Q\)), and a set of \(n\) customers {1, 2,..., \(n\)} is considered. The problem can be modeled by an undirected graph, \(G=(V,E)\), where \(V\) is a vertex set and \(E\) is an edge set (\(V=\{0\}\cup\subset\cup D\), and \(E=\{(i,j)\mid i,j\in V,\,i<j\}\)). Vertex \(0\) denotes a depot, which has a working time from \(e_{0}\) to \(l_{0}\) (\(0\leq e_{0}<l_{0}\)). C is a set of customers (requests) to be serviced. For each customer, (\(I\in S\cup D\)), there is a location (\(x_{i},y_{i}\)), a demand of goods (\(d_{i}\)), an appearance moment (\(a_{i}\) (\(e_{0}\leq a_{i}\leq l_{0}\))), and a service time (\(s_{i}\)). At the same time, each edge is defined by a non-negative distance (\(c_{ij}\)) and the travel time (\(t_{ij}\)) between all customers' locations. For DVRPs, there are two sets of customers: \(S\) and \(D\). \(S\) is composed of static customers, who are known from an earlier working day, and \(D\) includes all dynamic customers,who appear with time. A solution, \(S\), is composed of a set of routes satisfying all customers' demands once. Each route (\(R_{k}\in S\)) starts and ends at the depot, and does not exceed the vehicle capacity (\(Q\)). A route consists of a sequence of customers to visit (\(R_{k}=\{0,\ldots,j,\ldots,0\}\)), where \(j\in V\) denotes the \(j\)-th customer. For each customer (\(I\in R_{k}\)), \(w_{i}\) is the vehicle's waiting time, and the vehicle's arriving time (\(b_{i}\)) should satisfy \(b_{i}=b_{i-1}+s_{i-1}+w_{i-1}+t_{i-1j}\) (\(b_{0}=e_{0}\)), when we reversely calculate the latest arrival time with \(z_{i}=z_{i+1}-t_{i+1,i}-s_{i}\) (\(z_{i+1}=l_{0}\)). Similar to [14], we also divide a working day (\(T\)) into time slices (\(n_{ts}\)), each with an equal length of time (\(T/n_{ts}\), where \(T=l_{0}-e_{0}\)), where \(TS=\{TS_{1},TS_{2},\ldots,TS_{ts}\}\). Each time slice represents a partial static VRP, where \(TS_{1}\) only includes static customers in \(S\). The equation \(TS\backslash TS_{1}\) considers the customers received at the previous time slice and those who have not been visited yet. Hence, two decision variables, \(x_{ijk}\) and \(y_{ik}\), are defined as follows:  
\(x_{ijk}=1\) if the edge (\(i,j\)) is visited by vehicle \(k\) and \(0\) in all other cases. \(y_{ik}=1\) if customer \(i\) is visited by vehicle \(k\) and \(0\) in all other cases. The general mathematical model for DVRP is described as follows:  
\[\min\sum_{(i,j)\in E}\sum_{k\in K}c_{ij}\cdot x_{ijk} \tag{1}\]  
s.t.