CN111311002B - A bus travel planning method considering passengers' active transfer on the way - Google Patents

Abstract

The invention discloses a bus travel planning method that considers the active transfer of passengers on the way. According to the departure station and destination station of the passenger travel, combined with real-time bus information, the time is used as a virtual node to obtain the original bus network of the passenger travel, and based on this After the network is expanded, and the expanded bus network is obtained, the combined dynamic programming method is used to consider the waiting time weight of passengers at the departure station and the transfer station, the travel time weight between stations, and the weight of the congestion degree of the bus, so as to obtain Travel plans based on travel time and bus congestion. The invention can solve the problem of temporary transfer of passengers on the way to the bus, so as to meet the transfer requirements of passengers, and greatly improve the time utilization efficiency of passengers.

Description

A bus travel planning method considering passengers' active transfer on the way

technical field

The invention belongs to the field of public transport, in particular to a bus travel planning method which considers the active transfer of passengers on the way.

Background technique

In a city with a relatively mature bus network, there are often multiple lines from the starting point to the destination, and the total time of each line is different. Passengers generally choose the travel route with the shortest time. However, there are often a lot of passengers on this line. The passenger's ride comfort is affected, so the passenger chooses to transfer to another bus route.

In the existing technology, the map APP will search for nearby bus stops containing buses arriving at the destination station according to the passenger's current location, plan all travel routes, and sort the travel times of all routes from small to large, and Indicate the specific walking time, ride time, waiting time, etc.

In the prior art, when recommending a travel route, the bus map system often takes the shortest walking time and the shortest total travel time as the recommendation basis.

The current bus travel route planning has the following shortcomings:

The recommendation basis of the travel route plan is too single, and does not consider the passenger's riding needs, especially for transfer passengers, does not take into account the real needs of passengers, such as: the number of people in the car, the degree of bus congestion, and so on.

The choice of travel plan is too unique, the travel route chosen by passengers cannot be changed, and travel plans cannot be flexibly planned on the way.

SUMMARY OF THE INVENTION

In order to solve the above-mentioned shortcomings of the prior art, the present invention proposes a bus travel planning method that considers the active transfer of passengers on the way, in order to solve the problem of temporary transfer of passengers on the way, so as to meet the needs of passengers' transfer. To maximize the efficiency of passenger time utilization.

The present invention adopts the following technical scheme in order to achieve the above-mentioned purpose of the invention:

The characteristics of a bus trip planning method considering the active transfer of passengers on the road of the present invention are as follows:

Step 1. Obtain the original bus network for passengers to travel:

其中，

为从所述起始站点o到第k个换乘站点M_k的第i条进站线路，i＝1,2,…,I_k，I_k为从所述起始站点o到第k个换乘站点M_k的进站线路总数；AL为从换乘站点集合M到目的站点d的出站线路集合，且AL＝{AL₁,AL₂,…,AL_k,…,AL_K}，AL_k为从所述第k个换乘站点M_k到目的站点d的出站线路集合，且

其中，

为从所述第k个换乘站点M_k到目的站点d的第j条出站线路，j＝1,2,…,J_k，J_k为从k个换乘站点M_k到目的站点d的出站线路总数；According to the starting station o and destination station d of the passenger's trip, the original bus network G = (V, A) of the passenger's trip is obtained, where V is the station set, and V = {o, M, d}; M is the transfer station set, and M={M ₁ ,M ₂ ,…,M _k ,…,M _K }, where M _k is the k-th transfer station, k=1,2,…,K, K is the transfer station A is the set of lines in the original bus network G, and A={L,FL,AL}, where L is the set of direct lines between the starting station o and the destination station d, and L={ l ₁ ,l ₂ ,...,l _n ,...,l _N }, l _n is the nth direct line between the starting station o and the destination station d, n=1,2,...,N,N is the total number of direct lines; FL is the line set from the starting station o to each transfer station in the transfer station set M, and FL={FL ₁ ,FL ₂ ,...,FL _k ,...,FL _K } , where FL _k is the set of inbound routes from the starting station o to the k-th transfer station M _k , and

in,

is the i-th inbound line from the starting station o to the k-th transfer station M _k , i=1, 2, . . . , I _k , I _k is the starting station o to the k-th station The total number of inbound lines of transfer station M _k ; AL is the set of outbound lines from transfer station set M to destination station d, and AL={AL ₁ ,AL ₂ ,…,AL _k ,…,AL _K }, AL _k is the set of outbound lines from the k-th transfer station M _k to the destination station d, and

in,

is the j-th outbound line from the k-th transfer station M _k to the destination station d, j=1, 2,...,J _k , J _k is the k-th transfer station M _k to the destination station d The total number of outbound lines;

Step 2: Obtain the extended public transport network based on the original public transport network G:

2.1 Obtain the expanded site set V′={O,M′} from the site set V:

对应的虚拟出发节点分别记为

和

从而将从起始站点o出发的所有直达线路以及从起始站点o到所有换乘站点的所有进站线路所对应的虚拟出发节点与所述起始站点o共同构成起始站点集O；Step 2.1.1 In the line set A, the n-th direct line ln starting from the starting station o and the i- _th inbound line from the starting station o to the _k -th transfer station Mk are divided into

The corresponding virtual departure nodes are respectively recorded as

and

Thereby, the virtual departure nodes corresponding to all direct lines from the starting station o and all inbound lines from the starting station o to all transfer stations together with the starting station o constitute the starting station set O;

对应的虚拟到达节点记为

从第k个换乘站点M_k到目的站点d的第j条出站线路

对应的虚拟出发节点记为

从而将从起始站点o到第k个换乘站点M_k的所有进站线路对应的虚拟到达节点以及从第k个换乘站点M_k到目的站点d的所有出站线路对应的虚拟出发节点构成第k个换乘站点集合M_k′；进而得到所有换乘站点集合M′＝{M′_k|k＝1,2,…,K}；Step 2.1.2 Put the i-th incoming line of the k-th transfer station M _k in the line set A

The corresponding virtual arrival node is denoted as

The jth outbound line from the kth transfer station _Mk to the destination station d

The corresponding virtual departure node is recorded as

Thus, the virtual arrival nodes corresponding to all inbound lines from the starting station o to the _kth transfer station Mk and the virtual departure nodes corresponding to all outbound lines from the kth transfer station _Mk to the destination station d Constitute the kth transfer station set M _k ′; and then obtain all transfer station sets M′={M′ _k |k=1,2,…,K};

2.2 Construct a new line set A' to generate an extended bus network G'=(V', A'):

表示以起始站点o为起点，以第n条直达线路l_n对应的虚拟出发节点

为终点的等待弧；definition

Indicates the virtual departure node corresponding to the nth direct line l _n starting from the starting station o

is the waiting arc for the end point;

表示以起始站点o为起点，以第k个换乘站点M_k的第i条进站线路

对应的虚拟出发节点

为终点的等待弧；从而得到起始站点集O的等待弧集，记为

definition

Indicates the i-th inbound line starting from the starting station o and taking the k-th transfer station M _k

Corresponding virtual departure node

is the waiting arc of the end point; thus the waiting arc set of the initial site set O is obtained, denoted as

表示以第k个换乘站点M_k的第i条进站线路

的虚拟到达节点

为起点，以第k个换乘站点M_k的第j条出站线路

的虚拟出发节点

为终点的等待弧；从而得到第k个换乘站点集合M_k′的等待弧集，记为

进而得到所有换乘站点集合M′的等待弧集，记为

definition

Indicates the i-th inbound line at the k-th transfer station M _k

virtual arrival node of

as the starting point, take the jth outbound line of the kth transfer station M _k

virtual departure node

is the waiting arc of the end point; thus, the waiting arc set of the k-th transfer station set M _k ′ is obtained, denoted as

Then, the waiting arc set of all transfer station set M' is obtained, denoted as

The total waiting arc set WL is composed of the waiting arc set WLO of the starting station set _O and the waiting arc set WL _M of all transfer station sets M′, namely WL={ _WLO ,WL _M };

表示以第n条直达线路l_n的虚拟出发节点

为起点，以目的站点d为终点的行驶弧，从而得到以所有直达线路的虚拟出发节点为起点，以目的站点d为终点的行驶弧集，记为

definition

represents the virtual departure node of the nth direct line l _n

As the starting point and the destination station d as the end point, the travel arc set with the virtual departure nodes of all direct routes as the start point and the destination station d as the end point is obtained, which is recorded as

表示以第k个换乘站点M_k的第i条进站线路

的虚拟出发节点

为起点，以第k个换乘站点M_k的第i条进站线路

的虚拟到达节点

为终点的行驶弧，从而得到以所有换乘站点的所有进站线路的虚拟出发节点为起点，以所有换乘站点的所有进站线路的虚拟到达节点为终点的行驶弧集，记为

definition

Indicates the i-th inbound line at the k-th transfer station M _k

virtual departure node

as the starting point, take the i-th inbound line of the k-th transfer station M _k

virtual arrival node of

is the driving arc at the end point, so as to obtain the set of driving arcs starting from the virtual departure nodes of all inbound lines of all transfer stations and taking the virtual arrival nodes of all inbound lines of all transfer stations as the end point, denoted as

表示以第k个换乘站点M_k的第j条出站线路

的虚拟出发节点

