# Routing Optimization for Shared Electric Vehicles with Ride-Sharing

Authors: Chuanxiang Ren; Jinbo Wang; Yongquan You; Yu Zhang
Journal: Complexity
 (2020)

---

## Abstract

Shared electric vehicles (SEVs) are becoming a new way for urban residents to travel because of their environmental protection, energy saving, and sustainable development. However, at present, the operation mode of shared electric vehicles has the problem that the vehicle cannot be utilized efficiently. For this reason, this paper studied the mode of SEVs with ride-sharing (MSEVRS) and SEVs routing optimization under this mode. Firstly, the operation principle of MSEVRS is presented, which includes the collection of user demand information and SEVs information and the routing optimization of SEVs, both of which are completed by the user and SEVs management center. Secondly, the routing optimization model of SEVs with ride-sharing is proposed, in which the SEVs operation cost, user time cost, user rental cost, and user ride-sharing bonus are taken into account. And the genetic algorithm is designed to solve the model. Finally, a case study is carried out to illustrate the effectiveness of the proposed model. The results show that the proposed routing optimization model achieves the optimal SEVs route, realizes the MSEVRS, and improves the utilization rate of SEVs. Compared with the current SEVs mode (CSEVM), the MSEVRS reduces the number of vehicles, user rental cost, the total cost of users, and the total cost of user and company of SEVs. And the total distance is reduced, which means saving energy. Moreover, it shows that MSEVRS obtains a better cost performance and service for users and has a better application prospect.


---

## Body

## 1. Introduction

The increase in car ownership has facilitated people’s travel and promoted economic development; but it has also caused problems such as traffic jams, traffic accidents, energy crises, and environmental pollution. Meanwhile, the rapid development and application of technologies, including mobile Internet, smartphone, and global positioning system, provide support for real-time management and effective utilization of vehicle fleet. In this context, because of the advantages of reducing the number of private cars, saving energy, and reducing pollution and emissions [1–5], shared vehicle (or carsharing) has gained global attention and rapid application.Besides, with the lack of energy and city air pollution intensified from internal combustion engine-powered vehicles, developing electric vehicles (EVs) has attracted governments and automobile enterprises. For example, in China, the government has made plan that, by 2020, the cumulative sales volume of EVs will reach 5 million [6]. Also, policy measures to stimulate EVs consumption have been formulated and positively responded by consumers [7–9]. Electric vehicles are recognized as an important measure to alleviate the discrepancy between fuel supply and demand, reduce pollution, and improve the atmospheric environment [10–12]. EVs are considered as a natural match for carsharing as members tend to drive smaller and more fuel-efficient vehicles [13]. Shared EVs have become a developing trend of carsharing, and there are many carsharing operators around the world, which have deployed EVs, such as Autolib in France, Car2go in Germany, Zipcar in the USA, and EVCARD in China [14–17].Under the current operation mode, the process of using SEVs includes registration, reservation, use, return, and payment. For SEVs managers, their works mainly include reviewing user registration information, monitoring the real-time location of SEVs, and charging users for vehicle use. In the entire operation process of the SEVs, users only pay attention to the use process of their rented SEVs, while the managers only complete the monitoring of the SEV use process and user rental fee management.It is obvious that, in the current operation mode of the SEVs, there are problems that the resources are not fully utilized. For example, there is the case that two different users with the same origin and destination have demand of the SEV at the same time or similar time, and then two vehicles will be required for their demands under the current SEVs mode. However, one SEV can meet the demands. In this case, if SEVs have ride-sharing function, the waste can be avoided. After the SEVs company obtains demands of the two users, it can be found through the analysis that their demands could be realized through the ride-sharing function. Then, through information interaction with the two users, they are guided to ride one SEV to meet their demands. During the process, the ride-sharing bonus is proposed to encourage users to accept ride-sharing in this paper.This paper mainly discusses the mode of SEV with ride-sharing function, which is called MSEVRS, and how to use the user’s demand information and SEV information to realize the ride-sharing function of SEV and improve the utilization efficiency of vehicles. The contributions of this study mainly involve the following three aspects:(1)
The mode of SEVs with ride-sharing is proposed, in which users can complete their demands through the ride-sharing function of SEVs.(2)
A routing optimization model is proposed for MSEVRS with the objective of minimizing the total cost for SEVs company and users, in which SEVs operation cost, user time cost, user rental cost, and user ride-sharing bonus are taken into account.(3)
Case analyses indicate that MSEVRS reduces user total cost and the SEV operation cost, obtains a better cost performance and service for users, and has a better application prospect.The rest of this paper is presented as follows. In Section2, the research status related to the mode of SEVs and ride-sharing is introduced. In Section 3, a routing optimization model for SEVs with ride-sharing is established. In Section 4, the genetic algorithm for the proposed model is designed. In Section 5, a case for demonstration of the proposed model is presented and discussed. Finally, a brief conclusion and recommendations for future work are presented in Section 6.


## 2. Literature Review

