# Research on Taxi Pricing Model and Optimization for Carpooling Detour Problem

Authors: Wei Zhang; Ruichun He; Yong Chen; Mingxia Gao; Changxi Ma
Journal: Journal of Advanced Transportation
 (2019)

---

## Abstract

This paper builds a multiobjective optimization model for solving the taxi carpooling with detour problem and designs a genetic algorithm to determine a fair pricing scheme for riders and drivers. The researches show that it is feasible to share a taxi with detour. It is the key to determine appropriate carpooling payment ratio and detour carpooling payment ratio. The ratio of detour distance to travel distance has an important influence on detour carpooling. It should be limited to less than certain values. Payment ratios and the maximum value of the ratio of detour distance to travel distance are determined by the method proposed in this paper. The method can ensure benefits of passengers and drivers, which makes detour carpooling a reality. These conclusions and the method have a certain guiding significance for formulating taxi policy.


---

## Body

## 1. Introduction

Taxi carpooling mode has become a common travelling mode. The mode permits several passengers to share the same taxi. Taxi carpooling can effectively solve the problem of having difficulty getting a taxi at peak time. It does not only ease the traffic pressure and improve the transportation efficiency [1, 2], but also reduce energy consumption [3–6]. It is an effective solution to solve the urban traffic problem.Many scholars studied the problem of carpooling [7–12]. This research work focuses on the following two aspects: on the one hand, the characteristics of carpooling behavior, the influence factors of carpooling, and the effects of carpooling are studied [13–18]. Shaheen analyzed carpooling situation in the San Francisco Bay Area and studied passenger characteristics, behaviors, and motivation [19]. Delhomme researched the main determinants of the practice of carpooling by investigating the factual data and gave some strategies for increasing the number of carpoolers and the frequency of carpooling [20]. Malodia studied the characteristics of Indian residents preference for passenger sharing based on the data from the internet survey and found that cognitive attitudes have important effects on passenger sharing behaviour [21]. Tahmasseby found that distance, time, cost, gender, occupation, age, weather conditions, and other factors can affect the choice of sharing [22]. Javid studied the sharing characteristics of 50 states in the United States and the District of Columbia and analyzed the impact of the carpooling policy on the environment [23]. Sweta proved that carpooling mode can help to reduce congestion and fuel consumption [24]. Zhang built a model of multiple passengers carpooling, analyzed carpooling advantages, and proved that carpooling can bring benefits to passengers and drivers by simulation [25].On the other hand, the problem of carpooling matching and route optimization is studied. Jamal put forward route planning and ride matching algorithms and designed a system that can supply the users with alternative routes for their trips [26]. Mallus proposed a dynamic carpooling route matching algorithm, and the method is verified by the experiment [27]. Huang proposed carpool route and matching algorithm and solved carpool service problems in cloud computing based on genetic algorithm [28]. Chang designed a vehicular information system that combines the improved carpooling algorithm and the VANET-based route planning and computed the optimal carpooling sequence and precise fuel costs shared [29]. Ma built a taxi carpooling path optimization model, solved it based on the improved genetic algorithm, and obtained optimized path results [30]. He proposed an intelligent routing scheme based on GPS data. The carpooling system provides many-to-many services with multiple pickup and dropping points [31]. Xiao proposed a taxi carpooling matching algorithm based on fuzzy clustering and fuzzy recognition [32].In summary, the above researches proved the feasibility and effectiveness of carpooling mode and solved the problem of route planning in carpooling process. However, detour is a common phenomenon of taxi carpooling in reality. Destinations of passengers are different, but they would go to the same direction. Due to the factors, such as having difficulty getting another taxi and lower cost in carpooling, some passengers agree to detour for taking the same taxi. His travel time has to be delayed, but he can get more discount than other passengers in the same carpooling travel. Passengers’ payments have important influences on driver’s income. The reduction of the detour passenger’s cost will depress the driver’s income. How to control the payments of passengers to protect interest of the driver? It is important to study the problem, which can ensure implementation of carpooling policy. However, there are limited researches on the problem. For the problem of taxi detour carpooling, this paper builds a multiobjective optimization model, designs an algorithm to solve the model based on genetic algorithm, and gets reasonable pricing stagey of detour carpooling which ensures interests of passengers and drivers simultaneously. The method makes carpooling detour a reality. The works have a certain guide significance to formulate taxi carpooling policy.


## 2. Problem Description and Notation

### 2.1. Problem Description

Suppose two passengers intend to share the same taxi. Of course, it can also be two groups. There may be more than a passenger in each group, but the sum of passengers is not more than taxi capacity. The destinations of the passengers in the same group are the same ones. Therefore, the two groups carpooling can be considered as two passengers carpooling. The problem of two passengers carpooling is studied in this paper. Suppose source of passengerA is A1 and the destination is A2. The best route of passenger A is A1→A2. Source of passenger B is B1, and the destination is B2. The best route of passenger B is B1→B2. The destinations of the two passengers are different; that is, A2≠B2, but A2 and B2 are in the same direction. Passenger B agrees to make a detour in order to share the taxi successfully. The travel routes of the two passengers are shown in Figure 1.Figure 1
Travel route of the passengers.The problem contains two possible situations of detour as follows.( 1 ) The distance from A1 to B1 is zero, which means that the two passengers start from the same position. In the situation, passenger A is sent to his destination; then passenger B is sent to the destination. The travel route is A1(B1)→A2→B2. The travel route of passenger A is not changed. The travel route of passenger B is changed from B1A1→B2 to A1(B1)→A2→B2. Passenger B makes a detour.( 2 ) The distance from A1 to B1 is not zero, which means that the two passengers start from the different positions. In the situation, passenger A gets on the taxi at position A1; then passenger B gets on the taxi at position B1. Passenger A arrives at the destination first and gets off at position A2; then passenger B gets off at position B2. Travel route is A1→B1→A2→B2. The travel route of passenger A is not changed. The travel route of passenger B is changed from B1→B2 to B1→A2→B2. Passenger B makes a detour.In the above carpooling situations, passengerA keeps the original route unchanged, but he shares the taxi with others in his travel, so he should enjoy discount price for carpooling. His cost should be lower than that he takes a taxi alone. Passenger B travels a new route longer than his original. His time has to be delayed. So more discount should be given to the detour passenger in order to make up for the loss of time caused by a detour. The costs of the two passengers are both reduced, which will influence the income of drivers. Therefore, it is very important to work out a reasonable charging scheme to ensure the interests of the driver and passengers simultaneously. The multiobjective optimization model of taxi carpooling detour is built to study the problem as follows.


