Passenger-Vehicle Matching Method for Online Ride-sharing service

Abstract

Provided in the present invention is a passenger-vehicle matching method for an online ride sharing. In the present invention, firstly, matching is performed on passengers by using an integer linear programming algorithm, so as to form a passenger combination scheme involving the optimal total travel time of the passengers; and secondly, in the present invention, virtual passenger combinations or virtual vehicles are supplemented, such that the number of passenger combinations is the same as the number of vehicles, and the passenger combinations are matched with the vehicles by using the integer linear programming algorithm again, so as to obtain a passenger-vehicle matching scheme involving the optimal total travel time. The present invention optimizes the passenger-vehicle matching process in online ride-hailing shared travel, enhancing user experience and efficiency, while also promoting a green traffic mode that significantly reduces urban traffic pressure and pollution.

Claims

1. A computer-implemented passenger matching method for on line ride-sharing service, wherein the method comprises the following steps that: 1) receiving, via an App and a communication network, pooling demands of on-line contract shared travel information by users; assigning users into a plurality of user sets at a system cloud end server, and pre-processing information about each user set to form a data file which is sent to the App of the users in the set; 2) after receiving a data file, calculating a shortest passenger travel time and travel path in App, and sending a result to the system cloud end server; receiving the result to solve a 0-1 programming model of a passenger combination matching process by the system cloud end server, and screening to obtain a passenger combination matching scheme; 3) matching a passenger combination with a driver, and constructing a generalized driver set and a generalized passenger combination set, determining a 0-1 programming model of a driver-passenger combination matching process, and screening to obtain a driver-passenger combination matching scheme; and 4) sending the driver-passenger matching scheme to the App of the driver and the users, executing the matching scheme, and completing the on-line ride-sharing service shared travel.

2. The computer-implemented passenger matching method for on line ride-sharing service according to claim 1, wherein in step 1), the travel information comprises a start point, an end server point and the pooling demand, and each user set is pre-processed, and the system cloud end server forms information about the start point and the end server point in the user set into the data file which is sent to a smart phone App of the users in the set.

3. The computer-implemented passenger matching method for on line ride-sharing service according to claim 1, wherein in step 2), the pooling demand is two-person pooling demand and three-person pooling demand.

4. The computer-implemented passenger matching method for on line ride-sharing service according to claim 3, wherein the specific method in step 1) is as follows that: the user i issues, via App, on-line contract shared travel information, comprising a travel start point O.sub.i, a travel end server point D.sub.i and the pooling demand N.sub.i, wherein a vehicle in a system is a five-seat automobile, and the automobile meets the pooling demand of the two-person pooling and the three-person pooling; according to the users' pooling demand, the system cloud end server divides the users into two sets: RP.sub.A2 and RP.sub.A3, the pooling demand of the users in the set RP.sub.A2 being the two-person pooling, namely N.sub.i=2, a quantity of users being |RP.sub.A2|, while the pooling demand of the users in the set RP.sub.A3 being the three-person pooling, namely N.sub.i=3, a quantity of users being |RP.sub.A3|; taking the quantities |RP.sub.A2| and |RP.sub.A3| of the users in the set as a dividend, taking the pooling demands N.sub.i=2 and N.sub.i=3 of the users in the set as a divisor, a remainder operation is performed to obtain remainders |RP.sub.B2| and |RP.sub.B3|, namely: $.Math.{\mathrm{RP}}_{B2}.Math.=.Math.{\mathrm{RP}}_{A2}.Math.\mathrm{\%2}$ $.Math.{\mathrm{RP}}_{B3}.Math.=.Math.{\mathrm{RP}}_{A3}.Math.\mathrm{\%3}$ where % represents a remainder symbol; the system pre-processes the sets RP.sub.A2 and RP.sub.A3 as follows by: for the two-person pooling set RP.sub.A2: randomly selecting |RP.sub.B2| of the users in the set RP.sub.A2, wherein selected users constitute a set RP.sub.B2 referred to as a secondary user set 2; and unselected users constitute a set RP.sub.2 referred to as a main user set 2; and RP.sub.42=RP.sub.B2RP.sub.2, where if the remainder is |RP.sub.B2|=0, then RP.sub.B2=, and there is a set relationship of RP.sub.A2=RP.sub.2; for the three-person pooling set RP.sub.A3: randomly selecting |RP.sub.B3| of the users in the set RP.sub.A3, wherein selected users constitute a set RP.sub.B3 referred to as a secondary user set 3; and unselected users constitute a set RP.sub.3 referred to as a main user set 3; and RP.sub.A3=RP.sub.B3RP.sub.3, where if the remainder is |RP.sub.R3|=0, then RP.sub.B3=, and there is a set relationship of RP.sub.A3=RP.sub.3; and after receiving the on-line contract shared travel information about the user and completing user set classification and pre-processing, the cloud end server respectively aggregates the travel start points and the travel end server points of the users in the sets RP.sub.2 and RP.sub.3, and extracts travel times between all nodes to form two data files: File2 and File3, and the cloud end server sends the data file File2 to all the users in the set RP.sub.2, and sends the data file File3 to all the users in the set RP.sub.3.

5. The computer-implemented passenger matching method for on line ride-sharing service according to claim 4, wherein in the step 2), a process of matching a passenger combination within the user set RP.sub.A2 with a two-person pooling demand is such that: 1) the user in RP.sub.2 calculates a shortest passenger travel time and travel path of all possible two-person passenger combinations with himself as a first passenger, and returns a calculation result to the system cloud end server; after the user of the user iRP.sub.2 receives the data file File2 sent by the system cloud end server, the smart phone of the user takes the user i as the first passenger to calculate the shortest travel path and travel time of the two-person passenger combination formed by the user i and any other user jRP.sub.2\{i}, and returns a calculation result to the system cloud end server, and the calculation formula is as follows: $P_{\mathrm{ij}}=\left\{O_i.fwdarw.O_j.fwdarw.D_i.fwdarw.D_j,O_i.fwdarw.O_j.fwdarw.D_j.fwdarw.D_i\right\}$ $r_{\mathrm{ij}}=\min \left\{t\left(O_i,O_j\right)+t\left(O_j,D_i\right)+t\left(D_i,D_j\right),t\left(O_i,O_j\right)+t\left(O_j,D_j\right)+t\left(D_j,D_i\right)\right\}$ as stated above, taking the user i as the first passenger means taking the start point O.sub.i of the user i as a jumping-off place, so that the user d is the passenger gets aboard at first, and the driver needs to firstly receive the user i and j as the two passengers, and then send them to destinations respectively; in the formula, in both O.sub.i.fwdarw.O.sub.j.fwdarw.D.sub.i.fwdarw.D.sub.j and O.sub.i.fwdarw.O.sub.j.fwdarw.D.sub.j.fwdarw.D.sub.i, paths are represented by nodes which are passed through successively, and all possible travel paths of the two-person passenger combination {i, j} are taken when the user i is the first passenger, and P.sub.ij represents a travel path set of the two-person passenger combination {i, j} when the user is the first passenger, and t(O.sub.i, O.sub.j), t(O.sub.j, D.sub.i), t(D.sub.i, D.sub.i), t(O.sub.j, D.sub.j), and t(D.sub.i, D.sub.j) all represent travel time between two nodes in parentheses; t(O.sub.i, O.sub.j)+t(O.sub.j, D.sub.i)+t(D.sub.i, D.sub.j) and t(O.sub.i, O.sub.j)+t(O.sub.j, D.sub.i)+t(D.sub.j, D.sub.i) both represent possible travel time of the two-person passenger combination {i, j} when the user i is the first passenger, and r.sub.ij represents a shortest passenger travel time of the two-person passenger combination {i, j} when the user i is the first passenger; 2) the system cloud end server compares the shortest passenger travel times when different users in respective two-person passenger combinations serve as the first passenger, and determines the shortest passenger travel time and travel path of each two-person passenger combination; within the two-person passenger combination {i, j}, a sum of the shortest passenger travel times r.sub.ij and r.sub.ji with the user i and the user i as the first passenger are compared with each other, the shortest passenger travel time r.sub.ij of the two-person passenger combination is determined, and a travel path corresponding to r.sub.ij is recorded, wherein the formula is as follows: $r_{\stackrel{\_}{\mathrm{ij}}}=\min \left\{r_{\mathrm{ij}},r_{\mathrm{ji}}\right\}$ 3) the users within RP.sub.B2 are formed into a passenger combination RP.sub.C2, and the shortest passenger travel time r.sub.C2 and travel path of the passenger combination are calculated; under the two-person pooling demand of the user, if |RP.sub.B2|0, then |RP.sub.B2|=1, namely there is only one user in the secondary user set 2 RP.sub.B2, and the user is set as mRP.sub.B2; the one user in the RP.sub.B2 is formed into a passenger combination represented by RP.sub.C2, referred to as secondary passenger combination 2, there is RP.sub.C2={m}, the shortest passenger travel time r.sub.C2=t(O.sub.m, D.sub.m) of the secondary passenger combination 2 RP.sub.C2, and the corresponding travel path is O.sub.m.fwdarw.D.sub.m, and {RP.sub.C2} represents a passenger combination set having only one element RP.sub.C2; 4) a matching problem of the two-person passenger combination is solved, and a two-person pooling passenger matching scheme with an optimal total passenger travel time is obtained; for any user iRP.sub.2, he can only form a two-person passenger combination with another user jRP.sub.2\{i} ultimately, with a goal of minimizing the total passenger travel time, while under the user's two-person pooling demand, the matching problem of the two-person passenger combination is transformed into a 0-1 programming model as follows: $\min \underset{i=1}{\overset{.Math.{\mathrm{RP}}_2.Math.}{.Math.}}\underset{j=1}{\overset{.Math.{\mathrm{RP}}_2.Math.}{.Math.}}{r}_{\stackrel{\_}{\mathrm{ij}}}{x}_{\mathrm{ij}}$ $s.t.\{\begin{array}{c}\underset{i=1}{\overset{.Math.{\mathrm{RP}}_2.Math.}{.Math.}}{x}_{\mathrm{ij}}=1,j{\mathrm{RP}}_2\\ \underset{j=1}{\overset{.Math.{\mathrm{RP}}_2.Math.}{.Math.}}{x}_{\mathrm{ij}}=1,i{\mathrm{RP}}_2\\ x_{\mathrm{ij}}=0\mathrm{or}1,i,j{\mathrm{RP}}_2\end{array}$ where x.sub.ij is a 0-1 variable: in a solution result of the model, if the user i and the user j constitute a two-person passenger combination {i, j}, then x.sub.ij=1, otherwise x.sub.ij=0; furthermore, there is no constraint in the 0-1 programming model ij, and the shortest passenger travel time r.sub.ij for repeating the two-person passenger combination {i, i} is set as follows: $r_{\stackrel{\_}{\mathrm{ii}}}-=\mathrm{Inf},i{\mathrm{RP}}_2$ where Inf represents a positive infinite constant; Hungarian algorithm is used to solve the 0-1 programming model, and an obtained solution vector is x=(x.sub.ij, iRP.sub.2, jRP.sub.2).sup.T, the two-person passenger combination corresponding to x.sub.ij=1 is screened out, the passenger combination set RP.sub.2_2 is formed, which is referred to as the main passenger combination set 2, a quantity of set elements of which is |RP.sub.2_2=|RP.sub.2|/2; and a set RC.sub.2=RP.sub.2_2{RP.sub.C2} is allowed to represent the passenger combination set formed by the users with the two-person pooling demand, i.e. a union set of RP.sub.2_2 and {RP.sub.C2}, the travel path and travel time of each passenger combination in the set RC.sub.2 are recorded, and a quantity |RC.sub.2| of set elements represents a quantity of the passenger combinations under the two-person pooling demand.