为起点，以目的站点d为终点的行驶弧，从而得到以所有换乘站点的所有出站线路的虚拟出发节点为起点，以目的站点d为终点的行驶弧集，记为

definition

represents the jth outbound line at the _kth transfer station Mk

virtual departure node

As the starting point and the destination station d as the end point, the set of travel arcs with the virtual departure nodes of all outbound lines of all transfer stations as the start point and the destination station d as the end point is obtained, denoted as

From the travel arc set L' starting from the virtual departure nodes of all direct lines and ending at the destination station d, starting from the virtual departure nodes of all inbound lines of all transfer stations, and taking all inbound lines of all transfer stations as the starting point The travel arc set FL′ with the virtual arrival node as the end point and the travel arc set AL′ with the virtual departure nodes of all outbound lines of all transfer stations as the starting point and the destination station d as the end point constitute the total travel arc set RL, that is, RL ={L',FL',AL'};

A new line set is formed by the total waiting arc set WL and the total traveling arc set RL, denoted as A′={WL,RL};

Step 3: Calculate the weights of waiting arcs and driving arcs on the extended bus network:

Step 3.1. Set the moment when the passenger arrives at the starting station o as t _o , and at the same time add the real-time bus information and road condition information to the extended bus network G′=(V′, A′);

Step 3.2, assign the corresponding weight ω to the traveling arc and the waiting arc in the new line set A', so as to obtain the weighted directed graph G"=(V', A', ω), where the weight ω includes:

表示乘客乘坐第n条直达线路l_n上在时刻t_o后最先到达起始站点o的公交车所需要等待的时间，即

其中，

表示在时刻t_o后第n条直达线路l_n上的最先到达起始站点o的公交车到达起始站点o的时刻，如果在乘客到达起始站点o的时刻t_o后在第n条直达线路l_n上不再有公交车，则令

Let the weight of the waiting arc set WLO of the starting site set _O be

Represents the waiting time for passengers to take the bus on the nth direct line l _n that first arrives at the starting station o after time t _o , i.e.

in,

Represents the time at which the first bus on the nth direct line l _{n arrives at the starting station o after} the time to If there are no more buses on the direct line l _n , then let

表示乘客乘坐第k个换乘站点M_k的第i条进站线路

上最先到达起始站点o的公交车所需要等待的时间，即

其中，

表示在时刻t_o后第k个换乘站点M_k的第i条进站线路

上最先到达起始站点o的公交车到达o的时刻，如果时刻t_o后在第k个换乘站点M_k的第i条进站线路

上不再有公交车，则令

Let the weight of the waiting arc set WLO of the starting site set _O be

Indicates that the passenger takes the i-th inbound line of the k-th transfer station M _k

The waiting time for the bus that first arrives at the starting station o, i.e.

in,

represents the i-th inbound line at the k-th transfer station M _k after time t _o

The time when the bus that first arrives at the starting station o arrives at o, if the ith incoming line at the _kth transfer station Mk after time t _o

If there is no longer a bus on the

表示乘客乘坐第k个换乘站点M_k的第i条进站线路

上的公交车到达M_k后，乘客乘坐第k个换乘站点M_k的第j条出站线路

上最先到达M_k的公交车所需要等待的时间，即

其中，

为时刻t_o后最先到达起始站点o的公交车经过第k个换乘站点M_k的第i条进站线路

到达第k个换乘站点M_k的时刻，

表示在时刻

之后在第k个换乘站点M_k的第j条出站线路

上最先到达M_k时刻，如果时刻

后不再有到达第k个换乘站点M_k且经过第k个换乘站点M_k的第j条出站线路

的公交车，则令

Let the weight of the waiting arc set WLM of the transfer station set _M '

Indicates that the passenger takes the i-th inbound line of the k-th transfer station M _k

After the bus on board arrives at _Mk , the passenger takes the jth outbound line of the _kth transfer station Mk

The waiting time for the bus that arrives at M _k first, namely

in,

is the ith incoming line of the bus that first arrives at the starting station o after the time t _o and passes through the k th transfer station M _k

When arriving at the k-th transfer station M _k ,

expressed at the moment

Then the j-th outbound line at the k-th transfer station M _k

to arrive at time M _k first, if the time

After that, there is no longer the jth outbound line that arrives at the _kth transfer station _Mk and passes through the kth transfer station Mk

bus, the order

表示乘客乘坐最先到达起始站点o的公交车在第n条直达线路l_n上基于实时路况的行驶时间，即

其中，

为小汽车基于实时路况下经过第n条直达线路l_n的行驶时间，μ为换算系数，且μ＞1，

为第n条直达线路l_n上的公交车站个数且不包括起始站点o和目的站点d，T为公交车在每个车站的平均停靠时间；Let the weight of the travel arc set L′ starting from the virtual departure nodes of all direct routes and ending at the destination station d

Represents the travel time of passengers taking the bus that first arrives at the starting station o on the nth direct line l _n based on real-time road conditions, namely

in,

is the travel time of the car through the nth direct line l _n based on real-time road conditions, μ is the conversion factor, and μ>1,

is the number of bus stops on the _nth direct line ln and does not include the starting station o and destination station d, and T is the average bus stop time at each station;

Obtain the total number of buses between the starting station o and the destination station d on the nth direct line l _n , and the total number of buses with the same bus line number as the passenger's current bus line number is recorded as Q _n , the total number of buses Q Include the current vehicle;

Get the real-time number of people on the qth bus

的平均人数且记为

即

从而得到影响舒适度的权重

其中，k为公交车人数转换为影响程度的转换系数，c为调整系数；最终得到基于乘客当前乘坐的公交线路的行驶时间和公交车拥挤程度的综合权重

且

其中α为乘客对舒适度的重视程度，α∈[0,1]；当α等于0时，表示乘客希望得到最短出行时间的公交线路，当α等于1时，表示乘客希望得到舒适度最高的公交线路；α∈(0,1)时，表示乘客综合考虑出行时间和舒适度得到的最优公交线路；Calculate the time of all buses from the starting station o to the destination station d that have the same bus line number as the passenger's current bus line number on the nth direct line l _n

the average number of people and recorded as

which is

so as to get the weight that affects the comfort

Among them, k is the conversion coefficient of the number of buses converted into the degree of influence, and c is the adjustment coefficient; finally, the comprehensive weight based on the travel time of the bus line currently taken by passengers and the degree of bus congestion is obtained.

and

where α is the degree of importance that passengers place on comfort, α∈[0,1]; when α is equal to 0, it means that passengers want to get the bus line with the shortest travel time; when α is equal to 1, it means that passengers want to get the bus line with the highest comfort level bus route; when α∈(0,1), it represents the optimal bus route obtained by passengers considering travel time and comfort;

表示乘客乘坐最先到达起始站点o的公交车在第k个换乘站点M_k的第i条进站线路

上基于实时路况的行驶时间，即

其中，

为小汽车基于实时路况下经过第k个换乘站点M_k的第i条进站线路

的行驶时间，μ为换算系数，且μ＞1，

为第k个换乘站点M_k的第i条进站线路

上的公交车站个数且不包括起始站点o和第k个换乘站点M_k，T为公交车在每个车站的平均停靠时间；Let the weight of the travel arc set FL′ starting from the virtual departure nodes of all inbound lines of all transfer stations and taking the virtual arrival nodes of all inbound lines of all transfer stations as the end point

Indicates that the passenger takes the bus that first arrives at the starting station o at the i-th inbound line at the k-th transfer station M _k

The driving time based on real-time road conditions on the

in,

is the i-th inbound line of the car passing through the k-th transfer station M _k based on real-time road conditions

The travel time of , μ is the conversion factor, and μ > 1,

is the i-th inbound line of the k-th transfer station M _k

The number of bus stops on the bus and does not include the starting station o and the k-th transfer station M _k , T is the average stop time of the bus at each station;

上从起始站点o至第k个换乘站点M_k之间的公交车辆，且与乘客当前乘坐的公交线路编号相同的公交车总数，所述公交车总数

包含当前乘坐的车辆；Get the i-th inbound line of the k-th transfer station M _k

The total number of buses from the starting station o to the _k -th transfer station Mk, and the total number of buses with the same bus line number as the passenger's current bus line number, the total number of buses

Include the current vehicle;

Get the real-time number of people on the qth bus

上与乘客当前乘坐的公交线路编号相同的，从起始站点o至第k个换乘站点M_k之间的全部公交车在时刻

的平均人数且记为

即

从而得出影响舒适度的权重

且

其中，k为公交车人数转换为影响程度的转换系数，c为调整系数；最终得到基于乘客当前乘坐的公交线路的行驶时间和公交车拥挤程度的综合权重

且

其中，α为乘客对舒适度的重视程度，α∈[0,1]；当α等于0时，表示乘客希望得到最短出行时间的公交线路，当α等于1时，表示乘客希望得到舒适度最高的公交线路；α∈(0,1)时，表示乘客综合考虑出行时间和舒适度得到的最优公交线路；Calculate the i-th inbound line through the k-th transfer station M _k

All buses from the starting station o to the _k -th transfer station Mk with the same bus line number as the passenger's current bus line number are at the time

the average number of people and recorded as

which is

Thereby, the weights that affect the comfort level are obtained

and

Among them, k is the conversion coefficient of the number of buses converted into the degree of influence, and c is the adjustment coefficient; finally, the comprehensive weight based on the travel time of the bus line currently taken by passengers and the degree of bus congestion is obtained.