### 2.2. Notation in the Model

All notations in the model are described as follows:LA: the travel distance of passenger A, that is, the distance from A1 to A2.LB: the travel distance of passenger B, that is, the distance from B1 to B2LX: the travel distance of passenger A before passenger B getting on the taxi, that is, the distance from A1 to B1.LR: the travel distance of passenger B after passenger A getting off the taxi, that is, the distance from A2 to B2.CL: the cost of the passenger whose travel distance is L.g: the base kilometres in taxi charging regulations.cs: the initiate price in taxi charging regulations, that is, the fee within g kilometres.cr: the price per kilometre more than g kilometres according to taxi charging regulations.NPA: the cost of passenger A under the condition of non-carpooling.NPB: the cost of passenger B under the condition of non-carpooling.CPA: the cost of passenger A under the condition of carpooling.CPB: the cost of passenger B under the condition of carpooling.CNPB: the cost of passenger B when he just shares taxi with others and does not make a detour.α: the payment ratio of the non-detour passenger, which is called carpooling payment ratio.β: the payment ratio of detour passenger, which is called detour payment ratio.LD: the detour distance which describes the difference between travel distance after detour carpooling and original travel distance.NV: the driver’s income under the condition of non-carpooling.G(L): the gas fee vehicle consumed when travel distance is L.x: the gas consumption per 100 km.y: the gas price per cubic meter.LS: the actual travel distance of the vehicle in a carrying trip.NPV: the driver’s income per unit travel length.CV: the driver’s income under the condition of carpooling.CPV: the driver’s income per unit travel long under the condition of carpooling.θLD/LB: the maximum threshold of the ratio of detour distance to travel distance.


## 2.1. Problem Description

Suppose two passengers intend to share the same taxi. Of course, it can also be two groups. There may be more than a passenger in each group, but the sum of passengers is not more than taxi capacity. The destinations of the passengers in the same group are the same ones. Therefore, the two groups carpooling can be considered as two passengers carpooling. The problem of two passengers carpooling is studied in this paper. Suppose source of passengerA is A1 and the destination is A2. The best route of passenger A is A1→A2. Source of passenger B is B1, and the destination is B2. The best route of passenger B is B1→B2. The destinations of the two passengers are different; that is, A2≠B2, but A2 and B2 are in the same direction. Passenger B agrees to make a detour in order to share the taxi successfully. The travel routes of the two passengers are shown in Figure 1.Figure 1
Travel route of the passengers.The problem contains two possible situations of detour as follows.( 1 ) The distance from A1 to B1 is zero, which means that the two passengers start from the same position. In the situation, passenger A is sent to his destination; then passenger B is sent to the destination. The travel route is A1(B1)→A2→B2. The travel route of passenger A is not changed. The travel route of passenger B is changed from B1A1→B2 to A1(B1)→A2→B2. Passenger B makes a detour.( 2 ) The distance from A1 to B1 is not zero, which means that the two passengers start from the different positions. In the situation, passenger A gets on the taxi at position A1; then passenger B gets on the taxi at position B1. Passenger A arrives at the destination first and gets off at position A2; then passenger B gets off at position B2. Travel route is A1→B1→A2→B2. The travel route of passenger A is not changed. The travel route of passenger B is changed from B1→B2 to B1→A2→B2. Passenger B makes a detour.In the above carpooling situations, passengerA keeps the original route unchanged, but he shares the taxi with others in his travel, so he should enjoy discount price for carpooling. His cost should be lower than that he takes a taxi alone. Passenger B travels a new route longer than his original. His time has to be delayed. So more discount should be given to the detour passenger in order to make up for the loss of time caused by a detour. The costs of the two passengers are both reduced, which will influence the income of drivers. Therefore, it is very important to work out a reasonable charging scheme to ensure the interests of the driver and passengers simultaneously. The multiobjective optimization model of taxi carpooling detour is built to study the problem as follows.


## 2.2. Notation in the Model

All notations in the model are described as follows:LA: the travel distance of passenger A, that is, the distance from A1 to A2.LB: the travel distance of passenger B, that is, the distance from B1 to B2LX: the travel distance of passenger A before passenger B getting on the taxi, that is, the distance from A1 to B1.LR: the travel distance of passenger B after passenger A getting off the taxi, that is, the distance from A2 to B2.CL: the cost of the passenger whose travel distance is L.g: the base kilometres in taxi charging regulations.cs: the initiate price in taxi charging regulations, that is, the fee within g kilometres.cr: the price per kilometre more than g kilometres according to taxi charging regulations.NPA: the cost of passenger A under the condition of non-carpooling.NPB: the cost of passenger B under the condition of non-carpooling.CPA: the cost of passenger A under the condition of carpooling.CPB: the cost of passenger B under the condition of carpooling.CNPB: the cost of passenger B when he just shares taxi with others and does not make a detour.α: the payment ratio of the non-detour passenger, which is called carpooling payment ratio.β: the payment ratio of detour passenger, which is called detour payment ratio.LD: the detour distance which describes the difference between travel distance after detour carpooling and original travel distance.NV: the driver’s income under the condition of non-carpooling.G(L): the gas fee vehicle consumed when travel distance is L.x: the gas consumption per 100 km.y: the gas price per cubic meter.LS: the actual travel distance of the vehicle in a carrying trip.NPV: the driver’s income per unit travel length.CV: the driver’s income under the condition of carpooling.CPV: the driver’s income per unit travel long under the condition of carpooling.θLD/LB: the maximum threshold of the ratio of detour distance to travel distance.


## 3. Modelling

### 3.1. Cost of Passengers

