CN108764538B - Bus network optimization design method suitable for changes of unobvious demands - Google Patents

Abstract

The invention discloses a bus network optimization design method specially suitable for changes of unobvious demands, which is characterized in that an effective bus line network optimization model aiming at the total cost of drivers who go to the bus in a minimized and direct way and drivers who do not meet the demands is established by improving the existing genetic algorithm, so that a more economic, effective, reasonable and convenient bus network design method is provided under the changes of the unobvious demands, the traditional streamline unified bus network design method is broken through, the flexibility is higher, the operability and sustainability are higher, and the optimization quality and the search efficiency are greatly improved.

Description

An optimal design method of bus network suitable for unobvious changes in demand

Field of study

The invention relates to the field of traffic engineering, and provides a design method for the layout planning of a bus line network, in particular, to an optimization design method of a bus line network suitable for insignificant demand changes.

Background technique

With the continuous advancement of urbanization in my country, urban public transportation has become a very important aspect of urban construction. Public transportation can not only ensure the normal traffic travel of urban residents, but also become an important means to improve the utilization rate of traffic resources, ease traffic congestion, reduce traffic pollution, and save land resources and energy. Among them, public transportation is one of the most widely used and most used modes of transportation.

The bus line network is generally oriented by the travel needs of residents. Because their travel needs are constantly changing, the bus line network scheme needs to be designed and updated frequently. When there is no significant change in bus demand and the original bus network plan needs to be redesigned, transportation planners and managers usually do not want the configuration of the bus network to change too much. However, if you continue to use the traditional bus network design model, you may get a new scheme with greatly changed line configuration, which is contrary to the actual situation. At the same time, the implementation and layout of the new scheme will also generate unnecessary manpower and Time wasting.

Therefore, combined with the actual development of the current traffic engineering field and the complex and uncertain characteristics of the existing bus network design, based on the current situation of urban transportation in my country, an operable and cost-effective bus network is designed, especially suitable for The bus line network without obvious changes in demand is of great significance to the development of urban politics, economy, culture, education, science and technology.

SUMMARY OF THE INVENTION

The present invention provides a bus network optimization design method specially suitable for the insignificant demand change because the prior art pays less attention to the bus line network design method suitable for the insignificant demand change. The improvement of the genetic algorithm establishes an effective model of bus route network optimization aiming at minimizing the total cost of direct travelers, transferers and unmet needs, so as to provide a more economical model without obvious changes in demand. Effective, reasonable and convenient bus network design method.

In order to achieve the above-mentioned purpose, the technical solution adopted in the present invention is: a method for optimizing the design of a bus line network suitable for insignificant demand changes, comprising the following steps:

Step 1: Establish objective function and set constraints;

Step 2: Select the original bus network scheme as the initial scheme, and use the network analysis program to calculate its fitness value;

Step 3: Set the initial scheme as the candidate optimal scheme;

Step 4: Carry out the breeding process for the candidate optimal solution in Step 3, including the selection process and the mutation process,

Step 41: Selection process: select the lines that will be mutated in all schemes by probability.

Step 42: Probabilistic intermediate single-site mutation process

Step 421 : Determine the two adjacent stations of the intermediate station on the bus line, and the directly connected stations of the intermediate station not on the line, and check the above-mentioned "directly connected stations not on the line" and "two adjacent stations on the bus line" Whether it is directly connected, if there is a direct connection, go to step 422, and the connectable stations are the stations that the intermediate stations can mutate to; "Nearby sites" are not directly connected, go to step 43;

Step 422: Take the intermediate site determined in step 421 and the site to which it can be mutated as candidate sites, and determine the site to mutate to based on the sum of the upstream and downstream requirements of these candidate sites, and the upstream demand refers to all sites before the intermediate site. The number of trips to the candidate site, and the downstream demand refers to the number of trips from the candidate site to all the sites behind the intermediate site;

Step 43: Carry out the mutation process of the initial site according to the probability;