and

Among them, α is the passenger's degree of emphasis on comfort, α∈[0,1]; when α is equal to 0, it means that the passenger wants to get the bus line with the shortest travel time, and when α is equal to 1, it means that the passenger wants to get the highest level of comfort When α∈(0,1), it represents the optimal bus route obtained by passengers considering travel time and comfort;

表示乘客乘坐最先到达第k个换乘站点M_k的公交车在第j条出站线路

上基于实时路况的行驶时间，即

其中，

为小汽车基于实时路况下经过第k个换乘站点M_k的第j条出站线路

的行驶时间，μ为换算系数，且μ＞1，

为第k个换乘站点M_k的第j条出站线路

上的公交车站个数，且不包括第k个换乘站点M_k和目的站点d，T为公交车在每个车站的平均停靠时间；Let the weight of the travel arc set AL' starting from the virtual departure nodes of all outbound lines of all transfer stations and ending at the destination station d

Indicates that the passenger takes the bus that first arrives at the k-th transfer station M _k on the j-th outbound line

The driving time based on real-time road conditions on the

in,

is the jth outbound line of the car passing through the _kth transfer station Mk based on real-time road conditions

The travel time of , μ is the conversion factor, and μ > 1,

is the jth outbound line of the _kth transfer station Mk

The number of bus stops on the bus, excluding the k-th transfer station M _k and the destination station d, T is the average bus stop time at each station;

上从第k个换乘站点M_k至目的站点d之间的公交车辆，且与乘客当前乘坐的公交线路编号相同的公交车总数，所述公交车总数

包含当前乘坐的车辆；Get the jth outbound line of the kth transfer station M _k

The total number of buses from the k-th transfer station _Mk to the destination station d, and the total number of buses with the same bus line number as the passenger's current bus line number, the total number of buses

Include the current vehicle;

Get the real-time number of people on the qth bus

上与乘客当前乘坐的公交线路编号相同的，从第k个换乘站点M_k至目的站点d的全部公交车在时刻

的平均人数且记为

即

由此得出影响舒适度的权重

且

其中k为公交车人数转换为影响程度的转换系数，c为调整系数，最终得到基于乘客当前乘坐的公交线路的行驶时间和公交车拥挤程度的综合权重

且

其中α为乘客对舒适度的重视程度，α∈[0,1]；当α等于0时，表示乘客希望得到最短出行时间的公交线路，当α等于1时，表示乘客希望得到舒适度最高的公交线路；α∈(0,1)时，表示乘客综合考虑出行时间和舒适度得到的最优公交线路；Calculate the jth outbound line through the _kth transfer station Mk

All buses from the k-th transfer station M _k to the destination station d have the same bus line number as the passenger's current bus line number at the time

the average number of people and recorded as

which is

This results in a weight that affects comfort

and

Among them, k is the conversion coefficient of the number of buses converted into the degree of influence, and c is the adjustment coefficient, and finally the comprehensive weight based on the travel time of the bus line currently taken by the passenger and the degree of bus congestion is obtained.

and

where α is the degree of importance that passengers place on comfort, α∈[0,1]; when α is equal to 0, it means that passengers want to get the bus line with the shortest travel time; when α is equal to 1, it means that passengers want to get the bus line with the highest comfort level bus route; when α∈(0,1), it represents the optimal bus route obtained by passengers considering travel time and comfort;

Step 4: Use the combined dynamic programming algorithm to find the optimal path from the starting station o to the destination station d in the expanded public transport network graph G″=(V′, A′, ω) after loading the weight information:

Step 4.0. Divide the weighted directed graph G"=(V', A', ω) into direct line network, transfer line network and mixed line network according to whether there is a transfer line. If the weighted directed graph G" =(V′,A′,ω) is the direct line network, then go to step 4.1 and step 4.3; if the weighted directed graph G″=(V′,A′,ω) is the transfer line network, then go to step 4.2 and step 4.3; if the weighted directed graph G″=(V′, A′, ω) is a mixed line network, then perform steps 4.1 to 4.3;

Step 4.1. Obtain the optimal path of the direct line network:

Step 4.1.1. Let a represent the current stage, let the state variable s _a represent the possible node positions at the beginning of the current stage a, the decision variable u _a represent the arcs that may be selected at the beginning of the current stage a, and define the indicator function V _a (s ₁ ,u ₁ ,…s _a-1 ,u _a-1 ,s _a ) is the sum of the weights of waiting arcs and travel arcs corresponding to all bus lines selected before the current stage a, let the optimal value function f _a (s _a )=min{V _a (s ₁ , u ₁ ,...s _a-1 ,u _a-1 ,s _a )}, define the boundary condition f ₁ (s ₁ )=0;

When a=1, initialize s _a as the starting site o;

When a=2, initialize s _a as the virtual departure node corresponding to all direct routes from the starting station o;

When a=3, initialize s _a as the destination site d;

Step 4.1.2, let n=1;

Step 4.1.3, calculation

Step 4.1.4, assign n+1 to n, and judge whether n>N is established, if so, go to step 4.1.5, otherwise, go to step 4.1.3;

令l_n ^*为

中最小元素对应状态变量的线路；Step 4.1.5, calculation

Let _ln ^* be

The smallest element in the line corresponds to the state variable;

Step 4.2. Obtain the optimal path of the transfer line network:

Step 4.2.1. Let a denote the current stage, let the state variable s _a denote the possible node positions at the beginning of the current stage a, and the decision variable u _a denote the arcs that may be selected at the beginning of the current stage a, and define the indicator function V _a (s ₁ ,u ₁ ,…s _a-1 ,u _a-1 ,s _a ) is the sum of the weights of waiting arcs and travel arcs corresponding to all bus lines selected before the current stage a, let the optimal value function f _a (s _a )=min{V _a (s ₁ , u ₁ ,...s _a-1 ,u _a-1 ,s _a )}, define the boundary condition f ₁ (s ₁ )=0;

When a=1, initialize s _a as the starting site o;

When a=2, initialize s _a as the virtual departure node corresponding to all inbound lines from the starting station o to all transfer stations;

When a=3, the initialization s _a is the virtual arrival node corresponding to all incoming lines from the starting station o to all transfer stations;

When a=4, initialize s _a as the virtual departure node corresponding to all outbound lines from all transfer stations to the destination station;

When a=5, initialize s _a as the destination site d;

Step 4.2.2, let k=1;

Step 4.2.3, let i=1;

和

Step 4.2.4, calculation

and

Step 4.2.5, assign i+1 to i, and judge whether i>I _k is established, if so, execute step 4.2.6, otherwise, execute step 4.2.4;

Step 4.2.6, assign k+1 to k, and judge whether k>K is established, if so, go to step 4.2.7, otherwise, go to step 4.2.3;

Step 4.2.7, let k=1;

Step 4.2.8, let j=1;

Step 4.2.9, calculation

为

中最小元素对应状态变量的进站线路；make

for

The smallest element in the inbound line corresponds to the state variable;

Step 4.2.10, assign j+1 to j, and judge whether j>J _k is established, if so, go to step 4.2.11, otherwise, go to step 4.2.9;

Step 4.2.11, assign k+1 to k, and judge whether k>K is established, if so, go to step 4.2.12, otherwise, go to step 4.2.8;

Step 4.2.12, calculation

为

中最小元素对应状态变量的出站线路；make

for

The smallest element in the outbound line corresponding to the state variable;

Step 4.3. Comprehensively compare the travel time of the direct line and the transfer line, so as to obtain the optimal path of the weighted directed graph G″=(V′,A′,ω):

If f ₃ (d)≤f ₅ (d) or the weighted directed graph G″=(V′,A′,ω) is a direct line network, select a direct line, and the optimal direct line is from the starting station o Take the bus on the direct line l _n ^* to the destination station d, denoted as

上的公交车至第k个换乘站点M_k换乘，然后乘坐第j条出站线路

上的公交车至目的站点d，记为

If f ₃ (d)>f ₅ (d) or the weighted directed graph G″=(V′,A′,ω) is the transfer line network, select the transfer line, and the optimal transfer line is from Start station o take the i-th incoming line at the k-th transfer station

Take the bus on to the k-th transfer station M _k to transfer, and then take the j-th outbound line

take the bus to the destination station d, denoted as

If f ₃ (d)=f ₅ (d)=+∞, then the optimal route is empty, which means that based on the departure time t _o when the passenger arrives at the starting station o, the passenger cannot catch the last train, and thus cannot complete the trip. ;

Step 5: Obtain the current position of the passenger, and determine whether the current position has reached the new station. If it does not reach the new station, after updating the current position of the passenger, repeat step 5. If it reaches the new station, record the new station as o' ;

If the new station o' is not the destination station d, assign o' to the passenger's current location o, and execute step 1;

If the new station o' is the destination station d, the current bus travel planning is ended.

Compared with the prior art, the beneficial effects of the present invention are:

1. At present, the map APP will re-plan the travel route according to the real-time position of the vehicle that the passenger wants to transfer to, and recommend the travel plan according to the travel time. The travel plan and the current position, the travel time of the bus line currently taken by the passenger and the bus congestion degree are comprehensively considered to obtain the comprehensive weight. Similarly, the comprehensive weight of other travel plans is calculated, and the weight is loaded into the extended bus network diagram, using The combined dynamic programming algorithm calculates the optimal value of each travel plan, and then determines whether to transfer, if so, and obtains the transfer plan based on the travel plan previously selected by the passenger, that is, where to transfer, and what line to transfer to avoid It solves the problems of difficult, troublesome and no data reference for passengers to transfer in public travel, so that passengers can be more user-friendly. Use public transport to travel.

2. The present invention increases the weight of crowded bus lines according to the different requirements of different passengers for comfort, thereby giving passengers with different needs different choices, and solving the current map APP giving the same recommended route to different passenger needs. The problem is an alternative "custom bus". By recommending different routes for different passenger needs, the bus pressure during peak periods is also partially relieved.

3. The present invention uses the continuous updating of the real-time position and the continuous updating of the road information in the process of passengers taking the bus. When the bus arrives at the next station, the station is regarded as a new starting station for travel, and the optimal path is recalculated. It is repeated until the destination station is reached, which overcomes the problem of fixed transfer lines in the existing map APP, thus making the bus transfer more selective and improving the selectivity of passengers. At the same time, when a traffic accident occurs on the line ahead, it can timely feedback to the passengers, which greatly improves the efficiency of taking the bus in such cases. Through selective transfer, part of the bus pressure is also relieved.

Description of drawings

Fig. 1 is the original route network diagram of passenger travel of the present invention;

Fig. 2 is the flow chart of the present invention to obtain the original public transport network for passenger travel;

3 is a schematic diagram of an extended public transport network based on the original network of the present invention;

Fig. 4 is the general flow chart of the method of the present invention.

Detailed ways

In this embodiment, a bus travel planning method that considers the active transfer of passengers on the road is to recalculate the weight of the bus line by considering the different needs of different passengers for comfort, and obtain a comprehensive maximum based on comfort and bus travel time. Optimal routes, so that passengers with different needs have different bus ride plans, making user travel plans more humane, and in the process of bus driving, constantly updating the optimal bus routes, providing passengers with a possibility for transfer on the way. Selectivity, specifically, as shown in Figure 4, is performed as follows:

Step 1. Obtain the original bus network for passengers to travel:

其中，

为从起始站点o到第k个换乘站点M_k的第i条进站线路，i＝1,2,…,I_k，I_k为从起始站点o到第k个换乘站点M_k的进站线路总数；AL为从换乘站点集合M到目的站点d的出站线路集合，且AL＝{AL₁,AL₂,…,AL_k,…,AL_K}，AL_k为从第k个换乘站点M_k到目的站点d的出站线路集合，且

其中，

为从第k个换乘站点M_k到目的站点d的第j条出站线路，j＝1,2,…,J_k，J_k为从k个换乘站点M_k到目的站点d的出站线路总数。如图1所示，即为获得的原始公交网络图。According to the starting station o and destination station d of the passenger's trip, the original bus network G = (V, A) of the passenger's trip is obtained, where V is the station set, and V = {o, M, d}; M is the transfer station set, and M={M ₁ ,M ₂ ,…,M _k ,…,M _K }, where M _k is the k-th transfer station, k=1,2,…,K, K is the transfer station As shown in Figure 2, from the starting station and destination station input by the user, the set of all direct routes and transfer lines between the starting station and the destination station is obtained, and the original bus network is obtained. A is the line set in the original bus network G, and A={L,FL,AL}, where L is the direct line set between the starting station o and the destination station d, and L={l ₁ ,l ₂ ,...,l _n ,...,l _N }, l _n is the nth direct line between the starting station o and the destination station d, n=1,2,...,N, N is the total number of direct lines; FL is the line set from the starting station o to each transfer station in the transfer station set M, and FL={FL ₁ ,FL ₂ ,...,FL _k ,...,FL _K }, where FL _k is the starting point the set of inbound routes from station o to the _k -th transfer station Mk, and

in,

is the i-th inbound line from the starting station o to the k-th transfer station M _k , i=1,2,...,I _k , I _k is from the starting station o to the k-th transfer station M The total number of inbound lines of _k ; AL is the set of outbound lines from the transfer station set M to the destination station d, and AL={AL ₁ ,AL ₂ ,...,AL _k ,...,AL _K }, AL _k is the from The set of outbound routes from the k-th transfer station M _k to the destination station d, and

in,

is the j-th outbound line from the k-th transfer station _Mk to the destination station d, _j =1,2,...,Jk, Jk is the outbound line from the _k -th transfer station _Mk to the destination station d The total number of station lines. As shown in Figure 1, it is the obtained original public transportation network map.

Step 2: Obtain the extended public transport network based on the original public transport network G:

2.1 The expanded site set V′={O,M′} is obtained from the site set V:

对应的虚拟出发节点分别记为

和

设置该虚拟出发节点是为了方便后文中计算等待时间权重，从而将从起始站点o出发的所有直达线路以及从起始站点o到所有换乘站点的所有进站线路所对应的虚拟出发节点与起始站点o共同构成起始站点集O；Step 2.1.1 Combine the n-th direct line l _n from the starting station o and the i-th inbound line from the starting station o to the k-th transfer station M _k in the line set A

The corresponding virtual departure nodes are respectively recorded as

and

The virtual departure node is set to facilitate the calculation of the waiting time weight in the following text, so that the virtual departure nodes corresponding to all direct lines from the starting station o and all inbound lines from the starting station o to all transfer stations are the same as The starting sites o together constitute the starting site set O;

对应的虚拟到达节点记为

从第k个换乘站点M_k到目的站点d的第j条出站线路

对应的虚拟出发节点记为

由虚拟到达节点

和虚拟出发节点

可以构建新的网络，将换乘等待时间量化计算。从而将从起始站点o到第k个换乘站点M_k的所有进站线路对应的虚拟到达节点以及从第k个换乘站点M_k到目的站点d的所有出站线路对应的虚拟出发节点构成第k个换乘站点集合M_k′；进而得到所有换乘站点集合M′＝{M′_k|k＝1,2,…,K}；Step 2.1.2 Put the i-th incoming line of the k-th transfer station M _k in the line set A

The corresponding virtual arrival node is denoted as

The jth outbound line from the kth transfer station _Mk to the destination station d

The corresponding virtual departure node is recorded as

Arrive node by virtual

and virtual departure node

A new network can be constructed to quantify the transfer waiting time. Thus, the virtual arrival nodes corresponding to all inbound lines from the starting station o to the _kth transfer station Mk and the virtual departure nodes corresponding to all outbound lines from the kth transfer station _Mk to the destination station d Constitute the kth transfer station set M _k ′; and then obtain all transfer station sets M′={M′ _k |k=1,2,…,K};

2.2 Construct a new line set A' to generate an extended bus network G'=(V', A'):

表示以起始站点o为起点，以第n条直达线路l_n对应的虚拟出发节点

为终点的等待弧；definition

Indicates the virtual departure node corresponding to the nth direct line l _n starting from the starting station o

is the waiting arc for the end point;

表示以起始站点o为起点，以第k个换乘站点M_k的第i条进站线路

对应的虚拟出发节点

为终点的等待弧；表示乘客等待公交到达起始站点o，从而得到起始站点集O的等待弧集，记为

definition

Indicates the i-th inbound line starting from the starting station o and taking the k-th transfer station M _k

Corresponding virtual departure node

is the waiting arc of the end point; it means that passengers wait for the bus to arrive at the starting station o, so as to obtain the waiting arc set of the starting station set O, denoted as

表示以第k个换乘站点M_k的第i条进站线路

的虚拟到达节点

为起点，以第k个换乘站点M_k的第j条出站线路

的虚拟出发节点

为终点的等待弧；表示乘客到达虚拟到达节点

之后等待换乘公交到达虚拟出发节点

从而得到第k个换乘站点集合M_k′的等待弧集，记为

进而得到所有换乘站点集合M′的等待弧集，记为

definition

Indicates the i-th inbound line at the k-th transfer station M _k

virtual arrival node of

as the starting point, take the jth outbound line of the kth transfer station M _k

virtual departure node

is the waiting arc at the end point; indicates that the passenger arrives at the virtual arrival node

Then wait for the transfer bus to arrive at the virtual departure node

Thus, the waiting arc set of the k-th transfer station set M _k ′ is obtained, denoted as

Then, the waiting arc set of all transfer station set M' is obtained, denoted as

The total waiting arc set WL is composed of the waiting arc set WLO of the starting station set _O and the waiting arc set WL _M of all transfer station sets M′, namely WL={ _WLO ,WL _M };

表示以第n条直达线路l_n的虚拟出发节点

为起点，以目的站点d为终点的行驶弧，即公交车从出发站点到目的站点的行驶过程，从而得到以所有直达线路的虚拟出发节点为起点，以目的站点d为终点的行驶弧集，记为

definition

represents the virtual departure node of the nth direct line l _n

as the starting point and the destination station d as the destination point, that is, the driving process of the bus from the departure station to the destination station, so as to obtain the travel arc set starting from the virtual departure nodes of all direct routes and ending at the destination station d, marked as

表示以第k个换乘站点M_k的第i条进站线路

的虚拟出发节点

为起点，以第k个换乘站点M_k的第i条进站线路

的虚拟到达节点