According to the usual taxi charging regulations in China, cost of passenger is calculated as follows:(1)CL=csifL≤gL-g×cr+csifL>gIf the two passengers take a taxi to their destinations, respectively, that is, they do not share a taxi, cost of passengerA and cost of passenger B, respectively, are(2)NPA=CLA(3)NPB=CLBIf the two passengers take the same taxi, passengers just need to pay part charge according to the current traffic policy. The cost of the two passengers is calculated specifically as follows.PassengerA does not make a detour. His travel route is unchanged and the travel time is not delayed. If he shares a taxi with others in part road section, he can only enjoy the discount for the road section of carpooling. There is not any discount for the road section of noncarpooling. The distance of the road section passenger A shares taxi with passenger B is LA-LX. The distance of the road section passenger A rides taxi alone is LX. The cost of passenger A is (4)CPA=αLA-LXLACLA+LXLACLAPassengerB does not only share a taxi with others, but also make a detour. The travel route of passenger B is changed, and his travel time is also delayed. So passenger B should enjoy more discount than the other passenger to make up his loss. The detour passenger needs to pay a part of the cost he pays when he does not share a taxi with others. The cost of passenger B is (5)CPB=βCLBwhere detour payment ratio β is not fixed. β changes inversely with relative detour distance which is the ratio of detour distance to travel distance. β is defined as a function which depends on LD/LB as follows. (6)β=FLDLB(7)LD=LA-LX+LR-LBLD is detour distance, and LD/LB is the ratio of detour distance to travel distance. Function F is a decreasing function. When LD/LB=0, function F is the maximum value. The value decreases with the increases of LD/LB. If LD/LB is high so that the value is too low, the interest of the driver will be affected.Moreover, the cost of passengerA by carpooling mode must be lower than that by riding taxi alone; that is, (8)CPA<NPAThe cost of passengerB by carpooling mode must be lower than that by sharing a taxi but no detour; that is,(9)CPB<CNPB(10)CNPB=αCLB


### 3.2. Income of Driver

The income of the driver depends on the payments of passengers and the fee of gas consumed. When travel distance of a vehicle isL, the gas fee is (11)GL=xy100LUnder the condition of noncarpooling, the driver’s income of the whole travel is(12)NV=CLS-GLSIf the time the driver takes in a carrying trip is long, the number of carrying trips in a day will reduce, which influences the total income of the driver all day. So it is unreasonable to describe the driver’s income based on the income of the driver each time carrying trip. In order to reveal the income of the driver really, the income per unit travel length is used.(13)NPV=NVLSUnder the condition of carpooling, the driver’s income in a carrying trip is(14)CV=CPA+CPB-GLS(15)LS=LA+LRSimilarly, under the condition of carpooling, the income per unit travel length is(16)CPV=CVLSFor driver, the driver’s unit income of detour carpooling must be more than that of noncarpooling; that is,(17)CPV>NPV


### 3.3. The Ratio of Detour Distance

Passengers expect the costs reducing, while driver expects the income increasing. In addition, the ratio of detour distance to travel distanceLD/LB is the key to realize detour carpooling. On the one hand, too long detour distance causes that passenger to be delayed for a long time, which is not accepted by the passenger. On the other hand, according to formula (6), the bigger ratio of detour distance to travel distance is, the smaller β is. The decrease of detour passenger’s payment leads to the income reduction of the driver. Too small β cannot ensure interests of the driver. Therefore, the ratio of detour distance to travel distance must be confined within a range. If the ratio is more than a certain threshold, the detour carpooling will be become impossible. So the following constraint should be satisfied:(18)LDLB≤θLD/LB


### 3.4. The Multiobjective Optimization Model of Taxi Detour Carpooling

Based on the analysis above, considering the benefits of passengers and driver simultaneously, the multiobjective optimization model of taxi detour carpooling is built as follows.(19)maxZ1=NPA-CPA(20)maxZ2=CNPB-CPB(21)maxZ3=CPV-NPV(22)s.t.NPA-CPA>0CNPB-CPB>0CPV-NPV>0LDLB>0LDLB≤θLD/LB0≤LX<LALA-LX>LB-LRLR<LB0<β<α<1LA,LB,LX,LR>0Formulas (19) ~ (21) are objective functions. Formula (19) means maximizing the cost saving of passenger A. Formula (20) means maximizing the cost saving of passenger B. Formula (21) means maximizing the increase of driver’ income. Formula (22) describes all constraints in the model.


## 3.1. Cost of Passengers

According to the usual taxi charging regulations in China, cost of passenger is calculated as follows:(1)CL=csifL≤gL-g×cr+csifL>gIf the two passengers take a taxi to their destinations, respectively, that is, they do not share a taxi, cost of passengerA and cost of passenger B, respectively, are(2)NPA=CLA(3)NPB=CLBIf the two passengers take the same taxi, passengers just need to pay part charge according to the current traffic policy. The cost of the two passengers is calculated specifically as follows.PassengerA does not make a detour. His travel route is unchanged and the travel time is not delayed. If he shares a taxi with others in part road section, he can only enjoy the discount for the road section of carpooling. There is not any discount for the road section of noncarpooling. The distance of the road section passenger A shares taxi with passenger B is LA-LX. The distance of the road section passenger A rides taxi alone is LX. The cost of passenger A is (4)CPA=αLA-LXLACLA+LXLACLAPassengerB does not only share a taxi with others, but also make a detour. The travel route of passenger B is changed, and his travel time is also delayed. So passenger B should enjoy more discount than the other passenger to make up his loss. The detour passenger needs to pay a part of the cost he pays when he does not share a taxi with others. The cost of passenger B is (5)CPB=βCLBwhere detour payment ratio β is not fixed. β changes inversely with relative detour distance which is the ratio of detour distance to travel distance. β is defined as a function which depends on LD/LB as follows. (6)β=FLDLB(7)LD=LA-LX+LR-LBLD is detour distance, and LD/LB is the ratio of detour distance to travel distance. Function F is a decreasing function. When LD/LB=0, function F is the maximum value. The value decreases with the increases of LD/LB. If LD/LB is high so that the value is too low, the interest of the driver will be affected.Moreover, the cost of passengerA by carpooling mode must be lower than that by riding taxi alone; that is, (8)CPA<NPAThe cost of passengerB by carpooling mode must be lower than that by sharing a taxi but no detour; that is,(9)CPB<CNPB(10)CNPB=αCLB


## 3.2. Income of Driver

