CN111291303A - Electric bus scheduling optimization method considering heterogeneity of shift - Google Patents

Abstract

The invention discloses an electric bus scheduling optimization method considering the heterogeneity of shifts, which mainly solves the problem of difficulty in scheduling electric buses. The invention establishes a model suitable for multiple trips of the electric bus by combining the characteristic of multiple charging of the electric bus. The model determines the scheduling scheme of each electric bus and uses the interval of two trips for charging, thereby minimizing the number of electric buses and the operation cost. Meanwhile, the model also considers the influence of shift heterogeneity, such as time unbalance and space compatibility, on the electric bus shift scheduling. In the aspect of solving the algorithm, a satisfactory solution is found by the heuristic algorithm, the optimal scheduling scheme is quickly obtained by applying the column generation algorithm, the method has practical value, and the investment of the fixed cost and the operation cost of the public transport company can be effectively reduced.

Description

An optimization method for electric bus scheduling considering shift heterogeneity

technical field

The invention relates to an optimization method for the scheduling of electric buses, in particular to an optimization of the scheduling of electric buses which further reduces the operating cost on the basis of using the fewest vehicles by deciding the service frequency and the optimal charging timing of the electric buses. method.

Background technique

The popularization of electric buses can reduce greenhouse gas emissions, which is in line with the needs of the national sustainable development strategy. In the field of public transportation, the Ministry of Transport issued a document to vigorously promote the development of new energy vehicles, including electric buses. First-tier cities such as Beijing and Shanghai have already used electric buses on many routes. However, the electric bus itself still has some problems that need to be solved urgently, such as short mileage and long charging time, which also has an impact on the scheduling of electric buses.

The scheduling of traditional fuel buses is to dispatch fuel vehicles to serve a series of shifts with time windows, so that the total fleet size and operating costs are minimized. The scheduling method of electric bus is different from that of traditional fuel bus, because electric bus needs to be charged, and the charging time is long; moreover, bus has the characteristics of obvious high/flat peak heterogeneity, and the shifts are dense during peak hours, which is not suitable for electric bus. Buses are charged, the shifts are sparse during off-peak hours, and electric buses are idle. Therefore, if the charging timing of electric buses cannot be reasonably arranged, some shifts during peak hours will not be completed on time, which will affect subsequent shifts, and a large number of electric buses will waste resources during off-peak hours. The conventional solution is to buy more electric buses to meet the shift demand, which increases the fixed cost of purchasing electric buses and the operating cost of routine maintenance, and also causes waste of resources, which goes against the sustainable development strategy. Therefore, finding an optimal scheduling method suitable for electric buses, which can meet the charging needs and minimize the fleet size and operating cost is the most important problem facing the popularization of electric buses.

SUMMARY OF THE INVENTION

Purpose of the invention: The purpose of the present invention is to design an optimization method for electric bus scheduling considering the heterogeneity of shifts, wherein the characteristics of the heterogeneity of shifts are considered, and the characteristics of multiple trips are applied to the established model. Using this method, we can find the optimal electric bus scheduling strategy to minimize the fleet size and operating cost.

Technical solution: In order to realize the above design requirements, the present invention adopts the following technical solutions: (1) Collect basic information and shift information of electric buses, wherein the basic information of electric buses includes battery capacity, charging efficiency, and charging time; shift information includes each shift Start time, end time, running time, departure station, arrival station. (2) According to the characteristics of electric buses requiring multiple charging, construct an electric bus scheduling model that considers the heterogeneity of high/flat peak shifts and spatial compatibility, and minimizes the fleet size and daily operating costs while meeting its charging needs. And rewrite it into a form suitable for solving the column generation algorithm. (3) Through the column generation algorithm, adding new columns to the column pool makes the objective function of the problem drop continuously, and finds the tightest lower bound of the problem. (4) On the basis of the tightest lower bound, the branch-and-bound algorithm is used to obtain the optimal integer solution of the electric bus scheduling problem, that is, the optimal scheduling scheme of the problem.