Step 431: When the starting station and a certain station can be directly connected, the starting station can be changed to the second station, and the original second station becomes the starting station;

Step 432: If the starting site is not directly connected to any site, and there is no site that can be mutated to, then go to step 5; and then perform the mutation process of the starting site in step 431 on the end site according to the probability;

Step 5: Calculate the fitness value of the new scheme after the above steps according to the network analysis program, compare it with the fitness value of the candidate optimal scheme in step 2, and select the smaller one as the new candidate optimal scheme. There is one and only one final plan;

Step 6: Repeat steps 4-5. If the number of repetitions reaches a predetermined number of times, the iteration is stopped, and the candidate optimal solution is selected as the 'optimal solution'; if the number of reproductions does not reach the predetermined number of times, return to step 4.

As an improvement of the present invention, the probability in the step 4 is set according to the size of the network and the requirement of design time.

As another improvement of the present invention, the objective function in the step 1 is shown in the following formula:

The constraints in step 1 are as follows:

表示在路径n上满足站点i到站点j的公交需求，

表示在换乘路径tr上满足站点i到站点j的公交需求，DR_ij表示服务过从站点i到站点j的直达线路的集合，TR_ij表示服务过从站点i到站点j的换乘线路的集合，

表示在路径n上从站点i到站点j的出行时间，

表示在换乘路径tr上从站点i到站点j的出行时间，

表示在路径n的最大流量，C₁、C₂、C₃分别表示直达者成本、换乘者成本和为满足需求者成本的权重影响系数(C₁+C₂+C₃＝1)。where V is the set of all stations, i is station i, j is station j, d _ij is the travel demand from station i to station j, L _max is the maximum length of the bus line, L _min is the minimum length of the bus line, Q _max represents the maximum capacity of each vehicle, T _d represents the time cost of each unmet bus demand, n represents the nth line of a scheme, tr represents the transfer route when using more than two routes, L _n represents the total length of line n,

represents that the bus demand from station i to station j is satisfied on path n,

Indicates that the bus demand from station i to station j is satisfied on the transfer route tr, DR _ij represents the set of direct routes that have served from station i to station j, and TR _ij is the set of routes that have served the transfer lines from station i to station j. gather,

represents the travel time from station i to station j on path n,

represents the travel time from station i to station j on the transfer route tr,

Represents the maximum flow on the path n, C ₁ , C ₂ , and C ₃ represent the cost of direct access, the cost of transfer, and the weighted influence coefficient (C ₁ +C ₂ +C ₃ =1) to satisfy the cost of demanders, respectively.

As an improvement of the present invention, the network analysis program in the step 2 includes:

Step 21: Eliminate the direct bearer traffic of a path from the original demand matrix, and assign these traffic to this path as direct demand. When the direct bearer traffic of all paths is eliminated, the direct update demand matrix is obtained;

Step 22: Eliminate the transfer carrying traffic of a transfer path from the direct update demand matrix in step 21, and assign these flows to the corresponding paths as transfer requirements. After all the transfer carrying traffic is eliminated, Get a transfer update demand matrix updated by the transfer demand.

Step 23: Output the parameters and variables required in all objective functions of step 1, and calculate the fitness value of this scheme (Z in the objective function).

As a further improvement of the present invention, in the step 6, the predetermined number of times is determined according to the running time. When the running time is limited, the predetermined number of times must ensure that the program runs within the limited time, and the program ends; when there is no running time limit, according to feasible The solution space determines the predetermined number of times. The larger the space, the greater the predetermined number of times.

Compared with the prior art, the present invention proposes a bus network optimization design method specially suitable for insignificant demand changes, improves the selection and mutation process in the traditional genetic algorithm, and deletes the crossover process, so that it has Better optimization quality and search efficiency can not only meet the redesign of the bus line network scheme under not obvious demand changes, it is economical and effective, greatly saves the manpower, material resources and economic costs caused by the implementation and layout of the new scheme, and is also a reasonable resource allocation. Breaking the traditional streamlined design method of unified bus network, it is more flexible, maneuverable and more sustainable.