为终点的行驶弧，即公交车从出发站点到换乘站点的行驶过程，从而得到以所有换乘站点的所有进站线路的虚拟出发节点为起点，以所有换乘站点的所有进站线路的虚拟到达节点为终点的行驶弧集，记为

definition

Indicates the i-th inbound line at the k-th transfer station M _k

virtual departure node

as the starting point, take the i-th inbound line of the k-th transfer station M _k

virtual arrival node of

is the driving arc of the end point, that is, the driving process of the bus from the departure station to the transfer station, so that the virtual departure nodes of all inbound lines of all transfer stations are taken as the starting point, and the distances of all inbound lines of all transfer stations are obtained. The set of travel arcs with the virtual arrival node as the end point, denoted as

表示以第k个换乘站点M_k的第j条出站线路

的虚拟出发节点

为起点，以目的站点d为终点的行驶弧，即公交车从出发站点到换乘站点的行驶过程，从而得到以所有换乘站点的所有出站线路的虚拟出发节点为起点，以目的站点d为终点的行驶弧集，记为

definition

represents the jth outbound line at the _kth transfer station Mk

virtual departure node

As the starting point, the driving arc with the destination station d as the end point is the driving process of the bus from the departure station to the transfer station, so as to obtain the virtual departure nodes of all outbound lines of all transfer stations as the starting point, and the destination station d. is the set of driving arcs at the end point, denoted as

From the travel arc set L' starting from the virtual departure nodes of all direct lines and ending at the destination station d, starting from the virtual departure nodes of all inbound lines of all transfer stations, and taking all inbound lines of all transfer stations as the starting point The travel arc set FL′ with the virtual arrival node as the end point and the travel arc set AL′ with the virtual departure nodes of all outbound lines of all transfer stations as the starting point and the destination station d as the end point constitute the total travel arc set RL, that is, RL ={L',FL',AL'};

A new line set is formed by the total waiting arc set WL and the total traveling arc set RL, denoted as A′={WL,RL};

Step 3: Calculate the weights of waiting arcs and driving arcs on the extended bus network:

Step 3.1. Set the moment when the passenger arrives at the starting station o as t _o , and at the same time add the real-time bus information and road condition information to the extended bus network G′=(V′, A′);

Step 3.2, assign the corresponding weight ω to the traveling arc and the waiting arc in the new line set A', so as to obtain the weighted directed graph G"=(V', A', ω), where the weight ω includes:

表示乘客乘坐第n条直达线路l_n上在时刻t_o后最先到达起始站点o的公交车所需要等待的时间，即

其中，

表示在时刻t_o后第n条直达线路l_n上的最先到达起始站点o的公交车到达起始站点o的时刻，如果在乘客到达起始站点o的时刻t_o后在第n条直达线路l_n上不再有公交车，则令

Let the weight of the waiting arc set WLO of the starting site set _O be

Represents the waiting time for passengers to take the bus on the nth direct line l _n that first arrives at the starting station o after time t _o , i.e.

in,

Represents the time at which the first bus on the nth direct line l _{n arrives at the starting station o after} the time to If there are no more buses on the direct line l _n , then let

表示乘客乘坐第k个换乘站点M_k的第i条进站线路

上最先到达起始站点o的公交车所需要等待的时间，即

其中，

表示在时刻t_o后第k个换乘站点M_k的第i条进站线路

上最先到达起始站点o的公交车到达o的时刻，如果时刻t_o后在第k个换乘站点M_k的第i条进站线路

上不再有公交车，则令

Let the weight of the waiting arc set WLO of the starting site set _O be

Indicates that the passenger takes the i-th inbound line of the k-th transfer station M _k

The waiting time for the bus that first arrives at the starting station o, i.e.

in,

represents the i-th inbound line at the k-th transfer station M _k after time t _o

The time when the bus that first arrives at the starting station o arrives at o, if the ith incoming line at the _kth transfer station Mk after time t _o

If there is no longer a bus on the

表示乘客乘坐第k个换乘站点M_k的第i条进站线路

上的公交车到达M_k后，乘客乘坐第k个换乘站点M_k的第j条出站线路

上最先到达M_k的公交车所需要等待的时间，即

其中，

为时刻t_o后最先到达起始站点o的公交车经过第k个换乘站点M_k的第i条进站线路

到达第k个换乘站点M_k的时刻，

表示在时刻

之后在第k个换乘站点M_k的第j条出站线路

上最先到达M_k时刻，如果时刻

后不再有到达第k个换乘站点M_k且经过第k个换乘站点M_k的第j条出站线路

的公交车，则令

Let the weight of the waiting arc set WLM of the transfer station set _M '

Indicates that the passenger takes the i-th inbound line of the k-th transfer station M _k

After the bus on board arrives at _Mk , the passenger takes the jth outbound line of the _kth transfer station Mk

The waiting time for the bus that arrives at M _k first, namely

in,

is the ith incoming line of the bus that first arrives at the starting station o after the time t _o and passes through the k th transfer station M _k

When arriving at the k-th transfer station M _k ,

expressed at the moment

Then the j-th outbound line at the k-th transfer station M _k

to arrive at time M _k first, if the time

After that, there is no longer the jth outbound line that arrives at the _kth transfer station _Mk and passes through the kth transfer station Mk

bus, the order

表示乘客乘坐最先到达起始站点o的公交车在第n条直达线路l_n上基于实时路况的行驶时间，即

其中，

为小汽车基于实时路况下经过第n条直达线路l_n的行驶时间，μ为换算系数，且μ＞1，

为第n条直达线路l_n上的公交车站个数且不包括起始站点o和目的站点d，T为公交车在每个车站的平均停靠时间；Let the weight of the travel arc set L′ starting from the virtual departure nodes of all direct routes and ending at the destination station d

Represents the travel time of passengers taking the bus that first arrives at the starting station o on the nth direct line l _n based on real-time road conditions, namely

in,

is the travel time of the car through the nth direct line l _n based on real-time road conditions, μ is the conversion factor, and μ>1,

is the number of bus stops on the _nth direct line ln and does not include the starting station o and destination station d, and T is the average bus stop time at each station;

公交车总数

包含当前乘坐的车辆；Obtain the total number of buses between the starting station o and the destination station d on the nth direct line l _n , and the total number of buses with the same bus line number as the passenger's current bus line number is recorded as

Total number of buses

Include the current vehicle;

Get the real-time number of people on the qth bus

的平均人数且记为

即

由相同公交线路编号的公交车上人数的平均值，可以有效的预估线路l_n的拥挤情况，从而反映出乘客当前乘坐的公交车的舒适情况，后文此类计算意义相同。从而得到影响舒适度的权重

其中，k为公交车人数转换为影响程度的转换系数，c为调整系数；k和c通过大量数据拟合得到，后文中所有k和c与此步骤相同。最终得到基于乘客当前乘坐的公交线路的行驶时间和公交车拥挤程度的综合权重

且

其中α为乘客对舒适度的重视程度，α∈[0,1]；当α等于0时，表示乘客希望得到最短出行时间的公交线路，当α等于1时，表示乘客希望得到舒适度最高的公交线路；α∈(0,1)时，表示乘客综合考虑出行时间和舒适度得到的最优公交线路；Calculate the time of all buses from the starting station o to the destination station d that have the same bus line number as the passenger's current bus line number on the nth direct line l _n

the average number of people and recorded as

which is

The average of the number of people on the bus with the same bus line number can effectively estimate the congestion situation of the line l _n , thus reflecting the comfort of the bus that passengers are currently taking, and the following calculations have the same meaning. so as to get the weight that affects the comfort

Among them, k is the conversion coefficient of the number of buses converted into the degree of influence, and c is the adjustment coefficient; k and c are obtained by fitting a large amount of data, and all k and c in the following are the same as this step. Finally, a comprehensive weight based on the travel time of the bus line currently taken by the passenger and the degree of bus congestion is obtained.

and

where α is the degree of importance that passengers place on comfort, α∈[0,1]; when α is equal to 0, it means that passengers want to get the bus line with the shortest travel time; when α is equal to 1, it means that passengers want to get the bus line with the highest comfort level bus route; when α∈(0,1), it represents the optimal bus route obtained by passengers considering travel time and comfort;

表示乘客乘坐最先到达起始站点o的公交车在第k个换乘站点M_k的第i条进站线路

上基于实时路况的行驶时间，即

其中，

为小汽车基于实时路况下经过第k个换乘站点M_k的第i条进站线路

的行驶时间，μ为换算系数，且μ＞1，

为第k个换乘站点M_k的第i条进站线路

上的公交车站个数且不包括起始站点o和第k个换乘站点M_k，T为公交车在每个车站的平均停靠时间；Let the weight of the travel arc set FL′ starting from the virtual departure nodes of all inbound lines of all transfer stations and taking the virtual arrival nodes of all inbound lines of all transfer stations as the end point

Indicates that the passenger takes the bus that first arrives at the starting station o at the i-th inbound line at the k-th transfer station M _k

The driving time based on real-time road conditions on the

in,

is the i-th inbound line of the car passing through the k-th transfer station M _k based on real-time road conditions

The travel time of , μ is the conversion factor, and μ > 1,

is the i-th inbound line of the k-th transfer station M _k

The number of bus stops on the bus and does not include the starting station o and the k-th transfer station M _k , T is the average stop time of the bus at each station;

