CN111382947A - Vehicle shift scheduling algorithm based on greedy tabu search - Google Patents
Vehicle shift scheduling algorithm based on greedy tabu search Download PDFInfo
- Publication number
- CN111382947A CN111382947A CN202010186484.9A CN202010186484A CN111382947A CN 111382947 A CN111382947 A CN 111382947A CN 202010186484 A CN202010186484 A CN 202010186484A CN 111382947 A CN111382947 A CN 111382947A
- Authority
- CN
- China
- Prior art keywords
- shift
- solution
- vehicle
- algorithm
- scheduling
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000010845 search algorithm Methods 0.000 claims abstract description 59
- 230000006872 improvement Effects 0.000 claims abstract description 6
- 230000006378 damage Effects 0.000 claims abstract description 4
- 238000001914 filtration Methods 0.000 claims abstract description 4
- 230000005540 biological transmission Effects 0.000 claims description 18
- 238000003780 insertion Methods 0.000 claims description 12
- 230000037431 insertion Effects 0.000 claims description 12
- 238000005457 optimization Methods 0.000 claims description 11
- 230000009191 jumping Effects 0.000 claims description 3
- 230000006798 recombination Effects 0.000 claims description 2
- 238000005215 recombination Methods 0.000 claims description 2
- 230000003044 adaptive effect Effects 0.000 claims 2
- 238000000034 method Methods 0.000 description 21
- 238000007726 management method Methods 0.000 description 8
- 238000010586 diagram Methods 0.000 description 7
- 230000006978 adaptation Effects 0.000 description 6
- 230000008569 process Effects 0.000 description 5
- 238000002922 simulated annealing Methods 0.000 description 5
- 230000002457 bidirectional effect Effects 0.000 description 3
- 230000002068 genetic effect Effects 0.000 description 3
- 238000004458 analytical method Methods 0.000 description 2
- 238000013473 artificial intelligence Methods 0.000 description 2
- 238000011144 upstream manufacturing Methods 0.000 description 2
- 230000001174 ascending effect Effects 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000005265 energy consumption Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 239000012634 fragment Substances 0.000 description 1
- 230000004927 fusion Effects 0.000 description 1
- 239000011159 matrix material Substances 0.000 description 1
- 230000008521 reorganization Effects 0.000 description 1
- 238000000926 separation method Methods 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
- G06Q10/063—Operations research, analysis or management
- G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
- G06Q10/06312—Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q50/00—Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
- G06Q50/40—Business processes related to the transportation industry
Landscapes
- Business, Economics & Management (AREA)
- Human Resources & Organizations (AREA)
- Engineering & Computer Science (AREA)
- Economics (AREA)
- Strategic Management (AREA)
- Tourism & Hospitality (AREA)
- Theoretical Computer Science (AREA)
- Entrepreneurship & Innovation (AREA)
- General Physics & Mathematics (AREA)
- Marketing (AREA)
- General Business, Economics & Management (AREA)
- Physics & Mathematics (AREA)
- Educational Administration (AREA)
- Quality & Reliability (AREA)
- Operations Research (AREA)
- Game Theory and Decision Science (AREA)
- Development Economics (AREA)
- Health & Medical Sciences (AREA)
- General Health & Medical Sciences (AREA)
- Primary Health Care (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
The invention discloses a vehicle scheduling algorithm based on greedy tabu search, which is characterized in that a basic vehicle scheduling model is constructed and solved based on dynamic programming to obtain an initial vehicle scheduling solution; constructing a loss function based on a tabu search algorithm as a basis for iteration of an initial solution; local iterative search improvement is carried out based on the idea of a neighborhood structure to generate a plurality of reliable candidate solutions; in order to avoid the situation that the local search is trapped in the local optimal solution, a plurality of destruction operators are added to disturb the initial solution so that the initial solution has relatively high quality; and filtering the candidate solutions according to a loss function adopted by a tabu search algorithm to obtain the optimal solution in the candidate solutions and generating a final scheduling scheme. The invention considers the cost of vehicles and drivers, applies a scientific model algorithm, namely a greedy tabu search algorithm, a scheduling scheme for searching the minimum number of vehicles and conforming to the scheduling habit, verifies the effectiveness of the algorithm and applies the algorithm to the reality.
Description
Technical Field
The invention belongs to the technical field of electric bus dispatching, and particularly relates to a vehicle scheduling algorithm based on greedy tabu search.
Background
Public transportation is an important transportation mode for public travel and is also an important means for solving the problem of urban traffic congestion. Vehicle scheduling and scheduling are an important link in bus operation management. After the bus lines and the line schedules are determined, vehicle scheduling and scheduling are daily work of the bus enterprises. The optimal scheduling of the bus service can significantly save the operation cost by reducing the number of vehicles and drivers required by the bus enterprises. In addition, the work and rest time of the driver are reasonably arranged, so that the safety and high-efficiency bus operation is guaranteed.
Aiming at the problem of bus scheduling, scholars at home and abroad research the problem of bus scheduling, and some research achievements of the problem of bus scheduling exist at present. The methods for solving the vehicle shift scheduling problem can be divided into two methods, namely an optimization method and a heuristic algorithm. The optimization method adopts a traditional optimization model such as a linear programming model and algorithms such as a column generation technology and a branch-and-bound method, has the advantages that the obtained scheduling scheme is optimal, and has the disadvantages that the algorithm has long running time and is difficult to apply to the practical problem of large scale. The heuristic algorithm is an algorithm which is constructed according to experience or intuition, can obtain a suboptimal solution of a problem under the calculation complexity, and common heuristic algorithms comprise a simulated annealing algorithm, a genetic algorithm, a Lagrangian relaxation algorithm and the like.
For example, Chendingfang et al propose a one-way bus driving planning method in the article "bus driving planning method research considering vehicle driving mileage", establish a part coordination model, and design a greedy algorithm and a matrix coding genetic algorithm;
zhu Yan Fang, et al, put forward a people-vehicle separation scheduling mode, a meta-heuristic algorithm, and an iterative local search in the text of 'bus scheduling and driver scheduling algorithm research';
the simulated annealing algorithm is proposed in a text of 'a bus scheduling method based on the simulated annealing algorithm' by Chenoshihua and the like for scheduling the buses;
wang Qing Rong, Yuan Xian pavilion and the like propose a genetic-simulated annealing algorithm in the article of 'public transportation shift scheduling optimization research based on the improved genetic-simulated annealing algorithm'.
At present, numerous factors need to be considered in bus dispatching and driver scheduling planning compilation. The basis of planning is route timetable, route traffic characteristics, bus facility distribution, number of vehicles and drivers, etc. Planning is also closely related to enterprise management patterns, such as whether a driver is allowed to change driving vehicles during the same working day; the working time of the driver, the system design of the driver compensation, etc.
For a long time, public transport enterprises in China mostly adopt a man-vehicle fixed management mode, and the man-vehicle fixed management mode requires that a driver drives the same vehicle in a working day, so that the energy consumption cost, the operation income, the performance of the driver and the like of the vehicle can be conveniently examined.
Disclosure of Invention
Aiming at the scheduling requirements of different customers and different line types, the invention provides a random exchange (replacement) selection strategy for establishing a loss function and generating a candidate set, and a greedy tabu algorithm for solving the problem.
The technical scheme adopted by the invention is as follows: a vehicle shift algorithm based on greedy tabu search comprises the following steps: (1) constructing a basic vehicle scheduling model based on dynamic planning and solving to obtain an initial vehicle scheduling solution; (2) constructing a loss function based on a tabu search algorithm as a basis for iteration of an initial solution; (3) local iterative search improvement is carried out based on the idea of a neighborhood structure to generate a plurality of reliable candidate solutions; (4) in order to avoid the situation that the local search is trapped in the local optimal solution, a plurality of destruction operators are added to disturb the initial solution so that the initial solution has relatively high quality; (5) and filtering the candidate solutions according to a loss function adopted by a tabu search algorithm to obtain the optimal solution in the candidate solutions and generating a final scheduling scheme.
In the step (3), the local iterative search algorithm mainly adopts two strategies: (1) a random replacement strategy, namely randomly selecting a certain shift of the two candidate solutions and mutually replacing the position of the shift, thereby constructing a new candidate solution; (2) and (4) a random insertion strategy, namely, randomly selecting a certain shift of the two candidate solutions, and randomly inserting one shift of one candidate solution into the front or the back of the other shift of the other candidate solution so as to construct a new candidate solution.
The bus scheduling method comprises the steps of scheduling buses in a virtual man-vehicle binding scheduling mode by the vehicle, giving the scheduling mode, and calculating the iteration times M of the algorithm, wherein basic steps of the vehicle scheduling algorithm are described as follows.
(1) An initial solution. And carrying out vehicle scheduling by using a dynamic programming algorithm with the vehicle idle running cost and the driver stopping waiting cost as targets to obtain an initial shift chain of the vehicle, wherein the requirements of meeting the given limits of maximum intermediate stop time and minimum intermediate stop time are met.
(2) Redefining the loss function. The influence of non-simultaneous transmission and reception factors and idle driving factors is considered and converted into a loss value, and meanwhile, the idle driving cost of the vehicle and the successful waiting of a driver are considered to construct an objective function for the target through a tabu search algorithm.
(3) Local search: aiming at a man-vehicle fixed scheduling mode, a local search algorithm based on a neighborhood structure is executed to construct a vehicle shift chain candidate solution, operators such as an insertion strategy and a replacement strategy are used to improve the quality of the current shift chain candidate solution, and a new feasible shift chain candidate set is tried to be constructed.
(4) Local search: aiming at a human-vehicle fixed scheduling mode, local search is used for improving a vehicle shift chain; and adjusting the current shift chain using operators such as shift move, shift chain merge, shift chain reorganization, shift chain split, etc., in an attempt to adjust the feasible shift chain to a feasible shift chain, and also in an attempt to reduce vehicle and driver costs through adjustment.
(5) And (4) performing the steps (3) to (4) M times in an iteration mode.
(6) And returning the feasible solution with the minimum loss function at the moment, comparing the feasible solution with the best current solution (namely the optimal solution found by the search algorithm at present), and if the feasible solution is better than the best current solution, taking the solution as the final scheduling scheme.
Let set D ═ D1,d2,...,dmDenotes m parking lots, S ═ S1,s2,...,spAnd represents p bus starting stations or ending stations. Let set V ═ V1,v2,...,vnRepresents n task of shift on a bus line, task viThe system has the attributes of line number, driving direction, starting station, ending station, departure time, ending time, running time and the like.
The bus scheduling problem is to arrange the bus to execute the number of shifts specified by the existing bus route timetable, and to minimize the bus running cost on the premise of meeting the vehicle management regulations. Firstly, each shift in the set V has and can only be completed by a certain vehicle and a certain driver; secondly, vehicles are used as few as possible, and vehicle cost and road running cost are reduced; thirdly, the labor efficiency of the driver is improved as much as possible.
The system product of the invention mainly adopts a tabu search algorithm, a dynamic planning algorithm and a local search algorithm to carry out the dispatching and the scheduling of the public transport vehicles. Basic principle of algorithm:
the system algorithm mainly adopts a bus shift chain set B ═ B1,b2,...,bkExpresses vehicle scheduling and shift allocation schemes. In the human-vehicle binding scheduling mode, each shift chain biComprises a vehicle, a parking lot, executive shift numbers, an up-down lineAnd the shift system indicates that the vehicle starts from the yard, sequentially finishes a plurality of shift tasks in ascending or descending and returns to the yard. In practice, a shift chain needs to be equipped with one or two drivers to perform the associated shift execution.
When a vehicle scheduling model is established, a shift chain initial solution is solved through a dynamic programming algorithm. Four factors are mainly considered here, namely the empty driving cost from the yard to the starting station, the empty driving cost between shifts, the waiting cost for stopping between shifts, and the empty driving cost from the ending station back to the yard. Let dkiFor the cost of empty driving of the vehicle from the yard to the starting station, let tijFor the empty running cost between shifts, let wijFor the waiting time between shifts, order djkFor the empty running cost of the vehicle returning from the terminal station to the yard, order si，eiFor the start time and the end time of shift i, order
Order e for whether there is empty drive between shift i and shift jijThe empty time between shift i and shift j.
The Min function is a scheduling model mainly used for maximizing the labor efficiency, namely improving the on-board time of a driver, and the ST is a constraint condition aiming at the scheduling model, and the constraint conditions such as whether to allow empty driving, whether to allow non-simultaneous transmission and reception and the like are mainly based on the real requirements of the public transportation enterprises.
Let xkjIndicating whether a particular vehicle is performing a shift i, x from yard kijIndicating whether a particular vehicle has executed shift j, x after having executed shift ijkIndicating whether the vehicle returned to the yard after performing shift j.
Based on the shift chain provided by the initial solution, the shift arrangement scheme is improved through a tabu search algorithm. The tabu search algorithm is a manifestation of artificial intelligence and is an extension of local search. In order to avoid trapping in a local optimal solution, the tabu search algorithm records the information of the search process which is already performed, so as to guide the search direction of the next step.
The basic steps of the tabu search algorithm are as follows.
1) Initialization: and generating an initial solution by using the dynamic programming algorithm, emptying a tabu table, setting the tabu length to be 6 and the iteration number to be 200.
2) The neighborhood structure yields a candidate solution: candidate solutions are generated by a search operator and an adaptation value (i.e., an objective function value corresponding to the solution) is calculated for each candidate solution.
3) The best candidate solution is selected, the candidate solution with the best adaptation value is selected from all the candidate solutions generated in step 2, the candidate solution with the best adaptation value is compared with the current best solution (namely, the best solution found by the searching algorithm from the beginning), and if the best solution is better than the current solution, the current best solution is updated.
4) Judging a termination condition: if the termination condition is met, immediately stopping and outputting the current best solution; otherwise, the search is continued. The termination condition is typically whether a certain number of iterations has been reached or a time limit has been reached.
When the tabu search is used for constructing the candidate solution, the non-simultaneous transmission and reception phenomenon and the legal empty driving phenomenon need to be considered, so that compared with an objective function for constructing an initial solution by dynamic programming, some constraint conditions are added, and the objective function is divided into four parts.
The first part is the empty driving cost from the parking lot to the starting station:
the second part is the empty cost between shifts:
wherein s isijIndicating whether it is a legal empty-run or not,
expressed as the loss cost of legal and illegal empty drives.
The third part is the stay waiting cost between shifts:
the fourth part is the empty driving cost of the terminal station to the yard:
wherein z isjkIn order to determine whether the non-simultaneous transmission and reception phenomenon exists,
the loss cost of the non-simultaneous transmission and reception phenomenon and the non-simultaneous transmission and reception phenomenon is shown; and when the constructed optimization target is used for minimizing the total cost of the crew service, because the operation time of each shift is determined, any shift scheduling scheme comprises all shifts, and a complete loss function is constructed:
Min.O1+O2+O3+O4
the first constraint condition is mainly to screen out empty driving shifts, the second constraint condition is to ensure that each shift has and can only be executed once, and the third constraint condition is to ensure that the shift can only return to a parking lot or continue to execute the next shift after the execution of the executed shift is finished.
The method designs three operators to construct a local iterative search strategy so as to achieve the dilemma of jumping out of local optimum, which is as follows.
a) And replacing operators, namely randomly selecting two shift chains and randomly selecting a certain shift in the shift chains to replace the shifts on the premise of meeting the constraint conditions.
b) And the forward insertion operator randomly selects two shift chains and randomly selects a certain shift in one shift chain to be inserted in front of a certain shift in the other shift chain on the premise of meeting the constraint condition.
c) And a backward insertion operator, wherein two shift chains are randomly selected, a certain shift in one shift chain is randomly selected, and the shift is inserted into the back of the certain shift in the other shift chain on the premise of meeting the constraint condition.
The scheme of the invention is researched aiming at the scheduling problem of a bus driver in a domestic human-vehicle binding mode, simultaneously the cost of vehicles and the driver is considered, a scientific model algorithm, namely a greedy tabu search algorithm and a scheduling scheme for searching the minimum number of vehicles and meeting the scheduling habit, is applied, the effectiveness of the algorithm is verified, and the method is applied to practice.
Compared with the prior art, the scheme can be matched with various modes (unidirectional, bidirectional and loop) of bus driving plan compiling methods to establish a passenger flow matching model and design a taboo greedy algorithm.
Compared with the unoptimized heuristic algorithm, the speed is improved by more than sixty times, and the idle running phenomenon and the non-simultaneous transmission and reception phenomenon are obviously reduced.
Drawings
FIG. 1 is a basic flow diagram of the algorithm of the present invention.
FIG. 2 is a diagram showing the result of applying the method of the present invention to a system.
FIG. 3 is a diagram of a line 1 manual shift result display comparing greedy taboo shift.
FIG. 4 is a second graph showing the manual shift result of line 1 compared to the shift by the greedy tabu algorithm.
FIG. 5 is a third graph showing the manual shift result of line 1 compared to the shift by the greedy tabu algorithm.
Fig. 6 is a diagram showing the shift result of the tabu search algorithm of the line 1.
Fig. 7 is a second diagram of the shift scheduling result of the tabu search algorithm of the line 1.
FIG. 8 is a graph showing the results of a line 2 manual shift compared to a greedy tabu algorithm shift.
Fig. 9 is a diagram showing the shift result of the line 2 tabu search algorithm.
FIG. 10 is a graph showing the results of a line 3 manual shift compared to a greedy tabu algorithm shift.
Fig. 11 is a diagram showing the shift result of the line 3 tabu search algorithm.
FIG. 12 is a passenger flow characteristics analysis statistical chart.
Detailed Description
Let set D ═ D1,d2,...,dmDenotes m parking lots, S ═ S1,s2,...,spAnd represents p bus starting stations or ending stations. Let set V ═ V1,v2,...,vnRepresents n task of shift on a bus line, task viThe system has the attributes of line number, driving direction, starting station, ending station, departure time, ending time, running time and the like.
The bus scheduling problem is to arrange the bus to execute the number of shifts specified by the existing bus route timetable, and to minimize the bus running cost on the premise of meeting the vehicle management regulations. Firstly, each shift in the set V has and can only be completed by a certain vehicle and a certain driver; secondly, vehicles are used as few as possible, and vehicle cost and road running cost are reduced; thirdly, the labor efficiency of the driver is improved as much as possible.
The system product mainly discusses the bus shift of the human-vehicle binding scheduling mode. The algorithm of the bus dispatching and driver scheduling problem is as follows.
1 principle of algorithm
The system mainly adopts a tabu search algorithm, a dynamic planning algorithm and a local search algorithm to schedule and schedule the buses. Basic principle of algorithm: (1) constructing a basic vehicle scheduling model based on dynamic planning and solving to obtain an initial vehicle scheduling solution; (2) constructing a loss function based on a tabu search algorithm as a basis for iteration of an initial solution; (3) local iterative search improvement is carried out based on the idea of a neighborhood structure to generate a plurality of reliable candidate solutions; (4) in order to avoid the situation that the local search is trapped in the local optimal solution, a plurality of destruction operators are added to disturb the initial solution so that the initial solution has relatively high quality; (5) and filtering the candidate solutions according to a loss function adopted by a tabu search algorithm to obtain the optimal solution in the candidate solutions and generating a final scheduling scheme.
The algorithm of the system mainly adopts a bus shift chain set B ═ B1,b2,...,bkExpresses vehicle scheduling and shift allocation schemes. In the human-vehicle binding scheduling mode, each shift chain biThe system comprises a vehicle, a parking lot, an execution shift number, an up-down shift and a shift system thereof, and indicates that the vehicle starts from the parking lot, sequentially finishes a plurality of shift tasks in the up-down shift or the down shift, and returns to the parking lot. In practice, a shift chain needs to be equipped with one or two drivers to perform the associated shift execution.
The local iterative search algorithm based on the neighborhood structure is essentially a meta-heuristic algorithm, and has the main advantages of simplicity, effectiveness, easiness in fusion with other heuristic algorithms and the like. The vehicle scheduling method needs to meet the requirements of minimum intermediate stop time and maximum intermediate stop time. The running cost of the vehicle is reduced to the maximum extent. The local iterative search algorithm mainly adopts two strategies: (1) a random replacement strategy, namely randomly selecting a certain shift of the two candidate solutions and mutually replacing the position of the shift, thereby constructing a new candidate solution; (2) and (4) a random insertion strategy, namely, randomly selecting a certain shift of the two candidate solutions, and randomly inserting one shift of one candidate solution into the front or the back of the other shift of the other candidate solution so as to construct a new candidate solution.
Given a scheduling mode and the iteration number M of the algorithm, the basic steps of the vehicle scheduling algorithm of the system are described as follows:
(6) an initial solution. Carrying out vehicle scheduling by a dynamic programming algorithm with the vehicle idle running cost and the driver stopping waiting cost as targets to obtain an initial shift chain of the vehicle, wherein the requirements of the given maximum intermediate stop time and the minimum intermediate stop time are met;
(7) redefining the loss function. Considering influences of non-simultaneous transmission and reception factors and idle driving factors, converting the influences into loss values, considering vehicle idle driving cost and successful driver stopping waiting as targets, and constructing a target function through a tabu search algorithm;
(8) local search: aiming at a man-car fixed scheduling mode, constructing a vehicle shift chain candidate solution by executing a local search algorithm based on a neighborhood structure, improving the quality of the current shift chain candidate solution by using operators such as an insertion strategy and a replacement strategy, and trying to construct a new feasible shift chain candidate set;
(9) local search: aiming at a human-vehicle fixed scheduling mode, local search is used for improving a vehicle shift chain; adjusting the current shift chain by using operators such as shift movement, shift chain merging, shift chain recombination and shift chain splitting, trying to adjust the feasible shift chain into a feasible shift chain, and also trying to reduce the cost of vehicles and drivers by adjustment;
(10) iteratively executing the steps (3) to (4) M times;
(11) and returning the feasible solution with the minimum loss function at the moment, comparing the feasible solution with the best current solution (namely the optimal solution found by the search algorithm at present), and if the feasible solution is better than the best current solution, taking the solution as the final scheduling scheme.
The basic flow of the algorithm is shown in fig. 1.
2 vehicle dispatching model
And establishing a vehicle scheduling model, and solving a shift chain initial solution through a dynamic programming algorithm. Four factors are mainly considered here, namely the empty driving cost from the yard to the starting station, the empty driving cost between shifts, the waiting cost for stopping between shifts, and the empty driving cost from the ending station back to the yard. Let dkiFor the cost of empty driving of the vehicle from the yard to the starting station, let tijFor the empty running cost between shifts, let wijFor the waiting time between shifts, order djkFor the empty running cost of the vehicle returning from the terminal station to the yard, order si，eiFor the start time and the end time of shift i, order
Order e for whether there is empty drive between shift i and shift jijThe empty time between shift i and shift j.
Let xkjIndicating whether a particular vehicle is performing a shift i, x from yard kijIndicating whether a particular vehicle has executed shift j, x after having executed shift ijkIndicating whether the vehicle returned to the yard after performing shift j. The first constraint condition is mainly to screen out empty driving shifts, the second constraint condition is to ensure that each shift has and can only be executed once, and the third constraint condition is to ensure that the shift can only return to a parking lot or continue to execute the next shift after the execution of the executed shift is finished.
3 tabu search creation candidate solutions
Based on the shift chain provided by the initial solution, the shift arrangement scheme is improved through a tabu search algorithm. The tabu search algorithm is a manifestation of artificial intelligence and is an extension of local search. In order to avoid trapping in a local optimal solution, the tabu search algorithm records the information of the search process which is already performed, so as to guide the search direction of the next step.
The basic steps of the tabu search algorithm adopted by the product are as follows.
1) Initialization: and generating an initial solution by using the dynamic programming algorithm, emptying a tabu table, setting the tabu length to be 6 and the iteration number to be 200.
2) The neighborhood structure yields a candidate solution: candidate solutions are generated by a search operator and an adaptation value (i.e., an objective function value corresponding to the solution) is calculated for each candidate solution.
3) The best candidate solution is selected, the candidate solution with the best adaptation value is selected from all the candidate solutions generated in step 2, the candidate solution with the best adaptation value is compared with the current best solution (namely, the best solution found by the searching algorithm from the beginning), and if the best solution is better than the current solution, the current best solution is updated.
4) Judging a termination condition: if the termination condition is met, immediately stopping and outputting the current best solution; otherwise, the search is continued. The termination condition is typically whether a certain number of iterations has been reached or a time limit has been reached.
When tabu search is used for constructing a candidate solution, a non-simultaneous transmission and reception phenomenon and a legal empty driving phenomenon need to be considered, so that compared with an objective function for constructing an initial solution by dynamic programming, some constraint conditions are added, and the objective function can be divided into four parts:
the first part is the empty driving cost from the parking lot to the starting station:
the second part is the empty cost between shifts:
wherein s isijIndicating whether it is a legal empty-run or not,
expressed as the loss cost of legal and illegal empty drives.
The third part is the stay waiting cost between shifts:
the fourth part is the empty driving cost of the terminal station to the yard:
wherein z isjkIn order to determine whether the non-simultaneous transmission and reception phenomenon exists,
the loss cost of the non-simultaneous transmission and reception phenomenon and the non-simultaneous transmission and reception phenomenon is shown. Minimizing crew in building optimization objectivesThe total cost, since the operating time for each shift is determined, any one scheduling scheme includes all shifts, and thus the shift operating cost may not be considered in the objective function. The summary shows that a complete loss function can be constructed as follows.
Min.O1+O2+O3+O4
4 neighborhood structural perturbation
The neighborhood structure disturbance is consistent in a way of avoiding being trapped in local optimum in local search heuristic. In the process of creating a candidate solution by local iterative search, the scheduling method is extremely easy to fall into local optimization, so that a better shift chain cannot be found when a search operator falls into the local optimization, and at the moment, in order to jump out the local optimization, the system mainly designs three operators to construct a local iterative search strategy so as to achieve the dilemma of jumping out the local optimization. In the disturbance link, the operator does not consider cost factors when performing fall search, namely the link may increase the cost and also reduce the cost, and the link is only used for obtaining a legal candidate solution.
A replacement operator, randomly selecting two shift chains and randomly selecting a shift in the shift chains to replace between shifts on the premise of meeting the constraint condition.
Forward insertion operators, randomly selecting two shift chains and randomly selecting a shift in one shift chain to insert ahead of a shift in the other shift chain if the constraint is met.
Backward insertion operators, randomly selecting two shift chains and randomly selecting a shift in one shift chain to insert behind a shift in the other shift chain on the premise of meeting the constraint conditions.
5 iterative operator strategy
The local search has the defect of short-sight, that the local search largely falls into a strange circle of the local optimal solution and cannot jump out. Meanwhile, for the vehicle dispatching problem, it is necessary to arrange the vehicle dispatching system as compact as possible enough, because the effective work efficiency of the vehicle dispatching system for the driver is significantly improved if the shift is compact enough in the vehicle dispatching process, so in the iterative operator link, in order to consider the compactness between shifts, the weighting problem of the combination of far and near shifts should be considered in constructing the feasibility solution, for example, the stay waiting time between shift 1 and shift 2 is 20 minutes, and the stay waiting time between shift 1 and shift 3 is 5 minutes, and the combination of shift 1 and shift 2 is preferably selected here. Therefore, the strategy should be applied in the global search process, and the strategy can effectively improve the compactness among shifts.
Case analysis
Aiming at the application of the algorithm model to the practice, the obtained result is
Where Bus represents the vehicle number, Updown represents the uplink and downlink, shift represents the morning and afternoon shift, and Task represents the shift Task number.
The result of applying it to the system is shown in fig. 2.
The technical scheme of the invention is used for researching the scheduling problem of a bus driver in a domestic human-vehicle binding mode, simultaneously considering the costs of vehicles and the driver, applying a scientific model algorithm, namely a greedy tabu search algorithm, a scheduling scheme for searching the minimum number of vehicles and meeting the scheduling habit, verifying the effectiveness of the algorithm and applying the algorithm to the reality.
Compared with the prior art, the scheme can be matched with various modes (unidirectional, bidirectional and loop) of bus driving plan compiling methods to establish a passenger flow matching model and design a taboo greedy algorithm.
Compared with the unoptimized heuristic algorithm, the speed is improved by more than sixty times, and the idle running phenomenon and the non-simultaneous transmission and reception phenomenon are obviously reduced.
Taking the 1-way, 2-way and 3-way lines as examples, the shift of the greedy tabu algorithm and the manual shift are compared, and the advantages of the shift of the greedy tabu algorithm can be visually seen, which are respectively shown in fig. 3-11. Wherein, fig. 3-5 are line 1 manual shift results, fig. 6 and 7 are line 1 tabu search algorithm shift results, fig. 8 is line 2 manual shift results, fig. 9 is line 2 tabu search algorithm shift results, fig. 10 is line 3 manual shift results, and fig. 11 is line 3 tabu search algorithm shift results.
The results of the shift scheduling in the taboo search algorithm and the manual shift scheduling are compared to draw the following conclusion.
1. The taboo search algorithm is more convenient, faster and more automatic to arrange shifts, and fine management of enterprises is realized. Manually compiling a line vehicle operation plan is difficult, a very experienced dispatcher is required to compile a plan that approximately meets passenger flow, and a long time is required, one plan may take a week; the existing taboo search algorithm only needs to input two parameters and generate a driving operation plan by one key, and the taboo search algorithm is a plan which accords with the characteristics of passenger flow.
2. The taboo search algorithm can better realize reasonable matching of the capacity and the transportation amount. As shown in fig. 12, the amount of passengers going upstream in the morning and at the peak is obviously greater than that going downstream in the evening, the amount of passengers going downstream in the evening is obviously greater than that going upstream in the morning and at the peak, the difference in the demands of the passengers in different directions in the morning and at the evening is greater, and the imbalance of the directions of the passengers is obviously shown. Aiming at the line of the type, the bidirectional scheduling plan realized by the tabu search algorithm reduces the downlink shift of the early peak and the uplink shift of the late peak on the basis of guaranteeing the service of passengers, and better realizes the matching of the transport capacity and the transport capacity.
3. And the taboo search algorithm is used for scheduling to save vehicle resources. As can be seen from the plan comparison of the above three same schedules, the tabu search algorithm saves vehicle resources compared with manual shift scheduling. The cost is saved for the company, and the saved resources can be put into other places, such as running buses, network buses or supporting other lines, so that the passenger is better served, and higher value is created for the company.
4. The daily average mileage of the vehicle is improved by the shift scheduling of the taboo search algorithm. As can be seen from the plan comparison of the three same schedules, the daily mileage of the vehicle is improved compared with the manual shift scheduling by the taboo search algorithm.
| Line | Daily average mileage of manual shift | Daily average mileage of tabu search algorithm | Daily |
| Line | |||
| 1 | 173.54 | 217.94 | 44.4 |
| |
172.67 | 207.2 | 34.53 |
| |
173.57 | 186.92 | 13.35 |
5. The shift scheduling of the tabu search algorithm improves the labor efficiency of the driver. Compared with the manual scheduling, the taboo search algorithm can more reasonably arrange the stop time of the driver in the main and auxiliary fields, eliminate excessive time fragments, make the scheduling of the driver in the shift more compact and reasonable and improve the labor efficiency of the driver.
| Line | Labor efficiency of manual shift arrangement | Taboo search algorithm labor efficiency | Improvement of |
| Line | |||
| 1 | 76.08％ | 90.00％ | 13.92 |
| Line | |||
| 2 | 61.20％ | 74.60％ | 13.40 |
| Line | |||
| 3 | 64.29％ | 76.70％ | 12.41％ |
6. The shift scheduling of the tabu search algorithm simplifies the driver's shift scheduling. The algorithm realizes the approximate fairness among the same shift systems, the task amount and the working time, and the early working are carried out as far as possible. Moreover, the shift system is clear, and excessive shift system can not occur, so that the condition that multiple shifts are needed due to unbalanced task amount and working time is avoided, and the shift arrangement of a driver is simpler in operation management.
The technical scheme can be partially replaced by a genetic algorithm, a meta heuristic algorithm and the like, but the operation speed is obviously reduced, and the performability of the scheduling result in the scheduling level is obviously insufficient compared with the technical scheme.
Claims (8)
1. A vehicle shift algorithm based on greedy tabu search is characterized by comprising the following steps: (1) constructing a basic vehicle scheduling model based on dynamic planning and solving to obtain an initial vehicle scheduling solution; (2) constructing a loss function based on a tabu search algorithm as a basis for iteration of an initial solution; (3) local iterative search improvement is carried out based on the idea of a neighborhood structure to generate a plurality of reliable candidate solutions; (4) in order to avoid the situation that the local search is trapped in the local optimal solution, a plurality of destruction operators are added to disturb the initial solution so that the initial solution has relatively high quality; (5) and filtering the candidate solutions according to a loss function adopted by a tabu search algorithm to obtain the optimal solution in the candidate solutions and generating a final scheduling scheme.
2. The vehicle shift scheduling algorithm of claim 1, wherein in step (3), the local iterative search algorithm mainly adopts two strategies: 1) a random replacement strategy, namely randomly selecting a certain shift of the two candidate solutions and mutually replacing the position of the shift, thereby constructing a new candidate solution; 2) and (4) a random insertion strategy, namely, randomly selecting a certain shift of the two candidate solutions, and randomly inserting one shift of one candidate solution into the front or the back of the other shift of the other candidate solution so as to construct a new candidate solution.
3. The vehicle scheduling algorithm of claim 1 wherein the vehicle schedule is a bus schedule in a human-vehicle binding scheduling mode, given a scheduling mode, the number of iterations of the algorithm M, the vehicle scheduling algorithm steps are described as follows:
(1) initial solution: carrying out vehicle scheduling by a dynamic programming algorithm with the vehicle idle running cost and the driver stopping waiting cost as targets to obtain an initial shift chain of the vehicle, wherein the requirements of the given maximum intermediate stop time and the minimum intermediate stop time are met;
(2) redefining a loss function, considering the influence of non-simultaneous transmission and reception factors and idle driving factors, converting the influence into a loss value, considering the idle driving cost of the vehicle and the successful waiting of a driver, and constructing a target function for a target through a tabu search algorithm;
(3) local search: aiming at a man-car fixed scheduling mode, constructing a vehicle shift chain candidate solution by executing a local search algorithm based on a neighborhood structure, improving the quality of the current shift chain candidate solution by using operators such as an insertion strategy and a replacement strategy, and trying to construct a new feasible shift chain candidate set;
(4) local search: aiming at a human-vehicle fixed scheduling mode, local search is used for improving a vehicle shift chain; adjusting the current shift chain by using shift movement, shift chain merging, shift chain recombination and shift chain splitting operators, trying to adjust the feasible shift chain into a feasible shift chain, and also trying to reduce the cost of vehicles and drivers by adjustment;
(5) iteratively executing the steps (3) to (4) M times;
(6) and returning the feasible solution with the minimum loss function at the moment, comparing the feasible solution with the best current solution (namely the optimal solution found by the search algorithm at present), and if the feasible solution is better than the best current solution, taking the solution as the final scheduling scheme.
4. The vehicle scheduling algorithm of claim 1 wherein in establishing the vehicle scheduling model, a shift chain initial solution is solved by a dynamic programming algorithm; let dkiFor the cost of empty driving of the vehicle from the yard to the starting station, let tijFor the empty running cost between shifts, let wijFor the waiting time between shifts, order djkFor the empty running cost of the vehicle returning from the terminal station to the yard, order si，eiFor the start time and the end time of shift i, order
Order e for whether there is empty drive between shift i and shift jijIs the empty time between shift i and shift j;
let xkjIndicating whether a particular vehicle is performing a shift i, x from yard kijIndicating whether a particular vehicle has executed shift j, x after having executed shift ijkIndicating whether the vehicle returned to the yard after performing shift j.
5. The vehicle shift scheduling algorithm of claim 1, wherein the basic steps of the tabu search algorithm are as follows:
1) initialization: generating an initial solution by using the dynamic programming algorithm, emptying a tabu table, setting the tabu length to be 6 and the iteration number to be 200;
2) the neighborhood structure yields a candidate solution: generating candidate solutions through a search operator and calculating adaptive values of the candidate solutions;
3) selecting the best candidate solution, selecting the candidate solution with the best adaptive value from all the candidate solutions generated in the step 2, comparing the candidate solution with the current best solution, and if the candidate solution is better than the current solution, updating the current best solution;
4) judging a termination condition: if the termination condition is met, immediately stopping and outputting the current best solution; otherwise, the search is continued.
6. The vehicle shift scheduling algorithm according to claim 1, wherein the taboo search is performed to construct the candidate solution by considering a non-simultaneous transmission and reception phenomenon and a legal empty driving phenomenon, so that constraints are added thereto compared with an objective function for constructing an initial solution by dynamic planning, and the objective function is divided into four parts:
the first part is the empty driving cost from the parking lot to the starting station:
the second part is the empty cost between shifts:
wherein s isijIndicating whether it is a legal empty-run or not,
loss costs expressed as legal and illegal empty drives;
the third part is the stay waiting cost between shifts:
the fourth part is the empty driving cost of the terminal station to the yard:
wherein z isjkIn order to determine whether the non-simultaneous transmission and reception phenomenon exists,
the loss cost of the non-simultaneous transmission and reception phenomenon and the non-simultaneous transmission and reception phenomenon is shown; the total cost of the crew is minimized when the optimization target is constructed, and any scheduling scheme is included due to the determination of the operation time of each shiftFor some shifts, a complete loss function is constructed:
Min.O1+O2+O3+O4
7. the vehicle scheduling algorithm of claim 6 wherein the constraint one is to screen out empty shifts, the constraint two is to ensure that each shift is executed only once, and the constraint three is to ensure that the executed shift is returned to the yard or the next shift is executed.
8. The vehicle shift scheduling algorithm of claim 1, wherein three operators are designed to construct a local iterative search strategy to achieve the dilemma of jumping out of local optimality, respectively:
a) replacing operators, wherein two shift chains are randomly selected, and a certain shift in the shift chains is randomly selected to replace the shift chains on the premise of meeting the constraint condition;
b) the forward insertion operator randomly selects two shift chains and randomly selects a certain shift in one shift chain to be inserted in front of a certain shift in the other shift chain on the premise of meeting the constraint condition;
c) and a backward insertion operator, wherein two shift chains are randomly selected, a certain shift in one shift chain is randomly selected, and the shift is inserted into the back of the certain shift in the other shift chain on the premise of meeting the constraint condition.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010186484.9A CN111382947A (en) | 2020-03-17 | 2020-03-17 | Vehicle shift scheduling algorithm based on greedy tabu search |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010186484.9A CN111382947A (en) | 2020-03-17 | 2020-03-17 | Vehicle shift scheduling algorithm based on greedy tabu search |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN111382947A true CN111382947A (en) | 2020-07-07 |
Family
ID=71217379
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202010186484.9A Pending CN111382947A (en) | 2020-03-17 | 2020-03-17 | Vehicle shift scheduling algorithm based on greedy tabu search |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN111382947A (en) |
Cited By (22)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111985683A (en) * | 2020-07-14 | 2020-11-24 | 华南理工大学 | Path optimization method for material distribution of multi-target discrete assembly workshop |
| CN112001560A (en) * | 2020-09-01 | 2020-11-27 | 湖南智慧畅行交通科技有限公司 | Two-stage bus scheduling algorithm based on iterative neighborhood search |
| CN112101791A (en) * | 2020-09-16 | 2020-12-18 | 携程计算机技术（上海）有限公司 | Call center multi-target scheduling method, system, equipment and medium |
| CN112257999A (en) * | 2020-10-10 | 2021-01-22 | 东南大学 | An adaptive large-scale neighborhood search method for large-scale pure electric bus vehicle scheduling problem |
| CN112434844A (en) * | 2020-11-10 | 2021-03-02 | 郑州天迈科技股份有限公司 | New development and extension method for sorting net based on convex hull calculation and genetic algorithm |
| CN112863166A (en) * | 2021-01-25 | 2021-05-28 | 湖南智慧畅行交通科技有限公司 | Newly-added train number algorithm based on coordinate search |
| CN112884216A (en) * | 2021-02-04 | 2021-06-01 | 国网湖南省电力有限公司 | Method for calculating minimum number of vehicles in single bus line |
| CN112967519A (en) * | 2021-02-01 | 2021-06-15 | 青岛海信网络科技股份有限公司 | Public transport means scheduling method, device and equipment |
| CN113205239A (en) * | 2021-03-17 | 2021-08-03 | 郑州天迈科技股份有限公司 | Bus scheduling method and system with priority in task amount configuration |
| CN113393111A (en) * | 2021-06-09 | 2021-09-14 | 东南大学 | Cross-border transportation bilateral connection vehicle scheduling method based on variable neighborhood tabu search algorithm |
| CN113408866A (en) * | 2021-05-26 | 2021-09-17 | 上海闻政管理咨询有限公司 | Bus resource allocation reasonability analysis and optimization algorithm based on linear programming |
| CN113572500A (en) * | 2021-06-25 | 2021-10-29 | 西安电子科技大学 | NOMA multi-user detection algorithm of hybrid greedy and tabu search strategy |
| CN113743761A (en) * | 2021-08-26 | 2021-12-03 | 山东师范大学 | Intern shift-by-shift scheduling method and system based on random neighborhood search algorithm |
| CN113987730A (en) * | 2021-12-28 | 2022-01-28 | 广州市交通规划研究院 | Large-scale bus trunk line automatic selection method based on land utilization |
| CN114037240A (en) * | 2021-11-01 | 2022-02-11 | 青岛民航凯亚系统集成有限公司 | Passenger elevator car ramp task scheduling system and method |
| CN114282823A (en) * | 2021-12-27 | 2022-04-05 | 中国民航信息网络股份有限公司 | Vehicle scheduling method and device, storage medium and electronic equipment |
| CN114331143A (en) * | 2021-12-30 | 2022-04-12 | 南京迈特望科技股份有限公司 | A Nursing Worker Scheduling Method Based on Simulated Annealing Algorithm |
| CN114742426A (en) * | 2022-04-20 | 2022-07-12 | 北京化工大学 | Two-stage generation method and program product for bus shift scheduling plan of bus line |
| CN115438898A (en) * | 2022-05-25 | 2022-12-06 | 珠海优特电力科技股份有限公司 | First object distribution method and device, storage medium and electronic device |
| CN115545582A (en) * | 2022-12-02 | 2022-12-30 | 天津大学 | Method and device for solving circular delivery scheduling problem of electric tractor |
| CN116468352A (en) * | 2023-06-16 | 2023-07-21 | 跨越速运集团有限公司 | Logistics departure time calculation method, device, equipment and storage medium |
| GB2622294A (en) * | 2022-05-25 | 2024-03-13 | Zhuhai Unitech Power Tech Co | First object allocation method and apparatus, storage medium and electronic apparatus |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106570590A (en) * | 2016-11-07 | 2017-04-19 | 北京百度网讯科技有限公司 | Artificial intelligence-based travel itinerary planning method and device |
| CN108960634A (en) * | 2018-07-06 | 2018-12-07 | 郑州天迈科技股份有限公司 | A kind of vehicle based on people's vehicle binding pattern is arranged an order according to class and grade algorithm |
-
2020
- 2020-03-17 CN CN202010186484.9A patent/CN111382947A/en active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106570590A (en) * | 2016-11-07 | 2017-04-19 | 北京百度网讯科技有限公司 | Artificial intelligence-based travel itinerary planning method and device |
| CN108960634A (en) * | 2018-07-06 | 2018-12-07 | 郑州天迈科技股份有限公司 | A kind of vehicle based on people's vehicle binding pattern is arranged an order according to class and grade algorithm |
Non-Patent Citations (3)
| Title |
|---|
| 侯彦娥: "公交司机排班问题的混合元启发算法研究" * |
| 刘志刚: "基于禁忌搜索的公交区域调度配车模型研究" * |
| 陈明明: "多车场公交乘务排班问题优化" * |
Cited By (34)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111985683B (en) * | 2020-07-14 | 2023-10-24 | 华南理工大学 | Path optimization method for material distribution of multi-target discrete assembly workshop |
| CN111985683A (en) * | 2020-07-14 | 2020-11-24 | 华南理工大学 | Path optimization method for material distribution of multi-target discrete assembly workshop |
| CN112001560A (en) * | 2020-09-01 | 2020-11-27 | 湖南智慧畅行交通科技有限公司 | Two-stage bus scheduling algorithm based on iterative neighborhood search |
| CN112101791A (en) * | 2020-09-16 | 2020-12-18 | 携程计算机技术（上海）有限公司 | Call center multi-target scheduling method, system, equipment and medium |
| CN112101791B (en) * | 2020-09-16 | 2024-02-09 | 携程计算机技术（上海）有限公司 | Multi-target scheduling method, system, equipment and medium for call center |
| CN112257999A (en) * | 2020-10-10 | 2021-01-22 | 东南大学 | An adaptive large-scale neighborhood search method for large-scale pure electric bus vehicle scheduling problem |
| CN112434844B (en) * | 2020-11-10 | 2024-01-26 | 郑州天迈科技股份有限公司 | New opening and extension method of sorting wire net based on convex hull calculation and genetic algorithm |
| CN112434844A (en) * | 2020-11-10 | 2021-03-02 | 郑州天迈科技股份有限公司 | New development and extension method for sorting net based on convex hull calculation and genetic algorithm |
| CN112863166A (en) * | 2021-01-25 | 2021-05-28 | 湖南智慧畅行交通科技有限公司 | Newly-added train number algorithm based on coordinate search |
| CN112863166B (en) * | 2021-01-25 | 2022-09-23 | 湖南智慧畅行交通科技有限公司 | Method for newly adding bus number under corresponding shift of bus in planned dispatching process |
| CN112967519A (en) * | 2021-02-01 | 2021-06-15 | 青岛海信网络科技股份有限公司 | Public transport means scheduling method, device and equipment |
| CN112967519B (en) * | 2021-02-01 | 2022-05-13 | 青岛海信网络科技股份有限公司 | Public transport means scheduling method, device and equipment |
| CN112884216A (en) * | 2021-02-04 | 2021-06-01 | 国网湖南省电力有限公司 | Method for calculating minimum number of vehicles in single bus line |
| CN112884216B (en) * | 2021-02-04 | 2023-06-23 | 国网湖南省电力有限公司 | Calculation method of the minimum number of vehicles on a single bus line |
| CN113205239B (en) * | 2021-03-17 | 2024-03-15 | 郑州天迈科技股份有限公司 | Bus dispatching method and system with priority of task allocation |
| CN113205239A (en) * | 2021-03-17 | 2021-08-03 | 郑州天迈科技股份有限公司 | Bus scheduling method and system with priority in task amount configuration |
| CN113408866A (en) * | 2021-05-26 | 2021-09-17 | 上海闻政管理咨询有限公司 | Bus resource allocation reasonability analysis and optimization algorithm based on linear programming |
| CN113393111A (en) * | 2021-06-09 | 2021-09-14 | 东南大学 | Cross-border transportation bilateral connection vehicle scheduling method based on variable neighborhood tabu search algorithm |
| CN113572500B (en) * | 2021-06-25 | 2022-09-02 | 西安电子科技大学 | NOMA multi-user detection algorithm of hybrid greedy and tabu search strategy |
| CN113572500A (en) * | 2021-06-25 | 2021-10-29 | 西安电子科技大学 | NOMA multi-user detection algorithm of hybrid greedy and tabu search strategy |
| CN113743761A (en) * | 2021-08-26 | 2021-12-03 | 山东师范大学 | Intern shift-by-shift scheduling method and system based on random neighborhood search algorithm |
| CN114037240A (en) * | 2021-11-01 | 2022-02-11 | 青岛民航凯亚系统集成有限公司 | Passenger elevator car ramp task scheduling system and method |
| CN114282823A (en) * | 2021-12-27 | 2022-04-05 | 中国民航信息网络股份有限公司 | Vehicle scheduling method and device, storage medium and electronic equipment |
| CN113987730A (en) * | 2021-12-28 | 2022-01-28 | 广州市交通规划研究院 | Large-scale bus trunk line automatic selection method based on land utilization |
| CN114331143A (en) * | 2021-12-30 | 2022-04-12 | 南京迈特望科技股份有限公司 | A Nursing Worker Scheduling Method Based on Simulated Annealing Algorithm |
| CN114742426A (en) * | 2022-04-20 | 2022-07-12 | 北京化工大学 | Two-stage generation method and program product for bus shift scheduling plan of bus line |
| CN115438898B (en) * | 2022-05-25 | 2023-05-26 | 珠海优特电力科技股份有限公司 | Method and device for distributing first object, storage medium and electronic device |
| WO2023226324A1 (en) * | 2022-05-25 | 2023-11-30 | 珠海优特电力科技股份有限公司 | Method for allocating first object, and apparatus, storage medium and electronic apparatus |
| CN115438898A (en) * | 2022-05-25 | 2022-12-06 | 珠海优特电力科技股份有限公司 | First object distribution method and device, storage medium and electronic device |
| GB2622294A (en) * | 2022-05-25 | 2024-03-13 | Zhuhai Unitech Power Tech Co | First object allocation method and apparatus, storage medium and electronic apparatus |
| CN115545582B (en) * | 2022-12-02 | 2023-04-07 | 天津大学 | Method and device for solving problem of circular delivery scheduling of electric tractor |
| CN115545582A (en) * | 2022-12-02 | 2022-12-30 | 天津大学 | Method and device for solving circular delivery scheduling problem of electric tractor |
| CN116468352A (en) * | 2023-06-16 | 2023-07-21 | 跨越速运集团有限公司 | Logistics departure time calculation method, device, equipment and storage medium |
| CN116468352B (en) * | 2023-06-16 | 2023-09-22 | 跨越速运集团有限公司 | Logistics departure time calculation method, device, equipment and storage medium |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN111382947A (en) | Vehicle shift scheduling algorithm based on greedy tabu search | |
| Wang et al. | A multi-objective genetic algorithm based approach for dynamical bus vehicles scheduling under traffic congestion | |
| CN112193116B (en) | Electric vehicle charging optimization guiding strategy considering reward mechanism | |
| CN110341763A (en) | An intelligent dispatching system and method for quickly restoring punctual operation of high-speed trains | |
| CN111476490A (en) | Regional multi-line vehicle scheduling algorithm shared by resource pool | |
| CN113205239B (en) | Bus dispatching method and system with priority of task allocation | |
| CN109774750B (en) | Dynamic scheduling space-time decision method based on virtual coupling mode | |
| CN108960634A (en) | A kind of vehicle based on people's vehicle binding pattern is arranged an order according to class and grade algorithm | |
| CN110245779A (en) | A kind of public transport dynamic based on genetic algorithm is dispatched a car method for optimizing scheduling | |
| CN114132363B (en) | Train running chart compiling method based on passenger flow space-time state refined analysis | |
| CN111325483A (en) | Electric bus scheduling method based on battery capacity prediction | |
| CN112233451B (en) | Intelligent traveling plan compiling system considering endurance mileage of pure electric bus | |
| CN116757459B (en) | Intelligent scheduling scheme for automatic driving taxies and comprehensive evaluation method and system | |
| CN111667097B (en) | Multi-chain search-based scheduling method for drivers of vehicles in same scheduling room | |
| CN114298378B (en) | Night train operation plan preparation method, device and storage medium | |
| CN117575292B (en) | Demand response bus vehicle flexible dispatch optimization method based on human-machine collaborative decision-making | |
| CN112488379B (en) | Maintenance plan optimization method and system for high-speed railway motor train unit | |
| CN102955985B (en) | A kind of day shift traffic plan synergy compilation platform system and preparation method | |
| CN117635095A (en) | Scheduling compilation optimization algorithm | |
| CN106845734A (en) | Towards the multi-mode public transport timetable optimization method of last park-and-ride demand | |
| CN111222660B (en) | Rail transit traffic road generation method and system based on full-line two-dimensional cutting | |
| CN114822007B (en) | Automatic driving vehicle scheduling method and system | |
| CN115817588A (en) | Method and system for automatic compilation of urban rail train operation diagrams for large and small traffic modes | |
| Zhao et al. | Two-way vehicle scheduling approach in public transit based on Tabu search and dynamic programming algorithm | |
| CN112530155B (en) | Electric bus dispatching method |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| CB03 | Change of inventor or designer information | ||
| CB03 | Change of inventor or designer information |
Inventor after: Guo Jianguo Inventor after: Lv Houfa Inventor after: Cheng Xingwei Inventor after: Lin Zhongxia Inventor after: Yan Lei Inventor after: Liu Hongyu Inventor after: Guo Yuanyuan Inventor after: Zhao Xinchao Inventor after: Sun Hao Inventor after: Pu Xiuxia Inventor after: Shen Yang Inventor after: Bai Ke Inventor before: Guo Jianguo Inventor before: Cheng Xingwei Inventor before: Lin Zhongxia Inventor before: Guo Yuanyuan Inventor before: Yan Lei Inventor before: Zhao Xinchao Inventor before: Sun Hao Inventor before: Pu Xiuxia Inventor before: Shen Yang Inventor before: Bai Ke Inventor before: Lv Houfa |
|
| RJ01 | Rejection of invention patent application after publication | ||
| RJ01 | Rejection of invention patent application after publication |
Application publication date: 20200707 |