Description of drawings

Figure 1 is a schematic diagram of the optimization design of the bus network under no obvious changes;

2 is a schematic diagram of a case network in Embodiment 1 of the present invention;

FIG. 3 is a graph of the comparative test results of Example 2 of the present invention.

Detailed ways

The present invention will be described in more detail below with reference to the accompanying drawings and embodiments.

Example 1

An optimization design method of bus network suitable for insignificant changes in demand, as shown in Figure 1, includes the following steps:

Step 1: Establish objective function and set constraints,

The objective function is shown in the following formula:

The constraints are as follows:

表示在路径n上满足站点i到站点j的公交需求，

表示在换乘路径tr上满足站点i到站点j的公交需求，DR_ij表示服务过从站点i到站点j的直达线路的集合，TR_ij表示服务过从站点i到站点j的换乘线路的集合，

表示在路径n上从站点i到站点j的出行时间，

表示在换乘路径tr上从站点i到站点j的出行时间，

表示在路径n的最大流量，C₁、C₂、C₃分别表示直达者成本、换乘者成本和为满足需求者成本的权重影响系数(C₁+C₂+C₃＝1)。where V is the set of all stations, i is station i, j is station j, d _ij is the travel demand from station i to station j, L _max is the maximum length of the bus line, L _min is the minimum length of the bus line, Q _max represents the maximum capacity of each vehicle, T _d represents the time cost of each unmet bus demand, n represents the nth line of a scheme, tr represents the transfer route when using more than two routes, L _n represents the total length of line n,

represents that the bus demand from station i to station j is satisfied on path n,

Indicates that the bus demand from station i to station j is satisfied on the transfer route tr, DR _ij represents the set of direct routes that have served from station i to station j, and TR _ij is the set of routes that have served the transfer lines from station i to station j. gather,

represents the travel time from station i to station j on path n,

represents the travel time from station i to station j on the transfer route tr,

Represents the maximum flow on the path n, C ₁ , C ₂ , and C ₃ represent the cost of direct access, the cost of transfer, and the weighted influence coefficient (C ₁ +C ₂ +C ₃ =1) to satisfy the cost of demanders, respectively.

Step 2: Select the original bus network scheme as the initial scheme, and use the network analysis program to calculate its fitness value, wherein the network analysis program includes:

Step 21: Eliminate the direct bearer traffic of a path from the original demand matrix, and assign these traffic to this path as direct demand. When the direct bearer traffic of all paths is eliminated, the direct update demand matrix is obtained;

Step 22: Eliminate the transfer carrying traffic of a transfer path from the direct update demand matrix in step 21, and assign these flows to the corresponding paths as transfer requirements. After all the transfer carrying traffic is eliminated, Get a transfer update demand matrix updated by the transfer demand;

Step 23: Output the parameters and variables required in all objective functions of step 1, and calculate the fitness value of this scheme (Z in the objective function).

Step 3: Set the initial scheme as the candidate optimal scheme.

Step 4: Carry out the breeding process for the candidate optimal solution in Step 3, including the selection process and the mutation process,

Step 41: Selection process: set the probability according to the network size and design time requirements, and select the lines to be mutated in all schemes according to the probability.

Step 42: Probabilistic intermediate single-site mutation process

Step 421 : Determine the two adjacent stations of the intermediate station on the bus line, and the directly connected stations of the intermediate station not on the line, and check the above-mentioned "directly connected stations not on the line" and "two adjacent stations on the bus line" Whether it is directly connected, if there is a direct connection, go to step 422, and the connectable stations are the stations that the intermediate stations can mutate to; "Nearby sites" are not directly connected, go to step 43;