上从起始站点o至第k个换乘站点M_k之间的公交车辆，且与乘客当前乘坐的公交线路编号相同的公交车总数，公交车总数

包含当前乘坐的车辆；Get the i-th inbound line of the k-th transfer station M _k

The total number of buses from the starting station o to the _k -th transfer station Mk, and the total number of buses with the same bus line number as the passenger's current bus line number, the total number of buses

Include the current vehicle;

Get the real-time number of people on the qth bus

上与乘客当前乘坐的公交线路编号相同的，从起始站点o至第k个换乘站点M_k之间的全部公交车在时刻

的平均人数且记为

即

从而得出影响舒适度的权重

且

其中，k为公交车人数转换为影响程度的转换系数，c为调整系数。最终得到基于乘客当前乘坐的公交线路的行驶时间和公交车拥挤程度的综合权重

且

其中，α为乘客对舒适度的重视程度，α∈[0,1]；当α等于0时，表示乘客希望得到最短出行时间的公交线路，当α等于1时，表示乘客希望得到舒适度最高的公交线路；α∈(0,1)时，表示乘客综合考虑出行时间和舒适度得到的最优公交线路；Calculate the i-th inbound line through the k-th transfer station M _k

All buses from the starting station o to the _k -th transfer station Mk with the same bus line number as the passenger's current bus line number are at the time

the average number of people and recorded as

which is

Thereby, the weights that affect the comfort level are obtained

and

Among them, k is the conversion coefficient of the number of buses converted into the degree of influence, and c is the adjustment coefficient. Finally, a comprehensive weight based on the travel time of the bus line currently taken by the passenger and the degree of bus congestion is obtained.

and

Among them, α is the passenger's degree of emphasis on comfort, α∈[0,1]; when α is equal to 0, it means that the passenger wants to get the bus line with the shortest travel time, and when α is equal to 1, it means that the passenger wants to get the highest level of comfort When α∈(0,1), it represents the optimal bus route obtained by passengers considering travel time and comfort;

表示乘客乘坐最先到达第k个换乘站点M_k的公交车在第j条出站线路

上基于实时路况的行驶时间，即

其中，

为小汽车基于实时路况下经过第k个换乘站点M_k的第j条出站线路

的行驶时间，μ为换算系数，且μ＞1，

为第k个换乘站点M_k的第j条出站线路

上的公交车站个数，且不包括第k个换乘站点M_k和目的站点d，T为公交车在每个车站的平均停靠时间；Let the weight of the travel arc set AL' starting from the virtual departure nodes of all outbound lines of all transfer stations and ending at the destination station d

Indicates that the passenger takes the bus that first arrives at the k-th transfer station M _k on the j-th outbound line

The driving time based on real-time road conditions on the

in,

is the jth outbound line of the car passing through the _kth transfer station Mk based on real-time road conditions

The travel time of , μ is the conversion factor, and μ > 1,

is the jth outbound line of the _kth transfer station Mk

The number of bus stops on the bus, excluding the k-th transfer station M _k and the destination station d, T is the average bus stop time at each station;

上从第k个换乘站点M_k至目的站点d之间的公交车辆，且与乘客当前乘坐的公交线路编号相同的公交车总数，公交车总数

包含当前乘坐的车辆；Get the jth outbound line of the kth transfer station M _k

The total number of buses from the k-th transfer station M _k to the destination station d, and the total number of buses with the same bus line number as the passenger's current bus line number, the total number of buses

Include the current vehicle;

Get the real-time number of people on the qth bus

上与乘客当前乘坐的公交线路编号相同的，从第k个换乘站点M_k至目的站点d的全部公交车在时刻

的平均人数且记为

即

由此得出影响舒适度的权重

且

其中k为公交车人数转换为影响程度的转换系数，c为调整系数，最终得到基于乘客当前乘坐的公交线路的行驶时间和公交车拥挤程度的综合权重

且

其中α为乘客对舒适度的重视程度，α∈[0,1]。当α等于0时，表示乘客希望得到最短出行时间的公交线路，当α等于1时，表示乘客希望得到舒适度最高的公交线路。α∈(0,1)时，表示乘客综合考虑出行时间和舒适度得到的最优公交线路；得到扩展公交网络图，如图3所示。Calculate the jth outbound line through the _kth transfer station Mk

All buses from the k-th transfer station M _k to the destination station d have the same bus line number as the passenger's current bus line number at the time

the average number of people and recorded as

which is

This results in a weight that affects comfort

and

Among them, k is the conversion coefficient of the number of buses converted into the degree of influence, and c is the adjustment coefficient, and finally the comprehensive weight based on the travel time of the bus line currently taken by the passenger and the degree of bus congestion is obtained.

and

where α is the passenger's emphasis on comfort, α∈[0,1]. When α is equal to 0, it means that passengers want to get the bus line with the shortest travel time, and when α is equal to 1, it means that passengers want to get the bus line with the highest comfort level. When α∈(0,1), it represents the optimal bus route obtained by the passengers considering the travel time and comfort degree; the extended bus network diagram is obtained, as shown in Figure 3.

Step 4: Use the combined dynamic programming algorithm to find the optimal path from the starting station o to the destination station d in the expanded public transport network graph G″=(V′, A′, ω) after loading the weight information:

Step 4.0. Divide the weighted directed graph G"=(V', A', ω) into direct line network, transfer line network and mixed line network according to whether there is a transfer line. If the weighted directed graph G" =(V′,A′,ω) is the direct line network, then go to step 4.1 and step 4.3; if the weighted directed graph G″=(V′,A′,ω) is the transfer line network, then go to step 4.2 and step 4.3; if the weighted directed graph G″=(V′, A′, ω) is a mixed line network, then perform steps 4.1 to 4.3;

Step 4.1. Obtain the optimal path of the direct line network:

Step 4.1.1. Let a represent the current stage, let the state variable s _a represent the possible node positions at the beginning of the current stage a, the decision variable u _a represent the arcs that may be selected at the beginning of the current stage a, and define the indicator function V _a (s ₁ ,u ₁ ,…s _a-1 ,u _a-1 ,s _a ) is the sum of the weights of waiting arcs and travel arcs corresponding to all bus lines selected before the current stage a, let the optimal value function f _a (s _a )=min{V _a (s ₁ , u ₁ ,...s _a-1 ,u _a-1 ,s _a )}, define the boundary condition f ₁ (s ₁ )=0; reach the destination site, which is convenient for loop calculation.

When a=1, initialize s _a as the starting site o;

When a=2, initialize s _a as the virtual departure node corresponding to all direct routes from the starting station o;

When a=3, initialize s _a as the destination site d;

Step 4.1.2, let n=1;

Step 4.1.3, calculation

Step 4.1.4, assign n+1 to n, and judge whether n>N is established, if so, go to step 4.1.5, otherwise, go to step 4.1.3; this step traverses all virtual departure nodes of all direct routes.

令l_n ^*为

中最小元素对应状态变量的线路；Step 4.1.5, calculation

Let _ln ^* be

The smallest element in the line corresponds to the state variable;

Step 4.2. Obtain the optimal path of the transfer line network:

Step 4.2.1. Let a denote the current stage, let the state variable s _a denote the possible node positions at the beginning of the current stage a, and the decision variable u _a denote the arcs that may be selected at the beginning of the current stage a, and define the indicator function V _a (s ₁ ,u ₁ ,…s _a-1 ,u _a-1 ,s _a ) is the sum of the weights of waiting arcs and travel arcs corresponding to all bus lines selected before the current stage a, let the optimal value function f _a (s _a )=min{V _a (s ₁ , u ₁ ,...s _a-1 ,u _a-1 ,s _a )}, define the boundary condition f ₁ (s ₁ )=0;

When a=1, initialize s _a as the starting site o;

When a=2, initialize s _a as the virtual departure node corresponding to all inbound lines from the starting station o to all transfer stations;

When a=3, the initialization s _a is the virtual arrival node corresponding to all incoming lines from the starting station o to all transfer stations;

When a=4, initialize s _a as the virtual departure node corresponding to all outbound lines from all transfer stations to the destination station;

When a=5, initialize s _a as the destination site d;

Step 4.2.2, let k=1;

Step 4.2.3, let i=1;

和

Step 4.2.4, calculation

and

Step 4.2.5. Assign i+1 to i, and judge whether i>I _k is established. If so, execute step 4.2.6; otherwise, execute step 4.2.4; All virtual departure nodes in site set O are traversed.

Step 4.2.6. Assign k+1 to k, and judge whether k>K is established. If so, go to step 4.2.7. Otherwise, go to step 4.2.3; In the transfer line, the virtual departure node in the starting station set O and the virtual arrival node in the transfer station set M' are all traversed.

Step 4.2.7, let k=1;

Step 4.2.8, let j=1;

Step 4.2.9, calculation

为

中最小元素对应状态变量的进站线路；make

for

The smallest element in the inbound line corresponds to the state variable;

Step 4.2.10, assign j+1 to j, and judge whether j>J _k is established, if so, go to step 4.2.11, otherwise, go to step 4.2.9;

Step 4.2.11. Assign k+1 to k, and judge whether k>K is established. If so, execute step 4.2.12; otherwise, execute step 4.2.8; All virtual departure nodes in the transfer station set M' in the transfer line are traversed.

Step 4.2.12, calculation

为

中最小元素对应状态变量的出站线路；make

for

