CN-121981872-A - Public service vehicle scheduling and optimizing method and system for mixed type tasks

CN121981872ACN 121981872 ACN121981872 ACN 121981872ACN-121981872-A

Abstract

The invention discloses a public service vehicle dispatching and optimizing method and system for mixed type tasks, and belongs to the field of intelligent dispatching of public service vehicles. The method comprises the steps of firstly obtaining basic information of a business task, a driver and a vehicle, constructing a task distance matrix, then establishing a scheduling model which aims at minimum total fuel consumption and contains constraints such as level matching, passenger loading upper limit and the like, setting genetic and simulated annealing algorithm parameters, constructing an initial scheme population through chromosome coding of task level matching, calculating fitness values of all schemes, introducing the chromosome serving as a simulated annealing initial solution to perform cross and mutation iteration after local optimization, and finally outputting an optimal scheduling scheme. The invention adopts a mixed algorithm framework, combines global searching and local optimizing capability, realizes compliance, low oil consumption and high resource utilization rate of a scheduling scheme, solves the problems of level mismatch, resource waste and algorithm limitation of the traditional scheduling, and is suitable for the scheduling scenes of the public service vehicles of various institutions, enterprises and public institutions.

Inventors

CHANG LIANG
Zhong Lunxin
JIN TING
TIAN FEI
SONG YUEYUE
LIU YONGFANG

Assignees

中国电子科技集团公司第十五研究所

Dates

Publication Date: 20260505
Application Date: 20251219

Claims (10)

1. A public service vehicle dispatching and optimizing method for mixed type tasks is characterized by comprising the following steps: acquiring related known information of a public service vehicle task, wherein the related known information comprises a task starting point, each task end point, a task path distance, a task grade, the number of executives, a driver grade, a vehicle type, a vehicle passenger upper limit and a vehicle oil consumption parameter; determining path length between positions according to position information of a task starting point and each task ending point, and constructing a task distance matrix; Constructing a public service vehicle dispatching and optimizing model, wherein the model aims at the minimum total oil consumption of the public service vehicle for completing all tasks, and meets the constraint conditions that the class of the public service task is not higher than the class of a driver for executing the task, the passenger carrying number of the vehicle is not more than the upper limit of the passenger carrying number of the corresponding vehicle, and the number of drivers for executing the tasks at each class is not more than the upper limit of the number of drivers at the corresponding class; according to the service vehicle dispatching and optimizing model, carrying out genetic algorithm chromosome coding on a service vehicle task execution driver, and constructing a chromosome population and a fitness function; and taking the chromosome as an initial solution of the simulated annealing algorithm, carrying out local optimization through the simulated annealing algorithm, obtaining an optimal value, transmitting the optimal value into a genetic algorithm for crossover and mutation iteration until the maximum iteration number is reached, and outputting an optimal official vehicle scheduling scheme.
2. The public service vehicle dispatching optimization method for the mixed type tasks is characterized in that the public service tasks are divided into a first-level public service task, a second-level public service task and a third-level public service task, the public service drivers are correspondingly divided into a first-level driver, a second-level driver and a third-level driver, the first-level driver can execute the first-level public service tasks, the second-level driver can execute the second-level public service tasks and the third-level public service tasks, the third-level driver can only execute the third-level public service tasks, and the public service vehicles are divided into large vehicles, medium-sized vehicles and small vehicles.
3. The method for optimizing the scheduling of the utility vehicle for the mixed type task according to claim 1, wherein the optimization function of the scheduling and optimizing model of the utility vehicle is: , wherein F represents oil consumption, PENoF is a passenger carrying upper limit penalty function, and when the number of passengers carried by the vehicle exceeds the corresponding upper limit PENoF, the value is PoLU, and the values of the rest cases are 0.
4. The method for optimizing the scheduling of public service vehicles for mixed-type tasks according to claim 1, wherein the chromosome population size is an integer multiple of the total number of the public service vehicle tasks.
5. The hybrid-task-oriented business car scheduling optimization method according to claim 1, wherein the state generation operation of the simulated annealing algorithm comprises an interchange operation, a reverse order operation and an insertion operation; the simulated annealing algorithm accepts a new solution based on a Metropolis criterion, and directly accepts when the objective function value of the new solution is lower than that of the current solution, otherwise, calculates the acceptance probability based on an acceptance probability formula : , Wherein, the Representing a new solution A corresponding objective function value; Representing the current solution A corresponding objective function value; representing the temperature of the current iteration of the simulated annealing algorithm; generating a random number between 0 and 1 And is connected with the Comparing the sizes, if Accept the new solution Otherwise, discarding.
6. A public service vehicle dispatching and optimizing system facing mixed type tasks is characterized by comprising: The information collection module is used for acquiring related known information of a service vehicle task, wherein the related known information comprises a task starting point, task end points, a task path distance, a task grade, the number of executives, a driver grade, a vehicle type, a vehicle passenger upper limit and a vehicle oil consumption parameter; the task distance matrix construction module is used for determining the path length between the positions according to the position information of the task starting point and the task ending point and constructing a task distance matrix; The public service vehicle dispatching and optimizing model aims at the minimum total oil consumption of the public service vehicle for completing all tasks and meets the constraint conditions that the grade of the public service task is not higher than the grade of a driver for executing the task, the passenger carrying number of the vehicle is not more than the upper limit of the passenger carrying number of the corresponding vehicle, and the number of drivers for executing the tasks at each grade is not more than the upper limit of the number of drivers at the corresponding grade; the algorithm module is used for carrying out genetic algorithm chromosome coding on a driver of the service vehicle task according to the service vehicle dispatching and optimizing model, constructing a chromosome population and fitness function, taking the chromosome as an initial solution of a simulated annealing algorithm, carrying out local optimization through the simulated annealing algorithm, obtaining an optimal value, transmitting the optimal value into the genetic algorithm for crossover and mutation iteration until the maximum iteration times are reached, and outputting an optimal service vehicle dispatching scheme.
7. The public service vehicle dispatching optimization system for mixed type tasks according to claim 6 is characterized in that the public service tasks are divided into a first-level public service task, a second-level public service task and a third-level public service task, the public service drivers are correspondingly divided into a first-level driver, a second-level driver and a third-level driver, the first-level driver can execute the first-level public service tasks, the second-level driver can execute the second-level public service tasks and the third-level public service tasks, the third-level driver can execute the third-level public service tasks only, and the public service vehicles are divided into large vehicles, medium vehicles and small vehicles.
8. The hybrid-task-oriented utility vehicle scheduling optimization system of claim 6, wherein the optimization function of the utility vehicle scheduling and optimization model is: , wherein F represents oil consumption, PENoF is a passenger carrying upper limit penalty function, and when the number of passengers carried by the vehicle exceeds the corresponding upper limit PENoF, the value is PoLU, and the values of the rest cases are 0.
9. The hybrid task oriented utility vehicle dispatch optimization system of claim 6, wherein the chromosome population size is an integer multiple of the total number of utility vehicle tasks.
10. The hybrid-type task oriented business car dispatch optimization system of claim 6, wherein the simulated annealing algorithm state generation operation comprises an interchange operation, a reverse order operation, and an insert operation; the simulated annealing algorithm accepts a new solution based on a Metropolis criterion, and directly accepts when the objective function value of the new solution is lower than that of the current solution, otherwise, calculates the acceptance probability based on an acceptance probability formula : , Wherein, the Representing a new solution A corresponding objective function value; Representing the current solution A corresponding objective function value; representing the temperature of the current iteration of the simulated annealing algorithm; generating a random number between 0 and 1 And is connected with the Comparing the sizes, if Accept the new solution Otherwise, discarding.

