# Optimal Agent-Based Pickup and Delivery with Time Windows and Electric Vehicles
## 3 PDPTW-EV Formulation  
The PDPTW-EV can be stated as the problem of finding optimal routes by minimizing the distance and the number of vehicles used in a given set of customer locations using mixed-integer linear programming (MILP). The model can be depicted as follows:Variables
* \(k\) denotes the number of vehicles;
* \(n\) denotes the number of pickup locations;
* \(m\) denotes the number of delivery locations;
* \(s\) denotes the number of charging stations. * \(q_{i}\) denotes the goods to pick up or deliver at location \(i\); positive value for pickup location and negative value for delivery locations; \(q_{0}=q_{n+m+1}=0\);
* \(e_{i}\) denotes the lower time limit to start a service at location \(i\);
* \(l_{i}\geq e_{i}\) denotes the upper time limit to start a service at location \(i\);
* \(d_{i}\) denotes the service duration at location \(i\);
* \(c^{k}_{ij}\) denotes the travel cost of vehicle \(k\) from location \(i\) to location \(j\);
* \(Q^{k}\) denotes the capacity of vehicle \(k\);
* \(t^{k}_{ij}\) denotes the time that vehicle \(k\) spends traveling from location \(i\) to location \(j\);
* \(c^{k}\) denotes the maximum battery capacity of vehicle \(k\);
* \(L^{k}_{i}\) denotes the remaining battery level of vehicle \(k\) at location \(i\). Sets
* \(P\) denotes the set of pickup locations \(P=\{1,\ldots,n\}\);
* \(D\) denotes the set of delivery locations \(D=\{1,\ldots,m\}\);
* \(K\) denotes the set of vehicles \(K=\{1,\ldots,k\}\);
* \(S\) denotes the set of charging stations \(S=\{1,\ldots,s\}\). Decision variables
* \(x^{k}_{ij}\) is 1 if vehicle \(k\) travels from location \(i\) to location \(j\), else it is 0;
* \(Q^{k}_{i}\) is the current load of the vehicle at location \(i\);
* start of the service of vehicle \(k\) at location \(i\);
* \(L^{k}_{ij}\) is the remaining battery level of vehicle \(k\) after traveling from location \(i\) to location \(j\). Let \(G=(V,E)\) be an undirected graph with \(V=P\cup D\cup\{0,n+m+1\}\cup S\) as the set of nodes and \(E=\{(i,j)\mid i,j\in V\}\) as the set of edges that denote the shortest paths between locations. The goal is to optimize vehicle fleet usage by minimizing the total travel cost to deliver all customer orders within their required time windows. The MILP formulation of the problem is given by the following:  
minimize \[\sum_{k\in K}\sum_{i\in V}\sum_{j\in V}c_{ij}x^{k}_{ij}\] (1) subject to \[\sum_{k\in K}\sum_{j\in V}x^{k}_{ij}=1,\quad\forall i\in P\cup D\] (2) \[\sum_{j\in V}x^{k}_{0j}=1,\quad\forall k\in K\] (3) \[\sum_{i\in V}x^{k}_{i,n+m+1}=1,\quad\forall k\in K\] (4) \[\sum_{i\in V}x^{k}_{ij}-\sum_{i\in V}x^{k}_{ji}=0,\quad\forall j \in P\cup D,k\in K\] (5) \[B^{k}_{i}\geq x^{k}_{ij}(B^{k}_{i}+d_{i}),\quad\forall i,j\in V,k \in K\] (6) \[B^{k}_{i}\leq B^{k}_{n+i},\quad\forall i\in P,k\in K\] (7) \[Q^{k}_{j}\geq x^{k}_{ij}(Q^{k}_{i}+q_{i}),\quad\forall i,j\in V,k\in K\] (8) \[\max\{0,q_{i}\}\leq Q^{k}_{i}\leq\min\{Q^{k},Q^{k}+q_{i}\},\quad \forall i\in P,k\in K\] (9) \[\sum_{j\in V}x^{k}_{ij}-\sum_{j\in V}x^{k}_{n+i,j}=0,\quad\forall i \in P,k\in K\] (10)\[\sum_{k\in K}\sum_{j\in V}x^{k}_{ij}=1,\quad\forall i\in P\cup D\]0  
\[\sum_{k\in K}\sum_{j\in V}x^{k}_{ij}=1,\quad\forall i\in P\cup D\]1  
\[\sum_{k\in K}\sum_{j\in V}x^{k}_{ij}=1,\quad\forall i\in P\cup D\]2  
where the objective function is Equation (1) and it minimizes total travel costs across all vehicles and locations. Equation (2) ensures that each pickup or delivery location is visited by a vehicle exactly once. Equation (3) states that each vehicle starts its route from the depot, while Equation (4) ensures that the route ends at the depot. Equation (5) guarantees that each location is either the start or the end of a route segment for each vehicle. The next two equations are related to time constraints.