Shared vehicle operation mode affects the number of users, layout of parking facilities, and the management and deployment of vehicles. Many researchers have studied the shared vehicle operation mode and achieved a series of results. Shaheen and Cohen [18] analyzed the factors affecting the operation of carsharing and made a comparative analysis of global carsharing from the aspects of the proportion of people and vehicles, target market, parking strategy, model, cost, and technology. In [19], Le. Vine et al. established the models for choices of subscribing to and using carsharing service by the perceived activity set concept and discussed the market and impacts of round-trip and point-to-point carsharing systems. Shaheen et al. [20] focused on the one-way carsharing, compared the operation modes of one-way carsharing to round-trip carsharing, and discussed the evolution of the one-way carsharing system in Americas. Balac et al. investigated the effects of supply on the demand of the round-trip and one-way carsharing services using the multiagent simulation tool in [21], and the results show that there is still untapped potential of round-trip carsharing and one-way carsharing. It is expected to increase the number of user trips by three times. A mixed-integer nonlinear programming model is proposed in [22] to solve one-way carsharing station location and capacity problem, which considered imbalance between trip requests and vehicle availability, flexible travel demand and nonlinear demand. And a custom gradient algorithm is designed to solve the model. Becker et al. [23] analyzed original transaction data from a free-floating carsharing operator and developed a mode choice model for free-floating carsharing. It was found that free-floating carsharing is mainly used for discretionary trips. In [2], Firnkorn and Müller surveyed Car2go users and indicated that free-floating electric carsharing fleets could be an integral part of future smart cities. Based on multisource data, Wang et al. [24] studied the prediction for the dynamic pickup demand of one-way carsharing system. A demand prediction model and a demand time prediction model are formulated and tested. A set partitioning model was proposed by Xu and Meng in [25] to determine the EVs fleet size for one-way carsharing service, in which the vehicle relocation operation and nonlinear electric vehicle charging profile are considered. A tailored branch-and-price approach is proposed to find the optimal solution of the model. Xu et al. [26] studied the EV fleet size and trip pricing problem for one-way carsharing service. A mixed-integer nonlinear and nonconvex programming model is built considering the necessary practical requirements of vehicle relocation and personnel assignment. An effective global optimization method with several outer-approximation schemes is put up to solve the model. Li et al. propose a continuum approximation model to determine the sharing station locations and the EV fleet sizes for a one-way EV sharing system in [27]. Numerical experiments show that the continuum approximation approach is capable of providing a near-optimum solution. Based on the survey from users of Modo and Car2go, Namazu and Dowlatabadi compare the impact of two-way and free-floating carsharing service systems on the reduction of vehicle ownership in [28]. It is found that Modo users were close five times more likely to reduce car ownership compared to Car2go users. Hartl et al. discussed the sustainability role of peer-to-peer carsharing service and business-to-consumer service to environmental problems from a consumer perspective in [29]. It is found that environmental concerns play a role when consumers decide to use peer-to-peer service over business-to-consumer services.Besides, as an economic and ecological way to travel, ride-sharing (or carpooling) has been studied by many researchers. Shaheen and Cohen summarized some relevant literatures in [3] and pointed out the positive impact of ride-sharing on society and environment, especially the obvious benefits of reducing the amount of traffic, energy consumption, greenhouse gas emissions, and the number of private cars. A model was proposed by Pimentel in [30] for improving the flexibility of carpooling through the method of operation research, which is optimized by linear programming and tested by surveys conducted. Lin et al. studied the routing optimization of ride-sharing taxi and set up a model with the objective of minimizing operating cost and maximizing the passenger satisfaction, which is verified by a computational experiment in [31]. Catalano et al. calibrated a multinomial logit model to forecast the modal split of the urban transport demand and applied it to the analysis of the potential demand from carsharing and carpooling in Palermo in [32]. Pinson et al. [33] presented a generalized dial ride problem applied to carpool, and a greedy randomized adaptive search algorithm was proposed and tested on small instances and larger instances. In [34], Dakroub et al. discussed the many to many carpooling scenarios and presented a customized genetic algorithm to search for the solution with minimum travel distance, efficient ride-matching, timely arrival, and maximum fairness. A new heuristic simulated annealing genetic algorithm was proposed by Xu et al. in [35] to solve the ride-sharing problem with time guarantee in the road network, and the experiment results demonstrated the advancement of the algorithm. Huang et al. proposed a method to merge public transportation and carpooling networks and then studied multimode route planning considering the fuzziness and flexibility of carpooling in [36]. Meng et al. explored a multiobjective dynamic user matching mechanism in electric vehicles ride-sharing system considering the interests of both users and operators in [37]. Santos and Xavier modeled the situations of both dynamic ride-sharing and taxi-sharing and designed a greedy randomized adaptive search procedure to solve the model in [38]. The experiment results indicated that the passengers paid, on average, 30% less than what they would pay on private rides. Huang et al. [39] studied the problem of carpooling service with a high occupancy rate and established a mathematical model based on the problem. A heuristic multiobjective optimization algorithm is proposed to solve the model and evaluated to generate superior performance in the experiment. Al-Ayyash et al. [40] set up a taxi ride-sharing demand model and found that subsidies are a key factor affecting the number of carpoolers.The above research on shared vehicle (or SEVs) and ride-sharing, respectively, obtain several results. However, both of shared vehicle and ride-sharing are innovative transport systems in terms of accessibility and sustainability. The combination of SEVs and ride-sharing could have greater potential to reduce private vehicle ownership, improve the effective use of vehicles, bring greater energy saving, and mitigate traffic congestion. Some researchers have paid attention to the problem and studied carsharing with ride-sharing. Krueger et al. [41] conducted a stated choice survey, studied the travel behavior impacts of shared autonomous vehicles with and without ride-sharing, and found that shared autonomous vehicles with and without ride-sharing are perceived as two distinct mobility options. An integrated optimization and a stand-along agent-based simulation model was proposed in [42] to evaluate a fleet of shared autonomous EVs with ride-sharing. Results indicated that the service rate and system benefits were improved and the fleet size and the number of charging stations were decreased.Both of these studies are based on automated vehicle technology. Their results have an important role in advancing future research on shared autonomous vehicles. Although the research and application of artificial intelligence and control theory have promoted the rapid development of autonomous vehicles [43–49], there is still a long way to go for the wide application of fully autonomous vehicles in the actual urban road environment [50, 51]. In this paper, the mode of SEVs with ride-sharing, namely, MSEVRS, is studied. The SEVs are manually operated, more humanized, and more practical at present.


## 3. Methodology

### 3.1. Analysis of Problem

The schematic diagram of the operation principle of MSEVRS is shown in Figure1. The user and SEVs management center obtain the user demand information and SEVs information and optimize the SEVs routes through the analysis of the information. User demand information and SEVs information are the basis of SEVs route optimization.Figure 1
The schematic diagram of operation principle of MSEVRS.User demand information includes registration information, travel information (or trip origin-destination information), and real-time interactive information. Registration information includes user’s gender, age, and driving age. Registration is a prerequisite for users to use the SEV. At the same time, the information can be used to identify the driver and manage the user rental fee and user ride-sharing bonus. The user’s trip origin-destination information mainly includes the origin, destination, and time requirements, which are obtained when the user subscribes to the trip application. The real-time interactive information is obtained by the SEVs manager through interacting with users, i.e., whether users are willing to share vehicles with others to receive user ride-sharing bonus. The information can be accessed by SEVs manager via the mobile Internet and smartphone terminals.The information of SEVs mainly includes the real-time location, the battery power, and other pieces of information. SEV location information affects the vehicle route. The battery power of the SEV affects the working mileage and then affects the route of the vehicle. The managers can access the SEVs information in real-time via the mobile Internet and GPS terminals.SEVs routing optimization is the concrete realization of users’ demands. In Figure1, it is shown that there are two groups of user demands and their routes. The users of the first group are U1 and U2, who start from the same origin O1 at the same time and arrive at destinations D1 and D2, respectively. After the user and SEVs management center obtains the demands of U1 and U2, it is found that D1 is in the route to D2, and then one SEV route is given, which starts from O1 to D1, and finally to D2. In the route, from O1 to D1 is the ride-sharing section of U1 and U2. When the SEV arrives at D1, U1 gets off and U2 continues to move forward, and finally SEV arrives at D2 and U2 gets off. During the process U2 drives the SEV and gets ride-sharing bonus.In the same way, for the users ofU3 and U4 in the second group, user U3 starts from origin O2 to destination D3, and U4 starts from origin O3 to destination D3. Through the analysis of the two users’ demands, it is found that O3 is in the route of U3. In this case, users’ demands can be fulfilled by one SEV and the route is given, which starts from O2 to O3, and finally to D3. In the route, from O3 to D3 is the ride-sharing section of U3 and U4. During the process U3 drives the SEV and gets ride-sharing bonus.According to the above analysis, the focus of our study is how to provide the optimal vehicle route to achieve the ride-sharing function of SEVs as much as possible to improve the efficiency of SEV utilization based on the user demand information and SEVs information. The problem can be summarized as routing optimization of SEVs with ride-sharing under the condition of user demands meet. To solve the problem, a mathematical model is established by considering the SEVs operation cost and users’ costs.