Description

Public service vehicle scheduling and optimizing method and system for mixed type tasks Technical Field The invention relates to the technical field of vehicle dispatching and intelligent algorithms, in particular to a public service vehicle dispatching and optimizing method and system for mixed type tasks. Background The public service vehicle dispatching is one of basic works of the public service tasks such as daily business, special tasks, emergency matters and the like of unit staff, and the related optimization model algorithm can solve the problems of public service task allocation delay, public service vehicle allocation errors, non-busy public service driver and the like generated in manual dispatching of vehicles. Up to the present, the research of the optimization model algorithm for general vehicle dispatching is relatively perfect, and vehicle dispatching optimization factors such as shortest path, least time consumption, least oil consumption, shared carpooling, vehicle passenger limit and the like are all related. The public service vehicle dispatching is different from the general vehicle dispatching in that firstly, for safety and confidentiality reasons, the public service tasks have task grades, a public service driver needs to have corresponding grade qualification to bear the public service tasks of the corresponding grade, the vehicle dispatching model algorithm for the mixed type tasks is less, secondly, the traditional public service vehicle dispatching model algorithm mainly distributes public service vehicles with different types and different passenger capacities according to a preset rule, and generally, one public service task corresponds to one public service vehicle, the situation that a plurality of public service tasks share the carpooling is not considered, and the resource utilization is insufficient. Therefore, the research on the multi-constraint-condition public service vehicle scheduling model and the optimization algorithm for the mixed type public service task has important significance. Disclosure of Invention The embodiment of the invention provides a public service vehicle dispatching and optimizing method and system for mixed type tasks, which aim to solve the technical problems of mismatching of tasks and driver grades, low utilization rate of vehicle resources, easy sinking of an optimizing algorithm, local optimum and high total fuel consumption in the existing public service vehicle dispatching scheme, and realize the unification of compliance, low fuel consumption and high resource utilization rate of the dispatching scheme. The public service vehicle dispatching and optimizing method for the mixed type tasks comprises the following steps: The method comprises the steps of obtaining relevant known information of a public service vehicle task, wherein the relevant known information comprises a task starting point, each task end point, a task path distance, a task grade, an executive population, a driver grade, a vehicle type, a vehicle passenger upper limit and a vehicle oil consumption parameter, and the task path distance can be understood as the path distance of the task to the task end point. And determining the path length between the positions according to the position information of the task starting point and the task ending point, and constructing a task distance matrix, wherein the distance between any nodes is listed in the constructed task distance matrix, and any node can be any task ending point or task starting point. Constructing a public service vehicle dispatching and optimizing model, wherein the model aims at the minimum total oil consumption of the public service vehicle for completing all tasks, and meets the constraint conditions that the class of the public service task is not higher than the class of a driver for executing the task, the passenger carrying number of the vehicle is not more than the upper limit of the passenger carrying number of the corresponding vehicle, and the number of drivers for executing the tasks at each class is not more than the upper limit of the number of drivers at the corresponding class; According to the public service vehicle dispatching and optimizing model, a genetic algorithm is carried out on a driver for executing a public service vehicle task, a chromosome population and a fitness function are constructed, the coding content of the chromosome is that each public service task is distributed to a driver of which class, one chromosome represents a complete task-driver distribution scheme, the chromosome population is a set of public service vehicle dispatching candidate schemes, the number of the chromosomes in the population is a preset population scale, the gene position of each chromosome in the population is required to follow the rule that the task class corresponds to the driver range (the primary task gene position only selects one class driver, the secondary task can select a high class drive