The smallest element in the outbound line corresponding to the state variable;

Step 4.3. Comprehensively compare the travel time of the direct line and the transfer line, so as to obtain the optimal path of the weighted directed graph G″=(V′,A′,ω):

If f ₃ (d)≤f ₅ (d) or the weighted directed graph G″=(V′,A′,ω) is a direct line network, select a direct line, and the optimal direct line is from the starting station o Take the bus on the direct line l _n ^* to the destination station d, denoted as

上的公交车至第k个换乘站点M_k换乘，然后乘坐第j条出站线路

上的公交车至目的站点d，记为

If f ₃ (d)>f ₅ (d) or the weighted directed graph G″=(V′,A′,ω) is the transfer line network, select the transfer line, and the optimal transfer line is from Start station o take the i-th incoming line at the k-th transfer station

Take the bus on to the k-th transfer station M _k to transfer, and then take the j-th outbound line

take the bus to the destination station d, denoted as

If f ₃ (d)=f ₅ (d)=+∞, then the optimal route is empty, which means that based on the departure time t _o when the passenger arrives at the starting station o, the passenger cannot catch the last train, and thus cannot complete the trip. ;

Step 5: Obtain the current position of the passenger, and determine whether the current position has reached the new station. If it does not reach the new station, after updating the current position of the passenger, repeat step 5. If it reaches the new station, record the new station as o' ;

If the new station o' is not the destination station d, then assign o' to the passenger's current location o, and perform step 1; thus loop continuously, and constantly update the real-time optimal path.

If the new station o' is the destination station d, the current bus travel planning is ended.

Claims (1)

1. a bus travel planning method considering the active transfer of passengers on the way, it is characterized in that carrying out according to the following steps: Step 1. Obtain the original bus network for passengers to travel: According to the starting station o and destination station d of the passenger's trip, the original bus network G = (V, A) of the passenger's trip is obtained, where V is the station set, and V = {o, M, d}; M is the transfer station set, and M={M ₁ ,M ₂ ,…,M _k ,…,M _K }, where M _k is the k-th transfer station, k=1,2,…,K, K is the transfer station A is the set of lines in the original bus network G, and A={L,FL,AL}, where L is the set of direct lines between the starting station o and the destination station d, and L={ l ₁ ,l ₂ ,...,l _n ,...,l _N }, l _n is the nth direct line between the starting station o and the destination station d, n=1,2,...,N,N is the total number of direct lines; FL is the line set from the starting station o to each transfer station in the transfer station set M, and FL={FL ₁ ,FL ₂ ,...,FL _k ,...,FL _K } , where FL _k is the set of inbound routes from the starting station o to the k-th transfer station M _k , and

in,

is the i-th inbound line from the starting station o to the k-th transfer station M _k , i=1, 2, . . . , I _k , I _k is the starting station o to the k-th station The total number of inbound lines of transfer station M _k ; AL is the set of outbound lines from transfer station set M to destination station d, and AL={AL ₁ ,AL ₂ ,…,AL _k ,…,AL _K }, AL _k is the set of outbound lines from the k-th transfer station M _k to the destination station d, and

in,

is the j-th outbound line from the k-th transfer station M _k to the destination station d, j=1, 2,...,J _k , J _k is the k-th transfer station M _k to the destination station d The total number of outbound lines; Step 2: Obtain the extended public transport network based on the original public transport network G: 2.1 Obtain the expanded site set V′={O,M′} from the site set V: Step 2.1.1 In the line set A, the n-th direct line ln starting from the starting station o and the i- _th inbound line from the starting station o to the _k -th transfer station Mk are divided into

The corresponding virtual departure nodes are respectively recorded as

and

Thereby, the virtual departure nodes corresponding to all direct lines from the starting station o and all inbound lines from the starting station o to all transfer stations together with the starting station o constitute the starting station set O; Step 2.1.2 Put the i-th incoming line of the k-th transfer station M _k in the line set A

The corresponding virtual arrival node is denoted as

The jth outbound line from the kth transfer station _Mk to the destination station d

The corresponding virtual departure node is recorded as

Thus, the virtual arrival nodes corresponding to all inbound lines from the starting station o to the _kth transfer station Mk and the virtual departure nodes corresponding to all outbound lines from the kth transfer station _Mk to the destination station d form the k-th transfer station set M′ _k ; and then obtain all transfer station sets M′={M′ _k |k=1,2,…,K}; 2.2 Construct a new line set A' to generate an extended bus network G'=(V', A'): definition

Indicates the virtual departure node corresponding to the nth direct line l _n starting from the starting station o

is the waiting arc for the end point; definition

Indicates the i-th inbound line starting from the starting station o and taking the k-th transfer station M _k

Corresponding virtual departure node

is the waiting arc of the end point; thus the waiting arc set of the initial site set O is obtained, denoted as

definition

Indicates the i-th inbound line at the k-th transfer station M _k

virtual arrival node of

as the starting point, take the jth outbound line of the kth transfer station M _k

virtual departure node

is the waiting arc of the end point; thus the waiting arc set of the k-th transfer station set M′ _k is obtained, denoted as

Then, the waiting arc set of all transfer station set M' is obtained, denoted as

The total waiting arc set WL is composed of the waiting arc set WLO of the starting station set _O and the waiting arc set WL _M of all transfer station sets M′, namely WL={ _WLO ,WL _M }; definition

represents the virtual departure node of the nth direct line l _n

As the starting point and the destination station d as the end point, the travel arc set with the virtual departure nodes of all direct routes as the start point and the destination station d as the end point is obtained, which is recorded as

definition

Indicates the i-th inbound line at the k-th transfer station M _k

virtual departure node

as the starting point, take the i-th inbound line of the k-th transfer station M _k

virtual arrival node of

is the driving arc at the end point, so as to obtain the set of driving arcs starting from the virtual departure nodes of all inbound lines of all transfer stations and taking the virtual arrival nodes of all inbound lines of all transfer stations as the end point, denoted as

definition

represents the jth outbound line at the _kth transfer station Mk

virtual departure node

As the starting point and the destination station d as the end point, the set of travel arcs with the virtual departure nodes of all outbound lines of all transfer stations as the start point and the destination station d as the end point is obtained, denoted as

From the travel arc set L' starting from the virtual departure nodes of all direct lines and ending at the destination station d, starting from the virtual departure nodes of all inbound lines of all transfer stations, and taking all inbound lines of all transfer stations as the starting point The travel arc set FL′ with the virtual arrival node as the end point and the travel arc set AL′ with the virtual departure nodes of all outbound lines of all transfer stations as the starting point and the destination station d as the end point constitute the total travel arc set RL, that is, RL ={L',FL',AL'}; A new line set is formed by the total waiting arc set WL and the total traveling arc set RL, denoted as A′={WL,RL}; Step 3: Calculate the weights of waiting arcs and driving arcs on the extended bus network: Step 3.1. Set the moment when the passenger arrives at the starting station o as t _o , and at the same time add the real-time bus information and road condition information to the extended bus network G′=(V′, A′); Step 3.2, assign the corresponding weight ω to the traveling arc and the waiting arc in the new line set A', so as to obtain the weighted directed graph G"=(V', A', ω), where the weight ω includes:

Let the weight of the waiting arc set WLO of the starting site set _O be

Represents the waiting time for passengers to take the bus on the nth direct line l _n that first arrives at the starting station o after time t _o , i.e.

in,

Represents the time at which the first bus on the nth direct line l _{n arrives at the starting station o after} the time to If there are no more buses on the direct line l _n , then let

Let the weight of the waiting arc set WLO of the starting site set _O be

Indicates that the passenger takes the i-th inbound line of the k-th transfer station M _k

The waiting time for the bus that first arrives at the starting station o, i.e.

in,

represents the i-th inbound line at the k-th transfer station M _k after time t _o

The time when the bus that first arrives at the starting station o arrives at o, if the ith incoming line at the _kth transfer station Mk after time t _o

If there is no longer a bus on the

Let the weight of the waiting arc set WLM of the transfer station set _M '

Indicates that the passenger takes the i-th inbound line of the k-th transfer station M _k

After the bus on board arrives at _Mk , the passenger takes the jth outbound line of the _kth transfer station Mk

The waiting time for the first bus to arrive at M _k , namely

in,

is the ith incoming line of the bus that first arrives at the starting station o after the time t _o and passes through the _kth transfer station Mk

When arriving at the k-th transfer station M _k ,

expressed at the moment

Then the j-th outbound line at the k-th transfer station M _k

to arrive at time M _k first, if the time

After that, there is no longer the jth outbound line that arrives at the _kth transfer station _Mk and passes through the kth transfer station Mk

bus, the order

Let the weight of the travel arc set L′ starting from the virtual departure nodes of all direct routes and ending at the destination station d

Represents the travel time of passengers taking the bus that first arrives at the starting station o on the nth direct line l _n based on real-time road conditions, namely

in,

is the travel time of the car through the nth direct line l _n based on real-time road conditions, μ is the conversion factor, and μ>1,

is the number of bus stops on the _nth direct line ln and does not include the starting station o and destination station d, and T is the average bus stop time at each station; Obtain the total number of buses between the starting station o and the destination station d on the nth direct line l _n , and the total number of buses with the same bus line number as the passenger's current bus line number is recorded as Q _n , the total number of buses Q Include the current vehicle; Get the real-time number of people on the qth bus