Step 422: Take the intermediate site determined in step 421 and the site to which it can be mutated as candidate sites, and determine the site to mutate to based on the sum of the upstream and downstream requirements of these candidate sites, and the upstream demand refers to all sites before the intermediate site. The number of trips to the candidate site, and the downstream demand refers to the number of trips from the candidate site to all the sites behind the intermediate site;

Step 43: Carry out the mutation process of the initial site according to the probability;

Step 431: When the starting station and a certain station can be directly connected, the starting station can be changed to the second station, and the original second station becomes the starting station;

Step 432: If the starting site is not directly connected to any site, and there is no site that can be mutated to, then go to step 5; and then perform the mutation process of the starting site in step 431 on the end site according to the probability;

Step 5: Calculate the fitness value of the new scheme after the above steps according to the network analysis program, compare it with the fitness value of the candidate optimal scheme in step 2, and select the smaller one as the new candidate optimal scheme. There is one and only one final plan;

Step 6: Repeat steps 4-5. If the number of repetitions reaches a predetermined number of times, the iteration is stopped, and the candidate optimal solution is selected as the 'optimal solution'; if the number of reproductions does not reach the predetermined number of times, return to step 4. The predetermined number of times is determined according to the running time. When the running time is limited, the predetermined number of times must ensure that the program ends within the limited time; when there is no running time limit, the predetermined number of times is determined according to the feasible solution space. big.

Assuming that we select the sample network as shown in Figure 2, there are 10 stations and 19 road segments. According to the needs of the model, we make the following assumptions (judgments):

1. All buses have the same operating speed and capacity limit, and the roads are not congested;

2. When the travel demand does not change significantly and the original bus network plan needs to be redesigned, compared with the original plan, the optimized plan will not change much in the network configuration;

3. In different schemes, the number of bus lines, the operating frequency of each vehicle and the operating cost are the same.

Set the original scheme as the initial scheme, use the network analysis program to calculate its fitness value, and set it as the first candidate optimal scheme. The bus network scheme with three lines (Line 1: 7, 2, 3, 1, 6; Line 2: 9, 10, 2, 3, 4; Line 3: 8, 7, 1, 4, 6) is a candidate The optimal solution, starting from step 4, is as follows:

Step 41: Selection process: Set the selection probability to 1, which means that each line must undergo a mutation process. The execution in Step 4 is based on the network size and design time. A certain probability needs to be set.

Step 42: Intermediate site mutation process:

Taking line 1 as an example, the intermediate stations are 2, 3, and 1; the adjacent stations of intermediate station 2 on the line are points 3 and 7, and the directly connected stations not on the line are 8, 9 and 10; the intermediate station 3 is on the bus line The adjacent stations on the bus line are points 2 and 1, and the directly connected stations not on the line are 4 and 10; the adjacent stations of the intermediate station 1 on the bus line are points 3 and 6, and the directly connected stations not on the line are 4; the intermediate station 1 can be mutated to the site as point 4, intermediate sites 2 and 3 are not mutated to the site. Therefore, when (d ₇₁ +d ₂₁ +d ₃₁ +d ₁₆ )<(d ₇₄ +d ₂₄ +d ₃₄ +d ₄₆ ), the newly generated line 1 is: 7, 2, 3, 4, 6; when (d 74 +d 24 +d 34 +d 46 ) ₇₁ +d ₂₁ +d ₃₁ +d ₁₆ )>(d ₇₄ +d ₂₄ +d ₃₄ +d ₄₆ ), line 1 does not change.

Step 43: Starting Site Mutation Process:

Taking line 2 as an example, when the starting site is directly connected to the third site, the starting site and the second site exchange positions, and the newly generated line 2 is: 10, 9, 2, 3, 4.

Step 432: End-Site Mutation Process:

Taking line 3 as an example, when the end station is directly connected to the penultimate station, the end station and the penultimate station exchange positions, and the newly generated line 2 is: 8, 7, 1, 6, 4.