The income of the driver depends on the payments of passengers and the fee of gas consumed. When travel distance of a vehicle isL, the gas fee is (11)GL=xy100LUnder the condition of noncarpooling, the driver’s income of the whole travel is(12)NV=CLS-GLSIf the time the driver takes in a carrying trip is long, the number of carrying trips in a day will reduce, which influences the total income of the driver all day. So it is unreasonable to describe the driver’s income based on the income of the driver each time carrying trip. In order to reveal the income of the driver really, the income per unit travel length is used.(13)NPV=NVLSUnder the condition of carpooling, the driver’s income in a carrying trip is(14)CV=CPA+CPB-GLS(15)LS=LA+LRSimilarly, under the condition of carpooling, the income per unit travel length is(16)CPV=CVLSFor driver, the driver’s unit income of detour carpooling must be more than that of noncarpooling; that is,(17)CPV>NPV


## 3.3. The Ratio of Detour Distance

Passengers expect the costs reducing, while driver expects the income increasing. In addition, the ratio of detour distance to travel distanceLD/LB is the key to realize detour carpooling. On the one hand, too long detour distance causes that passenger to be delayed for a long time, which is not accepted by the passenger. On the other hand, according to formula (6), the bigger ratio of detour distance to travel distance is, the smaller β is. The decrease of detour passenger’s payment leads to the income reduction of the driver. Too small β cannot ensure interests of the driver. Therefore, the ratio of detour distance to travel distance must be confined within a range. If the ratio is more than a certain threshold, the detour carpooling will be become impossible. So the following constraint should be satisfied:(18)LDLB≤θLD/LB


## 3.4. The Multiobjective Optimization Model of Taxi Detour Carpooling

Based on the analysis above, considering the benefits of passengers and driver simultaneously, the multiobjective optimization model of taxi detour carpooling is built as follows.(19)maxZ1=NPA-CPA(20)maxZ2=CNPB-CPB(21)maxZ3=CPV-NPV(22)s.t.NPA-CPA>0CNPB-CPB>0CPV-NPV>0LDLB>0LDLB≤θLD/LB0≤LX<LALA-LX>LB-LRLR<LB0<β<α<1LA,LB,LX,LR>0Formulas (19) ~ (21) are objective functions. Formula (19) means maximizing the cost saving of passenger A. Formula (20) means maximizing the cost saving of passenger B. Formula (21) means maximizing the increase of driver’ income. Formula (22) describes all constraints in the model.


## 4. Algorithm Design

### 4.1. Algorithm Procedure

The model proposed in the paper is a problem of multiobjective optimization. The purpose is to find the best price parametersα and β. They must be appropriate for all the possible carpooling. Carpooling is described using travel distances of the passengers, the position of getting on or getting off the taxi, and detour distance. The population composed of various types of carpooling is called carpooling states. Carpooling is an individual of carpooling states population. The price parameters would be obtained based on the carpooling states. Good price parameters depend on carpooling states with good diversity. So the algorithm process is divided into the following two parts: (1) searching carpooling states of diversity; (2) seeking the best price parameters for the carpooling states found in problem (1). The solutions are designed based on genetic algorithm. The exact process is shown in Figure 2. Firstly, the work of searching for carpooling states is carried out. The population of carpooling states with good diversity is found. Then, the work of seeking the best price parameters for each individual of the population obtained from above the process is carried out.Figure 2
The algorithm procedure.The detail algorithm process would be described as follows.


### 4.2. Searching Carpooling States

#### 4.2.1. Generating Initial Population

An individual of carpooling states population is described as(LA,LX,LB,LR). For an individual, LA, LX, LB, and LR are random. Suppose travel distances of passengers are normal distribution, the mean value of which is μ and standard deviation is σ. LA and LB are created based on the normal distribution. In the process of data generation, the nonpositive values are not used. If a nonpositive value is obtained, regenerating the number until a positive value, LX is chosen equably in the range [0,LA]. LR is chosen equably in the range [LB-LA+LX,LB] to satisfy constraints. The size of carpooling states population is N1. N1 individuals are generated, which form a carpooling states population.


#### 4.2.2. Evaluation of Carpooling States

Evaluation of each individual of carpooling states population depends on the closeness to other individuals. The closeness of individuali is the average value of the Euclidean space distances between individual i and other individual s. It is defined as (23)DWi=1N1-1∑j=1N1∑k=14x^ik-x^jk2(24)x^ik=xik-xkminxkmax-xkminxik is the value of attribute k of individual i. x^ik is the standardized value for xik. xkmax is the maximum value of attribute k in the population. xkmin is the minimum value of attribute k in the population. The bigger evaluation value shows that the individual is far away from other individuals, which will be kept.Diversity of the carpooling states populationt is measured by D(t).(25)Dt=N1N1-12∑i=1N1∑j=iN1∑k=14x^ik-x^jk2D(t) is the average value of the distances between all individuals in population t. The bigger D(t) is, the better the diversity of the population is.


#### 4.2.3. Selection of Carpooling States

Good individuals are selected from the previous population. The selected individuals will form a new population, the size of which is the same as the previous population. Tournament selection strategy is used to select individuals in the paper. The method is as follows:( 1 )  m1 individuals are selected randomly from the population, and m1<N1.( 2 ) The evaluation values of the selected individuals are computed. The best individual will be selected according to the evaluation values.( 3 ) The above steps are repeated N1 times until N1 individuals are selected. The N1 individuals form a new population.


#### 4.2.4. Crossover of Carpooling States

Crossover operator between two individuals is carried out with probabilitypccs. LB and LR of individuals are exchanged. Suppose LBi is LB section of individual i and LRi is LR section of individual i. Crossover operator between individual i and individual j is LAi↔LAj and LXi↔LXj.If individuali and individual j before crossover operator arei=(LAi,LXi,LBi,LRi)j=(LAj,LXj,LBj,LRj),individuali and individual j after crossover operator isi′=(LAj,LXj,LBi,LRi)j′=(LAi,LXi,LBj,LRj).It is necessary to check whether the new individuals satisfy with constraints. The processes of checking and adjustment are as follows: ifLA-LX>LB-LR is not satisfied, LR will be increased gradually with ranges up to LB until satisfying the constraint. If there is no appropriate LR found, LB and LR are both increased until satisfying the constraint.