6. The computer-implemented passenger matching method for on line ride-sharing service according to claim 4, wherein in the step 2), a process of matching a passenger combination within the user set RP.sub.A3 with a three-person pooling demand is such that: 1) the system cloud end server pre-supplements a certain quantity of virtual users on the basis of RP.sub.3 to form a generalized user set RP.sub.E3, wherein the user in RP.sub.3 calculates the shortest passenger travel time and travel path of all possible two-person passenger combinations with himself as the first passenger, and returns a calculation result to the system cloud end server; a quantity |RP.sub.3|/3 of virtual users are pre-supplemented before passenger combination matching under the three-person pooling demand of the user, and the travel start points O.sub.i and the travel end server points D.sub.i of the virtual users are all virtual nodes; the virtual node does not exist in a real urban road network, and the distance to any real node is positively infinite, |RP.sub.3|/3 virtual users constitute a virtual user set RP.sub.V3, and a union set of the virtual user set RP.sub.V3 and RP.sub.3 is the generalized user set RP.sub.E3, namely RP.sub.E3=RP.sub.3RP.sub.V3, Inf representing a positive infinite constant; after the smart phone of the user iRP.sub.3 receives the data file File3 sent by the cloud end server, the smart phone of the user i takes the user i as the first passenger to calculate the shortest travel path and travel time of the two-person passenger combination formed by the user i and any other user jRP.sub.3 \{i}, and returns a calculation result to the system cloud end server, and the calculation formula is as follows: $P_{\mathrm{ij}}=\left\{O_i.fwdarw.O_j.fwdarw.D_i.fwdarw.D_j,O_i.fwdarw.O_j.fwdarw.D_j.fwdarw.D_i\right\}$ $r_{\mathrm{ij}}=\min \left\{t\left(O_i,O_j\right)+t\left(O_j,D_i\right)+t\left(D_i,D_j\right),t\left(O_i,O_j\right)+t\left(O_j,D_j\right)+t\left(D_j,D_i\right)\right\}$ as stated above, taking the user i as the first passenger, i.e. taking the start point O.sub.i of the user i as a jumping-off place, so that the user i is the passenger gets aboard at first, the driver firstly receives the users i and j as the two passengers, and then send them to destinations respectively; in the formula, in both O.sub.i.fwdarw.O.sub.j.fwdarw.D.sub.i.fwdarw.D.sub.j and O.sub.i.fwdarw.O.sub.j.fwdarw.D.sub.j.fwdarw.D.sub.i, paths are represented by nodes which are passed through successively, and all possible travel paths of the two-person passenger combination {i, j} are taken when the user i is the first passenger, and P.sub.ij represents a travel path set of the two-person passenger combination {i, j} when the user i is the first passenger, and t(O.sub.i, O.sub.j), t(O.sub.j, D.sub.i), t(D.sub.i, D.sub.j), t(O.sub.j, D.sub.j), and t(D.sub.i, D.sub.j) all represent travel time between two nodes in parentheses, t(O.sub.i, O.sub.j)+t(O.sub.j, D.sub.i)+t(D.sub.i, D.sub.j) and t(O.sub.i, O.sub.j)+t(O.sub.j, D.sub.i)+t(D.sub.j, D.sub.i) both represent possible travel time of the two-person passenger combination {i, j} when the user i is the first passenger, and r.sub.ij represents a shortest passenger travel time of the two-person passenger combination {i, j} when the user i is the first passenger; 2) the system cloud end server compares the shortest passenger travel times when different users in respective two-person passenger combinations serve as the first passenger, and determines the shortest passenger travel time and travel path of each two-person passenger combination; within the two-person passenger combination {i, j}, a sum of the shortest passenger travel times r.sub.ij and r.sub.ji with the user i and the user j as the first passenger are compared with each other, the shortest passenger travel time r.sub.ij of the two-person passenger combination is determined, and a travel path corresponding to r.sub.ij is recorded, wherein the formula is as follows: $r_{\stackrel{\_}{\mathrm{ij}}}=\min \left\{r_{\mathrm{ij}},r_{\mathrm{ji}}\right\}$ 3) all the users within secondary user set 3 RP.sub.B3 are formed into a passenger combination RP.sub.C3, and the shortest passenger travel time r.sub.C3 and travel path of the passenger combination are calculated; if |RP.sub.B3|0 under the user's three-person pooling demand, then |RP.sub.B3|=1 or |RP.sub.B3|=2, namely, there are 1 or 2 users in the secondary user set RP.sub.B3, all the users in the set RP.sub.B3 are formed into a passenger combination represented by RP.sub.C3, referred to as secondary passenger combination 3, and r.sub.C3 is allowed to represent the shortest passenger travel time of the passenger combination RP.sub.C3, and {RP.sub.C3} is allowed to represent a passenger combination set comprising only one element of the passenger combination RP.sub.C3, referred to as secondary passenger combination set 3; if there is one user in the set RP.sub.B3, the user is set to be mRP.sub.B3, then the secondary passenger combination 3 RP.sub.C3={m}, the shortest passenger travel time r.sub.C3=t(O.sub.m, D.sub.m) of RP.sub.C3 and a corresponding travel path is O.sub.m.fwdarw.D.sub.m; if there are two users in the set RP.sub.B3, represented as m.sub.1, m.sub.2RP.sub.B3, then secondary passenger combination 3 RP.sub.C3={m.sub.1, m.sub.2} is a two-person passenger combination, and the shortest passenger travel time r.sub.C3 of RP.sub.C3 is the shortest passenger travel time of the two-person passenger combination {m.sub.1, m.sub.2} and for it is also necessary to first respectively calculate the shortest passenger travel times r.sub.m.sub.1.sub.m.sub.2 and r.sub.m.sub.1.sub.m.sub.2 with m.sub.1 and m.sub.2 as the first passenger, and then make comparison to obtain the shortest passenger travel time of the two-person passenger combination {m.sub.1, m.sub.2}, and a travel path corresponding to is recorded; 4) to solve a first passenger combination matching problem under the three-person pooling demand of the user, |RP.sub.B3|/2 generalized two-person passenger combinations is matched in the generalized user set RP.sub.E3, and then real users in |RP.sub.3|/2 real two-person passenger combinations and |RP.sub.3|/2 mixed two-person passenger combinations are selected from the generalized two-person passenger combinations; real users and virtual users are collectively referred to as generalized users; if the passengers i and j in the two-person passenger combination {i, j} are both real users, then {i, j} is taken as the real two-person passenger combination; if the passenger i in the two-person passenger combination {i, j} is a real user and the passenger i is a virtual user, or if the passenger i is a virtual user and the passenger j is a real user, then {i, j} is taken as the mixed two-person passenger combination; if the passengers i and j in the two-person passenger combination {i, j} are both virtual users, then {i, j} is taken as a virtual two-person passenger combination, while the real two-person passenger combination, the mixed two-person passenger combination and the virtual two-person passenger combination are collectively referred to as the generalized two-person passenger combination; in the first passenger combination matching process under the three-person pooling demand of the user, |RP.sub.E3|/2 generalized two-person passenger combinations are matched in the generalized user set RP.sub.E3, and for any generalized user iRP.sub.E3, the generalized two-person passenger combination can only be formed by him with another generalized user jRP.sub.E3 \{i}, and aiming at minimizing the total passenger travel time, the matching problem of the generalized two-person passenger combination can be transformed into a 0-1 programming model as follows: $\min \stackrel{.Math.{\mathrm{RP}}_{E3}.Math.}{\underset{i=1}{.Math.}}\underset{j=1}{\overset{.Math.{\mathrm{RP}}_{E3}.Math.}{.Math.}}{r}_{\stackrel{}{\mathrm{ij}}}{x}_{\mathrm{ij}}$ $s.t.\{\begin{array}{c}\underset{i=1}{\overset{.Math.{\mathrm{RP}}_{E3}.Math.}{.Math.}}{x}_{\mathrm{ij}}=1,j{\mathrm{RP}}_{E3}\\ \underset{j=1}{\overset{.Math.{\mathrm{RP}}_{E3}.Math.}{.Math.}}{x}_{\mathrm{ij}}=1,i{\mathrm{RP}}_{E3}\\ x_{\mathrm{ij}}=0\mathrm{or}1,i,j{\mathrm{RP}}_{E3}\end{array}$ where x.sub.ij is a variable from 0 to 1; in a model solution result, if the generalized user i and the generalized user j constitute the generalized two-person passenger combination {i, j}, then x.sub.ij=1, otherwise x.sub.ij=0; since there is no constraint ij in the 0-1 programming model, the 0-1 programming model not only has the repeated two-person passenger combination {i, i} and the related parameter r.sub.ii and variable x.sub.ii, but also has the virtual user and the mixed two-person passenger combination and the virtual two-person passenger combination which may be formed; in order to match the real two-person passenger combination as much as possible, and at the same time enable the 0-1 programming model to solve the first passenger matching process of three-person pooling, Inf is allowed to represent a positive infinite constant, and the shortest passenger travel time of any generalized two-person passenger combination {i, j} is set as follows: if iRP.sub.3, jRP.sub.3 and ij, it is the real two-person passenger combination, and the shortest passenger travel time thereof is r.sub.ij; if iRP.sub.3, jRP.sub.V3 or jRP.sub.3, iRP.sub.V3, it is the mixed two-person passenger combination, and the shortest passenger travel time thereof is Inf; if iRP.sub.V3, jRP.sub.V3 and ij, it is the virtual two-person passenger combination, and the shortest passenger travel time thereof is 2*Inf; for the repeated two-person passenger combination {i, i}, the shortest passenger time r.sub.ii thereof is set as 2*Inf; the Hungarian algorithm is applied to solve the 0-1 programming model, and the solved vector is x=(x.sub.ij, iRP.sub.E3, jRP.sub.E3).sup.T, 2*(|RP.sub.3|/3) generalized two-person passenger combinations corresponding to x.sub.ij=1 are screened out, wherein there are |RP.sub.3|/3 real two-person passenger combinations and |RP.sub.3|/3 mixed two-person passenger combinations; |RP.sub.3|/3 real two-person passenger combinations are screened out to construct the real two-person passenger combination set RP.sub.3_2 and the quantity of set elements is |RP.sub.3_2=|RP.sub.3|/3; then the real users in |RP.sub.3|/3 mixed two-person passenger combinations are screened out to construct the user set RP.sub.3_1 and the quantity of set elements is |RP.sub.3_1|=|RP.sub.3|/3; after the system cloud end server completes the first passenger combination matching of the three-person pooling, the start points and the end server points of two users of each real two-person passenger combination in the real two-person passenger combination set RP.sub.3_2 are extracted to form a data file File3_2; start points and end server points of each user in the user set RP.sub.3_1 are extracted to form a data file File3_1; after forming the data files, the system cloud sends the data files File3_1 and File3_2 to all the smart phones of the users in RP.sub.3 again; 5) the user in RP.sub.3 calculates a shortest passenger travel time and travel path of all possible three-person passenger combinations with himself as a first passenger, and returns a calculation result to the system cloud end server; the real two-person passenger combination set RP.sub.3_2 and the user set RP.sub.3_1 are obtained in the first passenger combination matching process of the three-person pooling, so that the real two-person passenger combination {i, j}RP.sub.3_2 and the real user kRP.sub.3_1, then the user i, the user j and the user k constitute a three-person passenger combination {i, j, k}; a step of calculating the shortest passenger travel time of the three-person passenger combination {i, j, k} is as follows; smart phones of the user i, j{i, j}, {i, j}RP.sub.3_2 and the user kRP.sub.3_1 receive the data files File3_1 and File3_2 sent by the cloud end server; after receiving the files File3_1 and File3_2, the smart phone of the user i takes the user i as the first passenger to calculate the shortest travel path and travel time of the three-person passenger combination formed by the user i, the user j and the user k, and returns a calculation result to the system cloud end server, and the calculation formula is as follows: $P_{\mathrm{ijk}}=\left\{\begin{array}{c}{O}_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_i.fwdarw.D_j.fwdarw.D_k,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_i.fwdarw.D_j.fwdarw.D_k,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_i.fwdarw.D_k.fwdarw.D_j,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_i.fwdarw.D_k.fwdarw.D_j,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_j.fwdarw.D_i.fwdarw.D_k,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_j.fwdarw.D_i.fwdarw.D_k,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_j.fwdarw.D_k.fwdarw.D_i,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_j.fwdarw.D_k.fwdarw.D_i,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_k.fwdarw.D_i.fwdarw.D_j,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_k.fwdarw.D_i.fwdarw.D_j,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_k.fwdarw.D_j.fwdarw.D_i,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_k.fwdarw.D_j.fwdarw.D_i\end{array}\right\}$ $r_{\mathrm{ijk}}=\min \left\{\begin{array}{c}t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_i\right)+t\left(D_i,D_j\right)+t\left(D_j,D_k\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_i\right)+t\left(D_i,D_j\right)+t\left(D_j,D_k\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_i\right)+t\left(D_i,D_k\right)+t\left(D_k,D_j\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_i\right)+t\left(D_i,D_k\right)+t\left(D_k,D_j\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_j\right)+t\left(D_j,D_i\right)+t\left(D_i,D_k\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_j\right)+t\left(D_j,D_i\right)+t\left(D_i,D_k\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_j\right)+t\left(D_j,D_k\right)+t\left(D_k,D_i\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_j\right)+t\left(D_j,D_k\right)+t\left(D_k,D_i\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_k\right)+t\left(D_k,D_i\right)+t\left(D_i,D_j\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_k\right)+t\left(D_k,D_i\right)+t\left(D_i,D_j\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_k\right)+t\left(D_k,D_j\right)+t\left(D_j,D_i\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_k\right)+t\left(D_k,D_j\right)+t\left(D_j,D_i\right)\end{array}\right\}$ as stated above, in order to achieve the three-person pooling demand of the user, the driver first picks up the three passengers and then sends them to destinations respectively, where P.sub.ijk represents a travel path set of the three-person passenger combination {i, j, k} when the user i is the first passenger, wherein the elements O.sub.j.fwdarw.O.sub.i.fwdarw.O.sub.k.fwdarw.D.sub.i.fwdarw.D.sub.j.fwdarw.D.sub.k are all paths, which are represented by nodes that are passed through successively, and r.sub.ijk represent the shortest passenger travel time of the three-person passenger combination {i, j, k} when the user i is the first passenger, while the elements t(O.sub.k, O.sub.j)+t(O.sub.j, O.sub.i)+t(O.sub.i, D.sub.i)+t(D.sub.i, D.sub.j)+t(D.sub.j, D.sub.k) all represent possible travel times of the three-person passenger combination {i, j, k}; 6) the system cloud end server compares the shortest passenger travel times when different users in respective three-person passenger combinations serve as the first passenger, and determines the shortest passenger travel time and travel path of each three-person passenger combination; within the three-person passenger combination {i, j, k}, the system compares the shortest passenger travel times r.sub.ijk, r.sub.jik, and r.sub.kij with the user i, the user j and the user k as the first passenger, determines the shortest passenger travel time r.sub.ijk of the three-person passenger combination, and records a travel path corresponding to r.sub.ijk and the formula is as follows: $r_{\stackrel{\_}{\mathrm{ijk}}}=\min \left\{r_{\mathrm{ijk}},r_{\mathrm{jik}},r_{\mathrm{kij}}\right\}$ 7) a second passenger combination matching problem of three-person pooling is solved, and a three-person pooling passenger matching scheme with an optimal passenger travel time is obtained; for any two-person passenger combination {i, j}RP.sub.3_2, it can only form a three-person passenger combination with another user kRP.sub.3_1 ultimately, with a goal of minimizing the total passenger travel time, while under the user's three-person pooling demand, the matching problem of the two-person passenger combination can be transformed into a 0-1 programming model as follows: $\min \underset{\left\{i,j\right\}}{.Math.}\underset{k}{.Math.}{r}_{\stackrel{\_}{\mathrm{ijk}}}{x}_{\mathrm{ijk}}$ $s.t.\{\begin{array}{c}\underset{\left\{i,j\right\}}{.Math.}{x}_{\mathrm{ijk}}=1,k{\mathrm{RP}}_{3\_1}\\ \underset{k}{.Math.}{x}_{\mathrm{ijk}}=1,\left\{i,j\right\}{\mathrm{RP}}_{3\_2}\\ x_{\mathrm{ijk}}=0\mathrm{or}1,\left\{i,j\right\}{\mathrm{RP}}_{3\_2},k{\mathrm{RP}}_{3\_1}\end{array}$ where x.sub.ijk is a variable from 0 to 1; in a solution result of the model, if the two-person passenger combination {i, j} and the user k constitute the three-person passenger combination {i, j, k}, then x.sub.ijk=1, otherwise x.sub.ijk=0; Hungarian algorithm is used to solve the 0-1 programming model, and an obtained solution vector is x=(x.sub.ijk, {i, j}RP.sub.3_2, kRP.sub.3_1).sup.T, the three-person passenger combination corresponding to x.sub.ijk=1 is screened out, the passenger combination set RP.sub.3_3 is constituted, which is referred to as the main passenger combination set 3, a quantity of set elements of which is |RP.sub.3_3|=|RP.sub.3|/3; and a set RC.sub.3=RP.sub.3_3{RP.sub.C3} is allowed to represent the passenger combination set formed by the users with the three-person pooling demand, i.e. a union set of RP.sub.3_3 and RP.sub.C3, the travel path and travel time of each passenger combination in the set RC.sub.3 are recorded, and a quantity |RC.sub.3| of set elements represents a quantity of the passenger combinations under the three-person pooling demand; the set RC is allowed to represent a passenger combination set formed by all users in the system, which a union set of the passenger combination sets formed by users with two-passenger pooling demand and three-passenger pooling demand, that is RC=RC.sub.2RC.sub.3, a quantity |RC| of set elements represents a quantity of the passenger combinations in the system.

7. The computer-implemented passenger matching method for on line ride-sharing service according to claim 6, wherein in the step 3), a process of matching the passenger combination within each passenger set is such that: 5.1) the passenger combination and the driver in the system are matched to form the driver-passenger combination, and a driver-passenger travel time and travel path of each driver-passenger combination are calculated; 5.2) a preset quantity of drivers or passenger combinations are supplemented, so that a quantity of passenger combinations participating in matching is equal to a quantity of drivers, a matching problem of the driver-passenger combination is solved, and a driver-passenger matching scheme with an optimal total driver-passenger travel time is obtained.

