# Online and Offline Model for Housekeeping Order Assignment Based on Dynamic Programming Algorithm
## 4 Method
### Offline Assignment Model  
Each order must be matched with a domestic helper and solved by using single objective nonlinear programming.  
1. Objective function The goal of this model is to maximize the total weighted score \(Sum\), as follows: \[\text{Max}\ \ Sum=\sum_{i=0}^{2303}S(i,k)\] (1)
2. Constraints Each order must be assigned one and only one housekeepinger, assuming that \(order_{k}\) (\(k\) = 0, 1,..., 2303) is a 0-1 variable representing the order status, as follows: \[order_{k}=\left\{\begin{array}{l}0,\ \text{matched}\\ 1,\ \text{unmatched}\end{array}\right.\] (2) Each order must specify a service start time, which must be within the range of [earliest start time, latest start time] and be an integer multiple of half an hour, as follows: \[t_{k}=\left\{t_{\text{min}},\ t_{\text{min}}+0.5,\ \ldots,\ t_{\text{max}}\right\}\] (3) where \(t_{k}\) is the service start time of the \(k\)-th order, \(t_{\text{min}}\) is the earliest start time, and \(t_{\text{max}}\) is the latest start time; A housekeepinger can only serve one order at the same time. Assume that _housekeeper_\(i\) (\(i\) = 0, 1,..., 2794) is a 0-1 variable representing the housekeepinger status, as follows: \[housekeeper_{i}=\left\{\begin{array}{l}0,\ \text{free}\\ 1,\ \text{working}\end{array}\right.\] (4) The coordinates of the order marked with \(k\) are represented by (\(x_{k}\), \(y_{k}\)), and the coordinates of the housekeepinger marked with \(i\) are represented by (\(x_{i}\), \(y_{i}\)); thus, the Euclidean distance \(d\) can be expressed as follows [47]: \[d=\sqrt{\left(x_{i}-x_{k}\right)^{2}+\left(y_{i}-y_{k}\right)^{2}}\] (5) The housekeepinger's arrival time \(gtime_{i}\) must be earlier than the order service's start time \(t_{i}\), as follows: \[\left\{\begin{array}{l}gtime_{i}\leq t_{i}\\ gtime_{i}=historytime+d/v\end{array}\right.\] (6) where _historytime_ is Beijing time, and the housekeepinger's moving speed is 15 km/h. Assume that the \(i\)-th housekeepinger score is weighted \(S(i,k)\) after completing the \(k\)-th order, as follows: \[S(i,k)=\alpha A_{i}+\beta B_{k}+\gamma C_{k}\] (7) where \(A_{i}\) is the service score of the \(i\)-th housekeepinger, \(B_{k}\) is the travel distance of the \(k\)-th order, and \(C_{k}\) is the time interval of the \(k\)-th order, with a coefficient \(\alpha\) = 0.78, \(\beta\) = 0.025, \(\gamma\) = 0.195. (3) Final optimization model The final objective function refers to Equation (1). The decision variableis housekeeping number \(i\). All constraints are as follows:  
\[\left\{\begin{array}{l}order_{k}=\left\{\begin{array}{l}0,\text{ matched}\\ 1,\text{ unmatched}\\ \end{array}\right.\\ housekeeper_{i}=\left\{\begin{array}{l}0,\text{ free}\\ 1,\text{ working}\\ \end{array}\right.\\ t_{k}=\left\{t_{\text{min}},\text{ }t_{\text{min}}+0.5,\text{ }\ldots,\text{ }t_{\text{max}}\right\}\\ d=\sqrt{\left(x_{i}-x_{k}\right)^{2}+\left(y_{i}-y_{k}\right)^{2}}\\ v=15 km/h\\ gitime_{i}=historytime+d/v\\ gitime_{i}\leq t_{i}\\ S(i,k)=\alpha A_{i}+\beta B_{k}+\gamma C_{k}\end{array}\right. \tag{8}\]  
Finally, with the goal of making \(Sum\) as large as possible, and the number of housekeepingers as the decision variable, a single objective nonlinear programming model is established with the status of the order and the housekeepinger, the order time limit, and the movement trajectory as constraints.