### 3.2. Basic Assumption and Notation

Several basic assumptions are as follows:(1)
The mileage of SEVs can meet the users’ demand(2)
It is supposed that the speed of SEVs is constant(3)
There are enough SEVs available for users in their origins(4)
The relevant data has been obtained, including the number of users, users’ origin and destination, and the required time windowPrimary notations used in model establishment of this paper are listed as follows:m: the index of SEV, m = 1, 2, …, M, and M is the total number of SEVi, j: the index of user group, i = 1, 2, …, N, j = 1, 2, …, N, and N is the number of user groups required to be servedk: the index of user, k = 1, 2, …, K, and K is the total number of users required to be served, as each group may be more than one user, so K≠NTim: the time of the SEV m arriving at the location of user group iQim: the load of the SEV m leaving the location of user group iWk: the time of user k waiting for the SEVQ: capacity of SEVsi: the time of users getting on and off SEVs when the vehicle arrives at the location of the user group iqjm: the number of users getting on and off the SEV at the location of the user group j; if the number of users getting on the SEV is more than that of users getting off, its value is plus, or it is minustij: the time taken by SEV from user group i to user group j on the shortest routexijm: decision variable; if the SEV m travels from user group i to user group j, xijm=1; otherwise xijm=0δki: a binary variable; if the user k is the driver of user group i, δki=1; otherwise δki=0ei: the beginning of the required time windowli: the end of the required time windowb1,b2: penalty coefficient


### 3.3. Mathematical Model Formulation

The service system of SEVs includes vehicles, parking ground, charging facilities, SEV operation management, and users. In the operation process of the SEVs, users hope to use the vehicle conveniently and affordably, while the SEVs companies hope to gain as much as possible operation benefits. In MSEVRS, a mathematical model for routing optimization of SEVs is formulated with the objective function of minimizing the total costs of operation of SEVS and users, in which the SEVs operation cost represents the benefit of the SEVs company.


#### 3.3.1. The SEVs Operation Cost

The SEVs operation cost involves many aspects, such as electricity consumption, SEV maintenance, and management personnel costs. These factors are taken into account and their costs are attributed to the SEVs operation cost per minute, and the total of SEVs operation cost, labeled asC1, can be expressed as(1)C1=∑m∈M∑i∈N∑j∈Ntij⋅xijm⋅D1,where D1 is the operation cost of SEVs per minute; its unit is yuan/minute.


#### 3.3.2. User Cost

(1) User Time Cost. The user time includes the waiting time at their origins and the in-vehicle travel time; therefore, the user time cost includes waiting time cost and in-vehicle travel time cost.The user waiting time cost, labeled asC2, is calculated as follows:(2)C2=∑k∈KWk⋅D2,where D2 is the waiting time cost of user per minute; its unit is yuan/minute.The user in-vehicle travel time cost, labeled asC3, can be calculated as follows:(3)C3=∑m∈M∑i∈N∑j∈NQimTjm−Tim⋅D3,where D3 is the in-vehicle travel time cost of per minute; its unit is yuan/minute.(2) User Rental Cost. The user rental cost is the fee paid by the user to the company of SEVs for using the SEVs. Company of SEVs usually charges according to the time in which users use SEVs, and the calculation formula of user rental cost, labeled as C4, can be expressed by(4)C4=∑m∈M∑i∈N∑j∈NQimTjm−Tim⋅D4,where D4 is the rent fee that users need to pay per minute for using the SEV; its unit is yuan/minute.(3) User Ride-Sharing Bonus. The company of SEVs encourages users to use the ride-sharing function of SEVs. In order to achieve this goal, the company takes a part of the user’s rental fee as bonus to the users who provide ride-sharing service as drivers. The bonus calculation formula is as follows:(5)C5=∑k∈K∑i∈Nδki∑m∈M∑i∈N∑j∈NQimTjm−Tim⋅D4⋅D5,where D5 is the proportional coefficient of bonus given to drivers from the users’ rental fee.


#### 3.3.3. Penalty Function

SEVs are required to arrive at the user’s location within a specified period of time that is the time window. The SEV arriving in advance will produce idle time and result in a waste of operation, and if there is late arrival of SEV, it will cause user waiting time and affect user’s satisfaction. In order to make the arrival of the SEV meet the user’s required time window as much as possible and improve the operation efficiency of the SEVs, a penalty function is set, which is as follows:(6)PTim=b1ei−Tim,Tim<ei,0,ei≤Tim≤li,b2Tim−li,li<Tim,where PTim is a penalty function for the SEV m arriving at the location of the user group i.Based on (1)–(6), the routing optimization model of SEVs with ride-sharing is obtained as follows:(7)MinC=C1+C2+C3+C4−C5+∑m∈M∑i∈NPTim,subject to(8)1≤Qim≤Q,∀i∈N,∀m∈M,(9)Tjm≥Tim+tij+sixijm,∀i,j∈N,∀m∈M,(10)Qjm≥Qim+qjmxijm,∀i,j∈N,∀m∈M,(11)max1,qim≤Qim≤minQ,Q+qim,∀i∈N,∀m∈M,(12)xijm∑k∈K∑i∈Nδki≥1.Formula (7) is the objective function of the model, in which the SEVs operation cost and the total user cost are considered. Constraint (8) indicates the load of the SEV; the minimum is 1. Constraint (9) refers to the time for a SEV from user group i to user group j that should not be less than Tjm. Constraint (10) ensures that the load of SEV at location of user group j is equal or more than the sum of the load at location of user group i and the number of users getting on and off SEV at location of user group j. Constraint (11) guarantees that user number in SEV leaving each location does not exceed the capacity of SEV and there is at least one user. Constraint (12) guarantees the presence of at least one driver in SEV.


## 3.1. Analysis of Problem

