CN113393026B - Unmanned taxi transfer and path matching method - Google Patents

Abstract

The invention discloses an unmanned taxi transfer and route matching method, comprising the following steps: a background server collects basic demand information input by passengers _{P i} on a ride-sharing app; ground, search for all unbound passengers P _j in the request area, and perform initial binding; plan the route of the passenger group bound for the first time, and calculate whether the planned route meets the time constraint, if so, the final binding The passenger group, otherwise, add the passengers to the unbound set; match the final bound passenger group with the unmanned taxis in the unmanned taxi candidate set _Wc ; in the next time interval, update the unbounded set. The binding set W and the unmanned taxi candidate set W _c , and the transfer conditions are cyclically judged for the passengers in the newly joined and unbound sets until all passengers are assigned to the destination or there are no new passengers. The present invention has the advantages of increasing the unmanned taxi sharing rate, reducing the urban traffic congestion rate, and the like.

Description

An unmanned taxi transfer and path matching method

technical field

The invention relates to the technical field of intelligent transportation, in particular to an unmanned taxi transfer and path matching method.

Background technique

With the rapid development of autonomous driving technology in the transportation industry and the wide application of big data analysis, the main way for people to travel in the future will be driverless. However, the existing online car-hailing platforms can only allocate taxis to passengers at one time, and cannot intelligently allocate taxis in real time according to the situation on the road network, which is not enough to meet the needs of future driverless cars. In order to propose a more efficient matching algorithm, this patent proposes the definition of unmanned taxi transfer. Unmanned taxi transfer means that when passengers travel by unmanned taxis within a certain range, in order to save time and taxi costs, and increase the distance they share with others, a method of taking multiple unmanned taxis during the ride is adopted. way of taxi. When passengers travel in traditional taxis, they sometimes encounter the situation that there is no idle vehicle in the current time period or there is no vehicle on the way, and the waiting time is too long. The unmanned taxi transfer method can reduce the waiting time of passengers. It is of great significance to speed up the operation efficiency of unmanned taxis and further reduce the urban traffic congestion rate.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to provide an unmanned taxi transfer and route matching method, which can effectively solve the problem of passengers' second transfer and reduce the waiting time, substantially increase the carpooling rate again, and reduce the urban Traffic congestion rate.

In order to solve the above technical problems, the present invention provides an unmanned taxi transfer and path matching method, comprising the following steps:

S1. The background server collects the basic demand information input by the passenger Pi on the ride-sharing app, including the origin O _i , the destination D _j , the departure time T ₀ , the expected arrival time _{T t ,} and the allowable delay time T _d ;

S2. According to the origin O _i and the destination D _j submitted by the passenger _Pi , search for all the unbound passengers P _j in the request area, that is, the passengers in the unbound set W, and compare the basic demand information of the passenger P _i and the information of the unbound passenger P _j , according to the initial transfer conditions, filter out the passenger groups that meet the transfer conditions, and bind them for the first time, and then enter step S3; if there is no unbound matching with the passenger P _i Passenger P _j , directly add passenger P _i to the unbound set W, the matching ends, and the matching is performed again in the next time interval;

S3. Use the improved route algorithm to plan the route of the passenger group bound for the first time, and calculate whether the planned route meets the time constraint. If so, the passenger group is finally bound, and the passenger P _j in the passenger group After leaving the unbound set W, enter step S4; otherwise, add P _i to the unbound set W, and the matching ends;

S4, matching the final bound passenger group with the unmanned taxis in the unmanned taxi candidate set _Wc ;

S5. In the next time interval, update the unbound set W and the driverless taxi candidate set W _c , and cyclically judge the transfer conditions for the passengers in the newly added and unbound sets, until all passengers are assigned to destination or until there are no new passengers.

Further, the specific process of screening out the passenger groups that meet the transfer conditions according to the initial transfer conditions is as follows:

A1. Establish the center point;

Extract the coordinates of the origin O _i and destination D _j of the passenger P _i and the coordinate points of other unbound passengers P _j in the area requested by the passenger P _i , and determine the minimum range including all passengers, that is, by The rectangle bounded by max{X _i ,X _j }, min{X _i ,X _j }, max{Y _i ,Y _j }, min{Y _i ,Y _j }, and then:

as the center point;

A2, route change;

Connect each passenger's path as follows:

Y_j)→(X_j，Y_j)

