Trust-Based Recommendation for Shared Mobility Systems Based on a Discrete Self-Adaptive Neighborhood Search Differential Evolution Algorithm

Abstract

Safety is one concern that hinders the acceptance of ridesharing in the general public. Several studies have been conducted on the trust issue in recent years to relieve this concern. The introduction of trust in ridesharing systems provides a pragmatic approach to solving this problem. In this study, we will develop a trust-aware ridesharing recommender system decision model to generate recommendations for drivers and passengers. The requirements of trust for both sides, drivers and passengers, are taken into consideration in the decision model proposed in this paper. The decision model considers the factors in typical ridesharing systems, including vehicle capacities, timing, location and trust requirements, etc. The decision model aims to determine the shared rides that minimize cost while respecting the trust and relevant constraints. As the decision problem is a nonlinear integer programming problem, we combine a self-adaptive neighborhood search with Differential Evolution to develop an algorithm to solve it. To assess the effectiveness of the proposed algorithm, several other evolutionary computation approaches are also applied to solve the same problem. The effectiveness assessment is done based on the performance of applying different algorithms to find solutions for test cases, to provide a guideline for selecting a proper solution approach.

1. Introduction

Shared mobility refers to transportation services and resources shared among users. Depending on the resources used, several types of transportation modes emerge, e.g., bike-sharing, scooter sharing, carsharing and ridesharing. With shared mobility, the number of e-hailing trips roughly tripled in four years. It has created over 40 million e-hailing trips daily on major e-hailing platforms [1]. Due to the potential benefits to reduce overall costs, energy consumption and greenhouse gas emissions, shared mobility sparks many new research directions and opportunities. Shared mobility may take different forms in the shared economy era. Ridesharing and carpooling are two well-known transportation modes in shared mobility. In Ref. [2,3], an early survey of ridesharing problems was discussed. Ridesharing services rely on an effective recommender system to generate recommendations for users. A ridesharing recommender system must take into account the factors of location, time and cost savings. The research issues relevant to the design of such ridesharing recommender systems include modeling, optimization and allocation of cost savings. These research issues pose challenges in the development of ridesharing recommender systems [4,5].

Despite the numerous potential advantages of ridesharing, e.g., reducing energy consumption, travel cost, greenhouse gas emissions and providing a flexible alternative other than public transport with fixed routing, the concern about safety and trust still hinders the progress for accepting the ridesharing transportation mode. Safety and trust are the primary concern for not adopting ridesharing. One approach to ensuring safety and trust is to exploit the social relation information about potential ridesharing participants from social media [6]. Therefore, several studies on ensuring safety/trust in ridesharing through social networks have been carried out in recent years [7,8,9,10,11,12]. The decision models to generate recommendations for the trust-based ridesharing problem are generally formulated as non-linear integer programming problems, which consist of non-linear constraints and discrete decision variables. These problems are typically non-convex and the computational complexity grows with the scale of the problems. Therefore, an exact optimization method cannot be applied. Instead, approximate methods, such as evolutionary computation approaches, are adopted to find solutions. For example, ridesharing systems that consider the trust factor have been studied in [13,14,15], based on Particle Swarm Optimization (PSO) [16] and Differential Evolution (DE) [17] approaches.

In the literature on evolutionary computation, PSO [16] and DE [17] have over two decades of history and have been successfully applied to problems in several domains. Many variants of Particle Swarm Optimization approaches and Differential Evolution approaches have been proposed. For example, a discrete version of a Particle Swarm Optimization algorithm has been applied to solve to ridesharing problem with trust requirements in [13]. In Ref. [14], a discrete version of Differential Evolution has been developed to solve the trust-based ridesharing problem. Combining a neighborhood search with a Differential Evolution approach is adopted in [15] to solve the trust-based ridesharing problem. However, the effectiveness of applying different variants of DE approaches to solve the trust-based ridesharing decision problem needs to be studied. This study aims to develop a variant of a metaheuristic algorithm to solve the trust-based ridesharing decision problem with the goal to find a more effective solution algorithm. To achieve this goal, we will combine a self-adaptive neighborhood search with Differential Evolution (SaNSDE) to develop an algorithm. In particular, we will study the influence of the learning period parameter on the efficiency of the proposed discrete SaNSDE algorithm. We will assess the effectiveness of the proposed algorithm by comparing the proposed algorithm with other approaches, based on the results obtained by applying these algorithms to solve several test cases of the trust-based ridesharing problems.

The decision problem studied in this paper is different from the studies of [18,19], in that trust requirements are considered. This paper is also different from our recent study on the allocation of cost savings in [20], where trust requirements are not considered. The trust model adopted in this paper is different from the ones used in [9,11]. The contributions of this paper include a problem formulation for trust-based ridesharing systems and the development of a more effective self-adaptive neighborhood search algorithm for solving the trust-based ridesharing problem. The remainder of this paper is structured as follows. In Section 2, we first give a review of the literature relevant to the enhancement of trust in ridesharing systems. We will present the decision model of trust-based ridesharing systems in Section 3. We will propose several algorithms based on several variants of the DE approach in Section 4. In Section 5, we will present the results obtained by applying the algorithms developed. In Section 6, we will discuss the results and provide suggestions for selecting an effective solution approach to the trust-based ridesharing problem. We conclude this paper in Section 7.

2. Literature Review

Although ridesharing is helpful to reduce the number of cars, energy consumption and cost, there are still concerns from drivers and riders in ridesharing. These concerns are the primary obstacles for ridesharing. According to [21,22], cost and time are two determinant factors for the adoption of ridesharing. The issue to maximize monetary incentive has been studied in [19]. Proper allocation of cost savings is an important issue in ridesharing systems [20]. In addition to the two determinant factors for the adoption of ridesharing, according to the review about rideshare crime rates and safety tips in [23], over 3000 sexual assaults were reported in one year for one major ridesharing company, not including unreported cases. The study in [24] indicates that women feel less safe and comfortable when they share a ride in the night or with male strangers. In particular, young women and unemployed women have less trust in ridesharing. Therefore, how to ensure safety and trust in ridesharing systems is an important research issue to promote ridesharing.

One way to ensure safety/trust is to take advantage of the social relationship of ridesharing participants in relevant social networks. Social media provides a platform to extract the information of social networks. A recent survey on the challenges and opportunities of using social media to support ridesharing services is available in [6]. The types of ridesharing based on social networks are referred to as social ridesharing, sharing rides with friends or social-aware ridesharing in the literature. There are several studies relevant to social ridesharing. For example, in [7], the authors proposed a coalition formation algorithm for sharing rides with friends. A cooperative game-theoretic approach to the social ridesharing problem was proposed in [8]. The study of [8] considers a social network described by a graph to describe the social relationship between ridesharing participants. The social network restricts the formation of groups for creating a feasible coalition. A set of riders in the social network are a feasible coalition, if there exists a connected subgraph on the social network and there is at least one rider whose car has enough seats for all the members. However, the social network used in [8] does not consider the level of social relationship between ridesharing participants. In Ref. [9], the authors considered a social-aware ridesharing group query problem. The study of [9] indicates that the social-aware ridesharing group query problem is NP-hard. In Ref. [10], a relevant study of [9], an efficient method to match offers and requests in social-aware ridesharing was developed. A carpooling model based on both social and route networks was proposed in [11]. In Ref. [11], the degrees of separation concept and user preference are used to specify trust between ridesharing participants in the social networks. In [11], two problems are formulated: one problem aims to optimize trust in a ridesharing team based on social networks and the other problem is to minimize the cost for a ridesharing team with an integer programming model based on route networks. A decision model is obtained by combining the trust optimization problem and cost optimization problem. The concept of cohesive ridesharing in geo-social networks was studied in [12]. In Ref. [25], the authors take into account both social relations and revenue in the social-aware ridesharing group query problem.

The social network considered in the papers above is based on the social distance in social network model (an undirected graph). However, in the real world, the level that one participant trusts another may not be totally dependent on the social distance between them. For example, consider two people, A and B. Suppose A is a friend of B. But A also knows B often cannot be on time. The level that A trusts B is low. Suppose A is also a friend of C. Suppose the social distance between A and C is the same as that between A and B. A also knows C is always on time. The level that A trusts C is higher than the level that A trusts B. The above example indicates that although the level of trust between two participants may be linked to social distance, it may be negatively related to social distance between the two participants. A proper model to capture the level that one participant trusts another will be introduced in this paper.

Based on the discussion above, the goals of this study are to propose a decision model for ridesharing, based on a proper trust model, and develop a relevant solution methodology for solving the decision problem. For the decision problem to be addressed in this study, temporal constraints, spatial constraints and constraints due to trust requirements are considered. The decision model proposed in this paper aims to match multiple requests, which is different from the ones in [9,25]. The trust model used in this study can flexibly describe the level that one participant trusts another. In the proposed trust model, the trust level between two ridesharing participants may or may not be negatively related to social distance between the two participants. Therefore, the trust model adopted in this paper is different from the ones used in [9,11,25]. The decision model proposed in this study can be applied regardless of whether the level of trust between two participants is negatively related to their social distance.

The trust-based ridesharing problem is formulated as a non-linear integer programming problem, which consists of non-linear constraints and discrete decision variables. These problems are typically non-convex and the computational complexity grows with the scale of the problems. Therefore, an exact optimization method cannot be applied. Instead, approximate methods, such as evolutionary computation approaches, are adopted to find solutions. Evolutionary computation is inspired by biological evolution for global optimization. In evolutionary computation, a population of solutions is generated initially. The population of solutions is iteratively updated based on mutation and natural selection. Selection is based on the fitness function. Based on the iteratively updated solutions of population and natural selection, the quality of individuals in the population will be improved gradually. In the literature, a lot of evolutionary algorithms have been proposed to solve optimization problems. These include Differential Evolution [17], Particle Swarm Optimization [16] and Firefly algorithms [26], and their variants [27,28,29]. In this study, we will adopt several variants of Differential Evolution to develop algorithms to solve the trust-based ridesharing decision problem.

