## 3 Discount-Guaranteed Ridesharing Problem
The portion of cost savings allocated to driver \(d\), where \(d\in\{1,2,3,\ldots D\}\), is \(\frac{c_{dj}H_{dj}(x,y)}{\sum\limits_{p\in\Gamma_{dj}}y_{p}c_{pdf}+x_{dj}c_{dj}}\) if \(x_{dj}>0\). The cost savings discount for the \(j\)-th bid of driver agent is \(\frac{H_{dj}(x,y)}{\sum\limits_{p\in\Gamma_{dj}}y_{p}c_{f_{pdfj}+x_{dj}c_{dj}}}\) if \(x_{dj}>0\). For the discount-guaranteed ridesharing problem, the cost savings discount \(\frac{H_{dj}(x,y)}{\sum\limits_{p\in\Gamma_{dj}}y_{p}c_{f_{pdfj}+x_{dj}c_{dj}}}\) for driver \(d\) must satisfy the cost savings discount constraint. That is, \(x_{dj}(\frac{H_{dj}(x,y)}{\sum\limits_{p\in\Gamma_{dj}}y_{p}c_{f_{pdfj}+x_{dj}c_ {dj}}}-r_{D})\) must be greater than or equal to zero. The portion of the cost savings allocated to passenger \(p\), where \(p\in\{1,2,3,\ldots P\}\), is \(\frac{c_{f_{pdf}}H_{dj}(x,y)}{\sum\limits_{p\in\Gamma_{dj}}y_{p}c_{f_{pdfj}+x_{ dj}c_{dj}}}\) if \(y_{p}>0\). The cost savings discount for winning passenger \(p\) with \(y_{p}>0\) is \(\frac{H_{dj}(x,y)}{\sum\limits_{p\in\Gamma_{dj}}y_{p}c_{f_{pdfj}+x_{dj}c_{dj}}}\). For the discount-guaranteed ridesharing problem, the cost savings discount \(\frac{H_{dj}(x,y)}{\sum\limits_{p\in\Gamma_{dj}}y_{p}c_{f_{pdfj}+x_{dj}c_{dj}}}\) for passenger \(p\) must satisfy the cost savings discount constraint. That is, \(y_{p}(\frac{H_{dj}(x,y)}{\sum\limits_{p\in\Gamma_{dj}}y_{p}c_{f_{pdfj}+x_{dj}c_ {dj}}}-r_{P})\) must be greater than or equal to zero. Based on the objective function and the constraints defined above, we formulated the discount-guaranteed ridesharing problem as follows. Discount-guaranteed ridesharing problem:  
\[\max\limits_{x,y}H(x,y) \tag{1}\]  
\[\sum\limits_{d=1}^{D}\sum\limits_{j=1}^{\frac{J_{d}}{J_{dj}}}x_{dj}q_{djk}^{1} =y_{p}s_{pk}^{1}\forall p\in\{1,2,\ldots,P\}\ \forall k\in\{1,2,\ldots,P\} \tag{2}\]  
\[\sum\limits_{d=1}^{D}\sum\limits_{j=1}^{\frac{J_{d}}{J_{dj}}}x_{dj}q_{djk}^{2} =y_{p}s_{pk}^{2}\forall p\in\{1,2,\ldots,P\}\ \forall k\in\{1,2,\ldots,P\} \tag{3}\]  
\[\sum\limits_{p=1}^{p}y_{p}f_{p}+\sum\limits_{d=1}^{D}\sum\limits_{j=1}^{\frac{ J_{d}}{J_{d}}}x_{dj}\partial_{dj}\geq\sum\limits_{d=1}^{D}\sum\limits_{j=1}^{ \frac{J_{d}}{J_{d}}}x_{dj}c_{dj} \tag{4}\]  
\[\sum\limits_{j=1}^{\frac{J_{d}}{J_{d}}}x_{dj}\leq 1\forall d\in\{1,\ldots,D\} \tag{5}\]  
\[x_{dj}(\frac{H_{dj}(x,y)}{\sum\limits_{p\in\Gamma_{dj}}y_{p}c_{f_{pdfj}+x_{dj}c _{dj}}}-r_{D})\geq 0 \tag{6}\]  
\[y_{p}(\frac{H_{dj}(x,y)}{\sum\limits_{p\in\Gamma_{dj}}y_{p}c_{f_{pdfj}+x_{dj}c _{dj}}}-r_{P})\geq 0 \tag{7}\]  
where \(x_{dj}\in\{0,1\}\ \forall d\in\{1,2,\ldots,D\}\ \forall j\in\{1,2,\ldots,J_{d}\}\) and \(y_{p}\in\{0,1\}\ \forall p\in\{1,2,\ldots,P\}\). The constraints considered in the above formulation of the discount-guaranteed ridesharing problem included: the supply/demand constraints at pick-up (Equation (2)) and drop-off (Equation (3)) locations, the non-negative cost savings constraint (Equation (4)), the single winning bid constraint for drivers (Equation (5)), and the cost savings discount constraints for drivers (Equation (6)) and passengers (Equation (7)). Note that the constraints represented by Equations (6) and (7) are not considered in the existing studies on ridesharing, such as those reported in [12, 28, 40]. We analyzed the costs for passengers and drivers under the decision model of the above discount-guaranteed ridesharing problem. In the optimization model, the cost for passenger \(p\) without ridesharing, \(f_{p}\), is related to the transportation costs of alternative transport modes. It provides a reference for assessing the cost savings for passengers. The cost savings allocated to passenger \(p\) on the ride corresponding to the \(j\)-th bid submitted by driver \(d\), where \(p\in\Gamma_{dj}\), is \(\frac{cf_{pdij}H_{ij}(x_{y})}{\sum\limits_{p\in\Gamma_{dj}}y_{p}cf_{pdi}+x_{dj} c_{dj}}=\frac{cf_{pdij}\left[\left(\sum\limits_{p\in\Gamma_{dj}}y_{p}f_{p} \right)+x_{dj}a_{ij}-\left(x_{dj}c_{dj}\right)\right]}{\sum\limits_{p\in\Gamma _{dj}}y_{p}cf_{pdi}+x_{dj}c_{dj}}\).