#### 4.2.5. Mutation of Carpooling States

Mutation operator is carried out for individuals with probabilitypmcs. LX and LR have an important influence on individuals. A little change of LX or LR will lead to a great change. So LX or LR is used as mutation section. For an individual, mutation position is selected randomly. If LX is selected, LX section of the individual is changed into a new random number with constraints. If LR is selected, LR section of the individual is changed into a new random number with constraints.


### 4.3. Calculation of Price Parameters

The carpooling states population is obtained based on the above methods. Next, the best price parameters would be found based on the population. Searching price parameters is a process of optimization considering multiple objectives. The searching best price parameters are carried out for each individual found in the carpooling states population. The method is designed based on genetic algorithm as follows.


#### 4.3.1. Generating Fronts

The size of the price parameters population isN2. Individual of price parameters is represented by (α,β). α and β are generated randomly from 0 to 1, satisfying β<α.All price parameters individuals are divided into several fronts. Specific distribution principles are as follows:(1)
Each individual has three goals based on formulation (19)-(21), that is, Z1, Z2, and Z3. If one goal of individual p is better than that of q at least, and all goal of individual p is not worse than that of q, individual p dominates q, or individual q is dominated by p.(2)
If individuali is not dominated by other individuals, the individual i belongs to the first front; if individual i is only dominated by individuals in the first front, the individual i belongs to the second front; if individual i is only dominated by individuals in the second front, the individual i belongs to the third front, and so on.Then each individual is assigned to one front. The first front is not dominated totally. The individuals of the frontW+1 are dominated by that of the front W. The individuals of the front W are better than that of the front W+1.


#### 4.3.2. Crowding Distance

Crowding distance is the distance between individuals of the same front, which describes crowding degree of individuals. The bigger crowding distance shows that the individuals are not crowded, and the diversity of the population is better. Crowding distance of individuali is denoted by DSi:(26)DSi=∑j∈W∑kZki-ZkjZkmax-Zkmin2where i and j are two individuals of the front W; that is, i,j∈W. Zki is the value of goal k of individual i. Zkmax is the maximum value of goal k of all individuals in the front W. Zkmin is the minimum value of goal k of all individuals in the front W. DSi reflects the sum of distances between individual i and individual else in the front W. If DSi>DSj, crowding degree of individual i is less than that of individual j. It means that DSi has priority over DSj while selecting individuals.


#### 4.3.3. Selection Operator

Similarly, tournament selection strategy is used to select individuals in price parameters population.m2 individuals are selected randomly from the population, and m2<N2. The selected individuals are sorted in order to find the best individual. The sorting process is carried out based on the following rules.i and j are individuals of the population. W1 and W2 are fronts generated.(1)
Ifi∈W1, j∈W2, and W1 is superior to W2, then individual i is better than individual j.(2)
Ifi,j∈W1 and i≠j, then crowding distance is compared further. If DSi>DSj, individual i is better than individual j.Each individual selected is distributed with a rank. The rank indicates the superior order of individuals. The smaller rank shows the better individual. Based on the above rules, if the frontW1 is superior to W2, the ranks of all individuals in front W1 are smaller than that of individuals in W2. The ranks of individuals in the same front depend on crowding distances of individuals. The bigger the crowding distance is, the smaller the rank is. The individual with the smallest rank is selected based on the above method. The individual selected is the best one in the population.The above process is carried outN2 times until N2 individuals are selected.


#### 4.3.4. Crossover Operator

Crossover operator between individualsi and j is carried out with probability pcpp. β of individual i and that of individual j are exchanged. Suppose βi is β section of individual i, and βj is β section of individual j. Crossover operator is βi↔βj.If individuali and individual j before crossover operator arei=(αi,βi)j=(αj,βj),individuali and individual j after crossover operator arei′=(αi,βj)j′=(αj,βi).It is necessary to check whether the new individuals satisfyβ<α constraint. If the constraint is not satisfied, exchange α and β.


#### 4.3.5. Mutation Operator

Mutation operator is carried out for individuals with probabilitypmpp. Mutation position will be selected randomly in α and β. If α is selected, α is regenerated randomly in the range from β to 1. If β is selected, β is regenerated randomly in the range from 0 to α.


## 4.1. Algorithm Procedure

The model proposed in the paper is a problem of multiobjective optimization. The purpose is to find the best price parametersα and β. They must be appropriate for all the possible carpooling. Carpooling is described using travel distances of the passengers, the position of getting on or getting off the taxi, and detour distance. The population composed of various types of carpooling is called carpooling states. Carpooling is an individual of carpooling states population. The price parameters would be obtained based on the carpooling states. Good price parameters depend on carpooling states with good diversity. So the algorithm process is divided into the following two parts: (1) searching carpooling states of diversity; (2) seeking the best price parameters for the carpooling states found in problem (1). The solutions are designed based on genetic algorithm. The exact process is shown in Figure 2. Firstly, the work of searching for carpooling states is carried out. The population of carpooling states with good diversity is found. Then, the work of seeking the best price parameters for each individual of the population obtained from above the process is carried out.Figure 2
The algorithm procedure.The detail algorithm process would be described as follows.


## 4.2. Searching Carpooling States

### 4.2.1. Generating Initial Population

An individual of carpooling states population is described as(LA,LX,LB,LR). For an individual, LA, LX, LB, and LR are random. Suppose travel distances of passengers are normal distribution, the mean value of which is μ and standard deviation is σ. LA and LB are created based on the normal distribution. In the process of data generation, the nonpositive values are not used. If a nonpositive value is obtained, regenerating the number until a positive value, LX is chosen equably in the range [0,LA]. LR is chosen equably in the range [LB-LA+LX,LB] to satisfy constraints. The size of carpooling states population is N1. N1 individuals are generated, which form a carpooling states population.


### 4.2.2. Evaluation of Carpooling States