Many variants of DE algorithms have been proposed to improve the original DE method, including Differential Evolution with Neighborhood Search (NSDE) [30] and Self-adaptive Differential Evolution (SaDE) [31] and Self-adaptive NSDE (SaNSDE) [32], where SaNSDE is able to adapt the parameters of DE and combines the neighborhood search capability of NSDE. As the original DE and variants of DE algorithms are targeted at problems with continuous search space, these methods need to be modified for the discrete optimization problem formulated in this paper. In this paper, we will combine a self-adaptive neighborhood search with Differential Evolution to develop an algorithm variant of a discrete DE algorithm. In particular, we will study the influence of the learning period parameter on the efficiency of the proposed discrete SaNSDE algorithm. We will assess the effectiveness of the proposed algorithm by comparing with two Particle Swarm Optimization-based algorithms (standard PSO [13] and ALPSO [33]), a Firefly algorithm [26] and several DE algorithms, by applying these algorithms to the same set of test cases. We analyze the results of the experiments to compare the effectiveness of the algorithms mentioned above.

3. The Recommendation Problem of Trust-Based Shared Mobility Systems

In this section, we consider a shared mobility system in which trust requirements are considered. In shared mobility systems, drivers share rides with passengers to meet the transportation requirements. In this paper, a shared mobility system that considers the trust requirements of passengers and drivers is called a trust-based shared mobility system. A driver and a passenger can share a ride only if their trust requirements can be satisfied.

Although social network provides the social distance information that may be linked to safety or trust between people, in the real world, the level that one participant trusts another may not be totally dependent on the social distance between them. For example, consider two people, A and B, who are friends. Suppose A is always on time whereas B is rarely on time. The level that A trusts B is low but the level that B trusts A is high. The above example indicates that shorter social distance in the social network does not always imply a higher level of trust. That is, social distance may not always be negatively related to the level of trust. A proper trust model to capture the level that one participant trusts another is used in this study. The trust model used in this study can flexibly describe the level that one participant trusts another. In the proposed trust model, the trust level between two ridesharing participants may or may not be negatively related to social distance between the two participants. The solution methodology proposed in this study can still be applied, regardless of whether the trust model is the same as the social distance model. To describe the decision model in this paper, we summarize the notations used in this paper in

Table 1. Notations of symbols, variables and parameters.

Variable	Meaning
$P$	total number of potential passengers
$D$	total number of potential drivers
$K$	$\mathrm{total} \mathrm{number} \mathrm{of} \mathrm{locations} \mathrm{of} \mathrm{passengers}, K$
$p$	$\mathrm{a} \mathrm{passenger}, \mathrm{where} p\in \{1,2,3,\dots P\}$
$d$	$\mathrm{a} \mathrm{driver}, \mathrm{where} d\in \{1,2,3,\dots ,D\}$
$k$	$\mathrm{a} \mathrm{location}, k\in \{1,2,\dots ,K\}$
$J_d$	$\mathrm{total} \mathrm{bids} \mathrm{of} \mathrm{driver} d\in \{1,2,\dots ,D\}$
$j$	$\mathrm{The} j-th$$\mathrm{bid} \mathrm{of} \mathrm{driver} d$$\mathrm{with} j\in \{1,2,\dots ,J_d\}$
${\mathsf{\Gamma }}_d$	$\mathrm{the} \mathrm{minimal} \mathrm{trust} \mathrm{level} \mathrm{requested} \mathrm{by} \mathrm{driver}d$
${\mathsf{\Lambda }}_p$	$\mathrm{the} \mathrm{minimal} \mathrm{trust} \mathrm{level} \mathrm{requested} \mathrm{by} \mathrm{passenger} p$
$V$	the set of nodes associated with drivers and passengers in the social network model
$v_i$	$\mathrm{a} \mathrm{node} \mathrm{in} V$
$E$	the set of edges in the social network model
$e_{ij}$	$\mathrm{a} \mathrm{directed} \mathrm{edge} \mathrm{in} E$$\mathrm{connecting} v_i$$\mathrm{to} v_j$$, \mathrm{where} v_i,v_j\in V$
$\mathsf{\Theta }$	$\mathrm{a} \left|V\right|$$\mathrm{by} \left|V\right|$$\mathrm{matrix} \mathrm{with} \mathrm{element} {\mathsf{\Theta }}_{ij}$$\mathrm{for} \mathrm{all} v_i,v_j\in V$$, \mathrm{where} {\mathsf{\Theta }}_{ij}$$\mathrm{is} \mathrm{the} \mathrm{trust} \mathrm{level} \mathrm{that} v_i$$\mathrm{trusts} v_j$.
$S(V,E,\mathsf{\Theta })$	$\mathrm{a} \mathrm{graph} \mathrm{model} \mathrm{of} \mathrm{the} \mathrm{social} \mathrm{network} \mathrm{with} \mathrm{a} \mathrm{set} \mathrm{of} \mathrm{nodes}, V$$, \mathrm{a} \mathrm{set} \mathrm{of} \mathrm{edges} \mathrm{and} \mathrm{weight} \mathsf{\Theta }$.
$R_p$	$\mathrm{a} \mathrm{passenger}’\mathrm{s} \mathrm{request}; R_p$$=(L{o}_p,L{e}_p,{\omega }_p^e,{\omega }_p^l,n_p,{\mathsf{\Lambda }}_p)$$, \mathrm{where} R_p$$\mathrm{is} \mathrm{defined} \mathrm{by} \mathrm{the} \mathrm{origin} L{o}_p$$, \mathrm{destination}, L{e}_p$$, \mathrm{earliest} \mathrm{departure} \mathrm{time}, {\omega }_p^e$$, \mathrm{latest} \mathrm{arrival} \mathrm{time}, {\omega }_p^l$$, \mathrm{number} \mathrm{of} \mathrm{passengers}, n_p$$, \mathrm{and} \mathrm{the} \mathrm{minimal} \mathrm{trust} \mathrm{level} \mathrm{requested}, {\mathsf{\Lambda }}_p$.
$R_d$	$\mathrm{a} \mathrm{driver}’\mathrm{s} \mathrm{request}; R_d$$=(L{o}_d,L{e}_d,{\omega }_d^e,{\omega }_d^l,a_d,{\overline{\tau }}_d,{\mathsf{\Gamma }}_d)$$, \mathrm{where} R_d$$\mathrm{is} \mathrm{defined} \mathrm{by} \mathrm{the} \mathrm{origin}, L{o}_d$$, \mathrm{destination}, L{e}_d$$, \mathrm{earliest} \mathrm{departure} \mathrm{time}, {\omega }_d^e$$, \mathrm{latest} \mathrm{arrival} \mathrm{time}, {\omega }_d^l$$, \mathrm{quantity} \mathrm{of} \mathrm{seats} \mathrm{available}, a_d$$, \mathrm{maximum} \mathrm{detour} \mathrm{ratio}, {\overline{\tau }}_d$$, \mathrm{and} \mathrm{the} \mathrm{minimal} \mathrm{trust} \mathrm{level} {\mathsf{\Gamma }}_d$$. \mathrm{That} \mathrm{is}, R_d$$=(L{o}_d,L{e}_d,{\omega }_d^e,{\omega }_d^l,a_d,{\overline{\tau }}_d,{\mathsf{\Gamma }}_d)$.
$D\_BI{D}_{dj}$	$D\_BI{D}_{dj}$$=(q_{dj1}^1,q_{dj2}^1,\dots ,q_{djk}^1,\dots ,q_{djK}^1,q_{dj1}^2,q_{dj2}^2,\dots ,q_{djk}^2,\dots ,q_{djK}^2,{\pi }_{dj},o_{dj},c_{dj},a_d,{\mathsf{\Gamma }}_d)$$, \mathrm{the} j-th$$\mathrm{bid} \mathrm{of} \mathrm{driver} d$$, \mathrm{where} K$$\mathrm{is} \mathrm{the} \mathrm{number} \mathrm{of} \mathrm{locations}, q_{djk}^1$$\mathrm{is} \mathrm{the} \mathrm{number} \mathrm{of} \mathrm{seats} \mathrm{available} \mathrm{to} \mathrm{pick} \mathrm{up} \mathrm{passengers} \mathrm{at} \mathrm{location} k$$, q_{djk}^2$$\mathrm{is} \mathrm{the} \mathrm{number} \mathrm{of} \mathrm{seats} \mathrm{released} \mathrm{after} \mathrm{dropping} \mathrm{passengers} \mathrm{at} \mathrm{location} P+k$$, o_{dj}$$\mathrm{is} \mathrm{the} \mathrm{original} \cos \mathrm{t} \mathrm{of} \mathrm{driver} d$$\mathrm{without} \mathrm{ridesharing}, c_{dj}$$\mathrm{is} \mathrm{the} \cos \mathrm{t} \mathrm{for} \mathrm{driver} d$$\mathrm{to} \mathrm{transport} \mathrm{passengers} \mathrm{in} \mathrm{the} \mathrm{bid}, a_d$$\mathrm{is} \mathrm{the} \mathrm{total} \mathrm{number} \mathrm{of} \mathrm{seats} \mathrm{and} {\mathsf{\Gamma }}_d$ is the minimal trust level requested.
$P\_BI{D}_p$	$P\_BI{D}_p$$=(s_{p1}^1,s_{p2}^1,s_{p3}^1,\dots ,s_{pK}^1,s_{p1}^2,s_{p2}^2,s_{p3}^2,\dots ,s_{pK}^2,f_p,{\mathsf{\Lambda }}_p)$$: \mathrm{the} \mathrm{bid} \mathrm{of} \mathrm{passenger} p$, where $\mathrm{where} K$$\mathrm{is} \mathrm{the} \mathrm{number} \mathrm{of} \mathrm{locations}, s_{pk}^1$$\mathrm{is} \mathrm{the} \mathrm{number} \mathrm{of} \mathrm{seats} \mathrm{requested} \mathrm{to} \mathrm{pick} \mathrm{up} \mathrm{passengers} \mathrm{at} \mathrm{location} k$$, s_{pk}^2$$\mathrm{is} \mathrm{the} \mathrm{number} \mathrm{of} \mathrm{seats} \mathrm{released} \mathrm{after} \mathrm{dropping} \mathrm{passengers} \mathrm{at} \mathrm{location} P+k$$, f_p$$\mathrm{is} \mathrm{the} \mathrm{bid} \mathrm{price} \mathrm{and} {\mathsf{\Lambda }}_p$ is the minimal trust level requested.
$x_{dj}$	$\mathrm{a} \mathrm{binary} \mathrm{decision} \mathrm{variable}; x_{dj}$$\mathrm{equals} 1 \mathrm{if} \mathrm{the} j-th$$\mathrm{bid} \mathrm{of} \mathrm{driver} d$$\mathrm{is} \mathrm{a} \mathrm{winning} \mathrm{bid} \mathrm{and} x_{dj}$ equals 0 otherwise
$y_p$	$\mathrm{a} \mathrm{binary} \mathrm{decision} \mathrm{variable}; y_p$$\mathrm{equals} 1 \mathrm{if} \mathrm{the} \mathrm{bid} \mathrm{of} \mathrm{passenger} p$$\mathrm{is} \mathrm{a} \mathrm{winning} \mathrm{bid} \mathrm{and} y_p$ equals 0 otherwise
$F(x,y)$	$\mathrm{overall} \cos \mathrm{t} \mathrm{savings},F(x,y)=\left({\displaystyle \sum _{p=1}^P{y}_p\left(f_p^{}\right)}\right)+\left({\displaystyle \sum _{d=1}^D{\displaystyle \sum _{j=1}^{J_d}}{x}_{dj}{o}_{dj}}\right)- \left({\displaystyle \sum _{d=1}^D{\displaystyle \sum _{j=1}^{J_d}}{x}_{dj}{c}_{dj}}\right)$