The step (1) includes the following steps: (1-1) Determine the position of the electric bus station and expand the station into two virtual points, which are 0 and n+1 respectively. (1-2) Collect shift information, and number the shifts from 1 to n in chronological order. Record the start time a _i , end time b _i , running time t _i , shift interval time t _ij , running direction μ _i of the shift (upper row 1, down row -1), shift power consumption qi _, field The distance from the station to the originating station is m, and the distance from the depot to the terminal station is n. (1-3) Collect electric bus information, and number electric buses from 1 to k. Record the battery capacity Q of the electric bus, the charging efficiency θ, and the average travel speed v.

其中第一部分是购买车队的成本在使用年 限内的均摊，第二部分是日常运营成本，包括空驶成本和班次间等待成本。(2-3)添加约束 使电动公交排班问题符合实际，其中重要的约束是电动公交数量约束，电动公交电量约束， 基本流约束，班次空间兼容性约束，班次时间衔接性约束，出行时间衔接性约束。(2-4)根 据列生成算法的特点，将该模型改写成主-子问题形式。The step (2) includes the following steps: (2-1) Distinguish peak shifts and flat-peak shifts according to the obtained shift information, and peak shifts run longer and more frequently than flat-peak shifts. (2-2) According to the multiple charging characteristics of electric bus, a model suitable for multiple trips of electric bus is constructed, and the maximum number of trips is set to L to limit its excessive trips. Set the objective function to

The first part is the equal share of the cost of purchasing the fleet over the service life, and the second part is the daily operating cost, including the cost of empty driving and the cost of waiting between shifts. (2-3) Add constraints to make the electric bus scheduling problem in line with reality. The important constraints are electric bus quantity constraints, electric bus power constraints, basic flow constraints, shift space compatibility constraints, shift time cohesion constraints, and travel time cohesion constraints. Sexual constraints. (2-4) According to the characteristics of the column generation algorithm, the model is rewritten into a main-sub-problem form.

The corresponding step (3) includes the following steps: (3-1) Use the greedy algorithm to find a set of feasible solutions that satisfy the constraints, as the input of the column generation algorithm. (3-2) Solve the model through the cooperation of the main-sub-problem, that is, the main problem integrates the scheduling plans of all electric buses and transfers the scheduling information to the sub-problem, and the sub-problem is aimed at an electric bus to form a new scheduling After a finite number of iterations, the optimal lower bound of the model is obtained, that is, the non-integer solution closest to the optimal solution of the problem.

Beneficial effects: The present invention provides a set of optimization methods for electric bus scheduling considering the heterogeneity of shifts, and provides a column generation solution algorithm to obtain the optimal solution to the problem. The present invention has the following advantages: 1. To solve the problem of difficult charging of electric buses, and under the condition of minimizing disturbance to shifts, the best charging strategy for electric buses is given. This method can not only reduce the investment of electric buses, but also reduce the its operating expenses. 2. Considering the heterogeneity of shifts, it can be divided into time heterogeneity, such as the running time of shifts in high/off-peak hours, and the density is different; spatial compatibility, such as shifts are divided into up/down directions, Shifts must be alternately connected up and down. This consideration makes the model more practical. 3. Different from the heuristic algorithm to seek a satisfactory solution, the use of the column generation solution algorithm can make the problem quickly find the optimal solution.

Description of drawings

Fig. 1 is the flow chart of electric bus scheduling optimization, and Fig. 2 is the flow chart of the column generation algorithm

Detailed ways

The present invention will be described in detail below with reference to FIG. 1 and FIG. 2 .

As shown in Figure 1, the steps of the present invention are as follows:

1) According to the multiple charging characteristics of electric buses, the present invention applies the idea of multiple trips to the scheduling of electric buses, and constructs an electric bus scheduling model considering the heterogeneity of shifts based on the collected shift information and electric bus information, The main process is as follows:

A. Build the objective function

The objective function of this scheduling model is to minimize fleet size and operating cost, which is set as:

表示第k辆车在第l次出行中服务完班次i又服务了班次j，否则