Y _j )→(X _j , Y _j )

A3. Determine the passenger's path coincidence:

If the paths of two passengers P _i and P _j overlap from a certain node, that is, at least two nodes are the same, and the vector directions formed by connecting the nodes are the same, then the two passengers P _i and P are initially bound. _j , get the passenger group; if there are multiple passengers P _j and passengers P _i that _overlap at the same time _, they will be bound in pairs according to the time sequence of the overlapping nodes; The paths from _i to the destination D _j do not overlap, so the passenger _Pi is added to the unbound set W.

Further, step S3 uses the improved path algorithm to plan the path of the passenger group bound for the first time, and the specific process of determining whether the binding is finally performed is as follows:

B1. Use the Dijakstra algorithm to calculate the shortest paths of the two passengers P _i and P _j that have been finally bound respectively, and calculate their corresponding arrival times T _t ;

B2. Use the DFS algorithm to arrange all feasible paths for passengers Pi and P _j from the origin O _i to the destination D _{j respectively} ;

B3. Calculate the path similarity, integrate the two paths with high similarity, and confirm the final path trajectories of passengers P _i and P _j ;

B4. Calculate the time required for the final path trajectory of passengers P _i and P _j to determine whether they are within the time constraint [T ₀ , T _t + T _d ]; if both passengers P _i and P _j arrive within the time constraint range Their respective destinations, the binding can be finally confirmed, and the path trajectories of passengers P _i and P _j can be determined respectively; if at least one passenger is not within the time constraint, the final binding is not confirmed, and the passenger P _i is sent to the destination. Bind set W.

Further, the specific process of matching driver and passenger is as follows:

C1. Determine whether the current number of unmanned taxi passengers L _n is equal to 2; if so, it means that the unmanned taxi is fully loaded and no more passengers can be carried; if L _n is less than 2, the unmanned taxi is added to the unmanned taxi In the car candidate set W _c ;

C2. Allocate vehicles for bound passenger groups;

If there is an unmanned taxi with a passenger number L _n of 0 in the unmanned taxi candidate set W _c , according to the distance between the unmanned taxi and the passenger P _i , the one with the closest Manhattan distance will be matched; There is no unmanned taxi with the number of passengers L _{n equal} to 0 in the candidate set W _c of the vehicle, then in the candidate set W _c of the unmanned taxi, the unbound taxis taken by the passengers P _j in the set W are not bound According to the current location Sp of the unmanned taxi taken by the passenger _{P j} , the position N _s expected to arrive in the next time interval and the final destination T _j at the current moment, compare the bound passengers in turn. information, if the starting place O _i of the passenger _{P i} is the same as the current location Sp of the unmanned taxi, or the location N _s to be reached in the next time interval, or the final destination T _j , or the Manhattan distance is similar , then bind the passenger _Pi and the unmanned taxi information; if the passenger _Pi still does not match the unmanned taxi at this time, wait for the matching of the unmanned taxi in the next time period; once the unmanned taxi matches the passenger _Pi Binding, that is, remove the unmanned taxi from the unmanned taxi candidate set W _c , regardless of whether the number of passengers L _n of the unmanned taxi is 2.

Compared with the prior art, the principle and advantages of this scheme are as follows:

1. By uploading the passenger demand information through the shared ride app, the background server will aggregate the new passenger information and other unbound passenger information, and take the maximum number of rides as the goal. This scheme uses real-time road network information, and then uses the method of transfer judgment for matching, which improves the carpooling rate and greatly improves the utilization rate of vehicles.

2. Allow passengers to change driverless taxis midway until they reach their destination. Since some passengers do not have passengers on the same route as others, the system judges that they cannot ride together and can only travel alone, which may lead to excessively high fares for passengers. The present invention can effectively solve the problem for passengers by allowing passengers to transfer multiple times. problems, greatly reducing passenger costs.

Description of drawings

Fig. 1 is the principle flow chart of a kind of unmanned taxi transfer and route matching method of the present invention;

Figure 2 is a schematic diagram of a simulated road network;

Figure 3 is a comparison chart of the route.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings. Only this statement, the present invention appears or will appear in the text up, down, left, right, front, rear, inside, outside and other orientation terms, only based on the accompanying drawings of the present invention, which are not specific to the present invention limited.

The present invention provides an unmanned taxi transfer and path matching method, comprising the following steps:

S1. The background server collects the basic demand information input by the passenger Pi on the ride-sharing app, including the origin O _i , the destination D _j , the departure time T ₀ , the expected arrival time _{T t ,} and the allowable delay time T _d ;

S2. According to the origin O _i and the destination D _j submitted by the passenger _Pi , search for all the unbound passengers P _j in the request area, that is, the passengers in the unbound set W, and compare the basic demand information of the passenger P _i and the information of the unbound passenger P _j , according to the initial transfer conditions, filter out the passenger groups that meet the transfer conditions, and bind them for the first time, and then enter step S3; if there is no unbound matching with the passenger P _i Passenger P _j , directly add passenger P _i to the unbound set W, the matching ends, and the matching is performed again in the next time interval;

The specific process of selecting passenger groups that meet the transfer conditions according to the initial transfer conditions is as follows:

A1. Establish the center point;

Extract the coordinates of the origin O _i and destination D _j of the passenger P _i and the coordinate points of other unbound passengers P _j in the area requested by the passenger P _i , and determine the minimum range including all passengers, that is, by The rectangle bounded by max{X _i ,X _j }, min{X _i ,X _j }, max{Y _i ,Y _j }, min{Y _i ,Y _j }, and then:

as the center point;

A2, route change;

Connect each passenger's path as follows:

Y_j)→(X_j，Y_j)

Y _j )→(X _j , Y _j )

A3. Determine the passenger's path coincidence:

If the paths of two passengers P _i and P _j overlap from a certain node, that is, at least two nodes are the same, and the vector directions formed by connecting the nodes are the same, then the two passengers P _i and P are initially bound. _j , get the passenger group; if there are multiple passengers P _j and passengers P _i that _overlap at the same time _, they will be bound in pairs according to the time sequence of the overlapping nodes; The paths from _i to the destination D _j do not overlap, so the passenger _Pi is added to the unbound set W.

S3. Use the improved route algorithm to plan the route of the passenger group bound for the first time, and calculate whether the planned route meets the time constraints. If so, the passenger group is finally bound, and the passenger P _j in the passenger group After leaving the unbound set W, enter step S4; otherwise, add P _i to the unbound set W, and the matching ends;

The specific process is as follows:

B1. Use the Dijakstra algorithm to calculate the shortest paths of the two passengers P _i and P _j that have been finally bound respectively, and calculate their corresponding arrival times T _t ;

B2. Use the DFS algorithm to arrange all feasible paths for passengers Pi and P _j from the origin O _i to the destination D _{j respectively} ;

B3. Calculate the path similarity, integrate the two paths with high similarity, and confirm the final path trajectories of passengers P _i and P _j ;

B4. Calculate the time required for the final path trajectory of passengers P _i and P _j to determine whether they are within the time constraint [T ₀ , T _t + T _d ]; if both passengers P _i and P _j arrive within the time constraint range Their respective destinations, the binding can be finally confirmed, and the path trajectories of passengers P _i and P _j can be determined respectively; if at least one passenger is not within the time constraint, the final binding is not confirmed, and the passenger P _i is sent to the destination. Bind set W.

S4. Match the final bound passenger group with the unmanned taxis in the unmanned taxi candidate set _Wc . The process is as follows:

C1. Determine whether the current number of unmanned taxi passengers L _n is equal to 2; if so, it means that the unmanned taxi is fully loaded and no more passengers can be carried; if L _n is less than 2, the unmanned taxi is added to the unmanned taxi In the car candidate set W _c ;

C2. Allocate vehicles for bound passenger groups;

If there is an unmanned taxi with a passenger number L _n of 0 in the unmanned taxi candidate set W _c , according to the distance between the unmanned taxi and the passenger P _i , the one with the closest Manhattan distance will be matched; There is no unmanned taxi with the number of passengers L _{n equal} to 0 in the candidate set W _c of the vehicle, then in the candidate set W _c of the unmanned taxi, the unbound taxis taken by the passengers P _j in the set W are not bound Select a vehicle in the taxis; according to the current location Sp of the unmanned taxi taken by the passenger _{P j} , the position N _s expected to arrive in the next time interval and the final destination T _j at the current moment, compare the bound passengers in turn. information, if the starting place O _i of the passenger _{P i} is the same as the current location Sp of the unmanned taxi, or the location N _s to be reached in the next time interval, or the final destination T _j , or the Manhattan distance is similar , then bind the passenger P _i and the unmanned taxi information; if the passenger _Pi still does not match the unmanned taxi at this time, wait for the matching of the unmanned taxi in the next time period; once the unmanned taxi and the passenger P are matched _i binding, that is, remove the unmanned taxi from the unmanned taxi candidate set W _c , regardless of whether the number of passengers L _n of the unmanned taxi is 2.