Step 5: Scheme comparison: Obtain a new bus route network scheme through steps 41-42-43-432-5, use the network analysis program to calculate its fitness value, and compare it with the fitness value of the candidate optimal scheme, and select the smaller one. is a new candidate optimal solution, and there is only one candidate optimal solution.

Step 6: Checking the number of iterations: Check whether the number of iterations reaches the predetermined number of times, if not, return to step 3; if it does, the program ends, and the candidate optimal solution is output as the final optimal solution.

As shown above, set the original scheme as line 1: 7, 8, 9, 10, 3, 4; line 2: 5, 4, 3, 1, 7; line 3: 9, 10, 2, 1, 4, 6; Line 4: 2, 3, 1, 6, 5; Line 5: 8, 2, 1, 6, 5, 4. Assuming that the original bus network scheme can basically meet the original bus travel demand, only the travel demand within one hour after the insignificant demand change is listed here, as shown in Figure 1 below. Other settings: the length and time unit are the same (same as the length unit in Figure 2); the time cost of each unmet bus demand is 80; the maximum capacity of each vehicle is 40; the maximum and minimum lengths of the bus lines are respectively are 45 and 20; the departure frequency of each route is 5 vehicles/hour; the execution probability of steps 3.2-3.4 are all 0.1; the parameters C ₁ , C ₂ , and C ₃ are 0.15, 0.3, and 0.55, respectively.

Table 1 Demand matrix (times)

The indicators of the optimal plan and the original plan are compared and evaluated, as shown in Table 2 below. The content of the evaluation indicators includes the line network, the number of direct passengers, the number of transfer passengers, the number of unmet needs, the total travel mileage of direct passengers, The total travel mileage and plan adaptation value of the transfer passengers.

Table 2 Comparison of the results of the original scheme and the optimal scheme

It can be seen from the above table that there is not much change in the line configuration between the two schemes. The optimal scheme can meet more direct and transfer times than the original scheme, reduce the number of unmet needs, and maximize the use of The role of the bus line network, the total travel distance of direct travelers and transfer passengers increases, and the average transfer distance decreases. It can be seen that our bus line network optimization design method is very suitable for non-obvious demand changes, and it is very effective. .

Example 2

The difference between this embodiment and Embodiment 1 is that the traditional genetic algorithm (TGA) in the field of traffic engineering includes selection, crossover and mutation processes, while our improved genetic algorithm (IGA) deletes the crossover process and only includes the improved Selection and mutation process, in the comparison of Example 1, we apply the modified IGA and the traditional TGA respectively in our case. Each method was tested 10 times separately, and the predetermined number of iterations was set to 1000. The comparison results are shown in Figure 3.

As can be seen in Figure 3, the fitness values of IGA are better than TGA, which should be due to our improved selection and mutation process. The computation time of IGA is generally higher than that of TGA, which may be because we eliminate the crossover process. This comparison can prove that compared with TGA, IGA application can improve the optimization quality and search efficiency in the design of bus network under the condition of no obvious demand change.

The foregoing has shown and described the basic principles, main features and advantages of the present invention. It should be understood by those skilled in the art that the present invention is not limited by the above examples, the above examples and descriptions only illustrate the principles of the present invention, and the present invention will have various changes without departing from the spirit and scope of the present invention. and improvements, which fall within the scope of the claimed invention. The claimed scope of the present invention is defined by the appended claims and their equivalents.

Claims (4)

1. A method for optimizing the design of a bus network suitable for insignificant demand changes, comprising the following steps: Step 1: Establish an objective function and set constraints. The objective function is shown in the following formula:

The constraints are as follows:

where V is the set of all stations, i is station i, j is station j, d _ij is the travel demand from station i to station j, L _max is the maximum length of the bus line, L _min is the minimum length of the bus line, Q _max represents the maximum capacity of each vehicle, T _d represents the time cost of each unmet bus demand, n represents the nth line of a scheme, tr represents the transfer route when using more than two routes, L _n represents the total length of line n,

