# Online Optimization of Pickup and Delivery Problem Considering Feasibility
## 2 Pickup and Delivery Problem
### Problem Formulation  
Under the above preparations, we formulate the pickup and delivery problem at the update time \(\tau_{i}\). The cost function to be minimized is defined as follows:  
\[J_{i}=c_{i,1}+c_{i,2}+c_{i,3}. \tag{19}\]  
We describe \(c_{i,1}\), \(c_{i,2}\), and \(c_{i,3}\) in detail. At first, \(c_{i,1}\) is defined as follows:  
\[c_{i,1}=w_{1}\sum_{t=\tau_{1}}^{\tau_{i}+T_{f}}\sum_{l\in\mathcal{N}}\sum_{j\in \mathcal{C}\cup\mathcal{R}}p_{l,j}(t). \tag{20}\]  
\(p_{l}(t)\in\{0,1\}^{|\mathcal{V}|}\) is a binary variable vector for the agent \(l\in\mathcal{N}\), where \(t\in\{0,1,2,\dots,\}\) is discrete time. The \(j\)-th element \(p_{l,j}(t)\) of \(p_{l}(t)\) is 1 if the agent \(l\) is located at the vertex \(v_{j}\); otherwise, it is 0. The scalar \(w_{1}\) is a constant representing the weights and is determined through trial and error. In other words, Equation (20) implies the sum of the time spent at the vertices, except for the store for all agents. By reducing the value of this term, the running cost of the agents can be reduced. Next, \(c_{i,2}\) is defined as follows:  
\[c_{i,2}=w_{2}{\sum_{k}}\alpha_{k}(T_{k}-T_{\alpha_{k}}^{c}), \tag{21}\]  
where \(T_{k}\) is a variable that represents the time when the agent completes the delivery of order \(\alpha_{k}\) to the customer. Time \(T_{k}\) can be expressed as  
\[T_{k}={\sum_{l}}[T_{\alpha_{k}}^{c},...,\tau_{i}+T_{f}] \begin{bmatrix}z_{l,k} ^{\text{deil}}(T_{\alpha_{k}}^{c})\\ \vdots\\ z_{l,k}^{\text{deil}}(\tau_{i}+T_{f})\end{bmatrix} , \tag{22}\]  
where \(z_{l,k}^{\text{deil}}(t)\) is a binary variable that is 1 if agent \(l\) delivers order \(\alpha_{k}\) at time \(t\) and 0 if it does not. In (22), the column vectors are all zero, except for one element. Therefore, from this expression, we can find \(T_{k}\) when the value of \(z_{l,k}^{\text{deil}}(t)\) is equal to 1. The scalar \(\alpha_{k}\) is a variable that determines whether the delivery time of the order \(\alpha_{k}\) to be delivered meets the delivery deadline. The \(\alpha_{k}\) is defined as follows:  
\[\alpha_{k}= \begin{cases}1&\text{if }T_{k}\geq T_{\alpha_{k}}^{c},\\ 0&\text{otherwise}.\end{cases}  \tag{23}\]  
where \(\alpha_{k}=1\) implies that the time \(T_{k}\) when the order is delivered to the customer is later than the time limit \(T_{\alpha_{k}}^{c}\) to complete the delivery. The scalar \(w_{2}\) is a constant representing the weights and is determined through trial and error. In other words, Equation (21) is a summation of the delays in the delivery time. By reducing the value of this equation, we can obtain agent trajectories that satisfy the delivery time constraints of the order. Finally, \(c_{i,3}\) is defined as follows:  
\[c_{i,3}=w_{3}\sum_{t=\tau_{i}}^{\tau_{i}+T_{f}}\sum_{j\leq|\mathcal{S}|}\alpha_{j} (t)(\sigma_{j}(t)-d_{j}(t)), \tag{24}\]  
where \(\sigma_{j}(t)\) is a decision variable that represents the number of agents in store \(s_{j}\) at time \(t\). The constant \(d_{j}(t)\) is given in advance (see Section 2.3). We assume that the demand forecast is a prediction of when, where, and how many orders will be placed. The \(\alpha_{j}(t)\) is a binary variable that determines whether the number of agents in store \(s_{j}\) at time \(t\) satisfies the required number of agents in store \(s_{j}\) obtained from the demand forecast. The \(\alpha_{j}(t)\) is defined as follows:  
\[\alpha_{j}(t)= \begin{cases}1&\text{if }d_{j}(t)\geq\sigma_{j}(t),\\ 0&\text{otherwise},\end{cases}  \tag{25}\]  
where \(\alpha_{j}(t)=1\) implies that the number of agents in store \(s_{j}\) is less than the number of agents required for store \(s_{j}\) obtained from the demand forecast. The scalar \(w_{3}\) is a constant representing the weights and is determined through trial and error. In other words, Equation (24) is the sum of the number of agents that are less than the number of agents required for each store. By reducing the value of this equation, the agent trajectory can be obtained with more consideration given to demand forecasting.