k是 电动公交编号，i,j表示班次编号，0表示场站或者充电站，l表示电动公交的出行编号。目 标函数分为两部分，第一部分表示所有电动公交第一次出行的费用，这里实际为车队规模的 固定成本在使用年限内的均摊，第二部分表示场站到班次、班次与班次间、班次到场站的费 用，即完成每天所有班次的空驶成本和班次间等待成本。in,

Indicates that the kth vehicle has served shift i and then served shift j in the lth trip, otherwise

k is the electric bus number, i and j are the shift number, 0 is the station or charging station, and l is the trip number of the electric bus. The objective function is divided into two parts. The first part represents the cost of the first trip of all electric buses, which is actually the average share of the fixed cost of the fleet size within the service life. The second part represents the station-to-shift, between shifts and shifts, and shifts The cost of arriving at the station, that is, the cost of emptying all shifts per day and the cost of waiting between shifts.

B. Constraints on the number of electric buses

Constraints on the maximum input quantity for electric buses:

Indicates that in any trip, the maximum number of vehicles departing from the station cannot exceed |K|.

C. Electric bus power constraints

Constraints on the maximum usable electricity for electric buses:

It means that for any vehicle in one trip, the power consumption of completing all shifts cannot exceed Q _safety , that is, the safe power. q _i represents the power consumption to complete the i shift.

D. Elementary flow constraints

In order to ensure the balance of shifts, the flow balance equation is established as follows:

Formula (4) means that for any shift, it must be assigned to a vehicle. Equation (5) means that all vehicles must originate from the depot or charging station. Equation (6) indicates that after serving one shift, another shift is to be served. Equation (7) means that all vehicles must return to the depot or charging station.

E. Shift time coherence constraints

表示k车第l次出行开始服务班次i的时间，M表示一个十分大的数，用于惩罚。Formula (8) represents the time relationship between the two shifts i and j, and the service for shift j must be completed after the service of shift i. in,

Represents the time when car k starts to serve shift i for the lth trip, and M represents a very large number used for punishment.

F. Shift Space Compatibility Constraints

The formula (9) indicates that the upward shift and the downward shift must be alternately connected, wherein μ _i =1 indicates the upward movement, and μ _i =-1 indicates the downward movement.

G. Travel time connectivity constraints

Equation (10) represents the time constraint of the trip, the next trip must be after the end time of the previous trip + the charging time.

表示k车第l次出行回到场站的时间，ω^kl表示k车第l次出行后所需的充电时间，

表示k车第l+1次出行的开始时间。in,

Represents the time when car k returns to the station on the lth trip, ω ^kl represents the charging time required for car k after the lth trip,

represents the start time of the l+1th trip of car k.

H. Other constraints

The following auxiliary constraints are established here:

Equation (11) is the time window constraint for each shift, and Equation (12) represents the charging time required after each trip, that is, the power consumption multiplied by the charging efficiency. where θ is the charging efficiency, and Equation (13) defines a 0-1 decision variable.

The above is the actual model constructed, here the above model is converted into a mathematical form that can be solved by the column generation algorithm:

Main question:

表示k车第l次出行选择 列r，一列表示一次出行服务的班次序列。公式(15)对应公式(4)，公式(16)对应公式(10)，公式(17)对应公式(2)。The objective function (14) represents minimizing the cost corresponding to all selected columns,

Indicates that the lth trip of car k selects column r, and a column represents the shift sequence of a trip service. Formula (15) corresponds to formula (4), formula (16) corresponds to formula (10), and formula (17) corresponds to formula (2).

Sub-question:

According to the duality principle, the objective function (19) of the sub-problem is deduced from the main problem, where α, β, γ are the dual variables corresponding to formulas (15), (16), (17), and z _ij represents an in-trip service After the i shift, it will serve the j shift. Constraints (20) correspond to constraints (3), constraints (21-23) correspond to constraints (5-7), and constraints (24, 25) correspond to constraints (8, 9). The sub-problem actually determines the sequence of shifts that the electric bus should serve in a trip. This sequence of shifts is a column in the column generation algorithm, which is used to return to the main problem to continue solving.