The schematic diagram of the operation principle of MSEVRS is shown in Figure1. The user and SEVs management center obtain the user demand information and SEVs information and optimize the SEVs routes through the analysis of the information. User demand information and SEVs information are the basis of SEVs route optimization.Figure 1
The schematic diagram of operation principle of MSEVRS.User demand information includes registration information, travel information (or trip origin-destination information), and real-time interactive information. Registration information includes user’s gender, age, and driving age. Registration is a prerequisite for users to use the SEV. At the same time, the information can be used to identify the driver and manage the user rental fee and user ride-sharing bonus. The user’s trip origin-destination information mainly includes the origin, destination, and time requirements, which are obtained when the user subscribes to the trip application. The real-time interactive information is obtained by the SEVs manager through interacting with users, i.e., whether users are willing to share vehicles with others to receive user ride-sharing bonus. The information can be accessed by SEVs manager via the mobile Internet and smartphone terminals.The information of SEVs mainly includes the real-time location, the battery power, and other pieces of information. SEV location information affects the vehicle route. The battery power of the SEV affects the working mileage and then affects the route of the vehicle. The managers can access the SEVs information in real-time via the mobile Internet and GPS terminals.SEVs routing optimization is the concrete realization of users’ demands. In Figure1, it is shown that there are two groups of user demands and their routes. The users of the first group are U1 and U2, who start from the same origin O1 at the same time and arrive at destinations D1 and D2, respectively. After the user and SEVs management center obtains the demands of U1 and U2, it is found that D1 is in the route to D2, and then one SEV route is given, which starts from O1 to D1, and finally to D2. In the route, from O1 to D1 is the ride-sharing section of U1 and U2. When the SEV arrives at D1, U1 gets off and U2 continues to move forward, and finally SEV arrives at D2 and U2 gets off. During the process U2 drives the SEV and gets ride-sharing bonus.In the same way, for the users ofU3 and U4 in the second group, user U3 starts from origin O2 to destination D3, and U4 starts from origin O3 to destination D3. Through the analysis of the two users’ demands, it is found that O3 is in the route of U3. In this case, users’ demands can be fulfilled by one SEV and the route is given, which starts from O2 to O3, and finally to D3. In the route, from O3 to D3 is the ride-sharing section of U3 and U4. During the process U3 drives the SEV and gets ride-sharing bonus.According to the above analysis, the focus of our study is how to provide the optimal vehicle route to achieve the ride-sharing function of SEVs as much as possible to improve the efficiency of SEV utilization based on the user demand information and SEVs information. The problem can be summarized as routing optimization of SEVs with ride-sharing under the condition of user demands meet. To solve the problem, a mathematical model is established by considering the SEVs operation cost and users’ costs.


## 3.2. Basic Assumption and Notation

Several basic assumptions are as follows:(1)
The mileage of SEVs can meet the users’ demand(2)
It is supposed that the speed of SEVs is constant(3)
There are enough SEVs available for users in their origins(4)
The relevant data has been obtained, including the number of users, users’ origin and destination, and the required time windowPrimary notations used in model establishment of this paper are listed as follows:m: the index of SEV, m = 1, 2, …, M, and M is the total number of SEVi, j: the index of user group, i = 1, 2, …, N, j = 1, 2, …, N, and N is the number of user groups required to be servedk: the index of user, k = 1, 2, …, K, and K is the total number of users required to be served, as each group may be more than one user, so K≠NTim: the time of the SEV m arriving at the location of user group iQim: the load of the SEV m leaving the location of user group iWk: the time of user k waiting for the SEVQ: capacity of SEVsi: the time of users getting on and off SEVs when the vehicle arrives at the location of the user group iqjm: the number of users getting on and off the SEV at the location of the user group j; if the number of users getting on the SEV is more than that of users getting off, its value is plus, or it is minustij: the time taken by SEV from user group i to user group j on the shortest routexijm: decision variable; if the SEV m travels from user group i to user group j, xijm=1; otherwise xijm=0δki: a binary variable; if the user k is the driver of user group i, δki=1; otherwise δki=0ei: the beginning of the required time windowli: the end of the required time windowb1,b2: penalty coefficient


## 3.3. Mathematical Model Formulation

The service system of SEVs includes vehicles, parking ground, charging facilities, SEV operation management, and users. In the operation process of the SEVs, users hope to use the vehicle conveniently and affordably, while the SEVs companies hope to gain as much as possible operation benefits. In MSEVRS, a mathematical model for routing optimization of SEVs is formulated with the objective function of minimizing the total costs of operation of SEVS and users, in which the SEVs operation cost represents the benefit of the SEVs company.


### 3.3.1. The SEVs Operation Cost

The SEVs operation cost involves many aspects, such as electricity consumption, SEV maintenance, and management personnel costs. These factors are taken into account and their costs are attributed to the SEVs operation cost per minute, and the total of SEVs operation cost, labeled asC1, can be expressed as(1)C1=∑m∈M∑i∈N∑j∈Ntij⋅xijm⋅D1,where D1 is the operation cost of SEVs per minute; its unit is yuan/minute.


### 3.3.2. User Cost

(1) User Time Cost. The user time includes the waiting time at their origins and the in-vehicle travel time; therefore, the user time cost includes waiting time cost and in-vehicle travel time cost.The user waiting time cost, labeled asC2, is calculated as follows:(2)C2=∑k∈KWk⋅D2,where D2 is the waiting time cost of user per minute; its unit is yuan/minute.The user in-vehicle travel time cost, labeled asC3, can be calculated as follows:(3)C3=∑m∈M∑i∈N∑j∈NQimTjm−Tim⋅D3,where D3 is the in-vehicle travel time cost of per minute; its unit is yuan/minute.(2) User Rental Cost. The user rental cost is the fee paid by the user to the company of SEVs for using the SEVs. Company of SEVs usually charges according to the time in which users use SEVs, and the calculation formula of user rental cost, labeled as C4, can be expressed by(4)C4=∑m∈M∑i∈N∑j∈NQimTjm−Tim⋅D4,where D4 is the rent fee that users need to pay per minute for using the SEV; its unit is yuan/minute.(3) User Ride-Sharing Bonus. The company of SEVs encourages users to use the ride-sharing function of SEVs. In order to achieve this goal, the company takes a part of the user’s rental fee as bonus to the users who provide ride-sharing service as drivers. The bonus calculation formula is as follows:(5)C5=∑k∈K∑i∈Nδki∑m∈M∑i∈N∑j∈NQimTjm−Tim⋅D4⋅D5,where D5 is the proportional coefficient of bonus given to drivers from the users’ rental fee.


### 3.3.3. Penalty Function

SEVs are required to arrive at the user’s location within a specified period of time that is the time window. The SEV arriving in advance will produce idle time and result in a waste of operation, and if there is late arrival of SEV, it will cause user waiting time and affect user’s satisfaction. In order to make the arrival of the SEV meet the user’s required time window as much as possible and improve the operation efficiency of the SEVs, a penalty function is set, which is as follows:(6)PTim=b1ei−Tim,Tim<ei,0,ei≤Tim≤li,b2Tim−li,li<Tim,where PTim is a penalty function for the SEV m arriving at the location of the user group i.Based on (1)–(6), the routing optimization model of SEVs with ride-sharing is obtained as follows:(7)MinC=C1+C2+C3+C4−C5+∑m∈M∑i∈NPTim,subject to(8)1≤Qim≤Q,∀i∈N,∀m∈M,(9)Tjm≥Tim+tij+sixijm,∀i,j∈N,∀m∈M,(10)Qjm≥Qim+qjmxijm,∀i,j∈N,∀m∈M,(11)max1,qim≤Qim≤minQ,Q+qim,∀i∈N,∀m∈M,(12)xijm∑k∈K∑i∈Nδki≥1.Formula (7) is the objective function of the model, in which the SEVs operation cost and the total user cost are considered. Constraint (8) indicates the load of the SEV; the minimum is 1. Constraint (9) refers to the time for a SEV from user group i to user group j that should not be less than Tjm. Constraint (10) ensures that the load of SEV at location of user group j is equal or more than the sum of the load at location of user group i and the number of users getting on and off SEV at location of user group j. Constraint (11) guarantees that user number in SEV leaving each location does not exceed the capacity of SEV and there is at least one user. Constraint (12) guarantees the presence of at least one driver in SEV.


## 3.3.1. The SEVs Operation Cost