.

Trust between drivers and passengers is described based on their social network. The trust requirements are directly related to the connection of drivers and passengers in the social network. A graph-based model is adopted in this study to represent the social network. To represent drivers and passengers in the social network model, we use $V$ to denote the set of nodes associated with drivers and passengers. The trust level between nodes is represented by weight, associated with the set of edges, $E$, in the social network model. Let $v_i$ and $v_j$ be two nodes in $V$. We use $e_{ij}$ to denote a directed edge $e_{ij}$ connecting $v_i$ to $v_j$ and use weight ${\mathsf{\Theta }}_{ij}$ to denote the trust relation between $v_i$ and $v_j$, where the weight ${\mathsf{\Theta }}_{ij}$ specifies the degree (trust level) that $v_i$ trusts $v_j$. As the goal of this study is to develop a decision model and relevant solution methodology, it is assumed that ${\mathsf{\Theta }}_{ij}$ is available.

Let $\mathsf{\Theta }$ denote the $\left|V\right|$ by $\left|V\right|$ matrix with element ${\mathsf{\Theta }}_{ij}$ for all $v_i,v_j\in V$. The greater the value of ${\mathsf{\Theta }}_{ij}$, the more $v_i$ trusts $v_j$. If ${\mathsf{\Theta }}_{ij}$ equals zero, $v_i$ does not trust $v_j$. More specifically, there is a directed edge $e_{ij}$ connecting $v_i$ to $v_j$ with weight ${\mathsf{\Theta }}_{ij}$ for each $v_i$ and $v_j$ in $V$. We use a graph $S(V,E,\mathsf{\Theta })$ with weight $\mathsf{\Theta }$ to compactly represent the trust model.

In a trust-based shared mobility system, a driver may request his/her minimal trust level requirements to share a ride with a passenger. If the minimal trust level requirements requested by the driver cannot be satisfied, the driver will not share a ride with the passenger. Similarly, a passenger may request his/her minimal trust level requirements to share a ride with a driver. If the minimal trust level requirements requested by the passenger cannot be satisfied, the passenger will not share a ride with the driver. Furthermore, a passenger, say A, may request his/her minimal trust level requirements to share a ride with another passenger, say B. If the minimal trust level requirements requested by passenger A cannot be satisfied, passenger A will not share a ride with passenger B.

To represent the above trust level requirements requested by drivers and passengers, we use ${\mathsf{\Gamma }}_d$ to denote the minimal trust level requested by driver $d$ and ${\mathsf{\Lambda }}_p$ to denote the minimal trust level requested by passenger $p$. A driver $d$ will share a ride with passenger $p$ only if ${\mathsf{\Theta }}_{dp}\ge {\mathsf{\Gamma }}_d$. A passenger $p$ can be a rider with driver $d$ only if ${\mathsf{\Theta }}_{pd}\ge {\mathsf{\Lambda }}_p$. A passenger $p$ can be a rider with another passenger $p^{\prime }$ only if ${\mathsf{\Theta }}_{p{p}^{\prime }}\ge {\mathsf{\Lambda }}_p$.

Potential drivers and passengers express their transportation requirements and trust requirements by submitting requests to the shared mobility system. The shared mobility system needs to determine the drivers and passengers for ridesharing.

To formulate the decision problem, information from the requests submitted by drivers and passengers are briefly described first. A request of passenger $p$ is denoted by $R_p$, where $R_p$ is defined by the origin $L{o}_p$, destination, $L{e}_p$, earliest departure time, ${\omega }_p^e$, latest arrival time, ${\omega }_p^l$, number of passengers, $n_p$, and the minimal trust level requested, ${\mathsf{\Lambda }}_p$. That is, $R_p$ = $(L{o}_p,L{e}_p,{\omega }_p^e,{\omega }_p^l,n_p,{\mathsf{\Lambda }}_p)$.

A driver’s request is denoted by $R_d$, where $R_d$ is defined by the origin, $L{o}_d$, destination, $L{e}_d$, earliest departure time, ${\omega }_d^e$, latest arrival time, ${\omega }_d^l$, quantity of seats available, $a_d$, maximum detour ratio, ${\overline{\tau }}_d$, and the minimal trust level ${\mathsf{\Gamma }}_d$. That is, $R_d$ = $(L{o}_d,L{e}_d,{\omega }_d^e,{\omega }_d^l,a_d,{\overline{\tau }}_d,{\mathsf{\Gamma }}_d)$.

Let $P$ be the total number of potential passengers that submit requests to the shared mobility system and let $\{1,2,\dots ,P\}$ be the set of all potential passengers. Without loss of generality, it is assumed that there is only one request, $R_p$, submitted by each passenger $p\in \{1,2,\dots ,P\}$. For each passenger $p\in \{1,2,\dots ,P\}$, a procedure will be invoked by the shared mobility system to generate bid $P\_BI{D}_p$ = $(s_{p1}^1,s_{p2}^1,s_{p3}^1,\dots ,s_{pK}^1,s_{p1}^2,s_{p2}^2,s_{p3}^2,\dots ,s_{pK}^2,f_p,{\mathsf{\Lambda }}_p)$ based on $R_p$, where $K$ is the number of locations, $s_{pk}^1$ is the number of seats requested to pick up passengers at location $k$, $s_{pk}^2$ is the number of seats released after dropping passengers at location $P+k$, $f_p$ is the bid price and ${\mathsf{\Lambda }}_p$ is the minimal trust level requested.

Let $D$ denote the total number of potential drivers that submit requests to the shared mobility system and let $\{1,2,\dots ,D\}$ be the set of all potential drivers. Without loss of generality, it is assumed that there is only one request, $R_d$, will be submitted by each driver $d\in \{1,2,\dots ,D\}$. For each driver $d\in \{1,2,\dots ,D\}$, a procedure will be invoked by the shared mobility system to generate $J_d$ bids $D\_BI{D}_{dj}$ = $(q_{dj1}^1,q_{dj2}^1,\dots ,q_{djk}^1,\dots ,q_{djK}^1,q_{dj1}^2,q_{dj2}^2,\dots ,q_{djk}^2,\dots ,q_{djK}^2,{\pi }_{dj},o_{dj},c_{dj},a_d,{\mathsf{\Gamma }}_d)$ based on $R_d$, where $J_d$ is the total number of bids of a driver $d$, $j$ is the $j-th$ bid of driver $d$ with $j\in \{1,2,\dots ,J_d\}$, $K$ is the number of locations, $q_{djk}^1$ is the number of seats available to pick up passengers at location $k$, $q_{djk}^2$ is the number of seats released after dropping passengers at location $P+k$, $o_{dj}$ is the original cost of driver $d$ without ridesharing, $c_{dj}$ is the cost for driver $d$ to transport passengers in the bid, $a_d$ is the total number of seats and ${\mathsf{\Gamma }}_d$ is the minimal trust level requested.

Based on the bids, $P\_BI{D}_p$, $p\in \{1,2,\dots ,P\}$ and $D\_BI{D}_{dj}$, $d\in \{1,2,\dots ,D\}$, $j\in \{1,2,\dots ,J_d\}$, we define decision variables, $x_{dj}$$\forall d\in \{1,\dots ,D\} \forall j\in \{1,\dots ,J_d\}$ for the bids submitted by drivers. The $j$-th bid placed by driver $d$ is a winning bid if $x_{dj}$ = 1. Otherwise, $x_{dj}$ = 0. We define decision variables as, $y_p$$\forall p\in \{1,2,3,\dots P\}$. The bid submitted by passenger $p$ is a winning bid if $y_p$ = 1 and is not a winning bid if $y_p$ = 0. We define the objective function defined in (1) to maximize the cost savings, where $F(x,y)={\displaystyle \sum _{p=1}^P{y}_p{f}_p^{}}+{\displaystyle \sum _{d=1}^D{\displaystyle \sum _{j=1}^{J_d}}}{x}_{dj}(o_{dj}-c_{dj})$.

We formulate the problem for trust-based shared mobility systems considering the constraints that the number of seats supplied and the number of seats requested at each pick-up location must be the same (defined in (2)), the number of seats released must be equal to the number of passengers dropped off at each drop-off location (defined in (3)), the cost savings must be nonnegative (defined in (4)), each driver can have at most one bid accepted (defined in (5)), the minimal trust level requested by each driver must be satisfied (defined in (6)) and the minimal trust level requested by each passenger must be satisfied (defined in (7)). The decision variables must be binary (defined in (8)). The problem formulation is as follows:

$$\begin{array}{l}\underset{x,y}{\max } F(x,y)\\ s.t.\end{array}$$

(1)

$${\displaystyle \sum _{d=1}^D{\displaystyle \sum _{j=1}^{J_d}{x}_{dj}{q}_{djk}^1}=y_p{s}_{pk}^1}\hspace{1em}\forall p\in \{1,2,\dots ,P\} \hspace{1em}\forall \mathrm{k}\in \{1,2,\dots ,P\}$$

(2)