Evaluation of each individual of carpooling states population depends on the closeness to other individuals. The closeness of individuali is the average value of the Euclidean space distances between individual i and other individual s. It is defined as (23)DWi=1N1-1∑j=1N1∑k=14x^ik-x^jk2(24)x^ik=xik-xkminxkmax-xkminxik is the value of attribute k of individual i. x^ik is the standardized value for xik. xkmax is the maximum value of attribute k in the population. xkmin is the minimum value of attribute k in the population. The bigger evaluation value shows that the individual is far away from other individuals, which will be kept.Diversity of the carpooling states populationt is measured by D(t).(25)Dt=N1N1-12∑i=1N1∑j=iN1∑k=14x^ik-x^jk2D(t) is the average value of the distances between all individuals in population t. The bigger D(t) is, the better the diversity of the population is.


### 4.2.3. Selection of Carpooling States

Good individuals are selected from the previous population. The selected individuals will form a new population, the size of which is the same as the previous population. Tournament selection strategy is used to select individuals in the paper. The method is as follows:( 1 )  m1 individuals are selected randomly from the population, and m1<N1.( 2 ) The evaluation values of the selected individuals are computed. The best individual will be selected according to the evaluation values.( 3 ) The above steps are repeated N1 times until N1 individuals are selected. The N1 individuals form a new population.


### 4.2.4. Crossover of Carpooling States

Crossover operator between two individuals is carried out with probabilitypccs. LB and LR of individuals are exchanged. Suppose LBi is LB section of individual i and LRi is LR section of individual i. Crossover operator between individual i and individual j is LAi↔LAj and LXi↔LXj.If individuali and individual j before crossover operator arei=(LAi,LXi,LBi,LRi)j=(LAj,LXj,LBj,LRj),individuali and individual j after crossover operator isi′=(LAj,LXj,LBi,LRi)j′=(LAi,LXi,LBj,LRj).It is necessary to check whether the new individuals satisfy with constraints. The processes of checking and adjustment are as follows: ifLA-LX>LB-LR is not satisfied, LR will be increased gradually with ranges up to LB until satisfying the constraint. If there is no appropriate LR found, LB and LR are both increased until satisfying the constraint.


### 4.2.5. Mutation of Carpooling States

Mutation operator is carried out for individuals with probabilitypmcs. LX and LR have an important influence on individuals. A little change of LX or LR will lead to a great change. So LX or LR is used as mutation section. For an individual, mutation position is selected randomly. If LX is selected, LX section of the individual is changed into a new random number with constraints. If LR is selected, LR section of the individual is changed into a new random number with constraints.


## 4.2.1. Generating Initial Population

An individual of carpooling states population is described as(LA,LX,LB,LR). For an individual, LA, LX, LB, and LR are random. Suppose travel distances of passengers are normal distribution, the mean value of which is μ and standard deviation is σ. LA and LB are created based on the normal distribution. In the process of data generation, the nonpositive values are not used. If a nonpositive value is obtained, regenerating the number until a positive value, LX is chosen equably in the range [0,LA]. LR is chosen equably in the range [LB-LA+LX,LB] to satisfy constraints. The size of carpooling states population is N1. N1 individuals are generated, which form a carpooling states population.


## 4.2.2. Evaluation of Carpooling States

Evaluation of each individual of carpooling states population depends on the closeness to other individuals. The closeness of individuali is the average value of the Euclidean space distances between individual i and other individual s. It is defined as (23)DWi=1N1-1∑j=1N1∑k=14x^ik-x^jk2(24)x^ik=xik-xkminxkmax-xkminxik is the value of attribute k of individual i. x^ik is the standardized value for xik. xkmax is the maximum value of attribute k in the population. xkmin is the minimum value of attribute k in the population. The bigger evaluation value shows that the individual is far away from other individuals, which will be kept.Diversity of the carpooling states populationt is measured by D(t).(25)Dt=N1N1-12∑i=1N1∑j=iN1∑k=14x^ik-x^jk2D(t) is the average value of the distances between all individuals in population t. The bigger D(t) is, the better the diversity of the population is.


## 4.2.3. Selection of Carpooling States

Good individuals are selected from the previous population. The selected individuals will form a new population, the size of which is the same as the previous population. Tournament selection strategy is used to select individuals in the paper. The method is as follows:( 1 )  m1 individuals are selected randomly from the population, and m1<N1.( 2 ) The evaluation values of the selected individuals are computed. The best individual will be selected according to the evaluation values.( 3 ) The above steps are repeated N1 times until N1 individuals are selected. The N1 individuals form a new population.


## 4.2.4. Crossover of Carpooling States

Crossover operator between two individuals is carried out with probabilitypccs. LB and LR of individuals are exchanged. Suppose LBi is LB section of individual i and LRi is LR section of individual i. Crossover operator between individual i and individual j is LAi↔LAj and LXi↔LXj.If individuali and individual j before crossover operator arei=(LAi,LXi,LBi,LRi)j=(LAj,LXj,LBj,LRj),individuali and individual j after crossover operator isi′=(LAj,LXj,LBi,LRi)j′=(LAi,LXi,LBj,LRj).It is necessary to check whether the new individuals satisfy with constraints. The processes of checking and adjustment are as follows: ifLA-LX>LB-LR is not satisfied, LR will be increased gradually with ranges up to LB until satisfying the constraint. If there is no appropriate LR found, LB and LR are both increased until satisfying the constraint.


## 4.2.5. Mutation of Carpooling States

Mutation operator is carried out for individuals with probabilitypmcs. LX and LR have an important influence on individuals. A little change of LX or LR will lead to a great change. So LX or LR is used as mutation section. For an individual, mutation position is selected randomly. If LX is selected, LX section of the individual is changed into a new random number with constraints. If LR is selected, LR section of the individual is changed into a new random number with constraints.


## 4.3. Calculation of Price Parameters

The carpooling states population is obtained based on the above methods. Next, the best price parameters would be found based on the population. Searching price parameters is a process of optimization considering multiple objectives. The searching best price parameters are carried out for each individual found in the carpooling states population. The method is designed based on genetic algorithm as follows.


### 4.3.1. Generating Fronts