8. The computer-implemented passenger matching method for on line ride-sharing service according to claim 7, wherein a method of the step 5.1) is as follows such that: V is allowed to represent a driver set in the system, and a quantity |V| of set elements represents the quantity of drivers in the system; for any driver vV, V_O.sub.v is allowed to represent a current position of v; for any passenger combination eRC, C_O.sub.e and C_D.sub.e are allowed to represent a start point and an end server point of a passenger combination travel path of e, and C_T.sub.e represents a passenger combination travel time of e; the driver vV and the passenger combination eRC are matched to constitute the driver-passenger combination {v, e}, and a travel trajectory thereof is that the driver v starts from the current position V_O.sub.v to C_O.sub.e for picking up the first passenger until C_D.sub.e where all the passengers get off the vehicle; p.sub.ve is allowed to represent a travel path of the driver-passenger combination {v, e} and t.sub.ve is allowed to represent a path travel time of the driver-passenger combination {v, e}, i.e. a driver-passenger travel time, and the calculation formula is: $p_{\mathrm{ve}}=\left\{{\mathrm{V\_O}}_v.fwdarw.{\mathrm{C\_O}}_e.fwdarw.{\mathrm{C\_D}}_e\right\}$ $t_{\mathrm{ve}}=t\left({\mathrm{V\_O}}_v,{\mathrm{C\_O}}_e\right)+{\mathrm{C\_T}}_e$ where p.sub.ve represents a travel path from a current position V_O.sub.v to C_D.sub.e by the driver, and t(V_O.sub.v, C_O.sub.e) represents a travel time required by the driver u from the current position V_O.sub.v to the start point C_O.sub.e of the travel path of the passenger combination e.

9. The computer-implemented passenger matching method for on line ride-sharing service according to claim 8, wherein in the step 5.2), a method that a preset quantity of drivers or passenger combinations are supplemented so that a quantity of passenger combinations participating in matching is equal to a quantity of drivers is as follows such that: a real driver and a virtual driver are collectively referred to as a generalized driver, and the real passenger combination and the virtual passenger combination are collectively referred to as the generalized passenger combination, and the generalized driver and the generalized passenger combination are matched and can form a generalized driver-passenger combination; if the driver u in the driver-passenger combination {v, e} is the real driver and the passenger combination e is the real passenger combination, then {v, e} is a real driver-passenger combination; otherwise, {v, e} is a virtual driver-passenger combination, and the real driver-passenger combination and the virtual divisor-multiplier combination are collectively referred to as the generalized divisor-multiplier combination; Inf is allowed to represent a positive infinite constant, a certain quantity of virtual drivers or virtual passenger combinations are supplemented according to actual situations, and a generalized driver set and a generalized passenger combination set are constructed, and the specific processing is as follows: if a quantity of real passenger combinations is greater than a quantity of real drivers, namely |RC|>|V|, (|RC||V|) virtual drivers are supplemented in the driver set V to constitute the generalized driver set V.sub.g, wherein the generalized passenger combination set RC.sub.g is equal to the passenger combination set RC, namely RC.sub.g=RC, with the driver-passenger travel time t.sub.ve=Inf of the virtual driver u and any generalized passenger combination eRC.sub.g; if the quantity of real passenger combinations is less than the quantity of real drivers, namely |RC|<|V|, (|V||RC|) virtual passenger combinations are supplemented in the passenger combination set RC to constitute the generalized passenger combination set RC.sub.g, the generalized driver set V.sub.g is equal to the driver set V, namely V.sub.g=V, with the driver-passenger travel time t.sub.ve=Inf of the virtual passenger combination e and any generalized driver vV.sub.g.

10. The computer-implemented passenger matching method for on line ride-sharing service according to claim 9, wherein for the generalized driver set and the generalized passenger combination set, a method for driver-passenger combination matching is as follows such that: for any generalized driver vV.sub.g the generalized driver-passenger combination can only be formed by him with one generalized passenger combination eRC.sub.g, and with a goal of minimizing the total driver-passenger travel time, the matching problem of the driver-passenger combination can be transformed into a 0-1 programming model as follows: $\min \underset{v=1}{\overset{.Math.V_g.Math.}{.Math.}}\underset{e=1}{\overset{.Math.{\mathrm{RC}}_g.Math.}{.Math.}}{t}_{\mathrm{ve}}{y}_{\mathrm{ve}}$ $s.t.\{\begin{array}{c}\underset{e=1}{\overset{.Math.{\mathrm{RC}}_g.Math.}{.Math.}}{y}_{\mathrm{ve}}=1,e{\mathrm{RC}}_g\\ \underset{v=1}{\overset{.Math.V_g.Math.}{.Math.}}{y}_{\mathrm{ve}}=1,v{V}_g\\ y_{\mathrm{ve}}=0\mathrm{or}1,e{\mathrm{RC}}_g,v{V}_g\end{array}$ where y.sub.ve is a variable from 0 to 1; in a model solution result, if the generalized driver v and the generalized passenger combination e constitute the generalized driver-passenger combination {v, e}, then y.sub.ve=1, otherwise y.sub.ve=0; the Hungarian algorithm is applied to solve the 0-1 programming problem, and the obtained solution vector is y=(y.sub.ve, vV.sub.g, eRC.sub.g).sup.T, the generalized driver-passenger combinations corresponding to y.sub.ve=1 therein are screened out to constitute a generalized driver-passenger combination set VRC.sub.g, and then the real driver-passenger combinations in the set VRC.sub.g, are screened out to constitute a driver-passenger combination set VRC, wherein a quantity |VRC| of set elements is equal to a minimum value of a quantity |RC| of passenger combinations and a quantity |V| of drivers, namely |VRC|=min{|RC|, |V|}, and the travel path and travel time of each driver-passenger combination is recorded.

11. A computer system for passenger matching, comprising: one or more processors, one or more non-transitory computer-readable memories, one or more non-transitory computer-readable tangible storage medium, and program instructions stored on at least one of the one or more tangible storage medium for execution by at least one of the one or more processors via at least one of the one or more memories, wherein the computer system is capable of performing a method, comprising computer-implemented passenger matching method for on line ride-sharing service, wherein the method comprises the following steps that: 1) receiving, via an App and a communication network, a user publishes a pooling demands of on-line contract shared travel information by users via App; assigning a system cloud end server divides users into a plurality of user sets at a system cloud end server, and pre-processes pre-processing information about each user set to form a data file which is sent to the App of the users in the set; 2) after receiving a data file, the user calculates calculating a shortest passenger travel time and travel path in App, and returns sending a result to the system cloud end server; the system cloud end server receives receiving the result to solve a 0-1 programming model of a passenger combination matching process by the system cloud end server, and screening is performed to obtain a passenger combination matching scheme; 3) matching a passenger combination is matched with a driver, and constructing the system cloud end server constructs a generalized driver set and a generalized passenger combination set, determining a 0-1 programming model of a driver-passenger combination matching process is solved, and screening is performed to obtain a driver-passenger combination matching scheme; and 4) the system cloud end server sends sending the driver-passenger matching scheme to the App of the driver and the users, executes executing the matching scheme, and completes completing the on-line ride-sharing service shared travel.

12. The computer system for passenger matching according to claim 11, wherein in step 1), the travel information comprises a start point, an end server point and the pooling demand, and each user set is pre-processed, and the system cloud end server forms information about the start point and the end server point in the user set into the data file which is sent to a smart phone App of the users in the set.

13. The computer system for passenger matching according to claim 11, wherein in step 2), the pooling demand is two-person pooling demand and three-person pooling demand.

14. The computer system for passenger matching according to claim 13, wherein the specific method in step 1) is as follows that: the user i issues, via App, on-line contract shared travel information, comprising a travel start point O.sub.i, a travel end server point D.sub.i and the pooling demand N.sub.i, wherein a vehicle in a system is a five-seat automobile, and the automobile meets the pooling demand of the two-person pooling and the three-person pooling; according to the users' pooling demand, the system cloud end server divides the users into two sets: RP.sub.A2 and RP.sub.A3, the pooling demand of the users in the set RP.sub.A2 being the two-person pooling, namely N.sub.i=2, a quantity of users being |RP.sub.A2|, while the pooling demand of the users in the set RP.sub.A3 being the three-person pooling, namely N.sub.i=3, a quantity of users being |RP.sub.A3|; taking the quantities |RP.sub.A2| and |RP.sub.A3| of the users in the set as a dividend, taking the pooling demands N.sub.i=2 and N.sub.i=3 of the users in the set as a divisor, a remainder operation is performed to obtain remainders |RP.sub.B2| and |RP.sub.B3|, namely: $\left|R{P}_{B2}\right|=\left|R{P}_{A2}\right|\mathrm{\%2}\left|R{P}_{B3}\right|=\left|R{P}_{A3}\right|\mathrm{\%3}$ where % represents a remainder symbol; the system pre-processes the sets RP.sub.A2 and RP.sub.A3 as follows by: for the two-person pooling set RP.sub.A2: randomly selecting |RP.sub.B2| of the users in the set RP.sub.A2, wherein selected users constitute a set RP.sub.B2 referred to as a secondary user set 2; and unselected users constitute a set RP.sub.2 referred to as a main user set 2; and RP.sub.A2=RP.sub.B2RP.sub.2, where if the remainder is |RP.sub.B2|=0, then RP.sub.B2=, and there is a set relationship of RP.sub.A2=RP.sub.2; for the three-person pooling set RP.sub.A3: randomly selecting |RP.sub.B3| of the users in the set RP.sub.A3, wherein selected users constitute a set RP.sub.B3 referred to as a secondary user set 3; and unselected users constitute a set RP.sub.3 referred to as a main user set 3; and RP.sub.43=RP.sub.B3RP.sub.3, where if the remainder is |RP.sub.B3|=0, then RP.sub.B3=, and there is a set relationship of RP.sub.A3=RP.sub.3; and after receiving the on-line contract shared travel information about the user and completing user set classification and pre-processing, the cloud end server respectively aggregates the travel start points and the travel end server points of the users in the sets RP.sub.2 and RP.sub.3, and extracts travel times between all nodes to form two data files: File2 and File3, and the cloud end server sends the data file File2 to all the users in the set RP.sub.2, and sends the data file File3 to all the users in the set RP.sub.3.

15. The computer system for passenger matching according to claim 14, wherein in the step 2), a process of matching a passenger combination within the user set RP.sub.A2 with a two-person pooling demand is such that: 1) the user in RP.sub.2 calculates a shortest passenger travel time and travel path of all possible two-person passenger combinations with himself as a first passenger, and returns a calculation result to the system cloud end server; after the user of the user iRP.sub.2 receives the data file File2 sent by the system cloud end server, the smart phone of the user i takes the user i as the first passenger to calculate the shortest travel path and travel time of the two-person passenger combination formed by the user i and any other user jRP.sub.2\{i} and returns a calculation result to the system cloud end server, and the calculation formula is as follows: $p_{\mathrm{ij}}=\left\{O_i.fwdarw.O_j.fwdarw.D_i.fwdarw.D_j,O_i.fwdarw.O_j.fwdarw.D_j.fwdarw.D_i\right\}{r}_{\mathrm{ij}}=\min \{t\left(O_i,O_j\right)+t\left(O_j,D_i\right)+t\left(D_i,D_j\right),t\left(O_i,O_j\right)+t\left(O_j,D_j\right)+t\left(D_j,D_i\right)\}$ as stated above, taking the user i as the first passenger means taking the start point O.sub.i of the user i as a jumping-off place, so that the user i is the passenger gets aboard at first, and the driver needs to firstly receive the user i and j as the two passengers, and then send them to destinations respectively; in the formula, in both O.sub.i.fwdarw.O.sub.j.fwdarw.D.sub.i.fwdarw.D.sub.j and O.sub.i.fwdarw.O.sub.j.fwdarw.D.sub.j.fwdarw.D.sub.i, paths are represented by nodes which are passed through successively, and all possible travel paths of the two-person passenger combination {i, j} are taken when the user i is the first passenger, and P.sub.ij represents a travel path set of the two-person passenger combination {i, j} when the user i is the first passenger, and t(O.sub.i, O.sub.j), t(O.sub.j, D.sub.i), t(D.sub.i, D.sub.j), t(O.sub.j, D.sub.i), and t(D.sub.i, D.sub.j) all represent travel time between two nodes in parentheses; t(O.sub.i, O.sub.j)+t(O.sub.j, D.sub.i)+t(D.sub.i, D.sub.j) and t(O.sub.i, O.sub.j)+t(O.sub.j, D.sub.i)+t(D.sub.j, D.sub.i) both represent possible travel time of the two-person passenger combination {i, j} when the user i is the first passenger, and r.sub.ij represents a shortest passenger travel time of the two-person passenger combination {i, j} when the user i is the first passenger; 2) the system cloud end server compares the shortest passenger travel times when different users in respective two-person passenger combinations serve as the first passenger, and determines the shortest passenger travel time and travel path of each two-person passenger combination; within the two-person passenger combination {i,j}, a sum of the shortest passenger travel times r.sub.ij and r.sub.ji with the user i and the user i as the first passenger are compared with each other, the shortest passenger travel time r.sub.ij of the two-person passenger combination is determined, and a travel path corresponding r.sub.ij to is recorded, wherein the formula is as follows: $r_{\stackrel{\_}{\mathrm{ij}}}=\min \left\{r_{\mathrm{ij}},r_{\mathrm{ji}}\right\}$ 3) the users within RP.sub.B2 are formed into a passenger combination RP.sub.C2, and the shortest passenger travel time r.sub.C2 and travel path of the passenger combination are calculated; under the two-person pooling demand of the user, if |RP.sub.B2|0, then |RP.sub.B2|=1, namely there is only one user in the secondary user set 2 RP.sub.B2, and the user is set as mRP.sub.B2; the one user in the RP.sub.B2 is formed into a passenger combination represented by RP.sub.C2, referred to as secondary passenger combination 2, there is RP.sub.C2={m}, the shortest passenger travel time r.sub.C2=t(O.sub.m, D.sub.m) of the secondary passenger combination 2 RP.sub.C2, and the corresponding travel path is O.sub.m.fwdarw.D.sub.m, and {RP.sub.C2} represents a passenger combination set having only one element RP.sub.C2; 4) a matching problem of the two-person passenger combination is solved, and a two-person pooling passenger matching scheme with an optimal total passenger travel time is obtained; for any user iRP.sub.2, he can only form a two-person passenger combination with another user jRP.sub.2\{i} ultimately, with a goal of minimizing the total passenger travel time, while under the user's two-person pooling demand, the matching problem of the two-person passenger combination is transformed into a 0-1 programming model as follows: $\min \underset{i=1}{\overset{.Math.{\mathrm{RP}}_2.Math.}{.Math.}}\underset{j=1}{\overset{.Math.{\mathrm{RP}}_2.Math.}{.Math.}}{r}_{\stackrel{\_}{\mathrm{ij}}}{x}_{\mathrm{ij}}s.t.\{\begin{array}{c}\underset{i=1}{\overset{.Math.{\mathrm{RP}}_2.Math.}{.Math.}}{x}_{\mathrm{ij}}=1,j{\mathrm{RP}}_2\\ \underset{j=1}{\overset{.Math.{\mathrm{RP}}_2.Math.}{.Math.}}{x}_{\mathrm{ij}}=1,i{\mathrm{RP}}_2\\ x_{\mathrm{ij}}=0\mathrm{or}1,i,j{\mathrm{RP}}_2\end{array}$ where x.sub.ij is a 0-1 variable: in a solution result of the model, if the user i and the user j constitute a two-person passenger combination {i, j}, then x.sub.ij=1, otherwise x.sub.ij=0; furthermore, there is no constraint in the 0-1 programming model ij, and the shortest passenger travel time r.sub.ii for repeating the two-person passenger combination {i, i} is set as follows: $r_{\stackrel{\_}{\mathrm{ii}}}=\mathrm{Inf},iR{P}_2$ where Inf represents a positive infinite constant; Hungarian algorithm is used to solve the 0-1 programming model, and an obtained solution vector is x=(x.sub.ij, iRP.sub.2, jRP.sub.2).sup.T, the two-person passenger combination corresponding to x.sub.ij=1 is screened out, the passenger combination set RP.sub.2_2 is formed, which is referred to as the main passenger combination set 2, a quantity of set elements of which is |RP.sub.2_2|=|RP.sub.2|/2; and a set RC.sub.2=RP.sub.2_2{RP.sub.C2} is allowed to represent the passenger combination set formed by the users with the two-person pooling demand, i.e. a union set of RP.sub.2_2 and {RP.sub.C2}, the travel path and travel time of each passenger combination in the set RC.sub.2 are recorded, and a quantity |RC.sub.2| of set elements represents a quantity of the passenger combinations under the two-person pooling demand.

