## 1 Introduction
The operation of the MAS is very similar to auctions [10]. Modeling transportation systems with combinatorial auctions in a MAS was studied in [11]. The problem setting of ridesharing systems is more complex due to the presence of many transportation constraints on the side of both the driver agents and the passenger agents. Therefore, although the operation of a ridesharing system is similar to that of combinatorial double auctions in a MAS, the constraints on ridesharing systems are different to those on classic combinatorial double auctions. These differences pose a challenge for determining the winning bids for ridesharing systems. Applying combinatorial double auctions in a MAS to model ridesharing system has been studied in [12]. In this paper, we follow the double auction model of [12] and extend the additional constraints to incorporate the discount guarantee aspect of our ridesharing system. Due to exponential growth of the solution space and the number of solutions, finding a solution for classical combinatorial double auctions is already challenging from a computational point of view [13; 14]. A general combinatorial double auction is known to be an NP-hard problem in terms of computational complexity [14]. The constraints related to the issue of the guaranteed discount introduced additional complexity and posed a new challenge. Due to the complexity of the optimization problem, we adopted two evolutionary computation approaches [15; 16] to solve the problem. Ten algorithms were developed, and we illustrated the proposed method by an example. The results indicated that the proposed method could guarantee that the cost savings discount for users was no lower than the minimal expected cost savings discount. We compared the performance and efficiency of the ten algorithms proposed in this study by conducting two series of experiments and analyzing the results. Our findings provide insight into the selection of an appropriate algorithm to solve the discount-guaranteed ridesharing problem. The contributions of this paper are threefold:  
1. First, we propose a decision problem that offers a minimal cost savings discount for drivers and passengers. The ability to offer a minimal cost savings discount to users is essential for incentivizing participants to accept a ridesharing model. However, the existing literature and our previous paper only focused on the maximization of the overall savings or benefits. The issue of guaranteeing a minimal cost savings discount in ridesharing systems has not been addressed in the literature. Hence, the problem addressed and the decision model proposed in this paper are different from those discussed in our previous studies and the existing literature, in that we focus on the discount-guaranteed ridesharing problem. 2. Second, ten solution algorithms are proposed in this study to provide decision support tools for finding a set of users for whom the minimal cost savings discount can be guaranteed and the total cost savings achieved can be optimized. 3. Third, we compare the proposed algorithms by analyzing the results of several test cases to provide a guideline for selecting an appropriate solution algorithm. The organization of the rest of this paper is as follows. A review of the ridesharing literature is provided in Section 2. Following the literature review, the details of the discount-guaranteed ridesharing problem are described and formulated in Section 3. Several approaches to solving the discount-guaranteed ridesharing problem are proposed in Section 4. The experiments carried out based on the proposed methods are reported in Section 5, which consists of two subsections: an example for the verification of the proposed solution method is illustrated in Section 5.1, and a comparison of the ten algorithms is performed in Section 5.2. In Section 6, we analyze and discuss the results. Finally, we draw our conclusions in Section 7.