$${\displaystyle \sum _{d=1}^D{\displaystyle \sum _{j=1}^{J_d}{x}_{dj}{q}_{djk}^2}=y_p{s}_{pk}^2}\hspace{1em}\forall p\in \{1,2,\dots ,P\} \hspace{1em}\forall \mathrm{k}\in \{1,2,\dots ,P\}$$

(3)

$${\displaystyle \sum _{p=1}^P{y}_p{f}_p^{}}+{\displaystyle \sum _{d=1}^D{\displaystyle \sum _{j=1}^{J_d}}{x}_{dj}{o}_{dj}}\ge {\displaystyle \sum _{d=1}^D{\displaystyle \sum _{j=1}^{J_d}}{x}_{dj}{c}_{dj}}$$

(4)

$${\displaystyle \sum _{j=1}^{J_d}}{x}_{dj}\le 1\hspace{1em}\forall d\in \{1,\dots ,D\}$$

(5)

$$\begin{array}{l}{\displaystyle \sum _{k=1}^K{q}_{djk}{s}_{pk}}{x}_{dj}{y}_p({\mathsf{\Theta }}_{dp}{x}_{dj}{y}_p-{\mathsf{\Gamma }}_d)\ge 0\\ \forall d\in \{1,\dots ,D\}\forall j\in \{1,\dots ,J_d\}\forall p\in \{1,2,3,\dots P\}\end{array}$$

(6)

$$\begin{array}{l}{\displaystyle \sum _{k=1}^K{q}_{djk}{s}_{pk}}{x}_{dj}{y}_p({\mathsf{\Theta }}_{dp}{x}_{dj}{y}_p-{\mathsf{\Lambda }}_p)\ge 0\\ \forall d\in \{1,\dots ,D\} \forall j\in \{1,\dots ,J_d\} \forall p\in \{1,2,3,\dots P\}\end{array}$$

(7)

$$x_{dj}\in \{0,1\}\forall d\in \{1,\dots ,D\} \forall j\in \{1,\dots ,J_d\},y_p\in \{0,1\}\hspace{1em}\forall p\in \{1,2,\dots ,P\}$$

(8)

4. Development of a Self-Adaptive Neighborhood Search Differential Evolution Algorithm

In this section, we will present the proposed algorithm.

Table 2. Notations of symbols, variables and parameters used in the proposed algorithm.

Variable	Meaning
$NP$	population size
$G$	number of generations
$g$	the index of a generation
$LP$	learning period
$F_i$	$\mathrm{scale} \mathrm{factor} \mathrm{of} \mathrm{individual} i$
$c{r}_i$	$\mathrm{crossover} \mathrm{rate} \mathrm{of} \mathrm{individual} i$
$f_p$	$\mathrm{a} \mathrm{parameter} \mathrm{to} \mathrm{influence} \mathrm{the} \mathrm{scale} \mathrm{factor} F_i$
$s$	$\mathrm{a} \mathrm{mutation} \mathrm{strategy}: s$$=1 \mathrm{denotes} \mathrm{mutation} \mathrm{strategy} \mathrm{in} \left(9\right) \mathrm{and} s$ = 2 denotes mutation strategy in (13)
$n_1$	the number of individuals (offspring) generated by mutation strategy in (9) that successfully replace the original individual and enter the next generation
$m_1$	the number of individuals(offspring) generated by mutation strategy in (9) that fail to replace the original individual and are discarded
$n_2$	the number of individuals(offspring) generated by mutation strategy in (13) that successfully replace the original individual and enter the next generation
$m_2$	the number of individuals(offspring) generated by mutation strategy in (13) that fail to replace the original individual and are discarded
$f_p$	$\mathrm{a} \mathrm{parameter} \mathrm{to} \mathrm{influence} \mathrm{the} \mathrm{scale} \mathrm{factor} F_i$, $f_p=\frac{n_1(n_2+m_2)}{n_2(n_1+m_1)+n_1(n_2+m_2)}$
$C{R}_{rec}$	$\mathrm{an} \mathrm{array} \mathrm{that} \mathrm{records} \mathrm{the} \mathrm{crossover} \mathrm{rate} \mathrm{value} c{r}_i$$\mathrm{associated} \mathrm{with} \mathrm{individual} i$ that enter the next generation
$C{R}_m$	$\mathrm{a} \mathrm{parameter} \mathrm{to} \mathrm{generate} \mathrm{the} \mathrm{cross} \mathrm{over} \mathrm{rate} c{r}_i$$\mathrm{of} \mathrm{individual} i$ defined by $C{R}_m=\frac{{\displaystyle \sum _{k=1}^{\left|C{R}_{rec}\right|}C{R}_{rec}(k)}}{\left|C{R}_{rec}\right|}$
$r$	$\mathrm{A} \mathrm{random} \mathrm{variable} \mathrm{with} \mathrm{uniform} \mathrm{distribution} U(0,1)$
$r_1$	$\mathrm{A} \mathrm{random} \mathrm{variable} \mathrm{with} \mathrm{Gaussian} \mathrm{distribution} N(\mu ,{\sigma }_1^2)$$\mathrm{with} \mathrm{mean} \mu$$\mathrm{and} \mathrm{standard} \mathrm{deviation} {\sigma }_1$
$r_2$	$\mathrm{A} \mathrm{random} \mathrm{variable} r$$\mathrm{with} \mathrm{uniform} \mathrm{distribution} U(0,1)$

lists the symbols and notations used in this section. In the development of an evolutionary computation algorithm, a fitness function must be properly designed to guide the evolution process to find a solution. A proper fitness function needs to take into consideration the objective function of the problem and the constraints that need to be satisfied. A properly designed fitness function has to guide the evolution process based on constraint violations. We will apply a variant of penalty methods to design a fitness function.

The problem formulated in the previous section is an integer programming optimization problem, in which the decision variables are binary. A characteristic of this problem is the exponential growth of solution space with problem size and constraints. The exponentially growing solution space leads to high complexity from a computational point of view. In the literature, many variants of classical penalty methods have been proposed to deal with constraints in constrained optimization problems by applying penalty methods. Although these methods may work under the proper setting of penalty coefficients, they suffer from parameter tuning problems that are problem/data dependent. It is hard to find a one-size-fits-all approach to finding the right parameters for classical penalty methods. The variant of a penalty method, proposed in [34] and adopted in this paper, is different from the classical penalty methods in that it does not require any penalty parameter. It applies pair-wise comparison between two solutions in the optimization processes to select the better solution in the following way. If both solutions to be compared are feasible, the one with better objective function value will be selected. If one feasible solution and another infeasible solution is to be compared, the feasible one will be selected. If both solutions to be compared are infeasible, the one with a smaller constraint violation will be selected. This approach effectively reduces the constraint violation in the optimization processes and makes the solution found move towards the feasible region.

We adopt the method proposed in [34] to differentiate feasible solutions and infeasible ones. Just like classical penalty methods, this approach also captures the effects of constraint violation by adding several penalties. To describe the above method, we define the following notations. Let $S_f=\{(x,y)\left|(x,y)\right.$$\}$, a solution in the current population, $(x,y)$ satisfies constraints (1)–(8). $S_f$ is the set of all feasible solutions in the current population. Let $S_{f\min }$ be the object function value of the worst feasible solution in the current population. More formally, $S_{f\min }=\underset{(x,y)\in S_f}{\min }F(x,y)$.

The fitness function used in this paper is defined by $F_1(x,y)$ as follows: $F_1(x,y)=\left\{\begin{array}{l}F(x,y) if (x,y) satisfies constraints (1)~(8)\\ U(x,y) otherwise\end{array}\right.$, where

$$\begin{gathered} U(x,y)=S_{f\min }+U_1(x,y)+U_2(x,y)+U_3(x,y)+U_4(x,y)+U_5(x,y) \\ {U}_1(x,y)=\left|{\displaystyle \sum _{p=1}^P{\displaystyle \sum _{k=1}^K}({\displaystyle \sum _{d=1}^D{\displaystyle \sum _{j=1}^{J_d}}}{x}_{dj}{q}_{djk}-y_p{s}_{pk})}\right| \\ {U}_2(x,y)=\left|{\displaystyle \sum _{d=1}^D}(1-{\displaystyle \sum _{j=1}^{J_d}{x}_{dj}})\right| \\ {U}_3(x,y)=\min ({\displaystyle \sum _{p=1}^P{y}_p{f}_p^{}}+{\displaystyle \sum _{d=1}^D{\displaystyle \sum _{j=1}^{J_d}}}{x}_{dj}{o}_{dj}-{\displaystyle \sum _{d=1}^D{\displaystyle \sum _{j=1}^{J_d}}}{x}_{dj}{c}_{dj}),0.0) \\ \begin{array}{l}{U}_4(x,y)\\ ={\displaystyle \sum _{d=1}^D{\displaystyle \sum _{j=1}^{J_d}}}{\displaystyle \sum _{p=1}^P}\min ({\displaystyle \sum _{k=1}^K{q}_{djk}{s}_{pk}})x_{dj}{y}_p({\mathsf{\Theta }}_{dp}{x}_{dj}{y}_p-{\mathsf{\Gamma }}_d),0.0)\end{array} \\ \begin{array}{l}{U}_5(x,y)\\ ={\displaystyle \sum _{d=1}^D{\displaystyle \sum _{j=1}^{J_d}}}{\displaystyle \sum _{p=1}^P}\min ({\displaystyle \sum _{k=1}^K{q}_{djk}{s}_{pk}}{x}_{dj}{y}_p({\mathsf{\Theta }}_{dp}{x}_{dj}{y}_p-{\mathsf{\Lambda }}_p),0.0)\end{array} \end{gathered}$$

As the proposed SaNSDE algorithm is based on an extension of the standard DE algorithm, a brief introduction to the standard DE algorithm will be presented first. The details of the SaNSDE algorithm will be described next.