16. The computer system for passenger matching according to claim 14, wherein in the step 2), a process of matching a passenger combination within the user set RP.sub.A3 with a three-person pooling demand is such that: 1) the system cloud end server pre-supplements a certain quantity of virtual users on the basis of RP.sub.3 to form a generalized user set RP.sub.E3, wherein the user in RP.sub.3 calculates the shortest passenger travel time and travel path of all possible two-person passenger combinations with himself as the first passenger, and returns a calculation result to the system cloud end server; a quantity |RP.sub.3|/3 of virtual users are pre-supplemented before passenger combination matching under the three-person pooling demand of the user, and the travel start points O.sub.i and the travel end server points D.sub.i of the virtual users are all virtual nodes; the virtual node does not exist in a real urban road network, and the distance to any real node is positively infinite, |RP.sub.3|/3 virtual users constitute a virtual user set RP.sub.V3, and a union set of the virtual user set RP.sub.V3 and RP.sub.3 is the generalized user set RP.sub.E3, namely RP.sub.E3=RP.sub.3RP.sub.V3, Inf representing a positive infinite constant; after the smart phone of the user iRP.sub.3 receives the data file File3 sent by the cloud end server, the smart phone of the user i takes the user i as the first passenger to calculate the shortest travel path and travel time of the two-person passenger combination formed by the user i and any other user jRP.sub.3\{i}, and returns a calculation result to the system cloud end server, and the calculation formula is as follows: $p_{\mathrm{ij}}=\left\{O_i.fwdarw.O_j.fwdarw.D_i.fwdarw.D_j,O_i.fwdarw.O_j.fwdarw.D_j.fwdarw.D_i\right\}{r}_{\mathrm{ij}}=\min \{t\left(O_i,O_j\right)+t\left(O_j,D_i\right)+t\left(D_i,D_j\right),t\left(O_i,O_j\right)+t\left(O_j,D_j\right)+t\left(D_j,D_i\right)\}$ as stated above, taking the user i as the first passenger, i.e. taking the start point O.sub.i of the user i as a jumping-off place, so that the user i is the passenger gets aboard at first, the driver firstly receives the users i and j as the two passengers, and then send them to destinations respectively; in the formula, in both O.sub.i.fwdarw.O.sub.j.fwdarw.D.sub.i.fwdarw.D.sub.j and O.sub.i.fwdarw.O.sub.j.fwdarw.D.sub.j.fwdarw.D.sub.i, paths are represented by nodes which are passed through successively, and all possible travel paths of the two-person passenger combination {i, j} are taken when the user i is the first passenger, and P.sub.ij represents a travel path set of the two-person passenger combination {i, j} when the user i is the first passenger, and t(O.sub.i, O.sub.j), t(O.sub.j, D.sub.i), t(D.sub.i, D.sub.j), t(O.sub.j, D.sub.j), and t(D.sub.i, D.sub.j) all represent travel time between two nodes in parentheses, t(O.sub.i, O.sub.j)+t(O.sub.j, D.sub.i)+t(D.sub.i, D.sub.j) and t(O.sub.i, O.sub.j)+t(O.sub.j, D.sub.j)+t(D.sub.j, D.sub.i) both represent possible travel time of the two-person passenger combination {i, j} when the user i is the first passenger, and r.sub.ij represents a shortest passenger travel time of the two-person passenger combination {i, j} when the user i is the first passenger; 2) the system cloud end server compares the shortest passenger travel times when different users in respective two-person passenger combinations serve as the first passenger, and determines the shortest passenger travel time and travel path of each two-person passenger combination; within the two-person passenger combination {i, j}, a sum of the shortest passenger travel times r.sub.ij and r.sub.ij with the user i and the user j as the first passenger are compared with each other, the shortest passenger travel time r.sub.ij of the two-person passenger combination is determined, and a travel path corresponding to r.sub.ij is recorded, wherein the formula is as follows: $r_{\stackrel{\_}{\mathrm{ij}}}=\min \left\{r_{\mathrm{ij}},r_{\mathrm{ji}}\right\}$ 3) all the users within secondary user set 3 RP.sub.B3| are formed into a passenger combination RP.sub.C3, and the shortest passenger travel time r.sub.C3 and travel path of the passenger combination are calculated; if |RP.sub.B3|0 under the user's three-person pooling demand, then |RP.sub.B3|=1 or |RP.sub.B3|=2, namely, there are 1 or 2 users in the secondary user set RP.sub.B3, all the users in the set RP.sub.B3 are formed into a passenger combination represented by RP.sub.C3 referred to as secondary passenger combination 3, and r is allowed to represent the shortest passenger travel time of the passenger combination RP.sub.C3, and {RP.sub.C3} is allowed to represent a passenger combination set comprising only one element of the passenger combination RP.sub.C3 referred to as secondary passenger combination set 3; if there is one user in the set RP.sub.B3, the user is set to be mRP.sub.B3, then the secondary passenger combination 3 RP.sub.C3={m}, the shortest passenger travel time r.sub.C3=t(O.sub.m, D.sub.m) of RP.sub.C3 and a corresponding travel path is O.sub.m.fwdarw.D.sub.m; if there are two users in the set RP.sub.B3, represented as m.sub.1, m.sub.2RP.sub.B3, then secondary passenger combination 3 RP.sub.C3={m.sub.1, m.sub.2} is a two-person passenger combination, and the shortest passenger travel time r.sub.C3 of RP.sub.C3 is the shortest passenger travel time of the two-person passenger combination {m.sub.1, m.sub.2} and for it is also necessary to first respectively calculate the shortest passenger travel times r.sub.m.sub.1.sub.m.sub.2 and r.sub.m.sub.2.sub.m.sub.1 with m.sub.1 and m.sub.2 as the first passenger, and then make comparison to obtain the shortest passenger travel time of the two-person passenger combination {m.sub.1, m.sub.2}, and a travel path corresponding to is recorded; 4) to solve a first passenger combination matching problem under the three-person pooling demand of the user, |RP.sub.E3/2 generalized two-person passenger combinations is matched in the generalized user set RP.sub.E3, and then real users in |RP.sub.3|/2 real two-person passenger combinations and |RP.sub.3|/2 mixed two-person passenger combinations are selected from the generalized two-person passenger combinations; real users and virtual users are collectively referred to as generalized users; if the passengers i and j in the two-person passenger combination {i, j} are both real users, then {i, j} is taken as the real two-person passenger combination; if the passenger i in the two-person passenger combination {i, j} is a real user and the passenger j is a virtual user, or if the passenger i is a virtual user and the passenger j is a real user, then {i, j} is taken as the mixed two-person passenger combination; if the passengers i and j in the two-person passenger combination {i, j} are both virtual users, then {i, j} is taken as a virtual two-person passenger combination, while the real two-person passenger combination, the mixed two-person passenger combination and the virtual two-person passenger combination are collectively referred to as the generalized two-person passenger combination; in the first passenger combination matching process under the three-person pooling demand of the user, |RP.sub.E3|/2 generalized two-person passenger combinations are matched in the generalized user set RP.sub.E3, and for any generalized user iRP.sub.E3, the generalized two-person passenger combination can only be formed by him with another generalized user jRP.sub.E3\{i}, and aiming at minimizing the total passenger travel time, the matching problem of the generalized two-person passenger combination can be transformed into a 0-1 programming model as follows: $\min \underset{i=1}{\overset{.Math.{\mathrm{RP}}_{E3}.Math.}{.Math.}}\underset{j=1}{\overset{.Math.{\mathrm{RP}}_{E3}.Math.}{.Math.}}{r}_{\stackrel{\_}{\mathrm{ij}}}{x}_{\mathrm{ij}}s.t.\{\begin{array}{c}\underset{i=1}{\overset{.Math.{\mathrm{RP}}_{E3}.Math.}{.Math.}}{x}_{\mathrm{ij}}=1,j{\mathrm{RP}}_{E3}\\ \underset{j=1}{\overset{.Math.{\mathrm{RP}}_{E3}.Math.}{.Math.}}{x}_{\mathrm{ij}}=1,i{\mathrm{RP}}_{E3}\\ x_{\mathrm{ij}}=0\mathrm{or}1,i,j{\mathrm{RP}}_{E3}\end{array}$ where x.sub.ij is a variable from 0 to 1; in a model solution result, if the generalized user i and the generalized user i constitute the generalized two-person passenger combination {i, j}, then x.sub.ij=1, otherwise x.sub.ij=0; since there is no constraint ij in the 0-1 programming model, the 0-1 programming model not only has the repeated two-person passenger combination {i, i} and the related parameter r.sub.ii and variable x.sub.ii, but also has the virtual user and the mixed two-person passenger combination and the virtual two-person passenger combination which may be formed; in order to match the real two-person passenger combination as much as possible, and at the same time enable the 0-1 programming model to solve the first passenger matching process of three-person pooling, Inf is allowed to represent a positive infinite constant, and the shortest passenger travel time of any generalized two-person passenger combination {i, j} is set as follows: if iRP.sub.3, jRP.sub.3 and ij, it is the real two-person passenger combination, and the shortest passenger travel time thereof is r.sub.ij; if iRP.sub.3, jRP.sub.V3 or jRP.sub.3, iRP.sub.V3, it is the mixed two-person passenger combination, and the shortest passenger travel time thereof is Inf; if iRP.sub.V3, jRP.sub.V3 and ij, it is the virtual two-person passenger combination, and the shortest passenger travel time thereof is 2*Inf; for the repeated two-person passenger combination {i, i}, the shortest passenger time r.sub.ii thereof is set as 2*Inf; the Hungarian algorithm is applied to solve the 0-1 programming model, and the solved vector is x=(x.sub.ij, iRP.sub.E3, jRP.sub.E3).sup.T, 2*(|RP.sub.3|/3) generalized two-person passenger combinations corresponding to x.sub.ij=1 are screened out, wherein there are |RP.sub.3|/3 real two-person passenger combinations and |RP.sub.3|/3 mixed two-person passenger combinations; |RP.sub.3|/3 real two-person passenger combinations are screened out to construct the real two-person passenger combination set RP.sub.3_2 and the quantity of set elements is |RP.sub.3_2|=|RP.sub.3|/3; then the real users in |RP.sub.3|/3 mixed two-person passenger combinations are screened out to construct the user set RP.sub.3_1 and the quantity of set elements is |RP.sub.3_1|=|RP.sub.3|/3; after the system cloud end server completes the first passenger combination matching of the three-person pooling, the start points and the end server points of two users of each real two-person passenger combination in the real two-person passenger combination set RP.sub.3_2 are extracted to form a data file File3_2; start points and end server points of each user in the user set RP.sub.3_1 are extracted to form a data file File3_1; after forming the data files, the system cloud sends the data files File3_1 and File3_2 to all the smart phones of the users in RP.sub.3 again; 5) the user in RP.sub.3 calculates a shortest passenger travel time and travel path of all possible three-person passenger combinations with himself as a first passenger, and returns a calculation result to the system cloud end server; the real two-person passenger combination set RP.sub.3_2 and the user set RP.sub.3_1 are obtained in the first passenger combination matching process of the three-person pooling, so that the real two-person passenger combination {i, j}RP.sub.3_2 and the real user kRP.sub.3_1, then the user i, the user j and the user k constitute a three-person passenger combination {i, j, k}; a step of calculating the shortest passenger travel time of the three-person passenger combination {i, j, k} is as follows; smart phones of the user i, j{i, j}, {i, j}RP.sub.3_2 and the user kRP.sub.3_1 receive the data files File3_1 and File3_2 sent by the cloud end server; after receiving the files File3_1 and File3_2, the smart phone of the user i takes the user i as the first passenger to calculate the shortest travel path and travel time of the three-person passenger combination formed by the user i, the user j and the user k, and returns a calculation result to the system cloud end server, and the calculation formula is as follows: $P_{\mathrm{ijk}}=\left\{\begin{array}{c}{O}_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_i.fwdarw.D_j.fwdarw.D_k,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_i.fwdarw.D_j.fwdarw.D_k,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_i.fwdarw.D_k.fwdarw.D_j,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_i.fwdarw.D_k.fwdarw.D_j,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_j.fwdarw.D_i.fwdarw.D_k,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_j.fwdarw.D_i.fwdarw.D_k,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_j.fwdarw.D_k.fwdarw.D_i,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_j.fwdarw.D_k.fwdarw.D_i,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_k.fwdarw.D_i.fwdarw.D_j,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_k.fwdarw.D_i.fwdarw.D_j,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_k.fwdarw.D_j.fwdarw.D_i,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_k.fwdarw.D_j.fwdarw.D_i\end{array}\right\}$ $r_{\mathrm{ijk}}=\min \left\{\begin{array}{c}t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_i\right)+t\left(D_i,D_j\right)+t\left(D_j,D_k\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_i\right)+t\left(D_i,D_j\right)+t\left(D_j,D_k\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_i\right)+t\left(D_i,D_k\right)+t\left(D_k,D_j\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_i\right)+t\left(D_i,D_k\right)+t\left(D_k,D_j\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_j\right)+t\left(D_j,D_i\right)+t\left(D_i,D_k\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_j\right)+t\left(D_j,D_i\right)+t\left(D_i,D_k\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_j\right)+t\left(D_j,D_k\right)+t\left(D_k,D_i\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_j\right)+t\left(D_j,D_k\right)+t\left(D_k,D_i\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_k\right)+t\left(D_k,D_i\right)+t\left(D_i,D_j\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_k\right)+t\left(D_k,D_i\right)+t\left(D_i,D_j\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_k\right)+t\left(D_k,D_j\right)+t\left(D_j,D_i\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_k\right)+t\left(D_k,D_j\right)+t\left(D_j,D_i\right)\end{array}\right\}$ as stated above, in order to achieve the three-person pooling demand of the user, the driver first picks up the three passengers and then sends them to destinations respectively, where P.sub.ijk represents a travel path set of the three-person passenger combination {i, j, k} when the user i is the first passenger, wherein the elements O.sub.j.fwdarw.O.sub.i.fwdarw.O.sub.k.fwdarw.D.sub.i.fwdarw.D.sub.j.fwdarw.D.sub.k are all paths, which are represented by nodes that are passed through successively, and r.sub.ijk represent the shortest passenger travel time of the three-person passenger combination {i, j, k} when the user i is the first passenger, while the elements t(O.sub.k, O.sub.j)+t(O.sub.j, O.sub.i)+t(O.sub.i, D.sub.i)+t(D.sub.i, D.sub.j)+t(D.sub.j, D.sub.k) all represent possible travel times of the three-person passenger combination {i, j, k}; 6) the system cloud end server compares the shortest passenger travel times when different users in respective three-person passenger combinations serve as the first passenger, and determines the shortest passenger travel time and travel path of each three-person passenger combination; within the three-person passenger combination {i, j, k}, the system compares the shortest passenger travel times r.sub.ijk, r.sub.jik, and r.sub.kij with the user i, the user j and the user k as the first passenger, determines the shortest passenger travel time r.sub.ijk of the three-person passenger combination, and records a travel path corresponding to r.sub.ijk and the formula is as follows: $r_{\stackrel{\_}{\mathrm{ijk}}}=\min \left\{r_{\mathrm{ijk}},r_{\mathrm{jik}},r_{\mathrm{kij}}\right\}$ 7) a second passenger combination matching problem of three-person pooling is solved, and a three-person pooling passenger matching scheme with an optimal passenger travel time is obtained; for any two-person passenger combination {i, j}RP.sub.3_2, it can only form a three-person passenger combination with another user kRP.sub.3_1 ultimately, with a goal of minimizing the total passenger travel time, while under the user's three-person pooling demand, the matching problem of the two-person passenger combination can be transformed into a 0-1 programming model as follows: $\min \underset{\left\{i,j\right\}}{.Math.}\underset{k}{.Math.}{r}_{\stackrel{\_}{\mathrm{ijk}}}{x}_{\mathrm{ijk}}$ $s.t.\{\begin{array}{c}\underset{\left\{i,j\right\}}{.Math.}{x}_{\mathrm{ijk}}=1,k{\mathrm{RP}}_{3\_1}\\ \underset{k}{.Math.}{x}_{\mathrm{ijk}}=1,\left\{i,j\right\}{\mathrm{RP}}_{3\_2}\\ x_{\mathrm{ijk}}=0\mathrm{or}1,\left\{i,j\right\}{\mathrm{RP}}_{3\_2},k{\mathrm{RP}}_{3\_1}\end{array}$ where x.sub.ijk is a variable from 0 to 1; in a solution result of the model, if the two-person passenger combination {i, j} and the user k constitute the three-person passenger combination {i, j, k}, then x.sub.ijk=1, otherwise x.sub.ijk=0; Hungarian algorithm is used to solve the 0-1 programming model, and an obtained solution vector is x=(x.sub.ijk, {i,j}RP.sub.3_2, kRP.sub.3_1).sup.T, the three-person passenger combination corresponding to x.sub.ijk=1 is screened out, the passenger combination set RP.sub.3_3 is constituted, which is referred to as the main passenger combination set 3, a quantity of set elements of which is |RP.sub.3_3|=|RP.sub.3|/3; and a set RC.sub.3=RP.sub.3_3{RP.sub.C3} is allowed to represent the passenger combination set formed by the users with the three-person pooling demand, i.e. a union set of RP.sub.3_3 and RP.sub.C3, the travel path and travel time of each passenger combination in the set RC.sub.3 are recorded, and a quantity |RC.sub.3| of set elements represents a quantity of the passenger combinations under the three-person pooling demand; the set RC is allowed to represent a passenger combination set formed by all users in the system, which a union set of the passenger combination sets formed by users with two-passenger pooling demand and three-passenger pooling demand, that is RC=RC.sub.2RC.sub.3, a quantity |RC| of set elements represents a quantity of the passenger combinations in the system.

17. The computer system for passenger matching according to claim 16, wherein in the step 3), a process of matching the passenger combination within each passenger set is such that: 5.1) the passenger combination and the driver in the system are matched to form the driver-passenger combination, and a driver-passenger travel time and travel path of each driver-passenger combination are calculated; 5.2) a preset quantity of drivers or passenger combinations are supplemented, so that a quantity of passenger combinations participating in matching is equal to a quantity of drivers, a matching problem of the driver-passenger combination is solved, and a driver-passenger matching scheme with an optimal total driver-passenger travel time is obtained.