The SEVs operation cost involves many aspects, such as electricity consumption, SEV maintenance, and management personnel costs. These factors are taken into account and their costs are attributed to the SEVs operation cost per minute, and the total of SEVs operation cost, labeled asC1, can be expressed as(1)C1=∑m∈M∑i∈N∑j∈Ntij⋅xijm⋅D1,where D1 is the operation cost of SEVs per minute; its unit is yuan/minute.


## 3.3.2. User Cost

(1) User Time Cost. The user time includes the waiting time at their origins and the in-vehicle travel time; therefore, the user time cost includes waiting time cost and in-vehicle travel time cost.The user waiting time cost, labeled asC2, is calculated as follows:(2)C2=∑k∈KWk⋅D2,where D2 is the waiting time cost of user per minute; its unit is yuan/minute.The user in-vehicle travel time cost, labeled asC3, can be calculated as follows:(3)C3=∑m∈M∑i∈N∑j∈NQimTjm−Tim⋅D3,where D3 is the in-vehicle travel time cost of per minute; its unit is yuan/minute.(2) User Rental Cost. The user rental cost is the fee paid by the user to the company of SEVs for using the SEVs. Company of SEVs usually charges according to the time in which users use SEVs, and the calculation formula of user rental cost, labeled as C4, can be expressed by(4)C4=∑m∈M∑i∈N∑j∈NQimTjm−Tim⋅D4,where D4 is the rent fee that users need to pay per minute for using the SEV; its unit is yuan/minute.(3) User Ride-Sharing Bonus. The company of SEVs encourages users to use the ride-sharing function of SEVs. In order to achieve this goal, the company takes a part of the user’s rental fee as bonus to the users who provide ride-sharing service as drivers. The bonus calculation formula is as follows:(5)C5=∑k∈K∑i∈Nδki∑m∈M∑i∈N∑j∈NQimTjm−Tim⋅D4⋅D5,where D5 is the proportional coefficient of bonus given to drivers from the users’ rental fee.


## 3.3.3. Penalty Function

SEVs are required to arrive at the user’s location within a specified period of time that is the time window. The SEV arriving in advance will produce idle time and result in a waste of operation, and if there is late arrival of SEV, it will cause user waiting time and affect user’s satisfaction. In order to make the arrival of the SEV meet the user’s required time window as much as possible and improve the operation efficiency of the SEVs, a penalty function is set, which is as follows:(6)PTim=b1ei−Tim,Tim<ei,0,ei≤Tim≤li,b2Tim−li,li<Tim,where PTim is a penalty function for the SEV m arriving at the location of the user group i.Based on (1)–(6), the routing optimization model of SEVs with ride-sharing is obtained as follows:(7)MinC=C1+C2+C3+C4−C5+∑m∈M∑i∈NPTim,subject to(8)1≤Qim≤Q,∀i∈N,∀m∈M,(9)Tjm≥Tim+tij+sixijm,∀i,j∈N,∀m∈M,(10)Qjm≥Qim+qjmxijm,∀i,j∈N,∀m∈M,(11)max1,qim≤Qim≤minQ,Q+qim,∀i∈N,∀m∈M,(12)xijm∑k∈K∑i∈Nδki≥1.Formula (7) is the objective function of the model, in which the SEVs operation cost and the total user cost are considered. Constraint (8) indicates the load of the SEV; the minimum is 1. Constraint (9) refers to the time for a SEV from user group i to user group j that should not be less than Tjm. Constraint (10) ensures that the load of SEV at location of user group j is equal or more than the sum of the load at location of user group i and the number of users getting on and off SEV at location of user group j. Constraint (11) guarantees that user number in SEV leaving each location does not exceed the capacity of SEV and there is at least one user. Constraint (12) guarantees the presence of at least one driver in SEV.


## 4. Solution of Model

In order to solve the mathematical model proposed, the genetic algorithm is applied and designed.


### 4.1. Genetic Algorithm

Based on Darwin’s theory of evolution and Mendel’s genetic theory, the genetic algorithm simulates the evolution law (mechanism of survival of the fittest) of the biological world and is a global optimization algorithm [52]. The essence of the algorithm is to represent the problem as “chromosome” evolution process and obtain the “most suitable environment” individual through calculation which is the satisfactory solution or the optimal solution to the problem.The main steps of the GA are described as follows.(1)
Determine the coding strategy, fitness function, the size of the population, the genetic operation method (selection, crossover, and mutation), and the genetic parameters, such as crossover probability and mutation probability.(2)
Produce the chromosomes randomly according to the size of population.(3)
According to the genetic strategy, the next generation population is obtained by carrying out of replicating, crossover, and mutation operation.(4)
Calculate the optimal individual and judge the convergence criterion of the algorithm. If the convergence criterion is satisfied, then stop the calculation and output the result. Otherwise, return to (3).


### 4.2. The Design of GA

In this paper, based on the SEV users’ demands and road network information, GA is designed to solve the model proposed. The solution process of the model is shown in Figure2. The design of genetic algorithm is as follows.Figure 2
The solution process of the model using GA.


#### 4.2.1. Coding Method

The natural number coding method is adopted. This coding method can not only ensure good performance, but also reduce the difficulty of the algorithm to ensure operation efficiency. It can simplify the decoding process and reduce the calculation amount.In this paper, the number 0 represents the partition of SEV route, and the numbers 1, 2, 3, …,N represent group of users, respectively. For example, if the chromosome code is “027506801340,” it means that the services of 8 groups of users are completed by three SEVs. The routes of the three SEVs are as follows:The first route: First, SEV starts from the origin of user group 2 and then arrives at the location of the user group 7. Second, after some users get off and the user group 7 gets on, SEV moves on and arrives at the location of the user group 5. Third, after some users get off and the user group 5 gets on, SEV moves on and arrives at the destination of the user group 5 and completes the service.The second route: First, SEV starts from the origin of user group 6 and then arrives at the location of user group 8. Second, after some users get off and the user group 8 gets on, SEV moves on and arrives at the destination of the user group 8 and completes the service.The third route: First, SEV starts from the origin of user group 1 and then arrives at the location of user group 3. Second, after some users get off and user group 3 gets on, SEV moves on and arrives at the location of user group 4. Third, after some users get off and the user group 4 gets on, SEV moves on and arrives at the destination of the user group 4 and completes the service.


#### 4.2.2. Initial Population

The method of randomly generating populations is used. The first step is to generate a full array ofN users. In the second step, m + 1 zeros are randomly and nonadjacently inserted into the full permutation (assuming m routes), and the first and last gene location must be zero, thereby forming a chromosome. It repeats the above two steps until the number of chromosomes generated meets the requirements of the population size.


#### 4.2.3. Fitness Function

The fitness function is a reference function to measure the superiority of individuals in a population. In this paper, each chromosome corresponds to several feasible routes, so the fitness is used to evaluate the pros and cons of the SEVs routes. The objective function studied is composed of three parts: the SEVs operation cost, user cost, and the penalty. The purpose of the objective function is to find minimum value. Because the objective function value is negatively correlated with the fitness value, the reciprocal of the objective function value corresponding to the chromosome is taken as the fitness value of the chromosome. The formula of the fitness function is as follows:(13)Fx=1Cx,where Fx and Cx represent fitness function and the objective function value corresponding to the chromosome x in the population, respectively.


