## 4 Implementation and Deployment  
In this section, we discuss implementation, deployment, and testing efforts that have been addressed within the EMERGE initiative with respect to the algorithmic components of the system. Specifically, among all algorithms that have been considered and implemented in said system, we provide the details of the component that takes care of handling a specific problem of the class of problems discussed in Section 3, namely, the pickup and delivery multi-vehicle problem with time windows, whose solution is essential to coordinating vehicles to perform time-constrained operations requested by customers/users of the system. In more detail, daily, on the basis of requests provided to the system by users, vehicles have to be provided with routes to follow in the geographical area (road network) where they are operating in order to visit locations, as indicated by users, within certain intervals of time to perform operations of pickup or delivery. These routes have to be computed by considering optimization criteria, such as minimizing the makespan for completing all operations. Each request of a user, more precisely, specifies (i) a given location to visit; (ii) a corresponding time window within the day when at least one vehicle of the fleet must reside in said location; (iii) the type of operation to perform (either pickup or delivery). Figure 11: Formalization of mccp. Pickup and delivery operations concern fixed, small-sized payloads, so the capacity of vehicles is not taken into account. The above can be effectively modeled by the optimization problem on graphs, as shown in Figure 12. An example, in graphical form, of a generic input instance to the pickup and delivery problem with time windows taken from [[https://developers.google.com/optimization/routing/pickup_delivery](https://developers.google.com/optimization/routing/pickup_delivery)]([https://developers.google.com/optimization/routing/pickup_delivery](https://developers.google.com/optimization/routing/pickup_delivery)) (accessed on 25 March 2024) is shown in Figure 13. Observe that this problem, like the problems discussed in Section 3, is NP-hard since it includes instances of the TSP as a special case (when the fleet consists of a single vehicle and each time window is large enough to not represent a constraint). This implies that, for computing optimal solutions, no exact algorithm can be designed unless P = NP. Hence, an approximation algorithm must be considered. _Input:_ A set \(N\) of nodes, where node 0 represents the depot while nodes \(1,2,\ldots,n\) represent users' locations; a set \(A\) of arcs representing feasible routes between nodes; a set \(K\) of vehicles, where \(k\in K\) represents a vehicle. For each node \(i\in N\), we have the following parameters: \(t_{i}\): service time at a user's location \(i\); \((e_{i},l_{i})\): time window for user \(i\), where \(e_{i}\) is the earliest arrival time, and \(l_{i}\) is the latest arrival time; and \(c_{ij}\): cost (distance) of traversing arc \((i,j)\). _Feasible Solution:_ Assignment to decision variables: (i) \(\cup_{(i,j,k)\in A\times K}\{x_{ij}^{k}\}\), where \(x_{ij}^{k}=1\) if vehicle \(k\) traverses arc \((i,j)\) and 0 otherwise; (ii) \(\cup_{(i,k)\in N\times K}\{s_{ik}\}\), where \(s_{ik}\) is the arrival time at a user's location \(i\) for vehicle \(k\), with the following constraints:  
1. Each user's location must be visited exactly once, i.e., \(\sum_{i\in N,i\
eq j}x_{ij}^{k}=1\quad\forall j\in N,\forall k\in K\) and \(\sum_{j\in N,j\
eq i}x_{ij}^{k}=1\quad\forall i\in N,\forall k\in K\);
2. Flow conservation, i.e., \(\sum_{i\in N,i\
eq j}x_{ij}^{k}-\sum_{k\in N,k\
eq j}x_{jk}=0\quad\forall j \in N,\forall k\in K\);
3. Time-window constraints, i.e., \(e_{i}\leq s_{ik}\leq l_{i}\quad\forall i\in N,\forall k\in K\);
4. Arrival time computation, i.e., \(s_{jk}\geq s_{ik}+t_{i}+M(1-x_{ij}^{k})\quad\forall i\in N,\forall j\in N,j \
eq i,\forall k\in K\), where \(M\) is a sufficiently large constant;
5.