A Proofs in Plain-insertion-based Framework
This section lists the proofs of lemmas used in the plain-insertion algorithms (Section 5).
A.1 Proof of Lemma 4
Proof. As shown in Figure 3, condition (1) checks whether the deadline constraint of the new request \(r\) is violated, since \(\textsf {arr} [i]+\textsf {dis} (l_i,o_r)\) represents the arrival time at the new request’s origin (which is inserted after \(l_i\)). Condition (3) also checks whether the deadline constraint of the new request \(r\) is violated. For example, in Figures 3(b) and 3(c), \(\textsf {arr} [i]+\textsf {dis} (l_i,o_r)+\textsf {dis} (o_r, d_r)\) represents the arrival time at the new request’s destination, which should be earlier than the deadline \(e_r\).
Conditions (2) and (4) check whether the deadlines of the original requests are violated if \(o_r\) and \(d_r\) are inserted after \(l_i\) and \(l_j\). For condition (2), the detour of inserting \(o_r\) after \(l_i\) should satisfy the deadlines of all the requests after \(l_i\), i.e., the maximal tolerable time for detour. Thus, \(\textsf {det} (l_i,o_r,l_{i+1})\) should be smaller than \(\textsf {slack} [i]\). As for condition (4), the total detour to insert \(o_r\) and \(d_r\) should satisfy the deadlines of all the requests after \(l_j\). Similarly, \(\Delta _{i,j}\) should be smaller than \(\textsf {slack} [j]\).
A.2 Proof of Lemma 5
Proof. Condition (1) checks whether capacity constraint is violated if the new request is picked up after \(l_i\). After the new request has been picked up, condition (2) checks whether capacity constraint is violated if the following original requests are served. Here we only need to check the original requests between \(l_i\) and \(l_j\) since the new request will be delivered after \(l_j\).
A.3 Proof of Lemma 6
Proof. First, we assume \(i=\textsf {plc} [j]\) violates the capacity constraint (i.e., the first case of Equation (16) is satisfied). Based on Lemma 5, any other \(i \le j-1\) also violates the capacity constraint.
Next, we focus on the case when \(i=\textsf {plc} [j]\) only violates the deadline constraint in Lemma 4. Suppose to the contrary, there exists a \(z\) (\(z \lt j\) and \(z \ne \textsf {plc} [j]\)) which satisfies all the constraints. It indicates that for every \(k \in [z, j)\), the capacity constraint \(\textsf {pick} [k] \le c_w-c_r\) always holds. Based on the definitions of \(\textsf {dio} [\cdot ]\) and \(\textsf {plc} [\cdot ]\), we have \(\textsf {dio} [j] = \textsf {det} (l_i, o_r, l_{i+1}) \le \textsf {det} (l_z, o_r, l_{z+1}) \lt \infty\) and the integer \(i\) must exist. We complete our proof based on the four conditions of Lemma 4.
When \(i\) violates Lemma 4 (1), it will also violate Lemma 4 (3), which will be proved later.
When \(i\) violates Lemma 4 (2), then we have \(\textsf {det} (l_i, o_r, l_{i+1}) \gt \textsf {slack} [i]\). In other words, the second case of Equation (16) is satisfied and \(\textsf {plc} [i+1]\) should be equal to \(\textsf {plc} [i]\) instead of \((i+1)-1=i\). Thus, \(\textsf {plc} [j]\) cannot be equal to \(i\), which is contradicted to the assumption.
When \(i\) violates Lemma 4 (3), then we have \(\textsf {arr} [j] + \textsf {det} (l_i, o_r, l_{i+1}) + \textsf {dis} (l_j,d_r) \gt e_r\), where \(\textsf {det} (l_i, o_r, l_{i+1})\) can be simplified by \(\textsf {dio} [j]\). Since \(\textsf {det} (l_i, o_r, l_{i+1}) \le \textsf {det} (l_z, o_r, l_{z+1})\), then \(\textsf {arr} [j] + \textsf {det} (l_z, o_r, l_{z+1}) + \textsf {dis} (l_j,d_r)\) must be larger than \(e_r\). Thus, \(z\) also violates Lemma 4 (3), which is contradicted to the assumption.
When \(i\) violates Lemma 4 (4), then we have \(\Delta _{i,j} = \textsf {det} (l_j, d_r, l_{j+1}) + \textsf {det} (l_i, o_r, l_{i+1}) \gt \textsf {slack} [j]\), where \(\textsf {det} (l_i, o_r, l_{i+1})\) can be also simplified by \(\textsf {dio} [j]\). Since \(\textsf {det} (l_i, o_r, l_{i+1}) \le \textsf {det} (l_z, o_r, l_{z+1})\), then \(\Delta _{z,j} = \textsf {det} (l_j, d_r, l_{j+1}) + \textsf {det} (l_z, o_r, l_{z+1})\) must be larger than \(\textsf {slack} [j]\). Thus, \(z\) also violates Lemma 4 (4), which is contradicted to the assumption.
A.4 Proof of Lemma 7
Proof. According to the definition, \(\Delta\) is the actually increased time of worker \(w_i\) and \(\Delta ^\downarrow\) denotes the lower bound of the increased time of worker \(w_{i+1}\). Since the workers are already sorted in ascending order by \(\Delta ^\downarrow\), it indicates that every worker after \(w_{i+1}\) has a longer increased time in terms of the lower bound. As the lower bound \(\Delta ^\downarrow\) of \(w_{i+1}\) is already longer than the actually increased time \(\Delta\) of worker \(w_i\), he/she must have a longer increased time than \(\Delta\), which can be pruned.
A.5 Proof of Lemma 8
Proof. We can prove the correctness of Equation (18) by substituting \(\textsf {dis} (o_r,d_r) = \mathcal {L}\), \(\textsf {dis} (l_i, l_{i+1}) = \textsf {len} [i+1]\) and \(\forall u,v, \textsf {dis}^\downarrow (u,v) \le \textsf {dis} (u,v)\) into the first two cases of Equation (8). We can prove the correctness of Equation (20) by substituting \(\textsf {det} ^\downarrow (l_{j-1},o_r,l_j) \le \textsf {det} (l_{j-1},o_r,l_j)\) into Equation (15). We can prove the correctness of Equation (19) by substituting \(\textsf {dio} ^\downarrow [j] \le \textsf {dio} [j]\) into Equation (14).
B Proofs in Prophet-insertion-based Framework
This section lists the proofs of lemmas and theorems used in the prophet-insertion-based framework (Section 6) and the prophet-insertion algorithms (Section 7).
B.1 Proof of Lemma 9
Proof. First, as mentioned in Section 6.2, the plain-insertion is a special case of the prophet-insertion used in Algorithm 4. In other words, if a request can be served by plain-insertion, it will also be able to be served by prophet-insertion. Moreover, since the prophet-insertion allows the workers to move to the request’s origin earlier than its release time, it potentially serves more requests than plain-insertion.
Second, in Algorithm 4, we assume that there are sufficient hypothetical workers at the requests’ origins (lines 1–6). In lines 7–11, we ensure that the real workers are assigned with the top \(\lbrace |W|\rbrace\) most profitable routes by a max-heap, where the profit of a route is either the number of served request or the revenue of this route. Thus, each real worker is assigned to the currently most profitable route (i.e., the guidance route of the hypothetical worker \(\widetilde{w^*}\)). Suppose to the contrary, a real worker \(w\) is assigned to \(\widetilde{S_w}\), which is more profitable than the route of \(\widetilde{w^*}\) by Algorithm 4. Then, there must be a hypothetical worker \(\widetilde{w} \ne \widetilde{w^*}\) corresponding to \(\widetilde{S_w}\). Based on the definition of a max-heap, \(\widetilde{w}\) must be popped earlier than \(\widetilde{w^*}\) in line 9. However, since \(\widetilde{w}\) is not matched to the real worker \(w\) in Algorithm 4, then some other worker must serve the requests in \(\widetilde{w}\) with shorter increased travel time in line 9. Since insertion-based online algorithm always assigns the request to the worker with minimum increased travel time, this is contradicted to the prerequisite.
Finally, when the prediction is completely accurate, we can use Algorithm 4 to obtain the upper bound of any insertion-based online algorithm (only in the proof below).
B.2 Proof of Theorem 3
Proof. For brevity, we use \(\text{OPT}\) to denote the optimal insertion-based online algorithm and \(\text{UB}\) to denote the upper bound of \(\text{OPT}\) obtained by Algorithm 4. We also use \(\text{ALG}\) to denote our framework (i.e., Algorithm 5). We will prove the (expected) optimality ratio \(\text{E}[\text{ALG} ]/\text{E}[\text{OPT} ]\) is a constant and the probability of achieving this ratio (0.47) is high in practice.
We use
\(n\) and
\(m\) to denote the number of online requests and predicted requests, respectively. W.l.o.g., we let
\(n = k \cdot m\). Under the assumption of known IID, these
\(m\) predicted requests (a.k.a., request types) are sampled based on the distribution of the online requests in Algorithm 5. As prediction can be wrong, each online request has the probability of
\(\frac{1}{m}\) to match with a certain request type. Thus, each predicted request has the following probability to appear in the online requests.
Based on the proof of Lemma 9, we have \(\text{E}[\text{OPT} ] \le \text{E}[\text{UB} ]\). We next prove the optimality ratio of Algorithm 5 in terms of each objective as follows.
Maximizing the number of served requests. Let
\(x_i \in \lbrace 0,1\rbrace\) be a random variable that represents the online request
\(r_i\) is served in
\(\text{UB}\) and
\(X = \sum _{i}{x_i}\) be a random variable that represents the number of served requests in
\(\text{UB}\). As
\(\text{E}[\text{OPT} ] \le \text{E}[\text{UB} ]\), we can infer that
\(\text{E}[\text{UB} ] = \text{E}[X] = \text{E}[\sum _{i}{x_i}] \ge \text{E}[\text{OPT} ]\). Let
\(\widetilde{x_i} \in \lbrace 0,1\rbrace\) be a random variable that represents the online request
\(r_i\) is served in
\(\text{ALG}\) and
\(\widetilde{X} = \sum _{i}{\widetilde{x_i}}\) be a random variable that represents the number of served requests in
\(\text{ALG}\). Based on the probability in Equation (
39), we have
Thus, the (expected) optimality ratio is
\(1 - \frac{1}{e^k}\). Here, we assume
\(k \in [0.65, 1.35]\) based on the experimental results of the prediction methods. Specifically, since the MAPEs of all the compared methods in [
20] which predict the number of future requests are lower than 35%, the value of
\(k\) is
\([1-0.35, 1+0.35] = [0.65, 1.35]\). The optimality ratio is at least 0.47 based on this choice of
\(k\). We can derive the probability of getting this ratio by Azuma-Hoeffding inequality [
35] as follows.
In other words, with a probability at least
\(1-e^{-\Omega (n)}\), the optimality ratio is 0.47 in practice.
Maximizing the total revenue. Let
\(y_i = x_i \cdot rev_{r_i}\) be a random variable that represents the revenue of the online request
\(r_i\) if it is served in
\(\text{UB}\), where
\(rev_{r_i}\) denotes the fare from serving the request minus the income of the worker. Let
\(Y = \sum _{i}{y_i}\) be a random variable that represents the total revenue in
\(\text{UB}\). As
\(\text{E}[\text{OPT} ] \le \text{E}[\text{UB} ]\), we can infer that
\(\text{E}[\text{UB} ] = \text{E}[Y] = \text{E}[\sum _{i}{y_i}] \ge \text{E}[\text{OPT} ]\). Let
\(\widetilde{y_i} = \widetilde{x_i} \cdot rev_{r_i}\) be a random variable that represents the revenue of the online request
\(r_i\) if it is served in
\(\text{ALG}\) and
\(\widetilde{Y} = \sum _{i}{\widetilde{y_i}}\) be a random variable that represents the total revenue in
\(\text{ALG}\). Similar to the deduction in Equation (
40), we can infer that
Thus, the optimality ratio is
\(1 - \frac{1}{e^k}\) (i.e., at least 0.47 when
\(k \in [0.65, 1.35]\)). To infer the probability of achieving this optimality ratio, we assume that
\(|rev_{r_i} - rev_{r_j}| \le C\) for any two requests
\(r_i\) and
\(r_j\), where
\(C\) can be any large constant. Here, we only require
\(C\) is still bounded when
\(n\) approaches infinity. The assumption is reasonable since the fare of each request is much smaller than
\(O(n)\) in shared mobility. By Azuma-Hoeffding inequality [
35], we infer the probability as:
Therefore, with a high probability (at least \(1-e^{-\Omega (n)}\)), the optimality ratio is 0.47.
B.3 Proof of Lemma 10
Proof. W.l.o.g., we assume the unit of travel time is second. By Equation (29), we have the following facts: (1) the worker will be \(\textsf {detOD} (i)\) seconds late at the location \(l_{i+1}\); and (2) he now needs less time (i.e., \(\max \lbrace \textsf {wait} [i+1]-\textsf {detOD} (i),0\rbrace\)) to wait at the location \(l_{i+1}\). Similarly, he may also take a longer time to arrive at any location after \(l_{i+1}\) and wait less time there. Based on the facts, we prove Lemma 10 from the following two aspects.
If \(\textsf {detOD} (i) \gt \textsf {swait} [i+1]\), we will prove \(\Delta _{i,j} = \textsf {detOD} (i) - \textsf {swait} [i+1]\), where \(\textsf {swait} [i+1]\) is defined as \(\textsf {wait} [i+1]+\cdots +\textsf {wait} [n]\). Based on the facts above, the worker does not need to wait at location \(l_{i+1}\) any more, i.e., \(\max \lbrace \textsf {wait} [i+1]-\textsf {detOD} (i),0\rbrace = 0\). Similarly, he will be \((\textsf {detOD} (i)-\textsf {wait} [i+1])\) seconds late at the location \(l_{i+2}\) and does not need to wait there any more since \(\max \lbrace \textsf {wait} [i+2]-(\textsf {detOD} (i)-\textsf {wait} [i+1]),0\rbrace = 0\). Inductively, he will be \((\textsf {detOD} (i)-\textsf {wait} [i+1]-\cdots -\textsf {wait} [n-1])\) seconds late at the location \(l_{n}\). Since the last location \(l_n\) of any route is either a request’s destination or a worker’s initial location, he does not need to wait at \(l_n\) (i.e., \(\textsf {wait} [n] = 0\) by Equation (21)). Thus, the increased travel time is exactly \(\textsf {detOD} (i)-\textsf {wait} [i+1]-\cdots -\textsf {wait} [n-1]-\textsf {wait} [n] = \textsf {detOD} (i) - \textsf {swait} [i+1]\).
If \(\textsf {detOD} (i) \le \textsf {swait} [i+1]\), we will prove \(\Delta _{i,j} = 0\). Since \(\textsf {detOD} (i) \le \textsf {swait} [i+1]\), there exists at least one integer \(k \in [i+1,n]\) such that \(\textsf {detOD} (i) \le \textsf {wait} [i+1]+\cdots +\textsf {wait} [k]\). We also assume \(k\) is the smallest among such integers. Based on the analysis above, we know the worker will be \((\textsf {detOD} (i)-\textsf {wait} [i+1]-\cdots -\textsf {wait} [k-1])\) seconds late at the location \(l_{k}\), and only has to wait for \((\textsf {wait} [k] - (\textsf {detOD} (i)-\textsf {wait} [i+1]-\cdots -\textsf {wait} [k-1])) \ge 0\) seconds at the location \(l_{k}\). After that, he will arrive at the location \(l_{k+1}\) exactly the same time as the original route before insertion. In other words, the total travel time will not be increased, i.e., \(\Delta _{i,j} = 0\).
B.4 Proof of Lemma 11
Proof. Condition (1) checks whether the capacity constraint is violated if the new request \(r\) is inserted, which can be directly derived from Lemma 5.
Condition (2) checks whether the deadlines of the original requests are violated if \(o_r\) and \(d_r\) are sequentially inserted between \(l_i\) and \(l_{i+1}\). Since the new request is inserted after \(l_i\), the deadlines (\(\textsf {ddl} [\cdot ]\)) before the location \(l_i\) (including) will not be violated. Thus, we only need to verify whether any deadline after the location \(l_{i}\) (excluded) is violated. Based on the definition of \(\textsf {slack} [i]\), we only need to make sure that \(\textsf {detOD} (i) \le \textsf {slack} [i]\).
Condition (3) checks whether the new request’s deadline is violated. Since the LHS of this condition represents the arrival time at the new request’s destination (as in Figures 3(b) and 3(c)), we only need to check whether it is no larger than the new request’s deadline (i.e., \(e_r\)).
B.5 Proof of Lemma 12
Proof. By the proof of Lemma 10, we know the worker will be
\(\max \lbrace \textsf {detO} (i)-\textsf {wait} [i+1]-\cdots -\textsf {wait} [k], 0\rbrace\) seconds late at any location
\(l_k\) after
\(l_{i+1}\) (i.e.,
\(k \ge i+1\)). In other words, he will be
\(\max \lbrace \textsf {detO} (i)-\textsf {wait} [i+1]-\cdots -\textsf {wait} [j], 0\rbrace\) seconds late at the location
\(l_j\). As the new request’s destination is inserted between
\(l_j\) and
\(l_{j+1}\), he may be further
\(\textsf {detD} (j)\) seconds late at the location
\(l_{j+1}\), where
\(\textsf {detD} (j)\) is defined as the detour between
\(l_j\) and
\(l_{j+1}\) in Equation (32). Therefore, the late arrival time at the location
\(l_n\) is
where \(\textsf {swait} [k]\) is defined as \(\textsf {wait} [k]+\cdots +\textsf {wait} [n]\) in Equation (23).
B.6 Proof of Lemma 13
Proof. Condition (1) checks the capacity constraint, which can be directly derived from Lemma 5.
Condition (2) checks whether the deadlines of the original requests are violated if the new request’s origin is inserted between locations \(l_i\) and \(l_{i+1}\). Since the deadlines before the location \(l_i\) are unaffected, we only need to verify whether any deadline after the location \(l_{i}\) (excluded) is violated. Based on the definition of \(\textsf {slack} [i]\), we only need to ensure that \(\textsf {detO} (i) \le \textsf {slack} [i]\).
Condition (3) checks whether the deadlines of the original requests are violated if the new request’s destination is inserted between locations \(l_j\) and \(l_{j+1}\). Similarly, we only need to verify whether any deadline after the location \(l_{j}\) (excluded) is violated. Specifically, based on the proof of Lemma 12, the worker will be \(\max \lbrace \textsf {detO} (i)-\textsf {wait} [i+1]-\cdots -\textsf {wait} [j], 0\rbrace\) seconds late at the location \(l_j\). Based on the definition of \(\textsf {swait} [\cdot ]\), we have \(\textsf {wait} [i+1]+\cdots +\textsf {wait} [j] = \textsf {swait} [i+1]-\textsf {swait} [j+1]\) and hence the late arrival time at the location \(l_j\) also equals to \(\max \lbrace \textsf {detO} (i)-(\textsf {swait} [i+1]-\textsf {swait} [j+1]), 0\rbrace\). Thus, the late arrival time at the location \(l_{j+1}\) is \(\textsf {detD} (j) + \max \lbrace \textsf {detO} (i)-(\textsf {swait} [i+1]-\textsf {swait} [j+1]), 0\rbrace\). Based on the definition of \(\textsf {slack} [j]\), the late arrival time at the location \(l_{j+1}\) should be no larger than \(\textsf {slack} [j]\).
Condition (4) checks whether the new request’s deadline is violated. Specifically, the sum of the first three terms in the LHS of this condition represents the leaving time from the location \(l_j\). Thus, the LHS of this condition represents the arrival time at the new request’s destination. Here, we only need to check whether it is no larger than the new request’s deadline (i.e., \(e_r\)).
B.7 Proof of Lemma 14
Proof. By substituting
\(\Delta _{i,j}\) (in Lemma 12) into Equation (33), we can derive that
In Equation (
44), since
\(j\) is fixed, the terms related to only
\(j\) are constants, e.g.,
\(\textsf {detD} (j), \textsf {swait} [j+1]\). Thus, we can rewrite Equation (
44) by Equation (
45).
where the function
\(F(i)\) and constant
\(C\) are as follows (for proof brevity only):
We next prove the following fact in Equation (
48) from two aspects.
•
\(\exists i, F(i) \le C\). We have both LHS and RHS of Equation (
48) equal to
\(C\), since
\(\min _{i\lt j}\lbrace F(i)\rbrace \le C\).
•
\(\nexists i, F(i) \le C\). In other words,
\(\forall i, F(i) \gt C\). Thus, the LHS of Equation (
48) equals
\(\min _{i\lt j}\lbrace F(i)\rbrace\). The RHS of Equation (
48) also equals
\(\min _{i\lt j}\lbrace F(i)\rbrace\), since
\(\min _{i\lt j}\lbrace F(i)\rbrace\) is still larger than
\(C\).
Based on Equation (
48), we can rewrite Equation (
45) as follows:
As a result, we then focus on efficiently calculating
\(F(i)\). Since
\(\textsf {detD} (j)\) is a constant and
\(\textsf {dio} [j] = \min _{i \lt j}\lbrace \textsf {detO} (i)-\textsf {swait} [i+1]\rbrace\), we can calculate
\(\min _{i\lt j}\lbrace F(i)\rbrace\) as follows.
Finally, we prove this lemma by substituting Equation (
47) and (
50) into Equation (
49).
B.8 Proof of Lemma 15
Proof. First, we assume \(i=\textsf {plc} [j]\) violates the capacity constraint (i.e., the first case of Equation (38) is satisfied). By Lemma 13 (1), any other \(i \le j-1\) also violates the capacity constraint.
Next, we focus on the case when \(i=\textsf {plc} [j]\) only violates the deadline constraint in Lemma 13. Suppose to the contrary, there exists a \(z\) (\(z \lt j\) and \(z \ne \textsf {plc} [j]\)) which satisfies all the constraints. It indicates that for every \(k \in [z, j)\), the capacity constraint \(\textsf {pick} [k] \le c_w-c_r\) always holds. Based on the definitions of \(\textsf {dio} [\cdot ]\) and \(\textsf {plc} [\cdot ]\), we have \(\textsf {dio} [j] = \textsf {detO} (i)-\textsf {swait} [i+1] \le \textsf {detO} (z)-\textsf {swait} [z+1] \lt \infty\) and the integer \(i\) must exist. We complete our proof from the following three aspects.
When \(i\) violates Lemma 13 (2), we have \(\textsf {detO} (i) \gt \textsf {slack} [i]\). In other words, the second case of Equation (38) is satisfied and \(\textsf {plc} [i+1]\) should be equal to \(\textsf {plc} [i]\) instead of \((i+1)-1=i\). Thus, \(\textsf {plc} [j]\) cannot be equal to \(i\), which is contradicted to the assumption.
When \(i\) violates Lemma 13 (3), we have \(\textsf {detD} (j)+\max \lbrace \textsf {detO} (i)-\textsf {swait} [i+1]+\textsf {swait} [j+1], 0\rbrace \gt \textsf {slack} [j]\), where \(\textsf {detO} (i)-\textsf {swait} [i+1]\) can be simplified by \(\textsf {dio} [j]\). Since \(\textsf {detO} (i)-\textsf {swait} [i+1] \le \textsf {detO} (z)-\textsf {swait} [z+1]\), we can infer that \(\textsf {detD} (j)+\max \lbrace \textsf {detO} (z)-\textsf {swait} [z+1]+\textsf {swait} [j+1], 0\rbrace\) is larger than \(\textsf {slack} [j]\). Thus, \(z\) violates Lemma 13 (3), which is contradicted to the assumption.
When \(i\) violates Lemma 13 (4), we have \(\textsf {arr} [j] + \textsf {wait} [j] + \max \lbrace \textsf {detO} (i)-\textsf {swait} [i+1]+\textsf {swait} [j+1], 0\rbrace + \textsf {dis} (l_j,d_r) \gt e_r\) and \(\textsf {detO} (i)-\textsf {swait} [i+1]\) can be simplified by \(\textsf {dio} [j]\). As \(\textsf {detO} (i)-\textsf {swait} [i+1] \le \textsf {detO} (z)-\textsf {swait} [z+1]\), we derive \(\textsf {arr} [j] + \textsf {wait} [j] + \max \lbrace \textsf {detO} (z)-\textsf {swait} [z+1]+\textsf {swait} [j+1], 0\rbrace + \textsf {dis} (l_j,d_r) \gt e_r\). Thus, \(z\) violates Lemma 13 (4), which is contradicted to the assumption.
B.9 Proof of Lemma 16
Proof. We prove (1) by assuming the contrary. If the new request’s destination is feasible to be inserted after a location \(l_j\), where \(j \lt k\). Then the arrival time at the location \(l_k\) must be later than the release time of the request. By the prerequisite, we know the deadline of \(r_{l_k}\) must be violated, which is contradicted to the assumption.
We prove (2) by the prerequisite. We know \(\textsf {arr} [j] \gt e_r\). Thus, the new request’s deadline must be violated when its destination is inserted after location \(l_j\). By the definition of \(\textsf {arr} [\cdot ]\) in Equation (22), we know \(\textsf {arr} [j] \le \textsf {arr} [j+1]\). Thus, we can safely prune any \(j \ge k\).