#### 4.2.4. Selection and Crossover Operation

The selection operation is implemented by using a roulette strategy. In the population, the fitness value is divided into proportions according to the superiority, and then the gambling disk surface is allocated according to the proportion of the individual. The larger the proportion of individuals with higher fitness values, the larger the allocated disk surface. The size of the disk represents the selection probability of individual. This means that individuals with larger fitness values are more likely to be selected.The route optimization problem of the SEVs with ride-sharing requires the retention of adjacent relationships and order relations. Therefore, a sequential crossing method is employed.


#### 4.2.5. Mutation Operator

The reverse transformation method is used. That is, in the process of mutation, a reversal region composed of several genes is first randomly selected. Then, the values in them are reversed and returned to their original positions. For example, the individual is supposed as “027506801340.” First, the sequence of user group number is obtained by ignoring the number “0” in this chromosome, which is “27568134.” Then, the reversal region is supposed from the second gene to seventh gene, and the individual becomes “23186574” after reverse transformation operation. Finally, the all “0” are returned to their original positions, and the individual becomes “023108605740,” which is the individual after the mutation operation.


#### 4.2.6. Convergence Criterion

The maximum number of iterations is selected as the convergence criterion of GA. If the maximum number of iterations is reached, GA stops the calculation and outputs the result.


## 4.1. Genetic Algorithm

Based on Darwin’s theory of evolution and Mendel’s genetic theory, the genetic algorithm simulates the evolution law (mechanism of survival of the fittest) of the biological world and is a global optimization algorithm [52]. The essence of the algorithm is to represent the problem as “chromosome” evolution process and obtain the “most suitable environment” individual through calculation which is the satisfactory solution or the optimal solution to the problem.The main steps of the GA are described as follows.(1)
Determine the coding strategy, fitness function, the size of the population, the genetic operation method (selection, crossover, and mutation), and the genetic parameters, such as crossover probability and mutation probability.(2)
Produce the chromosomes randomly according to the size of population.(3)
According to the genetic strategy, the next generation population is obtained by carrying out of replicating, crossover, and mutation operation.(4)
Calculate the optimal individual and judge the convergence criterion of the algorithm. If the convergence criterion is satisfied, then stop the calculation and output the result. Otherwise, return to (3).


## 4.2. The Design of GA

In this paper, based on the SEV users’ demands and road network information, GA is designed to solve the model proposed. The solution process of the model is shown in Figure2. The design of genetic algorithm is as follows.Figure 2
The solution process of the model using GA.


### 4.2.1. Coding Method

The natural number coding method is adopted. This coding method can not only ensure good performance, but also reduce the difficulty of the algorithm to ensure operation efficiency. It can simplify the decoding process and reduce the calculation amount.In this paper, the number 0 represents the partition of SEV route, and the numbers 1, 2, 3, …,N represent group of users, respectively. For example, if the chromosome code is “027506801340,” it means that the services of 8 groups of users are completed by three SEVs. The routes of the three SEVs are as follows:The first route: First, SEV starts from the origin of user group 2 and then arrives at the location of the user group 7. Second, after some users get off and the user group 7 gets on, SEV moves on and arrives at the location of the user group 5. Third, after some users get off and the user group 5 gets on, SEV moves on and arrives at the destination of the user group 5 and completes the service.The second route: First, SEV starts from the origin of user group 6 and then arrives at the location of user group 8. Second, after some users get off and the user group 8 gets on, SEV moves on and arrives at the destination of the user group 8 and completes the service.The third route: First, SEV starts from the origin of user group 1 and then arrives at the location of user group 3. Second, after some users get off and user group 3 gets on, SEV moves on and arrives at the location of user group 4. Third, after some users get off and the user group 4 gets on, SEV moves on and arrives at the destination of the user group 4 and completes the service.


### 4.2.2. Initial Population

The method of randomly generating populations is used. The first step is to generate a full array ofN users. In the second step, m + 1 zeros are randomly and nonadjacently inserted into the full permutation (assuming m routes), and the first and last gene location must be zero, thereby forming a chromosome. It repeats the above two steps until the number of chromosomes generated meets the requirements of the population size.


### 4.2.3. Fitness Function

The fitness function is a reference function to measure the superiority of individuals in a population. In this paper, each chromosome corresponds to several feasible routes, so the fitness is used to evaluate the pros and cons of the SEVs routes. The objective function studied is composed of three parts: the SEVs operation cost, user cost, and the penalty. The purpose of the objective function is to find minimum value. Because the objective function value is negatively correlated with the fitness value, the reciprocal of the objective function value corresponding to the chromosome is taken as the fitness value of the chromosome. The formula of the fitness function is as follows:(13)Fx=1Cx,where Fx and Cx represent fitness function and the objective function value corresponding to the chromosome x in the population, respectively.


### 4.2.4. Selection and Crossover Operation

The selection operation is implemented by using a roulette strategy. In the population, the fitness value is divided into proportions according to the superiority, and then the gambling disk surface is allocated according to the proportion of the individual. The larger the proportion of individuals with higher fitness values, the larger the allocated disk surface. The size of the disk represents the selection probability of individual. This means that individuals with larger fitness values are more likely to be selected.The route optimization problem of the SEVs with ride-sharing requires the retention of adjacent relationships and order relations. Therefore, a sequential crossing method is employed.


### 4.2.5. Mutation Operator

The reverse transformation method is used. That is, in the process of mutation, a reversal region composed of several genes is first randomly selected. Then, the values in them are reversed and returned to their original positions. For example, the individual is supposed as “027506801340.” First, the sequence of user group number is obtained by ignoring the number “0” in this chromosome, which is “27568134.” Then, the reversal region is supposed from the second gene to seventh gene, and the individual becomes “23186574” after reverse transformation operation. Finally, the all “0” are returned to their original positions, and the individual becomes “023108605740,” which is the individual after the mutation operation.


### 4.2.6. Convergence Criterion

The maximum number of iterations is selected as the convergence criterion of GA. If the maximum number of iterations is reached, GA stops the calculation and outputs the result.


## 4.2.1. Coding Method

The natural number coding method is adopted. This coding method can not only ensure good performance, but also reduce the difficulty of the algorithm to ensure operation efficiency. It can simplify the decoding process and reduce the calculation amount.In this paper, the number 0 represents the partition of SEV route, and the numbers 1, 2, 3, …,N represent group of users, respectively. For example, if the chromosome code is “027506801340,” it means that the services of 8 groups of users are completed by three SEVs. The routes of the three SEVs are as follows:The first route: First, SEV starts from the origin of user group 2 and then arrives at the location of the user group 7. Second, after some users get off and the user group 7 gets on, SEV moves on and arrives at the location of the user group 5. Third, after some users get off and the user group 5 gets on, SEV moves on and arrives at the destination of the user group 5 and completes the service.The second route: First, SEV starts from the origin of user group 6 and then arrives at the location of user group 8. Second, after some users get off and the user group 8 gets on, SEV moves on and arrives at the destination of the user group 8 and completes the service.The third route: First, SEV starts from the origin of user group 1 and then arrives at the location of user group 3. Second, after some users get off and user group 3 gets on, SEV moves on and arrives at the location of user group 4. Third, after some users get off and the user group 4 gets on, SEV moves on and arrives at the destination of the user group 4 and completes the service.