18. The computer system for passenger matching according to claim 17, wherein a method of the step 5.1) is as follows such that: V is allowed to represent a driver set in the system, and a quantity |V| of set elements represents the quantity of drivers in the system; for any driver vV, V_O.sub.v is allowed to represent a current position of v; for any passenger combination eRC, C_O.sub.e and C_D.sub.e are allowed to represent a start point and an end server point of a passenger combination travel path of e, and C_T.sub.e represents a passenger combination travel time of e; the driver vV and the passenger combination eRC are matched to constitute the driver-passenger combination {v, e} and a travel trajectory thereof is that the driver v starts from the current position V_O.sub.v to C_O.sub.e for picking up the first passenger until C_D.sub.e where all the passengers get off the vehicle; p.sub.ve is allowed to represent a travel path of the driver-passenger combination {v, e}, and t.sub.ve is allowed to represent a path travel time of the driver-passenger combination {v, e}, i.e. a driver-passenger travel time, and the calculation formula is: $p_{\mathrm{ve}}=\left\{{\mathrm{V\_O}}_v.fwdarw.{\mathrm{C\_O}}_e.fwdarw.{\mathrm{C\_D}}_e\right\}{t}_{\mathrm{ve}}=t\left({\mathrm{V\_O}}_v,{\mathrm{C\_O}}_e\right)+{\mathrm{C\_T}}_e$ where p.sub.ve represents a travel path from a current position V_O.sub.v to C_D.sub.e by the driver, and t(V_O.sub.v, C_O.sub.e) represents a travel time required by the driver u from the current position V_O.sub.v to the start point C_O.sub.e of the travel path of the passenger combination e.

19. The computer system for passenger matching according to claim 18, wherein in the step 5.2), a method that a preset quantity of drivers or passenger combinations are supplemented so that a quantity of passenger combinations participating in matching is equal to a quantity of drivers is as follows such that: a real driver and a virtual driver are collectively referred to as a generalized driver, and the real passenger combination and the virtual passenger combination are collectively referred to as the generalized passenger combination, and the generalized driver and the generalized passenger combination are matched and can form a generalized driver-passenger combination; if the driver v in the driver-passenger combination {v, e} is the real driver and the passenger combination e is the real passenger combination, then {v, e} is a real driver-passenger combination; otherwise, {v, e} is a virtual driver-passenger combination, and the real driver-passenger combination and the virtual divisor-multiplier combination are collectively referred to as the generalized divisor-multiplier combination; Inf is allowed to represent a positive infinite constant, a certain quantity of virtual drivers or virtual passenger combinations are supplemented according to actual situations, and a generalized driver set and a generalized passenger combination set are constructed, and the specific processing is as follows: if a quantity of real passenger combinations is greater than a quantity of real drivers, namely |RC|>|V|, (|RC||V|) virtual drivers are supplemented in the driver set V to constitute the generalized driver set V.sub.g, wherein the generalized passenger combination set RC.sub.g is equal to the passenger combination set RC, namely RC.sub.g=RC, with the driver-passenger travel time t.sub.ve=Inf of the virtual driver v and any generalized passenger combination eRC.sub.g; if the quantity of real passenger combinations is less than the quantity of real drivers, namely |RC|<|V|, (|V||RC|) virtual passenger combinations are supplemented in the passenger combination set RC to constitute the generalized passenger combination set RC.sub.g, the generalized driver set V.sub.g is equal to the driver set V, namely V.sub.g=V, with the driver-passenger travel time t.sub.ve=Inf of the virtual passenger combination e and any generalized driver vV.sub.g.

20. The computer system for passenger matching according to claim 19, wherein for the generalized driver set and the generalized passenger combination set, a method for driver-passenger combination matching is as follows such that: for any generalized driver vV.sub.g, the generalized driver-passenger combination can only be formed by him with one generalized passenger combination eRC.sub.g, and with a goal of minimizing the total driver-passenger travel time, the matching problem of the driver-passenger combination can be transformed into a 0-1 programming model as follows: $\min \underset{v=1}{\overset{.Math.V_g.Math.}{.Math.}}\underset{e=1}{\overset{.Math.{\mathrm{RC}}_g.Math.}{.Math.}}{t}_{\mathrm{ve}}{y}_{\mathrm{ve}}s.t.\{\begin{array}{c}\underset{e=1}{\overset{.Math.{\mathrm{RC}}_g.Math.}{.Math.}}{y}_{\mathrm{ve}}=1,e{\mathrm{RC}}_g\\ \underset{v=1}{\overset{.Math.V_g.Math.}{.Math.}}{y}_{\mathrm{ve}}=1,v{V}_g\\ y_{\mathrm{ve}}=0\mathrm{or}1,e{\mathrm{RC}}_g,v{V}_g\end{array}$ where y.sub.ve is a variable from 0 to 1; in a model solution result, if the generalized driver v and the generalized passenger combination e constitute the generalized driver-passenger combination {v, e}, then y.sub.ve=1, otherwise y.sub.ve=0; the Hungarian algorithm is applied to solve the 0-1 programming problem, and the obtained y=(y.sub.ve, vV.sub.g, eRC.sub.g).sup.T, the generalized driver-passenger combinations solution vector is corresponding to y.sub.ve=1 therein are screened out to constitute a generalized driver-passenger combination set VRC.sub.g, and then the real driver-passenger combinations in the set VRC.sub.g are screened out to constitute a driver-passenger combination set VRC, wherein a quantity |VRC| of set elements is equal to a minimum value of a quantity |RC| of passenger combinations and a quantity |V| of drivers, namely |VRC|=min{|RC|, |V|}, and the travel path and travel time of each driver-passenger combination is recorded.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0106] FIG. 1 is a flow diagram of a method of the present disclosure;

[0107] FIG. 2 is a flow diagram of passenger combination matching under a two-person pooling demand;

[0108] FIG. 3 is a flow diagram of passenger combination matching under a three-person pooling demand.

DETAILED DESCRIPTION OF THE INVENTION

[0109] The disclosure will now be further described by way of embodiments and with reference to the accompanying drawings.

[0110] The present disclosure provides a passenger-vehicle matching method for on line ride-sharing service, as shown in FIG. 1, including the following processes:

[0111] I. A user publishes on-line contract shared travel information via a mobile phone App, wherein the travel information includes a start point, an end point and a pooling demand; the system divides users into a plurality of user sets according to their pooling demands, and pre-processes each user set. The system cloud end server forms information such as the start points and the end point in a user set into a data file and sends same to the smart phones of the users in the set.

[0112] The cloud end of the system stores real-time travel data of the points of getting on and off the Internet contract shared travel within the city. At a certain moment, 26 users in the system publish the shared travel demand through the mobile phone App, and the quantity of users with the pooling demand of two-person pooling and three-person pooling is each RP.sub.A2 13, respectively forming sets RP.sub.A2 and RP.sub.A3. The information for each user set is shown in Table 1.

TABLE-US-00001 TABLE 1 Individual passenger set Information User serial User start User end User serial User start User end number point point number point point User set RP.sub.A2 with the two-person pooling demand 1 406 260 8 199 445 2 391 432 9 464 99 3 118 146 10 175 483 4 315 400 11 341 387 5 154 490 12 107 342 6 424 290 13 58 162 7 433 391 User set RP.sub.A3 with the three-person pooling demand 1 492 116 8 441 88 2 233 210 9 368 486 3 168 61 10 100 459 4 104 112 11 235 388 5 96 56 12 51 374 6 64 95 13 180 245 7 383 20

Readily Available:

[00021]$\begin{array}{c}.Math.{\mathrm{RP}}_{A2}.Math.=13,.Math.{\mathrm{RP}}_{B2}.Math.=.Math.{\mathrm{RP}}_{A2}.Math.\mathrm{\%2}=1\\ .Math.{\mathrm{RP}}_{A3}.Math.=13,.Math.{\mathrm{RP}}_{B3}.Math.=.Math.{\mathrm{RP}}_{A3}.Math.\mathrm{\%2}=1\end{array}$

