# Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems
## 4 The Case \(c=2\): Algorithms and Their Analysis
### The Match-and-Assign Algorithm and Its Analysis  
We came up with a match-and-assign algorithm, the \(\text{MA}(\alpha,v)\), the idea being that, first, requests are matched into request pairs, after which the request pairs are assigned to the cars. Finding request pairs is performed by using a carefully chosen time \(v_{3}(\{i,j\})\) between a pair of requests \(\{i,j\}\), as well as a travel time \(v_{4}(k,\{i,j\})\) between each request pair \(\{i,j\}\) and a car \(k\in D\):  
\[v_{3}(\{i,j\})\equiv\frac{v_{ij}+v_{ji}}{2},\ \ \ v\in\{u,\mu\}. \tag{24}\]  
\[v_{4}(k,\{i,j\})\equiv\min\{aw(d_{k},s_{i})+\frac{v_{ij}-v_{ji}}{2},aw(d_{k},s _{j})-\frac{v_{ij}-v_{ji}}{2}\},\ \ \alpha\in\{1,2\},v\in\{u,\mu\}. \tag{25}\]  
Now, we introduce the match-and-assign Algorithm 2. The resulting quantity is \(v_{3}(M_{3})+v_{4}(M_{4})\); we now prove two lemmas concerning this quantity, which will be of use in the approximation analysis. **Lemma 5**. : _For each \(\alpha\in\{1,2\}\) and \(v\in\{u,\mu\}\), we have:_  
\[v_{3}(M_{3})+v_{4}(M_{4})=\sum_{(k,\{i,j\})\in M_{4}}\min\{\alpha w(d_{k},s_{i})+ v_{ij},\alpha w(d_{k},s_{j})+v_{ji}\}.\]  
Proof. : Without loss of generality, for any \(\{i,j\}\in M_{3}\), suppose \(v_{ij}-v_{ji}\geq 0\) (the other case is symmetric). \[v_{3}(M_{3})+v_{4}(M_{4})=\sum_{\{i,j\}\in M_{3}}\frac{v_{ij}+v_{ ji}}{2}+\] \[=\sum_{(k,\{i,j\})\in M_{4}}\min\{\alpha w(d_{k},s_{i})+\frac{v_{ ij}-v_{ji}}{2},\alpha w(d_{k},s_{j})-\frac{v_{ij}-v_{ji}}{2}\}\] \[=\sum_{(k,\{i,j\})\in M_{4}}\min\{\alpha w(d_{k},s_{i})+v_{ij}, \alpha w(d_{k},s_{j})+v_{ji}\}.\]  
The first equality follows from the definition of \(v_{3}\) and \(v_{4}\) (see Equations (24) and (25)). **Lemma 6**. : _For \(\alpha\in\{1,2\}\), \(v\in\{u,\mu\}\), and for each allocation \(M\), we have:_  
\[v_{3}(M_{3})+v_{4}(M_{2})\leq\sum_{(k,\{i,j\})\in M}\frac{\alpha w(d_{k},s_{i} )+\alpha w(d_{k},s_{j})+v_{ij}+v_{ji}}{2}.\]  
Proof. : For an allocation \(M\), let \(M_{R}=\{R_{k}:(k,R_{k})\in M\}\). Observe that:  
\[v_{3}(M_{3})\leq\sum_{\{i,j\}\in M_{R}}\frac{v_{ij}+v_{ji}}{2}, \tag{26}\]  
since \(M_{3}\) is a minimum weight perfect matching in \(G_{3}\equiv(R,v_{3})\). We claim that:  
\[v_{4}(M_{4})\leq\sum_{(k,\{i,j\})\in M}\frac{\alpha w(d_{k},s_{i})+\alpha w(d _{k},s_{j})}{2}. \tag{27}\]  
When summing (26) and (27), the lemma follows. Hence, it remains to prove (27). Consider an allocation \(M\), and consider the matching \(M_{3}\) found in the first step of the MA. Based on \(M\) and \(M_{3}\), we construct the graph \(G^{\prime}=(R\cup D,M_{1}\cup\{(\{i,k\},\{j,k\}):(k,\{i,j\})\in M\})\). Note that every vertex in graph \(G^{\prime}\) has degree two. Thus, we can partition \(G^{\prime}\) into a set of disjoint cycles called \(C\); each cycle \(c\in C\)can be written as \(c=(i_{1},i_{1},k_{1},i_{2},j_{2},k_{2},\ldots,k_{h},i_{1})\), where \(\{i_{s},j_{s}\}\in M_{3}\), \((k_{s},\{j_{s},i_{s+1}\})\in M\) for \(1\leq s<h\) and \((k_{h},\{j_{h},i_{1}\})\in M\). Consider now, for each cycle \(c\in\mathbb{C}\), the following two assignments called \(M^{c}_{\ell}\) and \(M^{c}_{r}\):  
* \(M^{c}_{\ell}=\{(\{i_{1},j_{1}\},k_{1}),(\{i_{2},j_{2}\},k_{2}),\ldots,(\{i_{h}, j_{h}\},k_{h})\}\),
* \(M^{c}_{r}=\{(k_{1},\{i_{2},j_{2}\}),(k_{2},\{i_{3},j_{3}\}),\ldots,(k_{h},\{i_ {1},j_{1}\})\}\). Obviously, both \(M_{\ell}\equiv\bigcup_{c\in\mathbb{C}}M^{c}_{\ell}\) and \(M_{r}\equiv\bigcup_{c\in\mathbb{C}}M^{c}_{r}\) are a feasible assignment in \(G_{4}=(D\cup M_{3},v_{4})\). Given the definition of \(v_{4}(k,\{i,j\})\) (see Equation (25)), we derive for each pair of requests \(\{i,j\}\) and two cars \(a,b\): \(v_{4}(a,\{i,j\})+v_{2}(b,\{i,j\})\leq\alpha w(d_{a},s_{i})+\frac{v_{ij}-v_{ji}} {2}+\alpha w(d_{b},s_{j})-\frac{v_{ji}-v_{ji}}{2}=\alpha(w(d_{a},s_{i})+w(d_{b },s_{j}))\). Similarly, it follows that: \(v_{4}(a,\{i,j\})+\frac{v_{ij}-v_{ji}}{2}(b,\{i,j\})\leq\alpha(w(d_{a},s_{j})+w (d_{b},s_{i}))\). Thus, for each \(c\in\mathbb{C}\):  
\[\sum_{(k,\{i,j\})\in M^{c}_{\ell}}v_{4}(k,\{i,j\})+\sum_{(k,\{i,j\})\in M^{c}_ {r}}v_{4}(k,\{i,j\})\leq\sum_{