## 4.2.2. Initial Population

The method of randomly generating populations is used. The first step is to generate a full array ofN users. In the second step, m + 1 zeros are randomly and nonadjacently inserted into the full permutation (assuming m routes), and the first and last gene location must be zero, thereby forming a chromosome. It repeats the above two steps until the number of chromosomes generated meets the requirements of the population size.


## 4.2.3. Fitness Function

The fitness function is a reference function to measure the superiority of individuals in a population. In this paper, each chromosome corresponds to several feasible routes, so the fitness is used to evaluate the pros and cons of the SEVs routes. The objective function studied is composed of three parts: the SEVs operation cost, user cost, and the penalty. The purpose of the objective function is to find minimum value. Because the objective function value is negatively correlated with the fitness value, the reciprocal of the objective function value corresponding to the chromosome is taken as the fitness value of the chromosome. The formula of the fitness function is as follows:(13)Fx=1Cx,where Fx and Cx represent fitness function and the objective function value corresponding to the chromosome x in the population, respectively.


## 4.2.4. Selection and Crossover Operation

The selection operation is implemented by using a roulette strategy. In the population, the fitness value is divided into proportions according to the superiority, and then the gambling disk surface is allocated according to the proportion of the individual. The larger the proportion of individuals with higher fitness values, the larger the allocated disk surface. The size of the disk represents the selection probability of individual. This means that individuals with larger fitness values are more likely to be selected.The route optimization problem of the SEVs with ride-sharing requires the retention of adjacent relationships and order relations. Therefore, a sequential crossing method is employed.


## 4.2.5. Mutation Operator

The reverse transformation method is used. That is, in the process of mutation, a reversal region composed of several genes is first randomly selected. Then, the values in them are reversed and returned to their original positions. For example, the individual is supposed as “027506801340.” First, the sequence of user group number is obtained by ignoring the number “0” in this chromosome, which is “27568134.” Then, the reversal region is supposed from the second gene to seventh gene, and the individual becomes “23186574” after reverse transformation operation. Finally, the all “0” are returned to their original positions, and the individual becomes “023108605740,” which is the individual after the mutation operation.


## 4.2.6. Convergence Criterion

The maximum number of iterations is selected as the convergence criterion of GA. If the maximum number of iterations is reached, GA stops the calculation and outputs the result.


## 5. Case Simulation and Analysis