2) As shown in Figure 2, this step mainly describes the application framework of the column generation algorithm.

A.CPLEX solves the main linear relaxation problem

The main problem is actually a linear combination of columns that minimizes the objective function (14). After linear relaxation, the main problem can be quickly solved by the CPLEX solver. Pass it to the subproblem (it can be seen from Equation 19 that the objective function of the subproblem contains dual variables and requires dual solutions).

B. Pass dual information to subproblems

The dual solution obtained by A is brought into the objective function of the subproblem, and the subproblem is actually transformed into the shortest path problem, that is, to find a shift sequence that minimizes the objective function (19), also called the shortest path.

C. Label Correction Algorithm to Solve Subproblems

In the process of finding the shortest path, based on the idea of dynamic programming, each shift is given a label ξ _i =(Γ _i ,Q _i ,τ _i ,ω _i , rc _i ,i), where Γ _i is the sequence of shifts passed, Q _i is the accumulated power consumption of the shift in service Γ _i , τ _i is the starting service time of the i shift, ω _i is the accumulated power consumption Q _i The charging time required in the case of , rc _i is the cumulative reduced cost (RC) value that reaches the i shift after Γ _i , the RC value is the value of the decrease of the objective function of the main problem in the mathematical sense, and i means that the shift i is reached.

Bidirectional dynamic programming is used here to expand the path, that is, from the station to expand the shift i (forward) in chronological order, and to expand the shift i (backward) through the station according to the chronological order. The expansion rules are as follows:

For forward expansion:

Γ _j = Γ _i ∪{j} (28)

Q _j =Q _i +q _j (29)

τ _j =max{a _j ,τ _i +t _i +t _ij } (30)

ω _j =ω _i +θ×q _j (31)

rc _j =rc _i -α _j +t _ij +β ^k,l+1 ×[(τ _j +t _j +t _j,n+1 )-(τ _i +t _i +t _i,n+1 )+ θ×q _j ] (32)

For backward expansion:

Γ _j = Γ _i ∪{j} (33)

Q _j =Q _i +q _j (34)

τ _j =min{b _j ,τ _i -t _ij -t _j } (35)

ω _j =ω _i +θ×q _j (36)

rc _j =rc _i -α _j +t _ij -β ^kl ×[(τ _j -t _0,j )-(τ _i -t _0,i )]+β ^k,l+1 ×θ×q _j (37 )

The key to the forward and backward extension lies in the contextual relationship in time and the logical relationship of the RC value obtained according to the objective function (19).

能够支配

当且仅当：The labels ξ _i of all shifts are calculated each time, because in the process of bidirectional dynamic programming search, for the same shift i, there will be multiple paths to reach the shift i, that is, there are multiple labels ξ _i about i, so it is necessary to compare Of these labels, the best ones are selected to dominate the others to reduce computation. The governing rule is,

able to dominate

if and only if:

能够比

经过更少的班次使目标函数下降的程度更大。which is

able to compare

Going through fewer shifts makes the objective function drop even more.

After the forward and backward dynamic search, the forward and backward paths are merged together to form a complete path, and the complete path is compared uniformly, and the path with the smallest RC value is found to be the optimal solution of the sub-problem.

D. Optimal solution determination

Determine whether the optimal value (RC value) obtained in C is less than zero. If it is less than zero, it means that the column (complete path formed in C) is put into the main problem column pool (the set of alternative columns) to make the main problem The objective function decreases, go to step A, and continue to iterate; if the optimal value is greater than zero, it means that there is no column that reduces the objective function of the main problem, and the main problem has been solved to the lower bound closest to the integer solution, then go to step E.

E. Branch-and-Bound Algorithm to Find the Optimal Integer Solution

Recording the result of the last main problem solution and substituting it into the branch-and-bound program of CPLEX, the optimal integer solution of the problem can be obtained, that is, the optimal electric bus scheduling scheme, which has reached the optimal in the mathematical sense. .

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the scope of the present invention. After reading the present invention, modifications to various equivalent forms of the present invention by those skilled in the art fall within the appended claims of the present application. limited range.