The standard DE algorithm follows a four-step evolution process to iteratively improve the quality of solutions. The first step of the standard DE algorithm is initialization. Suppose the problem dimension is $L$. In the initialization step, the standard DE algorithm creates a population of $NP$ trial individuals $z_{gi}$ = $(z_{gil})$, where $g$ is the generation index, $i$ is the index of an individual, $i\in \{1,2,\dots ,NP\}$, and $l\in \{1,2,\dots ,L\}$ is the dimension index. In the second step, the DE algorithm generates a mutant vector $v_{gi}$ = $(v_{gil})$ for individual $i$ in the $g$-th generation by applying a mutation strategy. There are six well-known mutation strategies for the standard DE algorithm in the literature. These six mutation strategies are defined based on the best individual $Z_{gbl}$ = $(z_{gbl})$ and the randomly selected individuals, $z_{g{r}_{1}l}$, $z_{g{r}_{2}l}$, $z_{g{r}_{3}l}$, $z_{g{r}_{4}l}$ and $z_{g{r}_{5}l}$, in the population, where $r_1$, $r_2$, $r_3$, $r_4$ and $r_5$ are random integers between 1 and $NP$. The six mutation strategies are defined as follows:

$$v_{(g+1)il}=z_{g{r}_{1}l}+F_i(z_{g{r}_{2}l}-z_{g{r}_{3}l})$$

(9)

$$v_{(g+1)il}=z_{gbl}+F_i(z_{g{r}_{2}l}-z_{g{r}_{3}l})$$

(10)

$$v_{(g+1)il}=z_{g{r}_{1}l}+F_i(z_{g{r}_{2}l}-z_{g{r}_{3}l})+F_i(z_{g{r}_{4}l}-z_{g{r}_{5}l})$$

(11)

$$v_{(g+1)il}=z_{gbl}+F_i(z_{g{r}_{1}l}-z_{g{r}_{2}l})+F_i(z_{g{r}_{3}l}-z_{g{r}_{4}l})$$

(12)

$$v_{(g+1)il}=z_{gil}+F_i(z_{gbl}-z_{gil})+F_i(z_{g{r}_{1}l}-z_{g{r}_{2}l})$$

(13)

$$v_{(g+1)il}=z_{gil}+F_i(z_{gbl}-z_{gil})+F_i(z_{g{r}_{1}l}-z_{g{r}_{2}l})+F_i(z_{g{r}_{3}l}-z_{g{r}_{4}l})$$

(14)

The third step is a crossover operation that follows after a mutant vector $v_{gi}$ is generated. The crossover operation will create a trial vector $u_{gi}$ by selecting the element between the mutant vector $v_{gi}$ and the original individual $z_{gi}$ with some probability. The last step is selection. In the selection step, $z_{gi}$ will be replaced by $u_{gi}$ if $u_{gi}$ is better than $z_{gi}$.

In the proposed Self-adaptive Neighborhood Search Differential Evolution (SaNSDE) Algorithm, the neighborhood search concept is combined with the self-adaptation of mutation strategies and scale factor to search solutions. The pseudocode of the SaNSDE algorithm is shown in

Table 3. The pseudo code of SaNSDE Algorithm.