S5. In the next time interval, update the unbound set W and the driverless taxi candidate set W _c , and cyclically judge the transfer conditions for the passengers in the newly added and unbound sets, until all passengers are assigned to destination or until there are no new passengers.

In order to prove the effectiveness of this embodiment, a simulation experiment is used to test this embodiment below, wherein the objects to be simulated include road network, passengers and unmanned taxis. The evaluation index adopted in the experiment is the total mileage saved in a certain period of time. The specific solution method is described as follows:

Introduction to Data Simulation Methods

The road network is shown in Figure 2. The road network has a total of 20 nodes and 34 edges.

For passenger requests, 4 passengers are randomly generated in one round, and the time interval between each round is 5 minutes. The origin and destination of each passenger appear randomly in the road network, and different passengers are allowed to have the same origin or destination. As shown in Table 1, the system randomly generates two rounds of new passengers, a total of 8 passengers, and the demand information of each passenger is shown in the table.

Table 1

For the unmanned taxi information, four unmanned taxis are selected as the basic running vehicles, and their initial positions are based on the positions of passengers appearing in the first round.

Experimental procedure

1) According to the introduced data simulation method, the request information of passengers is randomly generated, and 4 unmanned taxis are initialized.

2) Update the passenger and unmanned taxi information on the road network at intervals of 5 minutes, use the transfer method described in this embodiment to allocate passenger demand, and cycle until there are no new passengers and all passengers are sent to the destination .

3) In order to verify the validity of this method, the number of journeys traveled by unmanned taxis to complete three rounds of passengers is collected, and the route information of passengers is shown in Table 2; the mileage of unmanned taxis with passengers who do not share or transfer is compared. Calculate the number of kilometers to reduce the distance, and draw a comparison chart of the distance, as shown in Figure 3.

passenger route passenger route a 7-11-8 e 8-11-7 b 10-11-8 f 12-11-10 c 14-11-12 g 16-11-7 d 14-11-16 h 16-11-10

Table 2

Experimental Results and Analysis

The evaluation index of this simulation experiment is the mileage saved by the unmanned taxi after delivering the passengers. The total number of passengers for this experiment was 8. Figure 3 is a graph of the change in the distance traveled by the unmanned taxi after each passenger has been delivered. The asterisk represents the estimated total distance of unmanned taxi operation, the circle represents the actual total distance of unmanned taxi operation, and the positive five-pointed star represents the number of distances reduced in the operation of unmanned taxi (when calculating the total distance, excluding unmanned taxis) The number of journeys the taxi has made to the passenger's origin). It can be seen from the figure that with the increase of passengers, the greater the probability of transfer, the more kilometers can be saved, and the saved path length can reach 48% of the total distance.

Although the description of the present disclosure has been described in considerable detail and with particular reference to a few of the described embodiments, it is not intended to be limited to any of these details or embodiments or any particular embodiment, but should be considered by reference The appended claims are to provide the broadest possible interpretation of these claims in view of the prior art so as to effectively encompass the intended scope of the disclosure. Furthermore, the foregoing description of the present disclosure in terms of embodiments foreseen by the inventors is intended to provide a useful description, and those insubstantial modifications of the present disclosure that are not presently foreseen may nevertheless represent equivalent modifications of the present disclosure.

Claims (2)