Claims (4)

1. A kind of electric bus scheduling optimization method considering the heterogeneity of shifts, it is characterized in that in conjunction with the characteristic of electric bus multiple charging, set up a shift scheduling model suitable for the multiple trips of electric bus, this model considers shifts in high/flat peaks. The heterogeneity of time periods and the impact of the spatial compatibility characteristics of shifts on scheduling, determine the scheduling scheme of each electric bus, and use the interval between two trips for charging to minimize fleet size and operating costs. In terms of solution, the column generation algorithm is used to obtain the optimal scheduling scheme. The specific implementation of the method includes the following steps: (1) Collect basic information and shift information of electric buses, in which the basic information of electric buses includes battery capacity, charging efficiency, charging time, and average speed; shift information includes the start time, end time, running time, power consumption of each shift, Running direction, departure station, arrival station. (2) According to the characteristics of electric buses requiring multiple charging, construct an electric bus scheduling model that considers the heterogeneity of high/flat peak shifts and spatial compatibility, and minimizes the fleet size and daily operating costs while meeting its charging needs. And rewrite it into a form suitable for solving the column generation algorithm. (3) Through the column generation algorithm, adding new columns to the column pool makes the objective function of the problem drop continuously, and finds the tightest lower bound of the problem. (4) On the basis of the tightest lower bound, the branch-and-bound algorithm is used to obtain the optimal integer solution of the electric bus scheduling problem, that is, the optimal scheduling scheme of the problem. 2. The electric bus scheduling optimization method considering shift heterogeneity according to claim 1, is characterized in that: described step (1) comprises the steps: (1-1) Determine the location of the electric bus station and expand the station into two virtual points, which are 0 and n+1 respectively. (1-2) Collect shift information, number the shifts from 1 to n in chronological order, record the start time a _i , end time bi , running time t _i , shift interval time t _ij , and shift operation of shift _i Direction μ _i (up row is 1, down row is -1), shift power consumption q _i , distance m from depot to originating station, and distance n from depot to destination station. (1-3) Collect electric bus information, number the electric buses from 1 to k, and record the battery capacity Q, charging efficiency θ, and average running speed v of the electric bus. 3. The electric bus scheduling optimization method considering shift heterogeneity according to claim 1, is characterized in that: described step (2) comprises the steps: (2-1) According to the multiple charging characteristics of electric buses, a model suitable for multiple trips of electric buses is constructed, and the maximum number of trips is set to L to limit its excessive trips. (2-2) Set the objective function as

The first part is the equal share of the cost of purchasing the fleet over the service life, and the second part is the daily operating cost, including the cost of empty driving and the cost of waiting between shifts. (2-3) Considering the actual characteristics of the problem, add constraints on the number of electric buses:

(2-4) Add electric bus power constraints

(2-5) Add basic flow constraints

(2-6) Shift space compatibility constraints

(2-7) Shift time cohesion constraints

(2-8) Travel time connectivity constraints

(2-9) According to the characteristics of the column generation algorithm, the model is rewritten into a main problem in the form of main-sub-problem:

sub-question:

4. The electric bus scheduling optimization method considering shift heterogeneity according to claim 1, is characterized in that: described step (3) comprises the steps: (3-1) Use the greedy algorithm to find a set of feasible solutions that satisfy the constraints and put them into the column pool Ω as the input of the column generation algorithm. (3-2) CPLEX solves the main problem after linear relaxation, that is, selecting a combination of columns in the column pool Ω to make the objective function

minimum. (3-3) Pass dual information α, β, γ to the subproblems. (3-4) The label correction algorithm solves the sub-problem and finds the objective function of the sub-problem

The smallest label ξ _n+1 . (3-5) Repeat the process of (3-2)-(3-4) until the RC value is greater than zero, and the sub-problem has been the optimal solution. (3-6) Solve the main problem again to get the model's tightest lower bound, Lower Bound.

Images