[0113] Since |RP.sub.B2|, |RP.sub.B3|, and |RP.sub.B4| are neither 0, the passengers are selected to cope with this possibility, the system will process the passenger set in advance: two-person pooling: a set RP.sub.B2 is constituted by randomly selecting |RP.sub.B2|=1 users within the set RP.sub.A2. Finally, the user of number 13 selecting two-person pooling, the secondary user set 2 RP.sub.B2={13}, and the remaining users constitute primary user set 2 RP.sub.2.

[0114] Three-person pooling: a set RP.sub.B3 is constituted by randomly selecting |RP.sub.B3|=1 passengers within the set RP.sub.A3. Finally, the user of number 10 selecting three-person pooling, the secondary user set 3 RP.sub.B3={10}, and the remaining users constitute primary user set 3 RP.sub.3.

[0115] After receiving the on-line contract shared travel information about the user and completing user set classification and pre-processing, the cloud end respectively aggregates the travel start points and the travel end points of the users in the sets RP.sub.2 and RP.sub.3, and extracts travel times between these nodes to form three data files: File2 and File3.

[0116] After forming the data file, the cloud end sends the data file File2 to the smart phones of all the users in the set RP.sub.2, and sends the data file File3 to the smart phones of all the users in the set RP.sub.3.

[0117] II, the passenger combination is matched within the user sets RP.sub.A2 and RP.sub.A3 with two-person pooling and three-person pooling demands. Firstly, the user receives the data file, calculates the shortest passenger travel time and travel path of a two-person passenger combination when the current user is the first passenger, and returns the result to the cloud end; secondly, the system cloud end server receives the results, solves the 0-1 programming model of passenger combination matching process, and obtains the passenger combination matching scheme.

1. Two-Person Pooling

[0118] 1) The current passenger is taken as the first passenger, and the shortest passenger travel time and path of two-person passenger combination are calculated.

[0119] The smart phone of the user iRP.sub.2 receives the data file File2 sent by the cloud end. After receiving the File2, the smart phone of the user i takes the user i as the first passenger, calculates the shortest travel path and travel time of the two-person passenger combination formed by the user i and another user jRP.sub.2\{i}, and returns the calculation result to the system cloud end server. A calculation formula is as follows:

[00022]$P_{ij}=\left\{O_i.fwdarw.O_j.fwdarw.D_i.fwdarw.D_j,O_i.fwdarw.O_j.fwdarw.D_j.fwdarw.D_i\right\}$$r_{ij}=\min \left\{t\left(O_i,O_j\right)+t\left(O_j,D_i\right)+t\left(D_i,D_j\right),t\left(O_i,O_j\right)+t\left(O_j,D_j\right)+t\left(D_j,D_i\right)\right\}$

as stated above, taking the user i as the first passenger means taking the start point O.sub.i of the user i as a jumping-off place, so that the user i is the passenger gets aboard at first. In order to achieve the user's two-person pooling demand, the driver needs to first pick up the two passengers i and j and then send them to destinations respectively. In the formula, for O.sub.i.fwdarw.O.sub.j.fwdarw.D.sub.i.fwdarw.D.sub.j and O.sub.i.fwdarw.O.sub.j.fwdarw.D.sub.j.fwdarw.D.sub.i, all the paths are represented by nodes which are passed through in sequence, which are all the possible travel paths of the two-person passenger combination {i, j} when the user i is the first passenger. P.sub.ij represents a travel path set of the two-person passenger combination {i, j} when the user i is the first passenger, t(Ou, O.sub.j), t(O.sub.j, D.sub.i), t(D.sub.i, D.sub.j), t(O.sub.j, D.sub.j), and t(D.sub.i, D.sub.j) represent travel times between two nodes in parentheses; t(O.sub.i, O.sub.j)+t(O.sub.j, D.sub.i)+t(D.sub.i, D.sub.j) and t(O.sub.i, O.sub.j)+t(O.sub.j, D.sub.j)+t(D.sub.j, D.sub.i) each indicate the possible travel time of the two-person passenger combination {i, j} when the user i is the first passenger. r.sub.ij represents the shortest passenger travel time of the two-person passenger combination {i, j} when the user i is the first passenger. a quantity of users in RP.sub.2 is |RP.sub.2|, then the user iRP.sub.2 forms (|RP.sub.2|1) two-person passenger combinations with other users, and the smart phone of the user i E RP.sub.2 needs to perform no less than (|RP.sub.2|1) times of calculations.

[0120] 2) The system compares the shortest passenger travel times when different users in respective two-person passenger combinations serve as the first passenger, and determines the shortest passenger travel time and travel path of each two-person passenger combination.

[0121] Within the two-person passenger combination {i, j}, a sum of the shortest passenger travel times r.sub.ij and r.sub.ji with the user i and the user j as the first passenger are compared with each other, the shortest passenger travel time r.sub.ij of the two-person passenger combination is determined, and a travel path corresponding to r.sub.ij is recorded. A formula is as follows:

[00023]$r_{\stackrel{}{ij}}=\min \left\{r_{\mathrm{ij}},r_{ji}\right\}$

since

[00024]$\frac{.Math.{\mathrm{RP}}_2.Math.\left(.Math.{\mathrm{RP}}_2.Math.-1\right)}{2}$

possible two-person passenger combinations can be formed within the main user set 2 RP.sub.2, the system cloud end server needs to perform no less than

[00025]$\frac{.Math.{\mathrm{RP}}_2.Math.\left(.Math.{\mathrm{RP}}_2.Math.-1\right)}{2}$

times of comparisons.

[0122] Under the premise of existence of the user jRP.sub.2 \{i} in the two-person passenger combination {i, j}, there are parameters r.sub.ii and variables x.sub.ii about the two-person passenger combination {i, i} in the following 0-1 programming model. For this purpose, if the Inf=99999 in the system is set, then:

[00026]$r_{\stackrel{}{ii}}=\mathrm{Inf},iR{P}_2$

after calculation, the shortest passenger travel time of the two-person passenger combination is:

TABLE-US-00002 TABLE 2 Shortest passenger travel time for the two-person passenger combination (two-person pooling) Passenger 1 2 3 4 5 6 7 8 9 10 11 12 1 99999 106.05 103.84 140.68 116.25 62.37 142.9 85.85 144.13 87.19 37.81 76.11 2 106.05 99999 120.57 60.25 148.12 103.38 103.89 85.8 145.68 144.13 134.09 148.46 3 103.84 120.57 99999 73.52 145.25 49.8 89.33 62.29 85.54 66.53 122.09 55.21 4 140.68 60.25 73.52 99999 61.47 151.2 34.27 163.49 126.34 99.3 155.53 87.69 5 116.25 148.12 145.25 61.47 99999 113.95 87.29 107.52 145.97 13.02 161.96 92.79 6 62.37 103.38 49.8 151.2 113.95 99999 141.34 164.79 86.2 78.57 58.82 88.05 7 142.9 103.89 89.33 34.27 87.29 141.34 99999 114.34 91.81 118.84 37.94 81.86 8 85.85 85.8 62.29 163.49 107.52 164.79 114.34 99999 116.99 71.87 74.28 152.58 9 144.13 145.68 85.54 126.34 145.97 86.2 91.81 116.99 99999 56.97 134.55 86 10 87.19 144.13 66.53 99.3 13.02 78.57 118.84 71.87 56.97 99999 86.51 134.4 11 37.81 134.09 122.09 155.53 161.96 58.82 37.94 74.28 134.55 86.51 99999 28.1 12 76.11 148.46 55.21 87.69 92.79 88.05 81.86 152.58 86 134.4 28.15 99999

[0123] 3) all the users within the set RP.sub.B2 are formed into a passenger combination RP.sub.C2, and the shortest passenger travel time and travel path of the passenger combination are calculated.

Under the user's two-person pooling demand, due to |RP.sub.B2|=1, RP.sub.B2={13}; all users in the set RP.sub.B2 are formed into one passenger combination represented by RP.sub.C2, i.e. RP.sub.C2={13}, then =t(O.sub.m, D.sub.m)=t(58, 162)=55.896, and the path is 58.fwdarw.162. {RP.sub.C2} is allowed to represent the passenger combination set formed by the passenger combinations RP.sub.C2.

[0124] 4) A matching problem of the two-person passenger combination is solved, and a two-person pooling passenger matching scheme with an optimal total passenger travel time is obtained.

[0125] For any user iRP.sub.2, he can only form a two-person passenger combination with another user jRP.sub.2\{i} ultimately. With a goal of minimizing the total passenger travel time, while under the user's two-person pooling demand, the matching problem of the two-person passenger combination can be transformed into a 0-1 programming model as follows:

[00027]$\min \underset{i=1}{\overset{.Math.{\mathrm{RP}}_2.Math.}{.Math.}}\underset{j=1}{\overset{.Math.{\mathrm{RP}}_2.Math.}{.Math.}}{r}_{\stackrel{}{ij}}{x}_{ij}$$s.t.\{\begin{array}{c}\underset{i=1}{\overset{.Math.{\mathrm{RP}}_2.Math.}{.Math.}}{x}_{\mathrm{ij}}=1,j{\mathrm{RP}}_2\\ \underset{j=1}{\overset{.Math.{\mathrm{RP}}_2.Math.}{.Math.}}{x}_{\mathrm{ij}}=1,i{\mathrm{RP}}_2\\ x_{\mathrm{ij}}=0\mathrm{or}1,i,j{\mathrm{RP}}_2\end{array}$

[0126] where x.sub.ij is a 0-1 variable: in a solution result of the model, if the user i and the user j constitute a two-person passenger combination {i, j}, then x.sub.ij=1, otherwise x.sub.ij=0.

[0127] Since there is no constraint ij in the 0-1 programming model, there is a repeated two-person passenger combination {i, i} and relevant parameter r.sub.ii and variable x.sub.ii in the model, but it is impossible for a user i to form the two-person passenger combination with himself in practice, and in order to enable the 0-1 programming model to solve the two-person pooling passenger matching process, the shortest passenger travel time r.sub.ii for the repeated two-person passenger combination {i, i} is set as follows:

[00028]$r_{\stackrel{}{ii}}=\mathrm{Inf},iR{P}_2$

in the formula, Inf represents a positive infinite constant.

[0128] Hungarian algorithm is used to solve the 0-1 programming model, and an obtained solution vector is x=(x.sub.ij, iRP.sub.2, jRP.sub.2).sup.T, the two-person passenger combination corresponding to x.sub.ij=1 is screened out, the passenger combination set RP.sub.2_2 is formed, which is referred to as the main passenger combination set 2, a quantity of set elements of which is RP.sub.2_2=|RP.sub.2|/2.

[0129] The set RC.sub.2=RP.sub.2_2{RP.sub.C2} is allowed to represent the passenger combination set formed by the users of the two-person pooling demand, i.e. a union set of RP.sub.2_2 and {RP.sub.C2}. The travel path and travel time of each passenger combination in the set RC.sub.2 are recorded, and a quantity |RC.sub.2| of set elements represents a quantity of the passenger combinations under the two-person pooling demand.

[0130] The travel paths and travel times for the passenger combinations in Table 3.

TABLE-US-00003 TABLE 3 Passenger matching results of two-person pooling Passenger Travel combination Travel path time Set {1, 11} 341 .fwdarw. 406 .fwdarw. 387 .fwdarw. 260 37.812 RP.sub.2_2 {2, 8} 391 .fwdarw. 199 .fwdarw. 432 .fwdarw. 445 85.797 {3, 6} 424 .fwdarw. 118 .fwdarw. 146 .fwdarw. 290 49.798 {4, 7} 433 .fwdarw. 315 .fwdarw. 400 .fwdarw. 391 34.272 {5, 10} 154 .fwdarw. 175 .fwdarw. 490 .fwdarw. 483 13.016 {9, 12} 107 .fwdarw. 464 .fwdarw. 342 .fwdarw. 99 85.998 {13} 58 .fwdarw. 162 55.896 RP.sub.B2

2. Three-Person Pooling

[0131] 1) The system cloud end server pre-supplements a certain quantity of virtual users on the basis of RP.sub.3 to form a generalized user set RP.sub.E3; the user in RP.sub.3 calculates the shortest passenger travel time and travel path of all possible two-person passenger combinations with himself as the first passenger, and returns a calculation result to the system cloud end server;

[0132] A quantity |RP.sub.3|/3 of virtual users are pre-supplemented before passenger combination matching under the three-person pooling demand of the user, and the travel start points O.sub.i and the travel end points D.sub.i of the virtual users are all virtual nodes; the virtual node does not exist in a real urban road network, and the distance to any real node is positively infinite. |RP.sub.3|/3 virtual users constitute a virtual user set RP.sub.V3, and a union set of the virtual user set RP.sub.V3 and RP.sub.3 is the generalized user set RP.sub.E3, namely RP.sub.E3=RP.sub.3RP.sub.V3, Inf representing a positive infinite constant.

[0133] The smart phone of the user iRP.sub.3 receives the data file File3 sent by the cloud end. After receiving the File3, the smart phone of the user i takes the user i as the first passenger, calculates the shortest travel path and travel time of the two-person passenger combination formed by the user i and another user jRP.sub.3 \{i}, and returns the calculation result to the system cloud end server. A calculation formula is as follows:

[00029]$P_{ij}=\left\{O_i.fwdarw.O_j.fwdarw.D_i.fwdarw.D_j,O_i.fwdarw.O_j.fwdarw.D_j.fwdarw.D_i\right\}$$r_{ij}=\min \left\{t\left(O_i,O_j\right)+t\left(O_j,D_i\right)+t\left(D_i,D_j\right),t\left(O_i,O_j\right)+t\left(O_j,D_j\right)+t\left(D_j,D_i\right)\right\}$

as stated above, taking the user i as the first passenger means taking the start point O.sub.i of the user i as a jumping-off place, so that the user i is the passenger gets aboard at first, and the driver firstly receives the users i and j as the two passengers, and then send them to destinations respectively. In the formula, in both O.sub.i-O.sub.j.fwdarw.D.sub.i.fwdarw.D.sub.j and O.sub.i.fwdarw.O.sub.j.fwdarw.D.sub.j.fwdarw.D.sub.i, paths are represented by nodes which are passed through successively, and all possible travel paths of the two-person passenger combination {i, j} are taken when the user i is the first passenger, and P.sub.ij represents a travel path set of the two-person passenger combination {i, j} when the user i is the first passenger, and t(O.sub.i, O.sub.j), t(O.sub.j, D.sub.i), t(D.sub.i, D.sub.j), t(O.sub.j, D.sub.j), and t(D.sub.i, D.sub.j) all represent travel time between two nodes in parentheses, t(O.sub.i, O.sub.j)+t(O.sub.j, D.sub.i)+t(D.sub.i, D.sub.j) and t(O.sub.i, O.sub.j)+t(O.sub.j, D.sub.j)+t(D.sub.j, D.sub.i) both represent possible travel time of the two-person passenger combination {i, j} when the user i is the first passenger, and r.sub.ij represents a shortest passenger travel time of the two-person passenger combination {i, j} when the user {i, j} is the first passenger.