The size of the price parameters population isN2. Individual of price parameters is represented by (α,β). α and β are generated randomly from 0 to 1, satisfying β<α.All price parameters individuals are divided into several fronts. Specific distribution principles are as follows:(1)
Each individual has three goals based on formulation (19)-(21), that is, Z1, Z2, and Z3. If one goal of individual p is better than that of q at least, and all goal of individual p is not worse than that of q, individual p dominates q, or individual q is dominated by p.(2)
If individuali is not dominated by other individuals, the individual i belongs to the first front; if individual i is only dominated by individuals in the first front, the individual i belongs to the second front; if individual i is only dominated by individuals in the second front, the individual i belongs to the third front, and so on.Then each individual is assigned to one front. The first front is not dominated totally. The individuals of the frontW+1 are dominated by that of the front W. The individuals of the front W are better than that of the front W+1.


### 4.3.2. Crowding Distance

Crowding distance is the distance between individuals of the same front, which describes crowding degree of individuals. The bigger crowding distance shows that the individuals are not crowded, and the diversity of the population is better. Crowding distance of individuali is denoted by DSi:(26)DSi=∑j∈W∑kZki-ZkjZkmax-Zkmin2where i and j are two individuals of the front W; that is, i,j∈W. Zki is the value of goal k of individual i. Zkmax is the maximum value of goal k of all individuals in the front W. Zkmin is the minimum value of goal k of all individuals in the front W. DSi reflects the sum of distances between individual i and individual else in the front W. If DSi>DSj, crowding degree of individual i is less than that of individual j. It means that DSi has priority over DSj while selecting individuals.


### 4.3.3. Selection Operator

Similarly, tournament selection strategy is used to select individuals in price parameters population.m2 individuals are selected randomly from the population, and m2<N2. The selected individuals are sorted in order to find the best individual. The sorting process is carried out based on the following rules.i and j are individuals of the population. W1 and W2 are fronts generated.(1)
Ifi∈W1, j∈W2, and W1 is superior to W2, then individual i is better than individual j.(2)
Ifi,j∈W1 and i≠j, then crowding distance is compared further. If DSi>DSj, individual i is better than individual j.Each individual selected is distributed with a rank. The rank indicates the superior order of individuals. The smaller rank shows the better individual. Based on the above rules, if the frontW1 is superior to W2, the ranks of all individuals in front W1 are smaller than that of individuals in W2. The ranks of individuals in the same front depend on crowding distances of individuals. The bigger the crowding distance is, the smaller the rank is. The individual with the smallest rank is selected based on the above method. The individual selected is the best one in the population.The above process is carried outN2 times until N2 individuals are selected.


### 4.3.4. Crossover Operator

Crossover operator between individualsi and j is carried out with probability pcpp. β of individual i and that of individual j are exchanged. Suppose βi is β section of individual i, and βj is β section of individual j. Crossover operator is βi↔βj.If individuali and individual j before crossover operator arei=(αi,βi)j=(αj,βj),individuali and individual j after crossover operator arei′=(αi,βj)j′=(αj,βi).It is necessary to check whether the new individuals satisfyβ<α constraint. If the constraint is not satisfied, exchange α and β.


### 4.3.5. Mutation Operator

Mutation operator is carried out for individuals with probabilitypmpp. Mutation position will be selected randomly in α and β. If α is selected, α is regenerated randomly in the range from β to 1. If β is selected, β is regenerated randomly in the range from 0 to α.


## 4.3.1. Generating Fronts

The size of the price parameters population isN2. Individual of price parameters is represented by (α,β). α and β are generated randomly from 0 to 1, satisfying β<α.All price parameters individuals are divided into several fronts. Specific distribution principles are as follows:(1)
Each individual has three goals based on formulation (19)-(21), that is, Z1, Z2, and Z3. If one goal of individual p is better than that of q at least, and all goal of individual p is not worse than that of q, individual p dominates q, or individual q is dominated by p.(2)
If individuali is not dominated by other individuals, the individual i belongs to the first front; if individual i is only dominated by individuals in the first front, the individual i belongs to the second front; if individual i is only dominated by individuals in the second front, the individual i belongs to the third front, and so on.Then each individual is assigned to one front. The first front is not dominated totally. The individuals of the frontW+1 are dominated by that of the front W. The individuals of the front W are better than that of the front W+1.


## 4.3.2. Crowding Distance

Crowding distance is the distance between individuals of the same front, which describes crowding degree of individuals. The bigger crowding distance shows that the individuals are not crowded, and the diversity of the population is better. Crowding distance of individuali is denoted by DSi:(26)DSi=∑j∈W∑kZki-ZkjZkmax-Zkmin2where i and j are two individuals of the front W; that is, i,j∈W. Zki is the value of goal k of individual i. Zkmax is the maximum value of goal k of all individuals in the front W. Zkmin is the minimum value of goal k of all individuals in the front W. DSi reflects the sum of distances between individual i and individual else in the front W. If DSi>DSj, crowding degree of individual i is less than that of individual j. It means that DSi has priority over DSj while selecting individuals.


## 4.3.3. Selection Operator

Similarly, tournament selection strategy is used to select individuals in price parameters population.m2 individuals are selected randomly from the population, and m2<N2. The selected individuals are sorted in order to find the best individual. The sorting process is carried out based on the following rules.i and j are individuals of the population. W1 and W2 are fronts generated.(1)
Ifi∈W1, j∈W2, and W1 is superior to W2, then individual i is better than individual j.(2)
Ifi,j∈W1 and i≠j, then crowding distance is compared further. If DSi>DSj, individual i is better than individual j.Each individual selected is distributed with a rank. The rank indicates the superior order of individuals. The smaller rank shows the better individual. Based on the above rules, if the frontW1 is superior to W2, the ranks of all individuals in front W1 are smaller than that of individuals in W2. The ranks of individuals in the same front depend on crowding distances of individuals. The bigger the crowding distance is, the smaller the rank is. The individual with the smallest rank is selected based on the above method. The individual selected is the best one in the population.The above process is carried outN2 times until N2 individuals are selected.


## 4.3.4. Crossover Operator

Crossover operator between individualsi and j is carried out with probability pcpp. β of individual i and that of individual j are exchanged. Suppose βi is β section of individual i, and βj is β section of individual j. Crossover operator is βi↔βj.If individuali and individual j before crossover operator arei=(αi,βi)j=(αj,βj),individuali and individual j after crossover operator arei′=(αi,βj)j′=(αj,βi).It is necessary to check whether the new individuals satisfyβ<α constraint. If the constraint is not satisfied, exchange α and β.