represents that the bus demand from station i to station j is satisfied on path n,

Indicates that the bus demand from station i to station j is satisfied on the transfer route tr, DR _ij represents the set of direct routes that have served from station i to station j, and TR _ij is the set of routes that have served the transfer lines from station i to station j. gather,

represents the travel time from station i to station j on path n,

represents the travel time from station i to station j on the transfer route tr,

Represents the maximum flow on the path n, C ₁ , C ₂ , and C ₃ respectively represent the cost of direct access, the cost of transfer, and the weight influence coefficient to meet the cost of demanders (C ₁ +C ₂ +C ₃ =1); Step 2: Select the original bus network scheme as the initial scheme, and use the network analysis program to calculate its fitness value; Step 3: Set the initial scheme as the candidate optimal scheme; Step 4: Carry out the breeding process for the candidate optimal solution in Step 3, including the selection process and the mutation process, Step 41: Selection process: select the lines that will be mutated in all schemes according to the probability; Step 42: Perform an intermediate single-site mutation process according to probability; Step 421 : Determine the two adjacent stations of the intermediate station on the bus line, and the directly connected stations of the intermediate station not on the line, and check the above-mentioned "directly connected stations not on the line" and "two adjacent stations on the bus line" Whether it is directly connected, if there is a direct connection, go to step 422, and the connectable stations are the stations that the intermediate stations can mutate to; "Nearby sites" are not directly connected, go to step 43; Step 422: Take the intermediate site determined in step 421 and the site to which it can be mutated as candidate sites, and determine the site to mutate to based on the sum of the upstream and downstream requirements of these candidate sites, where the upstream demand refers to all sites before the intermediate site to The number of trips of the candidate site, and the downstream demand refers to the number of trips from the candidate site to all the sites behind the intermediate site; Step 43: Carry out the mutation process of the initial site according to the probability; Step 431: When the starting station and a certain station can be directly connected, the starting station can be changed to the second station, and the original second station becomes the starting station; Step 432: If the starting site is not directly connected to any site, and there is no site that can be mutated to, then go to step 5; and then perform the mutation process of the starting site in step 431 on the end site according to the probability; Step 5: Calculate the fitness value of the new scheme according to the above steps according to the network analysis program, compare it with the fitness value of the candidate optimal scheme in step 2, and select the smaller one as the new candidate optimal scheme. There is one and only one final plan; Step 6: Repeat steps 4-5. If the number of repetitions reaches a predetermined number of times, the iteration is stopped, and the candidate optimal solution is selected as the 'optimal solution'; if the number of reproductions does not reach the predetermined number of times, return to step 4. 2 . The method for optimizing the design of a bus network according to claim 1 , wherein the probability in step 4 is set according to the size of the network and the design time. 3 . 3. a kind of bus line network optimization design method suitable for insignificant demand change as claimed in claim 2 is characterized in that the network analysis program in described step 2 comprises: Step 21: Eliminate the direct carrying traffic of a path from the original demand matrix, and assign these flows to this path as direct demand. When the direct carrying traffic of all paths is eliminated, the direct update demand matrix is obtained; Step 22: Eliminate the transfer carrying traffic of a transfer path from the direct update demand matrix in step 21, and assign these flows to the corresponding paths as transfer requirements. After all the transfer carrying traffic is eliminated, Get a transfer update demand matrix updated by the transfer demand; Step 23: Output the parameters and variables required in all objective functions of step 1, and calculate the fitness value of this scheme, that is, Z in the objective function of step 1. 4. The method for optimizing the design of a public transport network suitable for insignificant changes in demand according to one of claims 1-3, wherein the predetermined number of times in the step 6 is determined according to the running time, and when the running time has When the limit is set, the predetermined number of times should ensure that the program ends within the limited time; when there is no running time limit, the predetermined number of times is determined according to the feasible solution space. The larger the space, the greater the predetermined number of times.

Images