Calculate the time of all buses from the starting station o to the destination station d that have the same bus line number as the passenger's current bus line number on the nth direct line l _n

the average number of people and recorded as

which is

so as to get the weight that affects the comfort

Among them, k is the conversion coefficient of the number of buses converted into the degree of influence, and c is the adjustment coefficient; finally, the comprehensive weight based on the travel time of the bus line currently taken by passengers and the degree of bus congestion is obtained.

and

where α is the passenger's degree of emphasis on comfort, α∈[0,1]; when α is equal to 0, it means that the passenger wants to get the bus route with the shortest travel time; when α is equal to 1, it means that the passenger wants to get the bus line with the highest comfort level bus route; when α∈(0,1), it represents the optimal bus route obtained by passengers considering travel time and comfort; Let the weight of the travel arc set FL′ starting from the virtual departure nodes of all inbound lines of all transfer stations and taking the virtual arrival nodes of all inbound lines of all transfer stations as the end point

Indicates that the passenger takes the bus that first arrives at the starting station o at the i-th inbound line at the k-th transfer station M _k

The driving time based on real-time road conditions on the

in,

is the i-th inbound line of the car passing through the k-th transfer station M _k based on real-time road conditions

The travel time of , μ is the conversion factor, and μ > 1,

is the i-th inbound line of the k-th transfer station M _k

The number of bus stops on the bus and does not include the starting station o and the k-th transfer station M _k , T is the average stop time of the bus at each station; Get the i-th inbound line of the k-th transfer station M _k

The total number of buses from the starting station o to the _k -th transfer station Mk, and the total number of buses with the same bus line number as the passenger's current bus line number, the total number of buses

Include the current vehicle; Get the real-time number of people on the qth bus

Calculate the i-th inbound line through the k-th transfer station M _k

All buses from the starting station o to the _k -th transfer station Mk with the same bus line number as the passenger's current bus line number are at the time

the average number of people and recorded as

which is

Thereby, the weights that affect the comfort level are obtained

and

Among them, k is the conversion coefficient of the number of buses converted into the degree of influence, and c is the adjustment coefficient; finally, the comprehensive weight based on the travel time of the bus line currently taken by passengers and the degree of bus congestion is obtained

and

Among them, α is the degree of importance that passengers place on comfort, α∈[0,1]; when α is equal to 0, it means that passengers want to get the bus line with the shortest travel time, and when α is equal to 1, it means that passengers want to get the highest level of comfort When α∈(0,1), it represents the optimal bus route obtained by passengers considering travel time and comfort; Let the weight of the travel arc set AL' starting from the virtual departure nodes of all outbound lines of all transfer stations and ending at the destination station d

Indicates that the passenger takes the bus that first arrives at the k-th transfer station M _k on the j-th outbound line

The driving time based on real-time road conditions on the

in,

is the jth outbound line of the car passing through the _kth transfer station Mk based on real-time road conditions

The travel time of , μ is the conversion factor, and μ > 1,

is the jth outbound line of the _kth transfer station Mk

The number of bus stops on the bus, excluding the k-th transfer station M _k and the destination station d, T is the average bus stop time at each station; Get the jth outbound line of the kth transfer station M _k

The total number of buses from the k-th transfer station _Mk to the destination station d, and the total number of buses with the same bus line number as the passenger's current bus line number, the total number of buses

Include the current vehicle; Get the real-time number of people on the qth bus

Calculate the jth outbound line through the _kth transfer station Mk

All buses from the k-th transfer station M _k to the destination station d have the same bus line number as the passenger's current bus line number at the time

the average number of people and recorded as

which is

This results in a weight that affects comfort

and

Among them, k is the conversion coefficient of the number of buses converted into the degree of influence, and c is the adjustment coefficient, and finally the comprehensive weight based on the travel time of the bus line currently taken by the passenger and the degree of bus congestion is obtained.

and

where α is the passenger's degree of emphasis on comfort, α∈[0,1]; when α is equal to 0, it means that the passenger wants to get the bus route with the shortest travel time; when α is equal to 1, it means that the passenger wants to get the bus line with the highest comfort level bus route; when α∈(0,1), it represents the optimal bus route obtained by passengers considering travel time and comfort; Step 4: Use the combined dynamic programming algorithm to find the optimal path from the starting station o to the destination station d in the expanded public transport network graph G″=(V′, A′, ω) after loading the weight information: Step 4.0. Divide the weighted directed graph G"=(V', A', ω) into direct line network, transfer line network and mixed line network according to whether there is a transfer line. If the weighted directed graph G" =(V′,A′,ω) is the direct line network, then go to step 4.1 and step 4.3; if the weighted directed graph G″=(V′,A′,ω) is the transfer line network, then go to step 4.2 and step 4.3; if the weighted directed graph G″=(V′, A′, ω) is a mixed line network, then perform steps 4.1 to 4.3; Step 4.1. Obtain the optimal path of the direct line network: Step 4.1.1. Let a represent the current stage, let the state variable s _a represent the possible node positions at the beginning of the current stage a, the decision variable u _a represent the arcs that may be selected at the beginning of the current stage a, and define the indicator function V _a (s ₁ ,u ₁ ,…s _a-1 ,u _a-1 ,s _a ) is the sum of the weights of waiting arcs and travel arcs corresponding to all bus lines selected before the current stage a, let the optimal value function f _a (s _a )=min{V _a (s ₁ , u ₁ ,...s _a-1 ,u _a-1 ,s _a )}, define the boundary condition f ₁ (s ₁ )=0; When a=1, initialize s _a as the starting site o; When a=2, initialize s _a as the virtual departure node corresponding to all direct routes from the starting station o; When a=3, initialize s _a as the destination site d; Step 4.1.2, let n=1; Step 4.1.3, calculation

Step 4.1.4, assign n+1 to n, and judge whether n>N is established, if so, go to step 4.1.5, otherwise, go to step 4.1.3; Step 4.1.5, calculation

Let _ln ^* be

The smallest element in the line corresponds to the state variable; Step 4.2. Obtain the optimal path of the transfer line network: Step 4.2.1. Let a represent the current stage, let the state variable s _a represent the possible node positions at the beginning of the current stage a, the decision variable u _a represent the arcs that may be selected at the beginning of the current stage a, and define the indicator function V _a (s ₁ ,u ₁ ,…s _a-1 ,u _a-1 ,s _a ) is the sum of the weights of waiting arcs and travel arcs corresponding to all bus lines selected before the current stage a, let the optimal value function f _a (s _a )=min{V _a (s ₁ , u ₁ ,...s _a-1 ,u _a-1 ,s _a )}, defining the boundary condition f ₁ (s ₁ )=0; When a=1, initialize s _a as the starting site o; When a=2, initialize s _a as the virtual departure node corresponding to all inbound lines from the starting station o to all transfer stations; When a=3, initialize s _a as the virtual arrival node corresponding to all incoming lines from the starting station o to all transfer stations; When a=4, initialize s _a as the virtual departure node corresponding to all outbound lines from all transfer stations to the destination station; When a=5, initialize s _a as the destination site d; Step 4.2.2, let k=1; Step 4.2.3, let i=1; Step 4.2.4, calculation

and

Step 4.2.5, assign i+1 to i, and judge whether i>I _k is established, if so, execute step 4.2.6, otherwise, execute step 4.2.4; Step 4.2.6, assign k+1 to k, and judge whether k>K is established, if so, go to step 4.2.7, otherwise, go to step 4.2.3; Step 4.2.7, let k=1; Step 4.2.8, let j=1; Step 4.2.9, calculation

make

for

The smallest element in the inbound line corresponds to the state variable; Step 4.2.10, assign j+1 to j, and judge whether j>J _k is true, if true, go to step 4.2.11, otherwise, go to step 4.2.9; Step 4.2.11, assign k+1 to k, and judge whether k>K is established, if so, go to step 4.2.12, otherwise, go to step 4.2.8; Step 4.2.12, calculation

make

for

The smallest element in the outbound line corresponding to the state variable; Step 4.3. Comprehensively compare the travel time of the direct line and the transfer line, so as to obtain the optimal path of the weighted directed graph G″=(V′,A′,ω): If f ₃ (d)≤f ₅ (d) or the weighted directed graph G″=(V′,A′,ω) is a direct line network, select a direct line, and the optimal direct line is from the starting station o Take the bus on the direct line l _n ^* to the destination station d, denoted as

If f ₃ (d)>f ₅ (d) or the weighted directed graph G″=(V′,A′,ω) is the transfer line network, select the transfer line, and the optimal transfer line is from Start station o take the i-th incoming line at the k-th transfer station

Take the bus on to the k-th transfer station M _k to transfer, and then take the j-th outbound line

take the bus to the destination station d, denoted as

If f ₃ (d)=f ₅ (d)=+∞, then the optimal route is empty, indicating that based on the departure of the passenger at the time t _o of the starting station o, the passenger cannot catch the last train and thus cannot complete the trip. ; Step 5: Obtain the current position of the passenger, and determine whether the current position has reached the new station. If it does not reach the new station, after updating the current position of the passenger, repeat step 5. If it reaches the new station, record the new station as o' ; If the new station o' is not the destination station d, assign o' to the passenger's current location o, and execute step 1; If the new station o' is the destination station d, the current bus travel planning is ended.

Images