1. an unmanned taxi transfer and path matching method, is characterized in that, comprises the following steps: S1. The background server collects the basic demand information input by the passenger Pi on the ride-sharing app, including the origin O _i , the destination D _j , the departure time T ₀ , the expected arrival time _{T t ,} and the allowable delay time T _d ; S2. According to the origin O _i and the destination D _j submitted by the passenger _Pi , search for all the unbound passengers P _j in the request area, that is, the passengers in the unbound set W, and compare the basic demand information of the passenger P _i and the information of the unbound passenger P _j , according to the initial transfer conditions, filter out the passenger groups that meet the transfer conditions, and bind them for the first time, and then enter step S3; if there is no unbound matching with the passenger P _i Passenger P _j , directly add passenger P _i to the unbound set W, the matching ends, and the matching is performed again in the next time interval; S3. Use the improved route algorithm to plan the route of the passenger group bound for the first time, and calculate whether the planned route meets the time constraints. If so, the passenger group is finally bound, and the passenger P _j in the passenger group After leaving the unbound set W, enter step S4; otherwise, add P _i to the unbound set W, and the matching ends; S4, matching the final bound passenger group with the unmanned taxis in the unmanned taxi candidate set _Wc ; S5. In the next time interval, update the unbound set W and the driverless taxi candidate set W _c , and cyclically judge the transfer conditions for the passengers in the newly added and unbound sets, until all passengers are assigned to destination or until there are no new passengers; The specific process of selecting passenger groups that meet the transfer conditions according to the initial transfer conditions is as follows: A1. Establish the center point; Extract the coordinates of the origin O _i and destination D _j of the passenger P _i and the position coordinates of other unbound passenger P _j in the area requested by the passenger P _i , and determine the minimum range including all passengers, that is, by max {X _i ,X _j }, min{X _i ,X _j }, max{Y _i ,Y _j }, min{Y _i ,Y _j } encircled by a rectangle, then:

as the center point; A2, route change; Connect each passenger's path as follows:

A3. Determine the passenger's path coincidence: If the paths of two passengers P _i and P _j overlap from a certain node, that is, at least two nodes are the same, and the vector directions formed by connecting the nodes are the same, then the two passengers P _i and P are initially bound. _j , get the passenger group; if there are multiple passengers P _j and passengers P _i that _overlap at the same time _, they will be bound in pairs according to the time sequence of the overlapping nodes; The paths from _i to the destination D _j do not overlap, then the passenger P _i is added to the unbound set W; Step S3 uses the improved path algorithm to plan the path of the passenger group bound for the first time, and the specific process of determining whether the binding is finally performed is as follows: B1. Use the Dijakstra algorithm to calculate the shortest paths of the two passengers P _i and P _j that have been finally bound respectively, and calculate their corresponding arrival times T _t ; B2. Use the DFS algorithm to arrange all feasible paths for passengers Pi and P _j from the origin O _i to the destination D _{j respectively} ; B3. Calculate the path similarity, integrate the two paths with high similarity, and confirm the final path trajectories of passengers P _i and P _j ; B4. Calculate the time required for the final path trajectory of passengers P _i and P _j to determine whether they are within the time constraint [T ₀ , T _t + T _d ]; if both passengers P _i and P _j arrive within the time constraint range Their respective destinations, the binding can be finally confirmed, and the path trajectories of passengers P _i and P _j can be determined respectively; if at least one passenger is not within the time constraint, the final binding is not confirmed, and the passenger P _i is sent to the destination. Bind set W. 2. a kind of unmanned taxi transfer and path matching method according to claim 1, is characterized in that, the concrete process of carrying out driver-passenger matching is as follows: C1. Determine whether the current number of unmanned taxi passengers L _n is equal to 2; if so, it means that the unmanned taxi is fully loaded and no more passengers can be carried; if L _n is less than 2, the unmanned taxi is added to the unmanned taxi In the car candidate set W _c ; C2. Allocate vehicles for bound passenger groups; If there is an unmanned taxi with a passenger number L _n of 0 in the unmanned taxi candidate set W _c , according to the distance between the unmanned taxi and the passenger P _i , the one with the closest Manhattan distance will be matched; There is no unmanned taxi with the number of passengers L _{n equal} to 0 in the candidate set W _c of the vehicle, then in the candidate set W _c of the unmanned taxi, the unbound taxis taken by the passengers P _j in the set W are not bound According to the current location Sp of the unmanned taxi taken by the passenger _{P j} , the position N _s expected to arrive in the next time interval and the final destination T _j at the current moment, compare the bound passengers in turn. information, if the starting place O _i of the passenger _{P i} is consistent with the current location Sp of the unmanned taxi, the location N _s reached in the next time interval, or the final destination T _j , then the binding Passenger _Pi and unmanned taxi information; if passenger _Pi still has no matching unmanned taxi at this time, wait for the matching of unmanned taxis in the next time period; once the unmanned taxi is bound to passenger _Pi , that is Remove the unmanned taxi from the unmanned taxi candidate set W _c , regardless of whether the number of passengers L _n of the unmanned taxi is 2.

Images