## 4.3.5. Mutation Operator

Mutation operator is carried out for individuals with probabilitypmpp. Mutation position will be selected randomly in α and β. If α is selected, α is regenerated randomly in the range from β to 1. If β is selected, β is regenerated randomly in the range from 0 to α.


## 5. Example Analysis

Take Lanzhou city in China, for example, taxi charging standard stipulates that initiate fee is 10¥/3km, 1.4¥ per kilometer more than 3 kilometers. It costs 8 cubic meters gas consumption per 100 km. Gas price is 3.10¥ per cubic meter. The travel distances of passengers are normal distributionL~N(16,52). Under these conditions, the problem of detour carpooling is analyzed based on the method proposed in this paper.Parameters of the algorithm are set as follows: population sizeN1=N2=100, crossover probability pccs=pcpp=0.5, mutation probability pmcs=0.2, pmpp=0.1, and the number of individuals selected by tournament selection strategy m1=m2=50.The evolution of diversity of the carpooling states population is shown as Figure3. The diversity of the carpooling states population increases gradually until it arrives at stabilization. The final carpooling states population obtained can represent the possible carpooling space with good diversity.Figure 3
The diversity evolution of the carpooling states population.The final carpooling states population containing 100 individuals are obtained. The partial results are shown in Table1.Table 1
The partial results of carpooling states population.
L A L X L B L R 15.81 6.92 7.66 5.62 14.2 3.47 6.29 3.33 6.72 0.98 10.17 6.97 7.16 5.06 9.63 8.61 24.17 19.7 12.17 8.79 15.07 2.8 13.46 3.02 14.3 12.37 19.64 18.84 10.2 4.87 21.17 19.2 11.64 8.94 10.2 7.87 13.76 8.97 19.79 16.26 8.38 0.13 8.69 1.66 21.07 15.39 19.42 19.21 19.68 11.87 15.48 9.19 16.07 12.23 17.71 14.38 22.82 12.3 26.23 23.41 9.08 3.48 10 6.75 4.04 3.61 9.44 9.03 20.85 9.41 19.54 16.08 …… …… …… ……The work of seeking price parameters is carried out for each individual of the carpooling states population. One of the evolutionary process is given. The average profit of passengerA of each population generation is shown as Figure 4. The profit describes the cost difference between noncarpooling and detour carpooling. The value finally converges to 2 CNY, which means that the average cost of the passenger who does not make a detour saves 2 CNY each time compared with taking a taxi alone.Figure 4
The evolution of passengerA’s average profit.The average profit of passengerB of each population generation is shown as Figure 5. The value finally converges to 5 CNY, which means that the average cost of the passenger who makes a detour saves 5 CNY each time relative to taking a taxi alone. The detour passenger gets more profitable than the nondetour passenger does.Figure 5
The evolution of passengerB’s average profit.The average profit per kilometer of the driver of each population generation is shown as Figure6. The value finally converges to about 0.2 CNY, which means that the average income per kilometer increases 0.2 CNY compared with carrying a single passenger.Figure 6
The evolution of the driver’s average profit per kilometer.Based on the results of price parameters of carpooling states, the valueα is shown as Figure 7. The average value of α is 0.82. α changes around 0.82. That is, the payment ratio of nondetour passenger is 0.82, which is reasonable. It can ensure the realization of carpooling detour.Figure 7
The valueα of carpooling states.The valueβ is shown as Figure 8. The value β ranges from 0.6 to 0.8. Discount coefficient of passenger B is smaller than that of passenger A due to time delay detour caused. The value β should be in the range from 0.6 to 0.8 to ensure the realization of carpooling detour.Figure 8
The valueβ of carpooling states.The relation betweenLD/LB and β is shown in Figure 9. β decreases with the increase of LD/LB. It can be seen from the scatter plot that there is an obvious linear relationship between LD/LB and β.Figure 9
The relation betweenLD/LB and β.The regression equation is obtained by regression analysis.(27)β=-0.1881LDLB+0.8044In the regression equation, regression coefficient is -0.1874, and intercept is 0.8039. The significance test of the regression equation is performed. The model has a significant linear relationship, and fitting degree is 0.964. If the passenger does not make a detour, that is, LD/LB=0, payment ratio of the passenger is β=0.8, which is consistent with the above analysis results. Therefore, it is easy to determine discount coefficient β based on LD/LB.In all individuals of the final carpooling states population, the maximum value ofLD/LB is 0.6. So the maximum ratio of detour distance to travel distance θLD/LB is 0.6. It shows that the passengers and the driver can get benefits simultaneously by the mode of carpooling detour when the ratio of detour distance to travel distance is within 0.6. It becomes possible to take the mode of carpooling detour under the condition.Based on the above analysis, we can set payment ratioα to 0.82, calculate detour payment ratio β according to the regression expression obtained, and limit the maximum ratio of detour distance to travel distance to 0.6. Only in this way can carpooling with detour be successful.


## 6. Conclusions

The paper establishes the multiobjective optimization model of taxi carpooling detour, designs a solution algorithm, and proposes a method of formulating price scheme to ensure benefits of passengers and driver, which can enable carpooling detour the smooth implementation.The following conclusions are obtained:( 1 ) It is feasible to take a taxi by the mode of carpooling detour. Benefits of passengers and driver can be protected simultaneously. Costs of non-detour and detour passengers are reduced, and the incomes of the drivers are increased.( 2 ) It is the key to determining appropriate payment ratio α and detour payment ratio β. The detour passenger can get more discount than the non-detour passenger can. The payment ratio α is a fixed value. The detour payment ratio β changes dynamically, and increases as the ratio of detour distance to travel distance decreases.( 3 ) The ratio of detour distance to travel distance has an important influence on carpooling detour. The ratio should be limited to less than certain values to protect the interests of passengers and drivers under the condition of carpooling detour. If the ratio exceeds the limit value, it is difficult to find appropriate payment ratio and detour payment ratio.( 4 ) The parameters, such as the payment ratio, the detour payment ratio, and the maximum value of the ratio of detour distance to travel distance, can be obtained by the method proposed in this paper in a real environment.The above conclusions and the proposed method has a certain guiding significance to formulate taxi carpooling policy.



---

*Source: 3867874-2019-04-14.xml*