[0134] A quantity of users in RP.sub.3 is |RP.sub.3|, then the user iRP.sub.3 forms (|RP.sub.3|1) two-person passenger combinations with other users, and the smart phone of the user iRP.sub.3 needs to perform no less than (|RP.sub.3|1) times of calculations.

[0135] 2) The system cloud end server compares the shortest passenger travel times when different users in respective two-person passenger combinations serve as the first passenger, and determines the shortest passenger travel time and travel path of each two-person passenger combination.

[0136] Within the two-person passenger combination {i, j}, a sum of the shortest passenger travel times r.sub.ij and r.sub.ji with the user i and the user j as the first passenger are compared with each other, the shortest passenger travel time r.sub.ij of the two-person passenger combination is determined, and a travel path corresponding to r.sub.ij is recorded. A formula is as follows:

[00030]$r_{\stackrel{}{ij}}=\min \left\{r_{\mathrm{ij}},r_{ji}\right\}$

since

[00031]$\frac{.Math.{\mathrm{RP}}_3.Math.\left(.Math.{\mathrm{RP}}_3.Math.-1\right)}{2}$

possible two-person passenger combinations can be formed within the main user set 3 RP.sub.3, the system cloud end server needs to perform no less than

[00032]$\frac{.Math.{\mathrm{RP}}_3.Math.\left(.Math.{\mathrm{RP}}_3.Math.-1\right)}{2}$

times of comparisons.

[0137] Real users and virtual users are collectively referred to as generalized users. If the passengers i and j in the two-person passenger combination {i, j} are both real users, then {i, j} is taken as the real two-person passenger combination; if the passenger i in the two-person passenger combination {i, j} is a real user and the passenger j is a virtual user, or if the passenger i is a virtual user and the passenger j is a real user, then {i, j} is taken as the mixed two-person passenger combination; if the passengers i and j in the two-person passenger combination {i, j} are both virtual users, then {i, j} is taken as a virtual two-person passenger combination. The real two-person passenger combination, the mixed two-person passenger combination and the virtual two-person passenger combination are collectively referred to as the generalized two-person passenger combination.

[0138] The generalized two-person passenger combination {i, j} also has the premise of generalized user jRP.sub.E3 \{i}, but it is not constrained to ij in the 0-1 programming model. The 0-1 programming model not only has the repeated two-person passenger combination {i, i} and the related parameter r.sub.ii and variable x.sub.ii, but also has the virtual user and the mixed two-person passenger combination and the virtual two-person passenger combination which may be formed.

[0139] In order to make it possible for the subsequent 0-1 programming model to solve the first passenger matching process of three-person pooling, the shortest passenger travel time of any generalized two-person passenger combination {i, j} is set as follows: [0140] if iRP.sub.3, jRP.sub.3 and ij, it is the real two-person passenger combination, and the shortest passenger travel time thereof is ; [0141] if iRP.sub.3, jRP.sub.V3 or jRP.sub.3, iRP.sub.V3, it is the mixed two-person passenger combination, and the shortest passenger travel time thereof is Inf; [0142] if iRP.sub.V3, jRP.sub.V3 and ij, it is the virtual two-person passenger combination, and the shortest passenger travel time thereof is 2*Inf.

[0143] For the repeated two-person passenger combination {i, i}, the shortest passenger time thereof is set as 2*Inf.

[0144] The shortest passenger travel time for the generalized two-person passenger combination at this time is shown in Table 4:

TABLE-US-00004 TABLE 4 Shortest passenger travel time for generalized two-person passenger combination (three-person pooling) Passenger 1 2 3 4 5 6 7 8 1 199998 95.33 50.79 63.36 176.58 77.01 111.74 72.42 2 95.33 199998 166.02 70.35 43.02 106.74 115.14 115.67 3 50.79 166.02 199998 80.12 90.06 11468 86.2 83.18 4 63.36 70.35 80.12 199998 61.75 152.43 93.54 76.63 5 176.58 43.02 90.06 61.75 199998 102.6 86.61 128.21 6 77.01 106.74 114.68 152.43 102.6 199998 82.98 99.07 7 111.74 115.14 86.2 93.54 86.61 82.98 199998 72.43 8 72.42 115.67 83.18 76.63 128.21 99.07 72.43 199998 9 131.46 86.08 100.43 56.15 111.79 100.71 133.4 127.1 11 81.52 195.25 96.57 129.31 109.67 172 123.09 84.24 12 153.13 143.74 146.66 107.12 100.78 69.31 91.67 191.82 13 184.93 97.66 164.49 84.95 107.49 101.52 75.61 34.74 1 99999 99999 99999 99999 99999 99999 99999 99999 2 99999 99999 99999 99999 99999 99999 99999 99999 3 99999 99999 99999 99999 99999 99999 99999 99999 4 99999 99999 99999 99999 99999 99999 99999 99999 Passenger 9 11 12 13 1 2 3 4 1 131.46 81.52 153.13 18493 99999 99999 99999 99999 2 86.08 195.25 143.74 97.66 99999 99999 99999 99999 3 100.43 96.57 146.66 164.49 99999 99999 99999 99999 4 56.15 12931 107.12 84.95 99999 99999 99999 99999 5 111.79 109.67 100.78 107.49 99999 99999 99999 99999 6 100.71 172 69.31 101.52 99999 99999 99999 99999 7 133.4 123.09 91.67 75.6 99999 99999 99999 99999 8 127.1 84.24 191.82 34.74 99999 99999 99999 99999 9 199998 123.16 117.4 99.99 99999 99999 99999 99999 11 123.16 199998 144.75 73.82 99999 99999 99999 99999 12 117.4 144.75 199998 115.13 99999 99999 99999 99999 13 99.99 73.82 115.13 199998 99999 99999 99999 99999 1 99999 99999 99999 99999 199998 199998 199998 199998 2 99999 99999 99999 99999 199998 199998 199998 199998 3 99999 99999 99999 99999 199998 199998 199998 199998 4 99999 99999 99999 99999 199998 199998 199998 199998

[0145] The passengers with negative numbers in Table 4 are all virtual passengers.

[0146] 3) All the users within secondary user set 3 RP.sub.B3 are formed into a passenger combination RP.sub.C3, and the shortest passenger travel time r.sub.C3 and travel path of the passenger combination are calculated.

[0147] Under the user's three-person pooling demand, due to |RP.sub.B3|=1, RP.sub.B3={10}; all users in the set RP.sub.B3 are formed into one passenger combination represented by RP.sub.C3, that is a secondary passenger combination 3 RP.sub.C3={10}, then =t(O.sub.m, D.sub.m)=t(100,459)=69.585, and the path is 100.fwdarw.459. {RP.sub.C3} is allowed to represent the passenger combination set formed by the passenger combinations RP.sub.C3, referred to as a secondary passenger combination set 3.

[0148] 4) To solve a first passenger combination matching problem under the three-person pooling demand of the user, |RP.sub.E3|/2 generalized two-person passenger combinations is matched in the generalized user set RP.sub.E3, and then real users in |RP.sub.3|/2 real two-person passenger combinations and |RP.sub.3|/2 mixed two-person passenger combinations are selected out.

[0149] The first passenger combination matching process under the of three-person pooling demand needs to match |RP.sub.E3|/2 generalized two-person passenger combinations in the generalized user set RP.sub.E3. For any generalized user iRP.sub.E3, he can only form a generalized two-person passenger combination with another generalized user jRP.sub.E3 \{i} ultimately. With a goal of minimizing the total passenger travel time, the matching problem of the generalized two-person passenger combination can be transformed into a 0-1 programming model as follows:

[00033]$\min \underset{i}{.Math.}\underset{j}{.Math.}{r}_{\stackrel{}{ij}}{x}_{ij}$$s.t.\{\begin{array}{c}\underset{i}{.Math.}{x}_{\mathrm{ij}}=1,j{\mathrm{RP}}_{E3}\\ \underset{j}{.Math.}{x}_{\mathrm{ij}}=1,i{\mathrm{RP}}_{E3}\\ x_{\mathrm{ij}}=0\mathrm{or}1,i,j{\mathrm{RP}}_{E3}\end{array}$

[0150] where x.sub.ij is a variable from 0 to 1; in a model solution result, if the generalized user i and the generalized user j constitute the generalized two-person passenger combination {i, j}, then x.sub.ij=1, otherwise x.sub.ij=0.

[0151] The Hungarian algorithm is applied to solve the 0-1 programming model, and the solved vector is x=(x.sub.ij, iRP.sub.E3, jRP.sub.E3).sup.T, 2*(|RP.sub.3|/3) generalized two-person passenger combinations corresponding to x.sub.ij=1 are screened out, wherein there are |RP.sub.3|/3 real two-person passenger combinations and |RP.sub.3|/3 mixed two-person passenger combinations.

[0152] The |RP.sub.3|/3 real two-person passenger combinations are screened out to construct the real two-person passenger combination set RP.sub.3_2 and the quantity of set elements is |RP.sub.3_2|=|RP.sub.3|/3=4.

[0153] Then the real users in |RP.sub.3|/3=4 mixed two-person passenger combinations are screened out to construct the user set RP.sub.3_1 and the quantity of set elements is |RP.sub.3_1|=|RP.sub.3|/3=4.

[0154] The sets RP.sub.3_2 and RP.sub.3_1 resulting from the processing are respectively:

[00034]$\begin{array}{c}R{P}_{3\_2}=\left\{\left\{1,3\right\},\left\{2,5\right\},\left\{4,9\right\},\left\{8,13\right\}\right\}\\ {\mathrm{RP}}_{3\_1}=\left\{6,7,11,12\right\}\end{array}$

after the system cloud end server completes the first passenger combination matching of the three-person pooling, the start points and the end points of two users of each real two-person passenger combination in the set RP.sub.3_2 are extracted to form a data file File3_2; start points and end points of each user in the set RP.sub.3_1 are extracted to form a data file File3_1. After forming the data files, the system cloud sends the data files File3-1 and File3-2 to all the smart phones of the users in the set RP.sub.3 again.

[0155] 5) The current passenger is taken as the first passenger, and the shortest passenger travel time and travel path of the three-person passenger combination are calculated.

[0156] The first pass passenger combination matching process of three-person pooling can obtain a real two-person passenger combination set RP.sub.3_2 and a user set RP.sub.3_1. A real two-person passenger combination {i, j}RP.sub.3_2 and a real user k E RP.sub.3_1, then the user i, the user j and the user k can constitute a three-person passenger combination {i, j, k}.

[0157] A step of calculating the shortest passenger travel time of the three-person passenger combination {i, j, k} is as follows:

[0158] Smart phones of the user i, j{i, j}, {i, j}RP.sub.3_2 and the user kRP.sub.3_1 receive data files File3_1 and File3_2 sent by the cloud end.

[0159] After receiving the files File3_1 and File3_2, the smart phone of the user i calculates the shortest travel path and travel time of the three-person passenger combination formed by the user i, the user j and the user k with the user i as the first passenger. The calculation results are returned to the system cloud end server. A calculation formula is as follows:

[00035]$P_{\mathrm{ijk}}=\left\{\begin{array}{c}{O}_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_i.fwdarw.D_j.fwdarw.D_k,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_i.fwdarw.D_j.fwdarw.D_k,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_i.fwdarw.D_k.fwdarw.D_j,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_i.fwdarw.D_k.fwdarw.D_j,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_j.fwdarw.D_i.fwdarw.D_k,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_j.fwdarw.D_i.fwdarw.D_k,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_j.fwdarw.D_k.fwdarw.D_i,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_j.fwdarw.D_k.fwdarw.D_i,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_k.fwdarw.D_i.fwdarw.D_j,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_k.fwdarw.D_i.fwdarw.D_j,\\ O_i.fwdarw.O_j.fwdarw.O_k.fwdarw.D_k.fwdarw.D_j.fwdarw.D_i,\\ O_i.fwdarw.O_k.fwdarw.O_j.fwdarw.D_k.fwdarw.D_j.fwdarw.D_i,\end{array}\right\}$$r_{\mathrm{ijk}}=\min \left\{\begin{array}{c}t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_i\right)+t\left(D_i,D_j\right)+t\left(D_j,D_k\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_i\right)+t\left(D_i,D_j\right)+t\left(D_j,D_k\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_i\right)+t\left(D_i,D_k\right)+\left(D_k,D_j\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_i\right)+t\left(D_i,D_k\right)+t\left(D_k,D_j\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_j\right)+t\left(D_j,D_i\right)+t\left(D_i,D_k\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_j\right)+t\left(D_j,D_i\right)+t\left(D_i,D_k\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_j\right)+t\left(D_j,D_k\right)+t\left(D_k,D_i\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_j\right)+t\left(D_j,D_k\right)+t\left(D_k,D_i\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_k\right)+t\left(D_k,D_i\right)+t\left(D_i,D_j\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_k\right)+t\left(D_k,D_i\right)+t\left(D_i,D_j\right),\\ t\left(O_i,O_j\right)+t\left(O_j,O_k\right)+t\left(O_k,D_k\right)+t\left(D_k,D_j\right)+t\left(D_j,D_i\right),\\ t\left(O_i,O_k\right)+t\left(O_k,O_j\right)+t\left(O_j,D_k\right)+t\left(D_k,D_j\right)+t\left(D_j,D_i\right)\end{array}\right\}$

as described above, in order to achieve the three-person pooling demand of the user, the driver needs to pick up three passengers and then send them to the destinations respectively. In the formula, P.sub.ijk represents a travel path set of the three-person passenger combination {i, j, k} when the user i is the first passenger; the elements O.sub.j.fwdarw.O.sub.i.fwdarw.O.sub.k.fwdarw.D.sub.i.fwdarw.D.sub.j.fwdarw.D.sub.k therein are all paths, which are represented by nodes that are passed through in sequence. r.sub.ijk represents the shortest passenger travel time of the three-person passenger combination {i, j, k} when the user i is the first passenger; the elements such as t(O.sub.k, O.sub.j)+t(O.sub.j, O.sub.i)+t(O.sub.i, D.sub.i)+t(D.sub.i, D.sub.j)+t(D.sub.j, D.sub.k) all represent possible travel times for the three-person passenger combination {i, j, k}.

[0160] 6) The system cloud end server compares the shortest passenger travel times when different users in respective three-person passenger combinations serve as the first passenger, and determines the shortest passenger travel time and travel path of each three-person passenger combination.

[0161] Within the three-person passenger combination {i, j, k}, the system compares the shortest passenger travel times r.sub.ijk, r.sub.jik, and r.sub.kij of the user i, the user j, and the user k as the first passenger, determines the shortest passenger travel time r.sub.jik of the three-person passenger combination, and records a travel path corresponding to . A formula is as follows:

