## 3 Discount-Guaranteed Ridesharing Problem
Let us denote the requirements of passenger \(p\) as \(R_{p}=(Lo_{p},Le_{p},\omega_{p}^{e},\omega_{p}^{l},n_{p})\), where \(R_{p}\) is defined by the start location \(Lo_{p}\), end location \(Le_{p}\), earliest departure time \(\omega_{p}^{e}\), latest arrival time \(\omega_{p}^{l}\), and number of seats requested \(n_{p}\). The driver's requirements are represented by \(R_{d}=(Lo_{d},Le_{d},\omega_{d}^{e},\omega_{d}^{l},a_{d},\overline{\tau}_{d}, \Gamma_{d})\), where \(R_{d}\) is defined by the start location \(Lo_{d}\), end location \(Le_{d}\), earliest departure time \(\omega_{d}^{e}\), latest arrival time \(\omega_{d}^{l}\), number of seats available \(a_{d}\), and maximum detour ratio \(\overline{\tau}_{d}\). That is, \(R_{d}=(Lo_{d},Le_{d},\omega_{d}^{e},\omega_{d}^{l},a_{d},\overline{\tau}_{d})\). The bids for passenger agents and driver agents could be generated by a bid generation procedure, such as that used in [12]. The bids generated by the bid generation procedure in [12] satisfied the spatial and temporal constraints of drivers and passengers and the capacity constraints of individual cars. All the other constraints were formulated and handled in the discount-guaranteed ridesharing problem introduced below. The bid of passenger agent \(p\) is denoted by \(PB_{p}=(S_{p1},\,S_{p2},\,S_{p3},\,\ldots,\,S_{pK},f_{p})\), where \(S_{pk}\) is the number of seats requested by passenger agent \(p\) for location \(k\) and \(f_{p}\) is the cost for passenger agent \(p\) without ridesharing. For a driver agent's bid, we used \(DB_{dj}=(q_{dj1},\,q_{dj2},\,q_{dj3},\,\ldots,\,q_{djp},\,a_{dj},\,c_{dj})\) to represent the \(j\)-th bid of driver agent \(d\), where \(q_{djp}\) is the available seats to serve passenger agent \(p\), \(o_{dj}\) is the original cost when the driver travels alone, and \(c_{dj}\) is the travel cost of the bid. Based on the bids submitted by the passenger agents and driver agents, \(PB_{p}\forall p\in\{1,2,3,\ldots P\}\) and \(DB_{dj}\forall d\in\{1,2,\ldots,D\}\), respectively, the ridesharing service agent must determine the winning bids such that the cost savings discount for all the winners is no less than the minimal expected cost savings discount. A discount-guaranteed ridesharing problem was formulated to describe this optimization problem, as described below. Just like the existing studies that focus on cost-saving optimization in ridesharing problems, the discount-guaranteed ridesharing problem considered in this paper had to satisfy several constraints. These constraints included the supply and demand constraints, the positive cost savings constraint, the single winning bid constraint for drivers, and the cost savings discount constraints for drivers and passengers. The potential drivers and passengers submit bids to the ridesharing system according to their transport requirements with the bid generation software tool. The bid generation software tool generates bids that satisfy the timing and capacity constraints. The winning bids are determined by solving the discount-guaranteed ridesharing problem, as formulated below. Different ways of allocating cost savings to ridesharing participants have been proposed in the literature and applied in practice. To formulate the discount-guaranteed ridesharing problem, we used the proportional allocation scheme to allocate cost savings to ridesharing participants. Under the proportional allocation scheme, the cost savings are allocated according to the costs for each ridesharing participant. The total cost savings can be calculated by \(H(x,y)=\left(\sum\limits_{p=1}^{P}y_{p}\left(f_{p}\right)\right)-\left(\sum \limits_{d=1}^{D}\sum\limits_{j=1}^{Id}x_{dj}(c_{dj}-o_{dj})\right)\). Let us define the set of passengers in the ride corresponding to the \(j\)-th bid submitted by driver \(d\) as \(\Gamma_{dj}\). Let \(c_{pdf}\) be the travel cost for passenger \(p\) on the ride of the \(j\)-th bid submitted by driver \(d\), where \(p\in\Gamma_{dj}\).