# Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems
## 3 The Transportation Algorithm and Its Analysis
### The Transportation Algorithm
We have:  
\[\text{wait}(\text{TA}(v_{2}))\leq v_{2}(M_{2}). \tag{8}\]  
Recall that our problem does not force the driver to return to the original position. This implies that the cost of a driver when serving a set of request \(R_{k}\) does not include the time from the last drop-off location to the driver's original location. This explains why in the expression for \(v_{1}(M_{1})\) (also, \(v_{2}(M_{2})\)), we can subtract the corresponding travel time from the total travel time. We now give two lemmas concerning \(v_{1}(M_{1})\) (which we need to prove Theorem 3.1) and two more lemmas concerning \(v_{2}(M_{2})\) (which we need to prove Theorem 3.1). Lemma 1: _For any \(c\geq 2\), we have:_  
\[v_{1}(M_{1})=\sum_{(k,R_{k})\in\text{TA}(v_{1})}\biggl{(}\sum_{r\in R_{k}}w(d_ {k},s_{r},t_{r},d_{k})-\max_{r\in R_{k}}w(d_{k},t_{r})\biggr{)}.\]  
Proof: We claim that \(v_{1}(M_{1})\) is minimized if and only if, for each car \(k\in D\) and \((\gamma_{c}(k),r_{c})\in M_{1}\), \(r_{c}=\arg\max_{\gamma\in R_{k}}w(d_{k},t_{r})\). If this claim holds, then based on the definition of the cost \(v_{1}(\cdot,\cdot)\), we have \(v_{1}(K,R_{k})=\sum_{r\in R_{k}}w(d_{k},s_{r},t_{r},d_{k})-w(d_{k},t_{r_{c}})= \sum_{r\in R_{k}}w(d_{k},s_{r},t_{r},d_{k})-\max_{r\in R_{k}}w(d_{k},t_{r})\), and thus:  
\[v_{1}(M_{1})=\sum_{(k,R_{k})\in\text{TA}(v_{1})}\biggl{(}\sum_{r\in R_{k}}w(d_ {k},s_{r},t_{r},d_{k})-\max_{r\in R_{k}}w(d_{k},t_{r})\biggr{)}.\]  
It remains to prove the claim. Consider any \(R_{k}=\{r_{1},r_{2},\ldots,r_{c}\}\) for car \(k\in D\). We prove that \(v_{1}(M_{1})\) is minimized if and only if \(w(d_{k},t_{r_{c}})\geq w(d_{k},t_{r_{c}})\) for all \(r_{x}\in R_{k}\). _Necessary condition:_ Since \(v_{1}(K,R_{k})\) is minimized, we have \(w(d_{k},s_{r_{x}},t_{r_{x}})+w(d_{k},t_{r_{x}})+w(d_{k},s_{r_{c}},t_{r_{c}}) \leq w(d_{k},s_{r_{c}},t_{r_{c}})+w(d_{k},t_{r_{c}})+w(d_{k},s_{r_{x}},t_{r_{x}})\) based on the definition of \(v_{1}\) (see Equation (5)), then \(w(d_{k},t_{r_{x}})\leq w(d_{k},t_{r_{c}})\) holds. _Sufficient condition:_ Since \(w(d_{k},t_{r_{c}})\geq w(d_{k},t_{r_{x}})\), then \(w(d_{k},s_{r_{c}},t_{r_{c}})+w(d_{k},t_{r_{c}})+w(d_{k},s_{r_{x}},t_{r_{x}}) \geq w(d_{k},s_{r_{x}},t_{r_{x}})+w(d_{k},t_{r_{x}})+w(d_{k},s_{r_{c}},t_{r_{c }})\), and that means \(v_{1}(M_{1})\) is minimized as \(r_{c}=\arg\max_{r\in R_{k}}w(d_{k},t_{r})\). From the above lemma and the fact that \(M_{1}\) is a minimum weight assignment in \(G_{1}\equiv(\Gamma\cup R,v_{1})\), we have the following lemma:  
Lemma 2: _For \(c\geq 2\) and for each allocation \(M\), we have:_  
\[v_{1}(M_{1})\leq\sum_{(k,R_{k})\in\text{M}}\biggl{(}\sum_{r\in R_{k}}w(d_{k},s_ {r},t_{r},d_{k})-\max_{r\in R_{k}}w(d_{k},t_{r})\biggr{)}.\]  
We now provide two lemmas concerning \(v_{2}(M_{2})\). In the statement of these lemmas, we index the requests such that, for each \(k\in D\), \(R_{k}=\{r_{1},r_{2},\ldots,r_{c}\}\). Lemma 3: _For any \(c\geq 2\), for each car \(k\in D\) and \(\forall r_{x},r_{y}\in R_{k}\) with \(x<y\), \(w(d_{k},s_{r_{x}},t_{r_{x}})+w(d_{k},t_{r_{x}})\leq w(d_{k},s_{r_{y}},t_{r_{y}})+ w(d_{k},t_{r_{y}})\)._Proof. : We claim that \(v_{2}(M_{2})\) is minimized if and only if for each car \(k\in D\) and \(\forall r_{x},r_{y}\in R_{k}=\{r_{1},r_{2},\ldots,r_{c}\}\) with \(x<y\), \(w(d_{k},s_{r_{k}},t_{r_{x}})+w(d_{k},t_{r_{x}})\leq w(d_{k},s_{r_{y}},t_{r_{y}})+ w(d_{k},t_{r_{y}})\). Consider \(\forall r_{x},r_{y}\in R_{k}=\{r_{1},r_{2},\ldots,r_{c}\}\) with \(x<y\) for car \(k\in D\). We prove that \(v_{2}(M_{2})\) is minimized if and only if \(w(d_{k},s_{r_{x}},t_{r_{x}})+w(d_{k},t_{r_{x}})\leq w(d_{k},s_{r_{y}},t_{r_{y}} )+w(d_{k},t_{r_{y}})\).