Discrete Self-Adaptive Neighborhood Search Differential Evolution with (SaNSDE) Algorithm
Step 0: Initialize a population with $NP$ individuals randomly
$C{R}_m=0.5$
$f_p$ = 0.5
For $g=1 to G$
For $i=1 to NP$
Generate a random variable $r$ with uniform distribution $U(0,1)$
If $r<f_p$
Generate a random variable $r_1$ with Gaussian distribution $N(\mu ,{\sigma }_1^2)$
$F_i=r_1$
Else
Generate a random variable $r_2$ with uniform distribution $U(0,1)$
$F_i=r_2$
End If
Generate a random variable $c{r}_i$ with Gaussian distribution $N(C{R}_m,{\sigma }_2^2)$
Step 1:  Create a mutant vector $v_{gi}$
Generate $ran{d}_i=U(0,1)$
If $ran{d}_i<f_p$
$s=1$
Calculate $v_{gi}$ according to (9)
Else
$s=2$
Calculate $v_{gi}$ according to (13)
End If
Step 2:  Create a trial vector $u_{gi}$
For $l\in$1, 2,…, $L$
$u_{gil}=\left\{\begin{array}{l}{v}_{gil} if Rand(0,1)<c{r}_i\\ z_{gil} otherwise\end{array}\right.$
${\overline{u}}_{gil}\leftarrow BinaryTrasform(u_{gil})$
End For
Step 3:  Select the trial vector if it outperforms individual $i$
If $F_1({\overline{u}}_{gi})\ge F_1(z_{gi})$
$z_{(g+1)i}$ = $u_{gi}$
Record $c{r}_i$ in $C{R}_{rec}$
$n_s=n_s+1$
Else
$m_s=m_s+1$
End If
End For
If $g>LP$
$f_p=\frac{n_1(n_2+m_2)}{n_2(n_1+m_1)+n_1(n_2+m_2)}$
$C{R}_m=\frac{{\displaystyle \sum _{k=1}^{\left|C{R}_{rec}\right|}C{R}_{rec}(k)}}{\left|C{R}_{rec}\right|}$
End If
End For

. In SaNSDE, there are two algorithmic parameters, $f_p$ and $C{R}_m$. These two parameters will be self-adapted to influence the scale factor and the crossover rate of DE. The scale factor $F_i$ is determined randomly based on the parameter $f_p$. The crossover rate $c{r}_i$ of individual $i$ is generated randomly according to the parameter $C{R}_m$.

The SaNSDE algorithm keeps track of four variables, $n_1$, $n_2$, $m_1$ and $m_2$, to adapt the parameter $f_p$ as follows:

$f_p=\frac{n_1(n_2+m_2)}{n_2(n_1+m_1)+n_1(n_2+m_2)}$, where $n_1$, $n_2$, $m_1$ and $m_2$ are defined as follows:

$n_1$: the number of individuals (offspring) generated by mutation strategy in (9) that successfully replace the original individual and enter the next generation,

$m_1$: the number of individuals (offspring) generated by mutation strategy in (9) that fail to replace the original individual and are discarded,

$n_2$: the number of individuals (offspring) generated by mutation strategy in (13) that successfully replace the original individual and enter the next generation,

$m_2$: the number of individuals (offspring) generated by mutation strategy in (13) that fail to replace the original individual and are discarded.

In the SaNSDE algorithm, it records the crossover rate value $c{r}_i$ associated with individual $i$ that enter the next generation in an array $C{R}_{rec}$ to adapt the parameter $C{R}_m$. Adaptation of the parameter $C{R}_m$ is done by the following formula:

$$C{R}_m=\frac{{\displaystyle \sum _{k=1}^{\left|C{R}_{rec}\right|}C{R}_{rec}(k)}}{\left|C{R}_{rec}\right|}.$$

As the solution space of the decision problem is discrete, a procedure, $BinaryTrasform$, is used to transform the continuous decision variables to zero or one. The fitness function is computed based on the transformed binary values of decision variables.

Procedure $BinaryTrasform$

Input: $a$

Output: $c$

Begin

$b=\left\{\begin{array}{ll}{V}_{\max }& if a>V_{\max }\\ a& if -V_{\max }\le a\le V_{\max }\\ -V_{\max }& if a<-V_{\max }\end{array}\right.$

$s(b)=\frac{1}{1+{\exp }^{-b}}$

Generate a random variable $rsid$ with uniform distribution $U(0,1)$

$c=\left\{\begin{array}{l}1 rsid<s(b)\\ 0 otherwise\end{array}\right.$

Return $c$

Based on the notations defined above, the proposed algorithm is shown in Table 3.

The underlying principle of the SaNSDE algorithm is very simple and intuitive. The learning period (LP) parameter is used to specify the number of generations to learn the effectiveness of different strategies. During the learning period, the SaNSDE algorithm attempts to apply different strategies to solve the problem and collects the data based on the solution found to calculate the probability to select different strategies. If a strategy $s$ applied can lead to improvement in solution quality, the strategy success counter $n_s$ will be increased by one. Otherwise, the failure counter $m_s$ will be increased by one. After the learning period, the success counter $n_s$ and the failure counter $m_s$ will be used to calculate $f_p$, which will influence the probability to select different strategies in Step 1. The strategy with the higher success count will have higher probability to be selected after the learning period.

5. Results

The purpose of this section is twofold: (1) to verify the functionality to meet trust requirements of drivers and passengers, (2) to study the characteristics of the proposed algorithm and (3) to assess the effectiveness of the proposed algorithm. For the first part, we apply the proposed algorithm to an example of the trust-based ridesharing problem to assess its functionality to satisfy the trust requirements of drivers and passengers, based on the results of the algorithm. For the second part, we study the influence of the learning period on the performance and efficiency of the proposed algorithm. For the third part, we study the effectiveness of the proposed algorithm by performing a number of experiments based on several test cases and analyze the numerical results of the experiments.

5.1. Two Scenarios

We consider two scenarios with different trust requirements to illustrate the influence of trust requirements on ridesharing. In Scenario 1 and Scenario 2, below, we consider the same set of three drivers and ten passengers in a trust-based ridesharing system. However, some of the trust requirements are not the same.

The data for these two scenarios can be downloaded from the following link: https://drive.google.com/drive/folders/1W4OdMQ6z8O0fX38TpSVFcVbsbzJkjHy3?usp=sharing (accessed on 20 January 2022).

5.1.1. Scenario 1

The origins and destinations of the drivers and passengers are listed in

Table 4. Origins and Destinations of Participants.

Participant	Origin	Destination
Driver 1	24.23785, 120.66993	24.11308, 120.65914
Driver 2	24.1692536, 120.6848233	24.20195, 120.56815
Driver 3	24.13425, 120.5539	24.14289, 120.70549
Passenger1	24.21872, 120.6469	24.12877, 120.66223
Passenger2	24.1790507, 120.6657476	24.17369, 120.61354
Passenger3	24.0611, 120.64342	24.1465287, 120.6532456
Passenger4	24.07962, 120.69454	24.12438, 120.66244
Passenger5	24.19422, 120.69538	24.15288, 120.69704
Passenger6	24.16048, 120.69173	24.16359, 120.65138
Passenger7	24.0611, 120.64342	24.11009, 120.64146
Passenger8	24.19422, 120.69538	24.13046, 120.7047
Passenger9	24.13623, 120.60693	24.13527, 120.6571
Passenger10	24.16429, 120.68522	24.15345, 120.65495

.

The minimal trust level ${\mathsf{\Gamma }}_d$ requested by each driver $d$ is listed in

Table 5. ${\mathsf{\Gamma }}_d$ for Drivers.

$\mathbf{Driver} \mathbf{ID} \left(\mathit{d}\right)$	1	2	3
${\mathsf{\Gamma }}_d$	1	1	3

. The minimal trust level ${\mathsf{\Lambda }}_p$ requested by each passenger $p$ is listed in

Table 6. ${\mathsf{\Lambda }}_p$ for Passengers.

$\mathbf{Passenger} \mathbf{ID} \left(\mathit{d}\right)$	1	2	3	4	5	6	7	8	9	10
${\mathsf{\Lambda }}_p$	1	1	1	1	1	1	1	1	1	1

. The trust level between driver and passenger is represented by the matrix $\mathsf{\Theta }$, shown in

Table 7. Matrix $\mathsf{\Theta }$.

	1	2	3	4	5	6	7	8	9	10
1	1	2	1	3	2	3	1	2	3	2
2	2	1	1	1	2	2	3	3	1	2
3	1	2	3	2	2	3	3	1	1	2

.

Table 8. Bid submitted by Driver 1.

$\mathbf{Driver} \mathbf{ID} \left(\mathit{d}\right)$	${\mathit{q}}_{\mathit{d}11}$	${\mathit{q}}_{\mathit{d}12}$	${\mathit{q}}_{\mathit{d}13}$	${\mathit{q}}_{\mathit{d}14}$	${\mathit{q}}_{\mathit{d}15}$	${\mathit{q}}_{\mathit{d}16}$	${\mathit{q}}_{\mathit{d}17}$	${\mathit{q}}_{\mathit{d}18}$	${\mathit{q}}_{\mathit{d}19}$	${\mathit{q}}_{\mathit{d}110}$	${\mathit{o}}_{\mathit{d}1}$	${\mathit{c}}_{\mathit{d}1}$
1	0	0	0	0	1	0	0	0	0	0	50.4025	51.4975
2	0	0	0	0	0	0	0	0	0	1	36.745	41.1575
3	0	0	0	0	0	0	0	0	1	0	57.485	57.485

and

Table 9. Bids submitted by Passengers.

$\mathbf{Passenger} \mathbf{ID} \left(\mathit{p}\right)$	${\mathit{s}}_{\mathit{p}1}$	${\mathit{s}}_{\mathit{p}2}$	${\mathit{s}}_{\mathit{p}3}$	${\mathit{s}}_{\mathit{p}4}$	${\mathit{s}}_{\mathit{p}4}$	${\mathit{s}}_{\mathit{p}4}$	${\mathit{s}}_{\mathit{p}4}$	${\mathit{s}}_{\mathit{p}4}$	${\mathit{s}}_{\mathit{p}4}$	${\mathit{s}}_{\mathit{p}4}$	${\mathit{f}}_{\mathit{p}}$
1	1	0	0	0	0	0	0	0	0	0	37.0475
2	0	1	0	0	0	0	0	0	0	0	18.3475
3	0	0	1	0	0	0	0	0	0	0	28.12
4	0	0	0	1	0	0	0	0	0	0	19.07
5	0	0	0	0	1	0	0	0	0	0	14.1675
6	0	0	0	0	0	1	0	0	0	0	12.25
7	0	0	0	0	0	0	1	0	0	0	17.1175
8	0	0	0	0	0	0	0	1	0	0	33.11
9	0	0	0	0	0	0	0	0	1	0	14.6925
10	0	0	0	0	0	0	0	0	0	1	9.645

show the bids of all drivers and passengers, respectively, generated by the bid generation procedure in Appendix II [31].

We apply the proposed SaNSDE algorithm to solve the decision problem using the following parameters:

• $MAX\_GEN$ = 10,000.
• Population size $NP$ = 30.
• $CR$ = 0.5.
• $F_i$ = $0.3r_1+0.5$, where $r_1$ is a Gaussian distribution $N(0,1)$.
• $LP$ = 10, 50, 100, 200, 1000.
• $V_{\max }$ = 4.

Based on the above input data, the solution found by applying the SaNSDE algorithm is shown in

Table 10. Solution $x$ for Drivers.

$\mathbf{Driver} \mathbf{ID} \left(\mathit{d}\right)$	${\mathit{x}}_{11}$	${\mathit{x}}_{21}$	${\mathit{x}}_{31}$
1	1	1	0

and

Table 11. Solution $y$ for Passengers.

$\mathbf{Passenger} \mathbf{ID} \left(\mathit{d}\right)$	${\mathit{y}}_1$	${\mathit{y}}_2$	${\mathit{y}}_3$	${\mathit{y}}_4$	${\mathit{y}}_5$	${\mathit{y}}_6$	${\mathit{y}}_7$	${\mathit{y}}_8$	${\mathit{y}}_9$	${\mathit{y}}_{10}$
1	0	0	0	0	1	0	0	0	0	1

.

The cost savings for this solution are 18.305.

The two shared routes generated by the solution found by applying the SaNSDE algorithm for Example 1 are shown in Figure 1. Please visit the following link to display the routes of Driver 1 and Driver 2 and the associated ridesharing passengers. https://www.google.com/maps/d/edit?mid=1_i--xWSlx6_a-ISgTLMzKP8_PPzjYACH&usp=sharing (accessed on 20 January 2022).

5.1.2. Scenario 2

In Scenario 2, the itineraries of drivers and passengers are the same as those of Scenario 1. However, the trust requirements between drivers and passengers in Scenario 2 are different from those of Scenario 1. We will study the influence of trust requirements between drivers and passengers on the number of matched shared rides.

As the itineraries of drivers and passengers in Scenario 2 are the same as those of Scenario 1, the origins and destinations of the drivers and passengers in Scenario 2 are the same as the information listed in Table 4.

The minimal trust level ${\mathsf{\Gamma }}_d$ requested by each driver $d$ is listed in

Table 12. ${\mathsf{\Gamma }}_d$ for Drivers.

$\mathbf{Driver} \mathbf{ID} \left(\mathit{d}\right)$	1	2	3
1	1	3	3

. The minimal trust level ${\mathsf{\Lambda }}_p$ requested by each passenger $p$ is listed in

Table 13. ${\mathsf{\Lambda }}_p$ for Passengers.

$\mathbf{Passenger} \mathbf{ID} \left(\mathit{d}\right)$	1	2	3	4	5	6	7	8	9	10
${\mathsf{\Lambda }}_p$	1	1	1	1	1	1	1	1	1	1

. The trust level between driver and passenger is represented by the matrix $\mathsf{\Theta }$, shown in

Table 14. Matrix $\mathsf{\Theta }$.

	1	2	3	4	5	6	7	8	9	10
1	1	2	1	3	2	3	1	2	3	2
2	2	1	1	1	2	2	3	3	1	2
3	1	2	3	2	2	3	3	1	1	2

.

We apply the proposed SaNSDE algorithm to solve the decision problem using the same parameters used in Scenario 1.

Based on the above input data, the solution found by applying the SaNSDE algorithm is shown in

Table 15. Solution $x$ for Drivers.

$\mathbf{Driver} \mathbf{ID} \left(\mathit{d}\right)$	${\mathit{x}}_{11}$	${\mathit{x}}_{21}$	${\mathit{x}}_{31}$
1	1	0	0

and

Table 16. Solution $y$ for Passengers.

$\mathbf{Passenger} \mathbf{ID} \left(\mathit{d}\right)$	${\mathit{y}}_1$	${\mathit{y}}_2$	${\mathit{y}}_3$	${\mathit{y}}_4$	${\mathit{y}}_5$	${\mathit{y}}_6$	${\mathit{y}}_7$	${\mathit{y}}_8$	${\mathit{y}}_9$	${\mathit{y}}_{10}$
1	0	0	0	0	1	0	0	0	0	0

. The results of Scenario 2 indicate that ${\mathsf{\Gamma }}_d$ has influence on the number of matched shared rides. The results of Scenario 2 show that the number of ridesharing passengers has been reduced to one. This is due to the constraints of the trust requirement set by driver two.

The cost savings for this solution are 13.07.

Two shared routes for Case 2 of Example 1 are shown in Figure 2.

Please visit the following link to display the routes of Driver 1 and Driver 2 and the associated ridesharing passengers. https://www.google.com/maps/d/edit?mid=1l_XW_SzWAu3hkvkS5pLrJF3XPqrm6xNh&usp=sharing (accessed on 20 January 2022).

5.2. Influence of Learning Period on Performance and Efficiency

There is an algorithmic parameter, learning period ($LP$), in the proposed SaNSDE algorithm. To apply the proposed method to solve problems, we first study the influence of the algorithmic parameter $LP$ on convergence speed.

The parameters used in the Self-adaptive Neighborhood Search Differential Evolution (SaNSDE) algorithm are listed as follows:

• $MAX\_GEN$ = 10,000.
• Population size $NP$ = 30.
• $CR$ = 0.5.
• $F_i$ = $0.3r_1+0.5$, where $r_1$ is a Gaussian distribution $N(0,1)$.
• $LP$ = 10, 50, 100, 200, 1000.
• $V_{\max }$ = 4.

Table 17. Average fitness values and average number of generations for SaNSDE with algorithmic parameter $LP$ to 10, 50, 100, 200 and 1000.

Test Case	Participant (D/P)	SaNSDE $(\mathit{L}\mathit{P}=10)$	SaNSDE $(\mathit{L}\mathit{P}=50)$	SaNSDE $(\mathit{L}\mathit{P}=100)$	SaNSDE $(\mathit{L}\mathit{P}=200)$	SaNSDE $(\mathit{L}\mathit{P}=1000)$
1	3/10	18.305/100.3	18.305/32.9	18.305/9.9	18.305/6.4	18.305/2.8
2	5/11	23.518/236.9	23.518/39.3	23.518/21.8	23.518/14.9	23.518/7.6
3	5/12	24.79/288.7	24.79/39.5	24.79/17.6	24.79/15.3	24.79/7.1
4	6/12	36.58/752.8	36.58/127	36.58/53.7	36.58/27.1	36.58/12.9
5	7/13	29.2442/1426.1	30.063/50.9	30.063/92.3	30.063/31.6	30.063/14.7
6	8/14	62.18/116	62.18/38	62.18/22.9	62.18/18.1	62.18/7
7	9/15	74.0355/1746.9	79.64/2055.2	79.64/609.1	79.64/200.4	79.64/45.4
8	20/20	23.644/2582.2	23.644/656.7	23.644/4186.7	23.5513/1005.7	23.644/601.2
9	30/30	135.0137/17,414.6	138.3127/11,675.2	138.3988/16,887	138.0833/23,072.8	139.7357/25,470.7
10	40/40	144.0469/20,968.4	145.3967/21,086	146.4824/16,469.5	144.7231/25,026.3	144.6829/15,030.9

shows the results obtained by setting the algorithmic parameter $LP$ to 10, 50, 100, 200 and 1000, respectively. For each test case, the average fitness values obtained by setting $LP$ to 100, 200 and 1000 are very close. However, the average number of generations required to find the best solutions are different for different algorithmic parameters $LP$. The average number of generations for Case 1, Case 2, Case 3, Case 4 and Case 5 are shown in the bar chart of Figure 3. The average number of generations for Case 6, Case 7, Case 8, Case 9 and Case 10 are shown in the bar chart of Figure 4. The results indicate that the average number of generations required to find the best solutions tend to decrease by increasing $LP$ for most test cases. This is due to the quality of the best strategy being improved with the growth of the algorithmic parameter $LP$. If the algorithmic parameter $LP$ is too small, the best strategy cannot be learned within the learning period. In this case, the probability to select the best strategy to create a mutant vector will be lower than expected. Therefore, the number of generations required to find the best solutions will be greater. If the algorithmic parameter $LP$ is big enough, the best strategy can be learned within the learning period. In this case, the probability to select the best strategy to create a mutant vector will be higher. Therefore, the number of generations required to find the best solutions will be smaller. Based on the above reasoning, the results in Figure 3 and Figure 4 are consistent with our expected results for almost all test cases, with the exception of Case 9. This is due to the fact that the SaNSDE algorithm is a stochastic optimization method.

The effectiveness of an evolutionary algorithm is assessed based on two indices: the average fitness value and the average number of generations needed to find the solutions. The average fitness value is the primary index to evaluate performance, whereas the average number of generations is the secondary index to evaluate computational efficiency. Although the average number of generations for Case 9 with $LP$ = 1000 is the worst, the average fitness value for Case 9 with $LP$ = 1000 is 139.7357, which is the best of all, according to Table 17. Therefore, for Case 9, the SaNSDE algorithm with $LP$ = 1000 still outperforms other $LP$ parameters, in the average fitness value Table 17. The average number of generations for Case 9 with $LP$ = 1000 is the worst. This is due to the fact that the SaNSDE algorithm is a stochastic optimization method. The number of generations to find the best solutions may not always be the smallest, even if it has learned the best strategy during the learning period. Despite the results of Case 9, the SaNSDE algorithm with $LP$ = 1000 outperforms other $LP$ parameters in all the other Cases, in terms of the average fitness value and the average number of generations. This means that the SaNSDE algorithm, with a sufficient large learning period, has a higher probability to achieve better performance and efficiency.

5.3. Effectiveness of the Proposed Algorithm

In this subsection, we will compare the proposed algorithm with several evolutionary algorithms through the results of the experiments. These evolutionary algorithms include standard DE [14], NSDE [15], PSO [13], Firefly [26] and ALPSO [33] algorithms. Comparison with the standard DE algorithm will be presented first, followed by comparisons with NSDE, PSO, Firefly and ALPSO algorithms.

5.3.1. Comparison with DE

In this subsection, we compare the proposed algorithm with the standard DE algorithm [14]. As there are six mutation strategies in the standard DE approach, we use DE1, DE2, DE3, DE4, DE5 and DE6 to represent the six standard DE algorithms with the six mutation strategies.

The parameters used in the DE1, DE2, DE3, DE4, DE5 and DE6 are listed as follows:

• $MAX\_GEN$ = 10,000.
• Population size $NP$ = 30.
• $CR$ = 0.5.
• $F$: a value arbitrarily selected from uniform (0, 2).
• $V_{\max }$ = 4.

The parameters used in the Self-adaptive Neighborhood Search Differential Evolution (SaNSDE) algorithm are listed as follows:

• $MAX\_GEN$ = 10,000.
• Population size $NP$ = 30.
• $CR$ = 0.5.
• $F_i$ = $0.3r_1+0.5$, where $r_1$ is a Gaussian distribution $N(0,1)$.
• $LP$ = 1000.
• $V_{\max }$ = 4.

Table 18. Average fitness values and average number of generations for DE with six strategies and SaNSDE with algorithmic parameter $LP$ = 1000.

Test Case	Participant (D/P)	DE1	DE2	DE3	DE4	DE5	DE6	SaNSDE $(\mathit{L}\mathit{P}=1000)$
1	4/10	18.305/14.3	18.305/20.9	18.305/19.2	18.305/35.9	18.305/15.7	18.305/16	18.305/2.8
2	5/11	23.518/54.6	21.1662/129.1	22.7885/514.3	23.518/577.1	23.518/25.9	23.518/63.5	23.518/7.6
3	5/12	24.79/63.3	24.79/334.9	24.3962/69.6	24.3962/171.8	24.0024/413.2	24.3962/77.9	24.79/7.1
4	6/12	36.58/167.6	35.4095/419.5	36.58/214.2	35.9755/212.9	34.1465/202	36.58/135.1	36.58/12.9
5	7/13	29.2442/968.5	25.482/73.4	29.0007/181	26.2379/139.1	26.8132/478.5	29.2442/203.7	30.063/14.7
6	8/14	62.18/48.7	62.18/42.5	62.18/51.8	60.7055/1056.4	62.18/341.2	62.18/41.7	62.18/7
7	9/15	75.1808/860	70.481/165.5	78.1356/932.7	76.2821/1139.3	59.7039/1054.7	74.4286/1004	79.64/45.4
8	20/20	23.644/475	15.4555/9261.1	23.644/1098.6	16.1718/5027	16.0075/14,904.6	19.3717/6478.8	23.644/601.2
9	30/30	126.2855/26,507.9	81.1175/211.6	133.3518/20,689.3	108.7805/19,178	107.5981/15,306.9	114.6592/15,030	139.7357/25,470.7
10	40/40	120.0865/7556.1	79.7772/21,756.2	122.8838/22,660.2	84.8821/18,684.8	53.8039/18,172.4	55.685/12,640.3	144.6829/15,030.9

shows the results obtained by applying the DE algorithm with six strategies and the SaNSDE algorithm with algorithmic parameter $LP$ set to 1000. The results indicate that the average fitness function values achieved by applying the DE algorithms are worse than those of the SaNSDE algorithm for some cases. In addition, the average fitness function values achieved by the SaNSDE algorithm are either as good as or better than DE. This indicates that the SaNSDE algorithm can stably find better solutions. In terms of convergence speed, the average number of generations required for the SaNSDE algorithm to find the best solutions is significantly smaller than those of the DE algorithm with six strategies, for most test cases, according to Table 18, Figure 5 and Figure 6.

5.3.2. Comparison with NSDE

In this subsection, we compare the proposed algorithm with the NSDE algorithm [15].

The parameters used in the Neighborhood Search Differential Evolution algorithm are listed as follows:

• $MAX\_GEN$ = 10,000.
• Population size $NP$ = 30.
• $CR$ = 0.5.
• $F_i$ = $0.5r_1+0.5$, where $r_1$ is a Gaussian distribution $N(0,1)$.
• $V_{\max }$ = 4.

The parameters used in the Self-adaptive Neighborhood Search Differential Evolution (SaNSDE) algorithm are listed as follows:

• $MAX\_GEN$ = 10,000.
• Population size $NP$ = 30.
• $CR$ = 0.5.
• $F_i$ = $0.3r_1+0.5$, where $r_1$ is a Gaussian distribution $N(0,1)$.
• $LP$ = 1000.
• $V_{\max }$ = 4.

Table 19. Average fitness values and average number of generations for NSDE and SaNSDE with algorithmic parameter $LP$ = 1000.

Test Case	Participant (D/P)	NSDE	$\mathbf{SaNSDE} (\mathit{L}\mathit{P}=1000)$
1	3/10	18.305/106.9	18.305/2.8
2	5/11	23.518/51.2	23.518/7.6
3	5/12	24.79/49.8	24.79/7.1
4	6/12	36.58/154.54	36.58/12.9
5	7/13	30.063/118	30.063/14.7
6	8/14	62.18/36.9	62.18/7
7	9/15	79.64/2173.4	79.64/45.4
8	20/20	23.5513/911.6	23.644/601.2
9	30/30	137.655/33,899.3	139.7357/25,470.7
10	40/40	137.2235/29,677.1	144.6829/15,030.9

shows the results obtained by applying the NSDE algorithm and the SaNSDE algorithm, with algorithmic parameter $LP$ set to 1000. The results indicate that the average fitness function values achieved by the SaNSDE algorithm are either as good as or better than the NSDE algorithm for all test cases. In addition, the average number of generations required for the SaNSDE algorithm to find the best solutions is significantly smaller than those of the NSDE algorithm, for all test cases, according to Table 19, Figure 7 and Figure 8. In short, the SaNSDE algorithm is more efficient than the NSDE algorithm.

5.3.3. Comparison with PSO, FA and ALPSO

In this subsection, we compare the proposed algorithm with the PSO algorithm [13], Firefly algorithm [26] and ALPSO algorithm [33].

The parameters used in the PSO algorithm are listed as follows:

• $MAX\_GEN$ = 10,000.
• Population size $NP$ = 30.
• $c_1$ = 0.4.
• $c_2$ = 0.6.
• $\omega$ = 0.4.
• $V_{\max }$ = 4.

The parameters used in the Firefly algorithm are listed as follows:

• $MAX\_GEN$ = 10,000.
• Population size $NP$ = 30.
• ${\beta }_0$ = 1.0.
• $\gamma$ = 0.2.
• $\alpha$ = 0.2.
• $V_{\max }$ = 4.

The parameters used in the ALPSO algorithm are listed as follows:

• $MAX\_GEN$ = 10,000.
• Population size $NP$ = 30.
• $c_1$ = 0.4.
• $c_2$ = 0.6.
• $\omega$ = 0.4.
• $V_{\max }$ = 4.

The parameters used in the Self-adaptive Neighborhood Search Differential Evolution (SaNSDE) algorithm are listed as follows:

• $MAX\_GEN$ = 10,000.
• Population size $NP$ = 30.
• $CR$ = 0.5.
• $F_i$ = $0.3r_1+0.5$, where $r_1$ is a Gaussian distribution $N(0,1)$.
• $LP$ = 1000.
• $V_{\max }$ = 4.

Table 20. Average fitness values and average number of generations for PSO, FA and SaNSDE with algorithmic parameter $LP$ = 1000.

Test Case	Participant (D/P)	PSO	FA	ALPSO	$\mathbf{SaNSDE} (\mathit{L}\mathit{P}=1000)$
1	3/10	18.305/43.6	18.305/52.7	18.305/82.5	18.305/2.8
2	5/11	23.518/233.1	20.9662/134.9	23.518/266.6	23.518/7.6
3	5/12	24.79/691.8	24.3962/328.3	24.79/406.9	24.79/7.1
4	6/12	36.58/929.1	36.58/573.1	36.58/548.6	36.58/12.9
5	7/13	30.063/969.5	30.063/1618.6	30.063/1196.6	30.063/14.7
6	8/14	62.18/638.3	62.18/546.5	62.18/483.4	62.18/7
7	9/15	79.64/2643.4	77.3834/3206	79.64/1245.1	79.64/45.4
8	20/20	15.6939/27,714.3	10.8847/19,374.3	15.7567/30,399.2	23.644/601.2
9	30/30	27.9224/28,346.9	−2.3761/23,731.4	28.9539/32,209	139.7357/25,470.7
10	40/40	−2.5351/29,242.7	−4.0021/21,267.9	−0.5502/29,617.2	144.6829/15,030.9

shows the results obtained by applying the PSO algorithm, Firefly algorithm (FA), ALPSO algorithm and the SaNSDE algorithm, with algorithmic parameter $LP$ set to 1000. The results indicate that the average fitness function values achieved by applying the PSO algorithm, Firefly algorithm (FA) and ALPSO algorithm are worse than those of the SaNSDE algorithm, for Test Case 8 through Test Case 10. This indicates that the SaNSDE algorithm can stably find better solutions. In terms of convergence speed, the average number of generations required for the SaNSDE algorithm to find the best solutions is significantly smaller than those of the PSO algorithm, Firefly algorithm (FA) and ALPSO algorithm, for most test cases, according to Table 20, Figure 9 and Figure 10. Therefore, the SaNSDE algorithm also enjoys faster convergence speed.

The experiments are conducted on a laptop with Intel^(R) Core^(TM) i7 CPU, 16 GB of memory on board and a base clock speed of 2.6 GHz. The average CPU time for SaNSDE with $LP$ = 1000 is shown in Figure 11. Case 9 takes about (over) 3 min. Case 10 takes about (over) 5 min. The CPU time can be cut down if a newer laptop with Intel^(R) Core^(TM) i9 CPU with a base clock speed of 3.5 GHz and a turbo clock speed of 4.8 GHz is used.

6. Discussion

Ridesharing has long been recognized as one potential way to improve sustainability in cities, by reducing energy consumption and greenhouse gas emissions. Besides the factors of cost and time, due to the relatively high rideshare crime rate, safety and trust become major determinants for the adoption of ridesharing. This paper aims to propose a social network assisted decision-making formulation for trust-based ridesharing and a more effective self-adaptive neighborhood search algorithm for solving the trust-based ridesharing problem. The proposed SaNSDE algorithm searches solutions by jointly taking into account scale factor, neighborhood search concept and self-adaptation of mutation strategies in the stochastic optimization process.

The lack of considering the trust factor is one of the main obstacles for people to adopt the ridesharing mode of transport in daily life. In this study, we propose a decision model to take the trust requirements of drivers and riders into account in the ridesharing problem. In this paper, a shared mobility system that considers the trust requirements of passengers and drivers is called a trust-based shared mobility system. To consider the trust factor in the ridesharing problem, it is assumed that a driver and a passenger can share a ride only if their trust requirements can be satisfied. A directed graph-based social network model is adopted in this study. Trust between drivers and passengers is described based on their social network. The trust level between nodes is represented by weight, associated with the set of edges in the social network model. The trust requirements are related to the trust level between drivers and passengers in the social network. In a trust-based shared mobility systems, a driver may request his/her minimal trust level requirements to share a ride with a passenger. If minimal trust level requirements requested by the driver cannot be satisfied, the driver will not share a ride with the passenger. Similarly, a passenger may request his/her minimal trust level requirements to share a ride with a driver. If minimal trust level requirements requested by the passenger cannot be satisfied, the passenger will not share a ride with the driver. Based on the trust level specified in the social network model, and minimal trust level requirements requested by the drivers/passengers, an optimization decision problem is formulated to find the solution for ridesharing recommendations. Due to computational complexity, a metaheuristic algorithm based on the Differential Evolution approach has been developed to solve the trust-based ridesharing decision problem and assess its effectiveness.

We verified the functionality to meet the trust requirements of drivers and passengers and studied the characteristics and effectiveness of the proposed algorithm. To verify the functionality to satisfy the trust requirements of drivers and passengers, we applied the proposed algorithm to two examples of the trust-based ridesharing problem and analyzed based on the outputs of the algorithm. The results indicate the proposed algorithm can meet the trust requirements of drivers and passengers.

To study the characteristics of the proposed algorithm, we conducted several experiments by changing the learning period parameter. The results indicate that the average number of generations required to find the best solutions tends to decrease by increasing $LP$ for most test cases. This is due to the fact that the best strategy can be found only if the learning period parameter $LP$ is big enough. If the algorithmic parameter $LP$ is too small, the best strategy cannot be learned within the learning period. In this case, the probability to select the best strategy to create a mutant vector will be lower than expected and, therefore, the number of generations required to find the best solutions will be greater. If the algorithmic parameter $LP$ is big enough, the best strategy can be learned within the learning period. In this case, the probability to select the best strategy to create a mutant vector will be higher and, hence, the number of generations required to find the best solutions will be smaller.

To study the effectiveness of the proposed algorithm, we performed a number of experiments on several test cases by applying the proposed SaNSDE algorithm and other algorithms, including DE, NSDE, PSO, FA and ALPSO algorithms, and analyzed the numerical results of the experiments. The results indicate that the average fitness function values achieved by the SaNSDE algorithm are either as good as or better than DE, NSDE, PSO, FA and ALPSO. In terms of convergence speed, the average number of generations required for the SaNSDE algorithm to find the best solutions is significantly smaller than those of the DE, NSDE, PSO, FA and ALPSO algorithms for most test cases. Therefore, the SaNSDE algorithm enjoys faster convergence speed.

The effectiveness of the SaNSDE algorithm is due to the mechanism to learn better strategies in the optimization. After the learning period, the SaNSDE algorithm will select better strategies in the evolution processes. The number of generations required for many evolutionary algorithms to find the best solutions grows dramatically with the problem scale. Therefore, the number of generations required by the SaNSDE algorithm to find the best solutions will also increases dramatically. The advantage is that the SaNSDE algorithm is able to identity better strategies to find better solutions and jointly switch between strategies. The issue to deal with larger cases is an interesting future research direction.

There are alternatives to deal with passengers and drivers that may enter the ridesharing system sequentially in the real world. Typically, a decision support system for ridesharing makes decisions within a time period. The requests of drivers and passengers arriving before the start of the decision time period will be considered by the ridesharing decision support system. The decision support system will determine the matched drivers and passengers. Unmatched drivers and passengers will be considered in the next time period. The decision model proposed in this paper supports multi-drivers/multi-passengers, multi-drivers/single-passenger and single-driver/multi-passengers. Although the decision model proposed in this paper is based on the multi-driver/multi-passenger scenario, it can be applied to multi-driver/single-passenger and single-driver/multi-passenger scenarios. The proposed decision support system for ridesharing may consider each passenger and the potential drivers as a matching problem and solves the problem one after another. It may also consider each driver and the potential passengers as a matching problem and solves the problem one by one. There is a trade-off between performance and response time of different application scenarios, mentioned above. A ridesharing decision support system based on the multi-driver/multi-passenger scenario may achieve better performance but need more computational time. A ridesharing decision support system based on the multi-driver/multi-passenger scenario may achieve better performance but may not be able to respond to users quickly, as it requires more computational time. A ridesharing decision support system based on the multi-driver/single-passenger or single-driver/multi-passenger scenarios need less computational time and provide quick responses to users, but the performance may be degraded.

7. Conclusions

Due to the relatively high rideshare crime rate, safety and trust become important factors for the adoption of ridesharing, besides the factors of cost and time. One way to ensure safety/trust is to take advantage of the social relationship of ridesharing participants in relevant social networks. Although trust level may be linked to social distance, it is not the same as social distance. A proper model to capture the level that one participant trusts another is to consider both the social distance and other factors not directly relevant to social distance. In this study, we consider a trust model that takes into account social distance as well as non-social distance factors. In this paper, we have taken the first step to develop a well-compatible ridesharing decision-making algorithm, taking into account the trust factor in the poly-variant stochastic optimization process. This study aims to develop a decision model and associated solution methods to ensure the satisfaction of trust requirements of ridesharing participants. In the proposed decision model, the trust level between nodes is represented by weight, associated with the set of edges in the social network model. In a trust-based shared mobility system, a driver may request his/her minimal trust level requirements to share a ride with a passenger. A ride can be shared between a driver and relevant passengers only if the minimal trust level requirements requested by the driver and relevant passengers are satisfied. Based on the trust level specified in the social network model and minimal trust level requirements requested by the drivers/passengers, an optimization problem is formulated to find the solution. Due to computational complexity, a self-adaptive DE with neighborhood search (SaNSDE) algorithm, based on the Differential Evolution approach, has been developed to solve the trust-based ridesharing decision problem and assess its effectiveness.

To study the effectiveness of the proposed algorithm, we performed a number of experiments by applying the proposed SaNSDE, DE, NSDE, PSO, FA and ALPSO algorithms to find solutions for several test cases. The results indicate that the solutions found by the SaNSDE algorithm are either as good as or better than DE, NSDE, PSO, FA and ALPSO algorithms. In addition, the SaNSDE algorithm outperforms DE, NSDE, PSO, FA and ALPSO algorithms in terms of convergence speed for most test cases. This study shows that the SaNSDE algorithm can be applied to generate ridesharing recommendations effectively. One future research direction is to apply the SaNSDE algorithm to other types of recommender systems or applications.