In order to test the MSEVRS and SEVs routing optimization model proposed, a case is discussed based on [31], in which some data is added according to the need of the model. In this case, there are nine nodes numbered N1, N2, …, N9 in the road network, which represent the origin and destination of user travel demands. Their topological map is shown in Figure 3.Figure 3
Road network topology map.In Figure3, the numbers on the line represent the shortest distance between nodes. The user’s demands are listed in Table 1, which includes the origin-destination (O-D) pairs, the total number of user groups, the number of users in each group, and their required time window.Table 1
User demands.
User groupO-DNumber of user groups with the same O-DNumber of users per groupTime windowU1N1-N64112:45–13:15U2N1-N6113:00–13:30U3N1-N6113:00–13:30U4N1-N6210:00–10:30U5N2-N83110:25–10:55U6N2-N838:30–9:00U7N2-N8110:20–10:50U8N3-N9419:30–10:00U9N3-N929:35–10:05U10N3-N919:30–10:00U11N3-N9213:45–14:15U12N4-N52113:30–14:00U13N4-N5113:35–14:05U14N5-N12210:00–10:30U15N5-N1211:00–11:30U16N6-N4318:45–9:15U17N6-N418:30–9:00U18N6-N4110:00–10:30U19N7-N3319:25–9:55U20N7-N329:30–10:00U21N7-N319:30–10:00U22N8-N7419:30–10:00U23N8-N7111:55–12:25U24N8-N7112:00–12:30U25N8-N729:30–10:00U26N9-N24212:50–13:20U27N9-N2110:15–10:45U28N9-N2110:20–10:50U29N9-N219:30–10:00U30N1-N31112:45–13:15U31N3-N61113:00–13:30Total—3141—The mathematical model of the case is established according to formula (7), and GA is applied to solve the model. The settings of relevant parameters in the model and GA are shown in Table 2. After simulation, the optimal number of SEVs and their routes needed to complete the travel demands of all users are obtained, as shown in Table 3. Table 3 also includes the distance of each route, user group serviced by each SEV, and the load at each node.Table 2
Parameters in the model and GA.
The capacity of SEV4Speed of SEV60 (km/h)D10.62D20.3D30.7D41.1D510%b1, b25The population size50Number of iterations200Pc0.95Pm0.05Table 3
SEVs and their routes for the users in MSEVRS.
SEVsRouteDistanceUser group servicedThe load at each nodeV1N2-N6-N810U63, 3, 0V2N9-N6-N211U262, 2, 0V3N6-N3-N414U181, 1, 0V4N3-N6-N915U112, 2, 0V5N5-N2-N1-N3-N637U14, U42, 2, 2, 2, 0V6N3-N6-N915U9, U10, U84, 4, 0V7N7-N4-N311U20, U21, U194, 4, 0V8N5-N2-N121U152, 2, 0V9N6-N3-N414U16, U172, 2, 0V10N4-N3-N6-N520U13, U122, 2, 2, 0V11N8-N75U24, U232, 0V12N1-N3-N616U1, U2, U3, U30, U314, 4, 0V13N9-N6-N211U291, 1, 0V14N8-N75U25, U223, 0V15N9-N6-N2-N6-N821U28, U27, U5, U72, 2, 2, 2, 0Total—22631—According to Table3, the following conclusions can be obtained:(1)
A total of 15 SEVs are needed to meet the travel demands of all users, and the maximum load of each SEV in the whole operation process is 4, which meets the limitation of SEV capacity.(2)
In MSEVRS, the SEVs can be fully utilized because of their ride-sharing function. For example,V12 starts from N1, passes through N3, and arrives at the destination N6 to complete the whole service process. Users serviced include U1, U2, U3, U30, and U31. At N1, users U1, U2, U3, and U30 get on the SEV, and the number of users in the SEV is 4. Then, when SEV arrives at N3 where there is the destination of U30, user U30 gets off, and, at this time, user U31 gets on the SEV, and the number of users in the SEV is kept as 4. Finally, the SEV arrives at the destination N6 and all users get off. In the whole process, from N1 to N3 is the ride-sharing section of U1, U2, U3, and U30. From N3 to N6 is the ride-sharing section of U1, U2, U3, and U31.In addition, SEVV6, V7, V9, V10, V11, V14, and V15 also reflect the ride-sharing function.(3)
In the process of completing all the travel demands of users, there are also situations where there is no ride-sharing. For example, SEVV4 starts from N3, goes through N6, and finally arrives at the destination N9. In the entire process, only user U11 is served; between the start point and the end point, no users get on and off the SEV, and the number of users in the SEV is kept as 2. Finally, the SEV arrives at the destination N9 and the two users get off. This shows that there also exists non-ride-sharing under the MSEVRS. This further indicates that ride-sharing is carried out on the premise of making full use of SEVs to improve efficiency; otherwise, there would be no ride-sharing.Besides, in order to further investigate the advantages of the MSEVRS proposed, we compared it with the current SEVs mode, which is named as CSEVM. Under CSEVM, the SEVs have no ride-sharing function. In the case (shown in Figure3 and Table 1), each group of users needs one SEV to provide service, which means that a total of 31 SEVs are required. The route is planned for each user group according to the shortest distance, as shown in Table 4. Table 4 also includes the distance of each route, the user group serviced by each SEV, and the load at each node.Table 4
SEVs and their routes for the users in CSEVM.
SEVsRouteDistanceUser group servicedThe load at each nodeV1N1-N3-N616U11V2N1-N3-N616U21V3N1-N3-N616U31V4N1-N3-N616U42V5N2-N6-N810U51V6N2-N6-N810U63V7N2-N6-N810U71V8N3-N6-N915U81V9N3-N6-N915U92V10N3-N6-N915U101V11N3-N6-N915U112V12N4-N3-N6-N520U121V13N4-N3-N6-N520U131V14N5-N2-N121U142V15N5-N2-N121U152V16N6-N3-N414U161V17N6-N3-N414U171V18N6-N3-N414U181V19N7-N4-N311U191V20N7-N4-N311U202V21N7-N4-N311U211V22N8-N75U221V23N8-N75U231V24N8-N75U241V25N8-N75U252V26N9-N6-N211U262V27N9-N6-N211U271V28N9-N6-N211U281V29N9-N6-N211U291V30N1-N38U301V31N3-N68U311Total—3913141The following can be found in Tables3 and 4:(1)
In MSEVRS, a total of 15 SEVs are needed to meet the demands of all users due to their ride-sharing function, while, in CSEVM, 31 SEVs are needed. This indicates that MSEVRS can significantly improve the utilization efficiency of SEVs and reduce the number of SEVs.(2)
The total distance under MSEVRS is 226 km, which is 17% less than the 391 km under CSEVM. This means saving energy.(3)
The number of SEVs used at each node in MSEVRS and CSEVM is counted, as shown in Figure4. It can be seen that the numbers of SEVs used at nodes in MSEVRS are less than those in CSEVM except node N5, at which the numbers are equal. In particular, at node N1, only one SEV can complete demands of five groups of users under MSEVRS, while, under CSEVM, five SEVs are needed to complete their demands. At node N5 there are two groups of users, U14 and U15. Due to the large time interval of demands of them, moreover the time interval between users at N5 and other users is also large; there is no valid ride-sharing at N5. So, the same as the CSEVM, two SEVs are needed to serve U14 and U15 at N5 in MSEVRS.In addition, according to (1)–(4), each item cost under the MSEVRS and CSEVM is calculated and shown in Table 5.Table 5
The various costs in CSEVM and MSEVRS.
Cost typeSubcategoryCSEVMMSEVRSMSEVRS-CSEVMDecreased percentageUser costIn-vehicle travel time cost368.20368.2000Waiting time cost042.60−42.60—User rental cost430.10223.74206.3647.98%The SEVs company costThe SEVs operation cost242.42140.12102.3042.20%Total cost—1040.72774.66266.0625.56%Figure 4
Number of SEVs at every node in MSEVRS and CSEVM.The following conclusions can be drawn from Table5:(1)
Compared to that in CSEVM, the user time cost in MSEVRS is increased. This is because in MSEVRS the ride-sharing improves the utilization efficiency of SEVs and reduces the number of SEVs and causes some users to incur the waiting time cost. In CSEVM, each group of users has one SEV to provide travel service for them, and there is no need to wait for ride-sharing vehicle, so the waiting time cost is 0. In MSEVRS, the user ride-sharing is also based on the shortest route, so the in-vehicle travel time cost is the same in both modes. Therefrom, in MSEVRS the user travel time is increased due to ride-sharing, which leads to an increase in user time cost.(2)
Compared to that in CSEVM, in MSEVRS the user rental cost is reduced by 206.36 yuan, with a reduction of 47.98%, the SEVs operation cost is reduced by 102.3 yuan, with a reduction of 42.2%, and the total cost of SEVs company and users is reduced 266.06 yuan, with a reduction of 22.56%.(3)
Overall, under MSEVRS, the user time cost increased, but the user rental cost, user total cost, and the SEVs operation cost are decreased. Also, the per capita travel time cost increased by 1.04 yuan, but the per capita SEV rental cost decreased by 5.03 yuan; the total per capita cost decreased by 3.99 yuan. This shows that a better cost performance and service for users are obtained in MSEVRS.In addition, under MSEVRS, some users can use SEVs through ride-sharing, such as userU31 (Table 3), which means that these users do not need to have driving licenses. This is different from CSEVM, in which all users are required to have a driving license. This shows that MSEVRS can make SEVs company expand the range of users and have a better application prospect.


## 6. Conclusion and Future Work

In view of the waste of vehicle resources in the current operation mode of SEVs, the mode of SEVs with ride-sharing function, namely, MSEVRS, is proposed. In MSEVRS, different users can fulfill their travel demands through the ride-sharing function of SEVs and reduce the waste of vehicle resources. The operation principle of MSEVRS is presented, in which the user and the SEVs management center collects information of the SEVs and users and then optimizes the SEVs route to realize the ride-sharing function of the SEVs and meet the travel demands of all users. The routing optimization of SEVs in MSEVRS is focused and a mathematical model is proposed, in which the SEVs operation cost, user time cost, user rental cost, user ride-sharing bonus, and the time window are considered and the objective is to minimize the total cost of the SEVs company and users. To solve the mathematical model, the genetic algorithm is designed and used. Finally, a case is given and simulated.The simulation results show that the proposed model achieves the optimal route for SEVs with ride-sharing and verifies the feasibility of MSEVRS. In addition, comparison from results between MSEVRS and CSEVM shows that MSEVRS can significantly reduce the number of SEVs and improve the utilization efficiency of SEVs. And the total distance is reduced, which means saving energy. Moreover, compared with CSEVM, MSEVRS reduces user total cost and the SEVs operation cost, obtains a better cost performance and service for users, and has a better application prospect.This paper studied the mode of SEVs with ride-sharing and user ride-sharing bonus is designed as the method to encourage users to accept the ride-sharing. However, the issue of coordinated ride-sharing among users is complex; for example, some users like driving alone, etc., which needs further discussion. Besides, it assumes that the vehicle speed is constant in the proposed model, but, in reality, it is dynamic on the traffic network and inevitably affects the route of the SEVs and the ride-sharing function, which is also the content of further research.



---

*Source: 9560135-2020-09-09.xml*