[00036]$r_{\stackrel{\_}{\mathrm{ijk}}}=\min \left\{r_{\mathrm{ijk}},r_{\mathrm{jik}},r_{kij}\right\}$

since the real two-person passenger combination set RP.sub.3_2 and the user set RP.sub.3_1 can form

[00037]$\frac{{.Math.{\mathrm{RP}}_3.Math.}^2}{9}$

possible two-person passenger combinations, the system cloud end server needs to perform no less than

[00038]$\frac{{.Math.{\mathrm{RP}}_3.Math.}^2}{9}$

times of comparisons.

[0162] After calculation, the shortest passenger travel time of the three-person passenger combination at this time is as shown in Table 5:

TABLE-US-00005 TABLE 5 Shortest passenger travel time for three-person passenger combination (three-person pooling) Passenger {1, 3} {2, 5} {4, 9} {8, 13} 6 75.61954 96.55938 105.0158 162.8163 7 122.7871 93.90218 144.6582 71.89998 11 160.6306 87.97411 172.3003 129.1913 12 73.84387 123.8725 133.9681 137.4431

[0163] 7) A second passenger combination matching problem of three-person pooling is solved, and aoptimal three-person pooling passenger matching scheme with an optimal passenger travel time is obtained.

[0164] For any two-person passenger combination {i, j}RP.sub.3_2, a three-person passenger combination can only be formed by him with another user kRP.sub.3_1 ultimately. With a goal of minimizing the total passenger travel time, while under the user's three-person pooling demand, the matching problem of the three-person passenger combination can be transformed into a 0-1 programming model as follows:

[00039]$\min \underset{\left\{i,j\right\}}{.Math.}\underset{k}{.Math.}{r}_{\stackrel{\_}{\mathrm{ijk}}}{x}_{ijk}$$s.t.\{\begin{array}{c}\underset{\left\{i,j\right\}}{.Math.}{x}_{\mathrm{ijk}}=1,k{\mathrm{RP}}_{3_1}\\ \underset{k}{.Math.}{x}_{\mathrm{ijk}}=1,\left\{i,j\right\}{\mathrm{RP}}_{3_2}\\ x_{\mathrm{ijk}}=0\mathrm{or}1,\left\{i,j\right\}{\mathrm{RP}}_{3_2},k{\mathrm{RP}}_{3_1}\end{array}$

where x.sub.ijk is a variable from 0 to 1; in a solution result of the model, if the two-person passenger combination {i, j} and the user k constitute the three-person passenger combination {i, j, k}, then x.sub.ijk=1, otherwise x.sub.ijk=0.

[0165] Hungarian algorithm is used to solve the 0-1 programming model, and an obtained solution vector is x=(x.sub.ijk, {i, j}RP.sub.3_2, kRP.sub.3_1).sup.T. The three-person passenger combination corresponding to x.sub.ijk=1 is screened out, the passenger combination set RP.sub.3_3 is constituted, which is referred to as the main passenger combination set 3, a quantity of set elements of which is |RP.sub.3_3|=|RP.sub.3|/3=4.

[0166] The set RC.sub.3=RP.sub.3_3{RP.sub.C3} is allowed to represent the passenger combination set formed by the users of the three-person pooling demand, i.e. a union set of RP.sub.3_3 and RP.sub.C3. Travel path and travel time for each passenger combination in the set RC.sub.3 are recorded. A quantity |RC.sub.3| of set elements represents the quantity of passenger combinations under the three-person pooling demand.

[0167] The travel paths and travel times for the passenger combinations in Table 6.

TABLE-US-00006 TABLE 6 Matching results of the three-person pooling Passenger Travel combination Travel path time Set {1, 3, 11} 492 .fwdarw. 168 .fwdarw. 235.fwdarw. 166 .fwdarw. 61 .fwdarw. 388 105.016 RP.sub.3_3 {2, 5, 12} 233 .fwdarw. 51 .fwdarw. 96 .fwdarw. 210 .fwdarw. 374 .fwdarw. 56 71.900 {4, 9, 7} 383 .fwdarw. 368 .fwdarw. 104 .fwdarw. 486 .fwdarw. 112 .fwdarw. 20 87.974 {8, 13, 6} 64 .fwdarw. 180 .fwdarw. 441 .fwdarw. 245 .fwdarw. 88 .fwdarw. 95 73.844 {10} 100 .fwdarw. 459 69.585 RP.sub.B3

[0168] The set RC is allowed to represent the passenger combination set formed by all users in the system, which is a union set of the passenger combination sets formed by users who have two-person pooling demand and three-person pooling demand, i.e. RC=RC.sub.2RC.sub.3. A quantity |RC| of set elements represents the quantity of passenger combinations in the system.

[0169] III. The passenger combinations and drivers in the system are matched. The system constructs a generalized driver set and a generalized passenger combination set, a 0-1 programming model of a driver-passenger combination matching process is solved, and screening is performed to obtain the driver-passenger combination matching scheme.

[0170] 1) The passenger combination and the driver in the system are matched to form the driver-passenger combination, and a driver-passenger travel time and travel path of each driver-passenger combination are calculated.

[0171] The set of free drivers in the current system is V, wherein a quantity |V| of set elements represents a quantity of drivers in the system. The specific set information is shown in Table 7:

TABLE-US-00007 TABLE 7 Driver set information Driver Driver Driver serial Driver serial Driver serial Driver number position number position number position 1 228 11 232 21 66 2 279 12 386 22 219 3 361 13 340 23 142 4 158 14 375 24 181 5 318 15 443 25 139 6 92 16 311 26 245 7 221 17 338 27 399 8 497 18 50 28 265 9 488 19 154 29 447 10 277 20 241 30 254

[0172] For any driver vV, V_O.sub.v is allowed to represent a current position of v; for any passenger combination eRC, C_O.sub.e and C_D.sub.e are allowed to represent a start point and an end point of a passenger combination travel path of e, and C_T.sub.e represents a passenger combination travel time of e.

[0173] The driver v EV and the passenger combination eRC are matched to constitute the driver-passenger combination {v, e}, and a travel trajectory thereof is that the driver v starts from the current position V_O.sub.v to C_O.sub.e for picking up the first passenger until C_D.sub.e where all the passengers get off the vehicle.

p.sub.ve is allowed to represent a travel path of the driver-passenger combination {v, e}, and t.sub.ve is allowed to represent a path travel time of the driver-passenger combination {v, e}, i.e. a driver-passenger travel time. A calculation formula is:

[00040]$\begin{array}{c}{p}_{ve}=\left\{{\mathrm{V\_O}}_v.fwdarw.{\mathrm{C\_O}}_e.fwdarw.{\mathrm{C\_D}}_e\right\}\\ t_{ve}=t\left({\mathrm{V\_O}}_v,{\mathrm{C\_O}}_e\right)+{\mathrm{C\_T}}_e\end{array}$

where p.sub.ve represents a travel path from a current position V_O.sub.v to C_D.sub.e by the driver; and t(V_O.sub.v, C_O.sub.e) represents a travel time required by the driver v from the current position V_O.sub.v to the start point C_O.sub.e of the travel path of the passenger combination e.

[0174] If in the system the quantity of drivers is |V|=30 and the quantity of passenger combinations is |RC|=16, then there are |V|.Math.|RC|=480 possible driver-passenger combinations, and the driver-passenger travel time needs to be calculated for |V|.Math.|RC|=480 times.

[0175] 2) A preset quantity of drivers or passenger combinations are supplemented, so that a quantity of passenger combinations participating in matching is equal to a quantity of drivers, a matching problem of the driver-passenger combination is solved, and a driver-passenger matching scheme with an optimal total driver-passenger travel time is obtained.

[0176] A real driver and a virtual driver are collectively referred to as a generalized driver, and the real passenger combination and the virtual passenger combination are collectively referred to as the generalized passenger combination. The generalized driver and the generalized passenger combination are matched and can form a generalized driver-passenger combination.

[0177] If the driver v in the driver-passenger combination {v, e} is the real driver and the passenger combination e is the real passenger combination, then {v, e} is a real driver-passenger combination; otherwise, {v, e} is a virtual driver-passenger combination The real driver-passenger combination and the virtual driver-passenger combination are collectively referred to as the generalized driver-passenger combination.

[0178] Before solving the matching problem of driver-passenger combination, it is necessary to ensure that the quantity of passenger combinations participating in matching is equal to the quantity of drivers. Therefore, Inf is allowed to represent a sufficiently large, positive constant, a certain quantity of virtual drivers or virtual passenger combinations are supplemented according to actual situations, and a generalized driver set and a generalized passenger combination set are constructed. The specific processing is as follows:

[0179] If the quantity of real passenger combinations is greater than the quantity of real drivers, i.e. |RC|>|V|, (IRC||V|) virtual drivers are supplemented to the driver set V, constituting a generalized driver set V.sub.g. The generalized passenger combination set RC.sub.g is equal to the passenger combination set RC, i.e. RC.sub.g=RC. The driver-passenger travel time t.sub.ve=Inf for the virtual driver v and any generalized passenger combination eRC.sub.g.

[0180] If the quantity of real passenger combinations is less than the quantity of real drivers, i.e. |RC|<|V|, (|V||RC|) virtual passenger combinations are supplemented in the passenger combination set RC to form a generalized passenger combination set RC.sub.g. The generalized driver set V.sub.g is equal to the driver set V, i.e. V.sub.g=V. The driver-passenger travel time t.sub.ve=Inf for the virtual passenger combination e and any generalized driver vV.sub.g.

[0181] In this case |RC|<|V|, |V||RC|=3016=14 virtual passenger combinations are supplemented in the passenger combination set RC.

[0182] After completing the supplement of the virtual drivers or the virtual passenger combinations, the driver-passenger combination matching is performed for the generalized driver set and the generalized passenger combination set.

[0183] For any generalized driver vV.sub.g, a generalized driver-passenger combination can be formed by him with only one generalized passenger combination eRC.sub.g. To minimize the total driver-passenger travel time, the matching problem of the driver-passenger combination can be transformed into a 0-1 programming model as follows:

[00041]$\min \stackrel{.Math.V_g.Math.}{\underset{v=1}{.Math.}}\stackrel{.Math.{\mathrm{RC}}_g.Math.}{\underset{e=1}{.Math.}}{t}_{\mathrm{ve}}{y}_{ve}$$s.t.\{\begin{array}{c}\stackrel{.Math.{\mathrm{RC}}_g.Math.}{\underset{e=1}{.Math.}}{y}_{\mathrm{ve}}=1,e{\mathrm{RC}}_g\\ \stackrel{.Math.V_g.Math.}{\underset{v=1}{.Math.}}{y}_{\mathrm{ve}}=1,v{V}_g\\ y_{\mathrm{ve}}=0\mathrm{or}1,e{\mathrm{RC}}_g,v{V}_g\end{array}$

where y.sub.ve is a variable from 0 to 1; in a model solution result, if the generalized driver v and the generalized passenger combination e constitute the generalized driver-passenger combination {v, e}, then y.sub.ve=1, otherwise y.sub.ve=0.

[0184] Hungarian algorithm is applied to solve the 0-1 programming problem. The obtained solution vector is y=(y.sub.ve, vV.sub.g, eRC.sub.g).sup.T. The generalized driver-passenger combinations corresponding to y.sub.ve=1 are screened out to constitute a generalized driver-passenger combination set VRC.sub.g. Then the real driver-passenger combinations in the set VRC.sub.g are selected to form a driver-passenger combination set VRC, wherein a quantity |VRC| of the set elements is equal to a minimum value of the quantity |RC| of passenger combinations and the quantity |V| of drivers, with a quantity |VRC|=min {|RC|, |V|} of the set elements. Travel path and travel time for each driver-passenger combination are recorded.

[0185] The travel path and travel time for each driver-passenger combination in the set VRC are shown in Table 8.

TABLE-US-00008 TABLE 8 Driver-passenger matching results Passenger Travel Driver combination Travel path time Two-person pooling 20 {1, 11} 241 .fwdarw. 341 .fwdarw. 406 .fwdarw. 387 .fwdarw. 260 37.812 14 {2, 8} 375 .fwdarw. 391 .fwdarw. 199 .fwdarw. 432 .fwdarw. 445 85.797 9 {3, 6} 488 .fwdarw. 424 .fwdarw. 118 .fwdarw. 146 .fwdarw. 290 49.798 25 {4, 7} 139 .fwdarw. 433 .fwdarw. 315 .fwdarw. 400 .fwdarw. 391 34.272 19 {5, 10} 154 .fwdarw. 154 .fwdarw. 175 .fwdarw. 490 .fwdarw. 483 13.016 7 {9, 12} 221 .fwdarw. 107 .fwdarw. 464 .fwdarw. 342 .fwdarw. 99 85.998 13 {13} 340 .fwdarw. 58 .fwdarw. 162 55.896 Three-person pooling 17 {1, 3, 11} 338 .fwdarw. 492 .fwdarw. 168 .fwdarw. 235 .fwdarw. 105.016 166 .fwdarw. 61 .fwdarw. 388 4 {2, 5, 12} 158 .fwdarw. 233 .fwdarw. 51 .fwdarw. 96 .fwdarw. 71.900 210 .fwdarw. 374 .fwdarw. 56 10 {4, 9, 7} 277 .fwdarw. 383 .fwdarw. 368 .fwdarw. 104 .fwdarw. 87.974 486 .fwdarw. 112 .fwdarw. 20 18 {8, 13, 6} 50.fwdarw. 64 .fwdarw.180 .fwdarw. 441 .fwdarw. 73.844 245 .fwdarw. 88 .fwdarw. 95 26 {10} 245 .fwdarw. 100 .fwdarw. 459 69.585

[0186] IV. The cloud end sends the driver-passenger matching scheme to the phone App of the driver and the passenger, executes the matching scheme, and completes the on-line ride-sharing service shared travel.

[0187] The system sends the matching result and travel path to the mobile phone App of the driver and passenger respectively in the form of an order. After receiving the order, the driver travels according to the travel path given by the order, and sequentially receives and sends each passenger. The user waits on the spot to get on the vehicle and pays a certain fee to the driver according to the price calculated by App after arriving at the destination to get off the vehicle. When the last passenger gets out of the vehicle and the payment is completed, the present Internet contract shared travel is completed. The above-mentioned embodiments are only preferred embodiments of the present disclosure. It should be pointed out that for one having ordinary skill in the art, several improvements and equivalent replacements can be made without departing from the principles of the present disclosure. These technical solutions that improve and equivalently replace the claims of the present disclosure fall within the scope of protection of the present disclosure.