CN114330800B - Vehicle path planning method and device - Google Patents
Vehicle path planning method and device Download PDFInfo
- Publication number
- CN114330800B CN114330800B CN202011056281.4A CN202011056281A CN114330800B CN 114330800 B CN114330800 B CN 114330800B CN 202011056281 A CN202011056281 A CN 202011056281A CN 114330800 B CN114330800 B CN 114330800B
- Authority
- CN
- China
- Prior art keywords
- route
- partition
- training
- partitions
- local
- 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.)
- Active
Links
Landscapes
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
The invention provides a vehicle path planning method and device, wherein the method comprises a data acquisition step, an initial calculation step, a re-partition step, an iterative calculation step, an updating processing step and an iterative stop judgment step, wherein in the initial calculation step, clustering partitions are carried out on client sites according to geographic positions of the client sites in input data to obtain a plurality of partitions, local optimized routes and local route costs of each partition are obtained through calculation, and in the re-partition step, a partition adjustment network obtained through pre-training is utilized to fuse and re-partition two partitions in the plurality of partitions to obtain two new partitions. According to the vehicle path planning method and device, the plurality of client stations are divided into the plurality of partitions, the VRP solution is respectively carried out under each partition, direct solution to a large number of client stations is avoided, and the performance and efficiency of large-scale VRP solution can be improved.
Description
Technical Field
The invention relates to the technical field of vehicle path problems (Vehicle Routing Problem, VRP), in particular to a vehicle path planning method and device.
Background
The large-scale vehicle path planning problem (VRP) has wide application in reality, such as bus planning, cargo transportation, and the like. For this problem, the prior art solutions mainly include both the conventional method and the reinforcement learning-based method.
The traditional method specifically comprises an accurate algorithm and a heuristic method, the accurate algorithm is low in efficiency and has no practical value, and the heuristic method is not high enough in efficiency due to the fact that the performance of the heuristic method depends on fine manual design.
Reinforcement learning-based methods can also be divided into two categories, direct generation solutions and generation-first-and-last-improvement solutions. The model is difficult to expand, the performance is greatly reduced along with the large-scale increase, and the like, so that the model is difficult to be suitable for the large-scale vehicle VRP problem, and the model has the characteristics of long training time index, difficult convergence in the training process, and the like on the large-scale VRP problem due to small improvement range and long consumption time each time, and has low practicability.
For example, in one chinese patent application (CN 110147901 a), a Pointer Network (Pointer Network) is used to directly generate a solution to the VRP problem, and when the VRP scale increases, the number of states, the number of motion spaces, and the model scale greatly increase, and the model is difficult to train, and the performance greatly decreases, so that it is difficult to apply to the VRP problem on a large scale.
For another example, another chinese patent application (CN 106251009 a) uses an ant colony optimization algorithm to solve the VRP problem and generate solutions, but has the drawbacks of slow generation speed and no real-time response capability on a large-scale data distribution.
In addition, in the prior art, the obstacle avoidance control is mostly performed on the basis of the vehicle path planning problem, and the problem of receiving and dispatching of vehicles with capacity cannot be solved regardless of the vehicle dispatching in the VRP problem.
Therefore, there is a need for a VRP method that can address the problem of large-scale vehicle path planning while simultaneously achieving high performance and high efficiency.
Disclosure of Invention
The technical problem to be solved by the embodiment of the invention is to provide a vehicle path planning method and device, which can improve the performance and efficiency of path planning in large-scale vehicle path planning.
In order to solve the above technical problems, a vehicle path planning method provided by an embodiment of the present invention includes:
A data acquisition step of acquiring an originating station for path planning, a maximum loading capacity of a delivery vehicle, geographic positions of a plurality of client stations and delivery demand information of each client station as input data;
According to the maximum loading capacity of the starting station, the delivery vehicles, the geographic positions of the client stations and the delivery demand information of the client stations in the input data, calculating to obtain local optimized routes and local route costs of each zone, obtaining global optimized routes and route total cost of all the client stations, and updating optimal optimized routes and optimal route total cost according to the global optimized routes and route total cost;
a re-partitioning step, namely fusing and re-partitioning two partitions in the plurality of partitions by utilizing a partition adjustment network obtained by pre-training to obtain two new partitions;
An iterative calculation step of calculating a local optimization route of the two new partitions and updating the global optimization route and the route total cost;
An updating processing step, namely judging whether the updated route total cost is lower than the optimal route total cost, if so, updating the optimal optimized route and the optimal route total cost according to the updated global optimized route and the updated route total cost, and returning to the repartitioning step, otherwise, entering an iteration stop judging step;
And the iteration stop judging step is used for judging whether a preset iteration stop condition is met, if yes, outputting the optimal optimization route, and otherwise, returning to the repartitioning step.
Optionally, the iteration stop condition is that the total route cost after being updated for N times is not lower than the optimal route cost, and N is a preset integer greater than 2.
Optionally, the fusing and repartitioning the two partitions in the plurality of partitions to obtain two new partitions includes:
generating a local feature vector of each partition according to the local optimized route and the local route cost of each partition, and generating a global feature vector according to the local feature vectors of all the partitions;
selecting two partitions from the multiple partitions according to the global feature vector and the local feature vector, and fusing the two partitions into one partition;
And calculating the local optimization route of the fusion partition, and re-dividing the fusion partition into two new partitions according to the local optimization route of the fusion partition.
Optionally, the generating the local feature vector of each partition according to the local optimized route and the local route cost of each partition includes:
for each partition, inputting a client site sequence in a local optimized route of the partition as an input sequence to a long-short-term memory LSTM network to generate a primary characteristic sequence of the partition;
And inputting the primary characteristic sequence and the local route cost of the partition into a full convolution network to generate a local characteristic vector of the partition.
Optionally, the generating a global feature vector according to the local feature vectors of all the partitions includes:
and averaging the local feature vectors of all the partitions to obtain the global feature vector.
Optionally, the selecting two partitions from the plurality of partitions according to the global feature vector and the local feature vector includes:
Generating selection probability values of all partitions by taking the global features as indexes and adopting an attention mechanism, and selecting one partition with the largest selection probability value as a first selected partition;
And taking the local area characteristics of the first partition as indexes, adopting an attention mechanism to generate a selection probability value of the rest partitions, and selecting one partition with the largest probability value as a selected second partition.
Optionally, the repartitioning the fused partition into two new partitions according to the locally optimized route of the fused partition includes:
Selecting a coordinate average point for each path in the local optimization route of the fusion partition, and carrying out principal component analysis on the coordinate average point to obtain one-dimensional characterization of the path, and dividing the paths in the local optimization route of the fusion partition into two groups according to the one-dimensional characterization of each path, wherein stations in each group of paths belong to the same new partition.
Optionally, before the data input step, the method further includes:
training to obtain the partition adjustment network.
Optionally, the training step specifically includes:
The method comprises the steps that a training set is obtained, wherein the training set comprises a plurality of groups of training data, and each group of training data comprises an originating station, the maximum loading capacity of a delivery vehicle, the geographic positions of a plurality of client stations and delivery demand information of each client station;
initializing a reference model of a partition adjustment network;
selecting a group of training data which are not used yet, and training the partition adjustment network by utilizing the selected training data for one round, wherein the partition adjustment network adopts a current reference model when each round of training is started; in the training process of each round, updating the model parameters of the partition adjusting network by utilizing the training data, and updating the reference model according to the updated partition adjusting network when the updated partition adjusting network has improved performance relative to the current reference model;
And a fourth step of judging whether a preset network training ending condition is met when each round of training is ended, if yes, ending the training of the partition adjustment network, outputting the reference model as the partition adjustment network obtained by final training, and otherwise, returning to the third step.
Optionally, the training the partition adjustment network by using the selected training data for one round of training includes:
According to the maximum loading capacity of the starting station, the delivery vehicle, the geographic position of the client station and the delivery demand information of the client station in the training data, calculating to obtain a local optimized route and a local route cost of each zone, obtaining global optimized routes and route total cost of all the client stations, and updating the optimal optimized route and the optimal route total cost according to the global optimized routes and the route total cost;
a second training sub-step, utilizing the partition adjustment network to fuse and repartition two partitions in the multiple partitions to obtain two new partitions;
a third training sub-step of calculating a local optimized route of the two new partitions and updating the global optimized route and the route total cost;
A fourth training sub-step of calculating the reduction amount of the total route cost before and after updating, taking the reduction amount as a rewarding function value, and guiding the subarea adjustment network to carry out gradient descent so as to obtain the updated subarea adjustment network;
a fifth training sub-step of judging whether the updated route total cost is lower than the optimal route total cost, if so, updating the optimal optimized route and the optimal route total cost according to the updated global optimized route and the updated route total cost, and updating the reference model according to the updated partition adjustment network and returning to the second training sub-step, otherwise, entering a sixth training sub-step;
and a sixth step of judging whether a preset stopping condition of each training round is met, if yes, ending the training of the current training round, otherwise, returning to the second training sub-step.
Optionally, the method further comprises:
After each round of training is finished, taking a current reference model as the partition adjustment network, taking a group of verification data as input data, and executing the initial calculation step, the repartitioning step, the iterative calculation step, the updating processing step and the iteration stop judging step to obtain a global optimized route and a route total cost corresponding to the verification data;
The network training ending condition is that the total route cost corresponding to the verification data obtained after the continuous M rounds of training is ended is not lower than the optimal route total cost corresponding to the verification data, and M is a preset integer greater than 2.
The embodiment of the invention also provides a vehicle path planning device, which comprises:
the data acquisition module is used for acquiring an originating station for path planning, the maximum loading capacity of a delivery vehicle, the geographic positions of a plurality of client stations and the delivery demand information of each client station as input data;
The system comprises an initial calculation module, a local optimization route and local route cost calculation module, a global optimization route and route total cost calculation module, a global optimization route and optimal route total cost calculation module, a local optimization route and optimal route total cost calculation module and a global optimization route and route total cost calculation module, wherein the initial calculation module is used for carrying out clustering partition on a plurality of client sites according to geographic positions of the client sites in the input data to obtain a plurality of partitions;
the re-partition module is used for fusing and re-partitioning two partitions in the multiple partitions by utilizing the partition adjustment network obtained through pre-training to obtain two new partitions;
the iterative computation module is used for computing the local optimization routes of the two new partitions and updating the global optimization route and the route total cost;
The updating processing module is used for judging whether the updated route total cost is lower than the optimal route total cost, if so, updating the optimal optimized route and the optimal route total cost according to the updated global optimized route and the updated route total cost, and returning to the repartitioning module;
The iteration stop judging module is used for judging whether a preset iteration stop condition is met, if yes, outputting the optimal optimization route, and otherwise, returning to the repartitioning module.
Optionally, the repartitioning module includes:
The first calculation module is used for generating a local feature vector of each partition according to the local optimization route and the local route cost of each partition, and generating a global feature vector according to the local feature vectors of all the partitions;
the selection fusion module is used for selecting two partitions from the partitions according to the global feature vector and the local feature vector and fusing the two partitions into one partition;
The division module is used for calculating the local optimization route of the fusion partition, and re-dividing the fusion partition into two new partitions according to the local optimization route of the fusion partition.
Optionally, the vehicle path planning device further includes:
and the training module is used for training to obtain the partition adjustment network.
Optionally, the training module specifically includes:
A first module for obtaining a training set, the training set comprising a plurality of sets of training data, each set of training data comprising an originating site, a maximum load of delivery vehicles, geographic locations of a plurality of customer sites, and delivery demand information for each customer site;
A second module for initializing a reference model of a partition adjustment network;
The system comprises a third module, a third module and a control module, wherein the third module is used for selecting a group of training data which is not used yet, performing one-round training by utilizing the selected training data, and training the partition adjustment network, wherein the partition adjustment network adopts a current reference model when each-round training is started;
And the fourth module is used for judging whether a preset network training ending condition is met when each round of training is ended, if yes, ending the training of the partition adjustment network, outputting the reference model as the partition adjustment network obtained by final training, and otherwise, returning to the third module.
Embodiments of the present invention also provide a computer readable storage medium having stored thereon a computer program which, when executed by a processor, implements the steps of a vehicle path planning method as described above.
Compared with the prior art, the vehicle path planning method and device provided by the embodiment of the invention can improve the performance and efficiency of large-scale VRP solution by dividing a plurality of customer sites into a plurality of partitions and respectively carrying out VRP solution under each partition.
Drawings
In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the drawings that are needed in the description of the embodiments of the present invention will be briefly described below, and it is obvious that the drawings in the following description are only some embodiments of the present invention, and other drawings may be obtained according to these drawings without inventive effort for a person skilled in the art.
Fig. 1 is a schematic flow chart of a vehicle path planning method according to an embodiment of the present invention;
FIG. 2 is an exemplary diagram of a vehicle path planning method according to an embodiment of the present invention;
FIG. 3 is a training overall flow chart of a partition adjustment network provided by an embodiment of the present invention;
FIG. 4 is a flowchart of each training of a partition adjustment network according to an embodiment of the present invention;
Fig. 5 is a schematic structural diagram of a vehicle path planning apparatus according to an embodiment of the present invention;
fig. 6 is another schematic structural diagram of a vehicle path planning apparatus according to an embodiment of the present invention.
Detailed Description
In order to make the technical problems, technical solutions and advantages to be solved more apparent, the following detailed description will be given with reference to the accompanying drawings and specific embodiments. In the following description, specific details such as specific configurations and components are provided merely to facilitate a thorough understanding of embodiments of the invention. It will therefore be apparent to those skilled in the art that various changes and modifications can be made to the embodiments described herein without departing from the scope and spirit of the invention. In addition, descriptions of well-known functions and constructions are omitted for clarity and conciseness.
It should be appreciated that reference throughout this specification to "one embodiment" or "an embodiment" means that a particular feature, structure or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, the appearances of the phrases "in one embodiment" or "in an embodiment" in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more embodiments.
In various embodiments of the present invention, it should be understood that the sequence numbers of the following processes do not mean the order of execution, and the order of execution of the processes should be determined by the functions and internal logic, and should not constitute any limitation on the implementation process of the embodiments of the present invention.
As described in the background art, the vehicle path planning method in the prior art generally has problems of low performance and efficiency, even no practicality, etc. when applied to a large-scale VRP. To solve at least one of the above problems, an embodiment of the present invention provides a vehicle path planning method, as shown in fig. 1, including:
step 101, acquiring an originating station for path planning, the maximum loading capacity of a delivery vehicle, the geographic positions of a plurality of client stations and delivery requirement information of each client station as input data.
Here, in the embodiment of the present invention, the vehicle path planning needs to be performed by inputting the initial station to be planned, the maximum load capacity of the delivery vehicle, the geographical locations of the plurality of customer stations, and the delivery demand information of each customer station, and may also input the maximum load capacity (such as the maximum capacity, the maximum load capacity, etc.) of the vehicle. The geographic location may be represented by latitude and longitude coordinates, and the delivery demand information may be a load demand (e.g., volume demand, load demand, etc.) of the delivered cargo. Optionally, in the embodiment of the present invention, more information may be input when path planning is performed, for example, a service time window of each customer site (i.e., the customer site can be serviced only within the time window), road congestion information, a vehicle number limitation, and other conditions.
The embodiment of the invention is particularly suitable for executing the distribution tasks of the plurality of client stations by a single vehicle. Specifically, when the vehicle executes a delivery task, the vehicle generally starts from an originating station, runs according to a planned path, sequentially serves all customer stations in the path, returns to an initial station after all station services in the path are completed, and thus completes the delivery task once. When the number of customer sites is high and/or the amount of delivered goods is high, the vehicle may need to perform multiple delivery tasks to service all customer sites, each delivery task corresponding to a planned path.
And 102, clustering and partitioning the customer sites according to the geographic positions of the customer sites in the input data to obtain a plurality of partitions, calculating to obtain a local optimized route and a local route cost of each partition according to the maximum loading capacity of the originating site, the delivery vehicle, the geographic position of the customer site and the delivery demand information of the customer site in the input data, obtaining global optimized routes and route total cost of all the customer sites, and updating the optimal optimized routes and the optimal route total cost according to the global optimized routes and route total cost.
In this embodiment of the present invention, clustering is performed on the client sites according to the geographical location coordinates of the client sites, so as to obtain a plurality of classes, where each class corresponds to a partition and includes at least one client site. Specifically, clustering algorithms such as K-means and the like can be adopted to perform clustering partition on site clients. In general, in the clustering process, the maximum number of partitioned sites may be set, for example, the number of partitioned sites obtained after partitioning is about 50. In performing the clustering process, a partition condition may be calculated by geographical coordinates, and the partition condition may include one or more of the following conditions:
1) The relative distance between customer sites, which may be expressed in terms of the linear distance between sites.
2) The client site is compared to the originating site and the azimuth of the nominal coordinate axis. For example, the azimuth angle is determined by taking the north direction as a calibration coordinate axis and determining the azimuth angle according to the included angle between the connecting line between the client station and the originating station and the calibration coordinate axis.
When the clustering process is performed using the above two conditions, the contour of the obtained partitions is similar to a sector, and 7 partitions are obtained by the clustering process as shown in fig. 2. When the clustering process is performed using the condition 1 described above, the obtained partition profile is similar to a rectangle or a circle.
After the subareas, the embodiment of the invention carries out VRP solving on each subarea, and particularly various small-scale VRP solving algorithms in the prior art, such as a small-scale solving algorithm based on reinforcement learning, can be adopted to generate an optimized route of the distribution task in the subarea, namely a local optimized route, by inputting the geographic position coordinates of each client station in the subarea, the geographic position coordinates of the originating station and the maximum loading capacity of the vehicle, and obtain the local route cost of the local optimized route in the subarea. The locally optimized route in each partition is shown in FIG. 2, where each partition includes a path. In general, a partitioned locally optimized route may include at least one path, with each path having a start point and an end point that are originating sites. The local route cost is the sum of the route costs of all paths in the subarea, and the route cost can be represented by one parameter of the driving distance, the driving expense and the driving time, or can be represented by the combination of the parameters. After obtaining the local optimized route and the local route cost of each partition, the local optimized routes of all the partitions can be summarized, so that global optimized routes of all the client sites are obtained, and the sum value of the local route costs of all the partitions is calculated, so that the route total cost of the global optimized routes of all the client sites is obtained.
In addition, the embodiment of the present invention maintains an optimal optimized route and an optimal route total cost, and after calculating the global optimized route and route total cost of all the client sites in step 102, the optimal optimized route and the optimal route total cost may be updated. Here, the updating means that if the total route cost of the currently calculated global optimized route is lower, the optimal optimized route and the optimal route total cost are respectively updated to the currently calculated global optimized route and the route total cost thereof, otherwise, the current optimal optimized route and the optimal route total cost are kept unchanged. Since the optimized route and the optimal route total cost have not been obtained before step 102, the initially calculated global optimized route and the route total cost thereof may be directly used as the optimal optimized route and the optimal route total cost.
And 103, fusing and repartitioning the two partitions in the plurality of partitions by utilizing the partition adjustment network obtained by pre-training to obtain two new partitions.
Here, in the embodiment of the present invention, two partitions of the plurality of partitions obtained in step 102 are fused by using a pre-trained partition adjustment network, and the fused partition obtained by the fusion is divided into two partitions again, so as to obtain two new partitions. The inputs of the partition adjustment network are the multiple partitions obtained in step 102, the local optimized route and the local route cost of each partition, and the route total cost of the global optimized route, and the outputs are two new partitions. Training on the zone adjustment network will be further described below.
In step 103, the partition adjustment network selects two partitions from the plurality of partitions for fusing and repartitioning in the following manner:
A) Local feature vectors for each partition are generated based on the local optimized route and the local route cost for each partition, and global feature vectors are generated based on the local feature vectors for all partitions.
Here, the local optimized route of the partition may include one or more paths, and the client sites in each path are combined according to the order in the paths to obtain the client site sequence in the local optimized route. And inputting a client site sequence in a local optimized route of each partition into a Long Short-Term Memory (LSTM) network as an input sequence to obtain a primary characteristic sequence of the partition output by the LSTM network. The primary signature sequence and local route cost of the partition are then input to a full convolutional network (Fully Convolutional Networks, FCN), and the feature vector output by the FCN is used as the local feature vector of the partition. In addition, the local feature vectors of all the partitions can be averaged to obtain the global feature vector.
B) And selecting two partitions from the multiple partitions according to the global feature vector and the local feature vector, and fusing the two partitions into one partition.
Here, after the global feature vector and the local feature vector of each partition are obtained, two partitions may be selected from the plurality of partitions to be fused in the following manner:
firstly, taking the global features as indexes, adopting an attention mechanism to generate selection probability values of all partitions, and selecting one partition with the largest probability value as a first selected partition according to the selection probability values of all partitions;
And then, taking the local area characteristics of the first partition as indexes, adopting an attention mechanism to generate selection probability values of the remaining partitions (the remaining partitions refer to other partitions except the first partition), and selecting one partition with the largest probability value from the selection probability values of all the remaining partitions as a selected second partition according to the selection probability values of all the remaining partitions, so that the first partition and the second partition are used as partitions to be fused.
C) And calculating the local optimization route of the fusion partition, and re-dividing the fusion partition into two new partitions according to the local optimization route of the fusion partition.
Here, various small-scale VRP solving algorithms in the prior art, for example, a small-scale solving algorithm based on reinforcement learning, may be used to generate a locally optimized route of the distribution task in the fusion partition by inputting the geographic position coordinates of each client site in the fusion partition, the geographic position coordinates of the originating site, and the maximum loading capacity of the vehicle. And then, according to the local optimization route of the fusion partition, re-dividing the fusion partition into two new partitions. One manner in which the embodiments of the present invention may be employed to repartition partitions is as follows:
And selecting a coordinate average point for each path in the local optimization route of the fusion partition, wherein the coordinate average point can be an average point of geographic coordinates of all client stations in the path, and can also be a central point of a geometric shape surrounded by each path. And then, carrying out principal component analysis (PRINCIPAL COMPONENTS ANALYSIS, PCA) on the coordinate average points to obtain one-dimensional characterization of the paths, and dividing the paths in the local optimization route of the fusion partition into two groups according to the one-dimensional characterization of each path, wherein the stations in each group of paths belong to the same new partition. For example, the one-dimensional characterizations of each path of the fused partition are divided into two groups, and the paths contained in each group are determined according to the one-dimensional characterizations contained in each group, so that each client site in the paths in each group belongs to the same new partition, and two new partitions and client sites in each new partition are obtained. The one-dimensional characterizations are grouped, and one grouping mode can be that an average value of all the one-dimensional characterizations is calculated, one group is taken as one-dimensional characterization which is not smaller than the average value, and the rest one-dimensional characterizations are taken as another group.
Step 104, calculating the local optimized route of the two new partitions, and updating the global optimized route and the route total cost.
Here, various small-scale VRP solving algorithms using the prior art, for example, a small-scale solving algorithm based on reinforcement learning, may be used to generate a locally optimized route and a local route cost of the distribution task in the new partition by inputting the geographic position coordinates of each client site in the new partition, the geographic position coordinates of the originating site, and the maximum loading capacity of the vehicle. Since the local route costs of the two new partitions after repartitioning may change with respect to the original partition, the global optimized route and route total cost of all client sites obtained in step 102 needs to be updated according to the local optimized route and local route costs of the two new partitions.
Step 105, judging whether the updated route total cost is lower than the optimal route total cost, if yes, entering step 106, otherwise, entering an iteration stop judging step 107.
Here, the updated route total cost obtained in step 104 is compared with the optimal route total cost, and it is determined whether the route total cost after repartitioning is reduced.
Step 106, updating the optimal optimized route and the optimal route total cost according to the updated global optimized route and route total cost, and returning to step 103.
Here, when the total cost of the route after repartitioning is reduced, the optimal optimized route and the optimal route total cost need to be correspondingly updated according to the updated global optimized route and the updated route total cost, then step 103 is returned, two partitions are continuously selected from the current partitions to be fused and repartitioned, and the steps are iteratively executed to solve the better route and cost.
Step 107, judging whether a preset iteration stop condition is met, if yes, entering step 108, otherwise, returning to the repartitioning step 103.
Here, when the total route cost after repartitioning is not reduced, it is determined whether a preset iteration stop condition is satisfied, where the iteration stop condition may specifically be that the total route cost after N consecutive updates is not lower than the optimal route cost, and N is a preset integer greater than 2. If the iteration stop condition is met, step 108 is entered, otherwise, step 103 is returned to, and two partitions are selected from the current partitions to be fused and repartitioned, and the above steps are executed iteratively to solve the better route and cost.
And step 108, outputting the optimal optimized route, and ending the flow.
In step 108, the current optimal optimized route is output as the final route planning result. In addition, the current total cost of the optimal route can be output as the total cost of the optimal route.
Fig. 2 shows an example of the above iterative calculation, in fig. 2, black large dots represent the originating site, and each black small dot represents the client site. Taking fig. 2 as an example, partitioning is performed by the step 102, and assuming that 7 partitions from partition 1 to partition 7 are obtained after partitioning (step 201 in fig. 2), and the local optimized route and the local route cost of the 7 partitions are obtained (step 202 in fig. 2), and then the global optimized route and the route total cost are obtained by summarizing. In step 103, the partition 1 and the partition 2 are fused (step 203 of fig. 2), and the fused partition is calculated to obtain a new partition 1 and a new partition 2 by re-dividing the fused partition (step 205 of fig. 2), and at this time, the local optimized route and the local route cost of the new partition 1 and the new partition 2 need to be combined with the local optimized route and the local route cost of the original partitions 3 to 7, so as to obtain a new global optimized route and a new route total cost. If the updated route total cost is reduced, the process returns to step 203, and the current partition is fused, repartitioned, and the like.
Through the steps, the embodiment of the invention can find the optimal or near-optimal global optimization route and the total cost thereof through repeated iterative computation. According to the embodiment of the invention, a large number of client stations can be divided into a plurality of subareas, and then small-scale VRP solving is carried out under each subarea, so that the problem of low performance and efficiency of directly solving the large-scale client stations is avoided, and the performance and efficiency of path planning in large-scale vehicle path planning are improved.
Prior to step 101, embodiments of the present invention may pre-train a zone adjustment network, which may include an LSTM network and an FCN and attention mechanism network, as described above. As shown in fig. 3, the specific training steps include:
Step 301, obtaining a training set, wherein the training set comprises a plurality of groups of training data, and each group of training data comprises an originating station, a maximum loading capacity of a delivery vehicle, geographic positions of a plurality of client stations and delivery requirement information of each client station.
Here, the maximum load amount (e.g., maximum capacity, maximum load, etc.) of the vehicle may also be input. Alternatively, more information may be entered, such as a service time window for each customer site (i.e., the customer site can only be serviced within the time window), road congestion information, vehicle number limitations, etc.
Step 302, initializing a reference model of a partition adjustment network.
Here, a reference model of the partition adjustment network is initialized, and may be updated during each subsequent training process. The partition adjustment network adopts a current reference model at the beginning of each round of training, namely, the partition adjustment network is initialized according to the model parameters of the current reference model at the beginning of each round of training.
And 303, selecting a group of training data which is not used yet, performing one-round training by using the selected training data, and training the partition adjustment network, wherein the partition adjustment network adopts a current reference model when each-round training is started, updating model parameters of the partition adjustment network by using the training data in the process of each-round training, and updating the reference model according to the updated partition adjustment network when the updated partition adjustment network has improved performance relative to the current reference model.
Step 304, judging whether a preset network training ending condition is met when each round of training is ended, if yes, entering step 305, otherwise, returning to step 303.
Here, the network training end condition may be that all training data is trained.
Considering that the model is prevented from being trained and the training efficiency is improved, the embodiment of the invention can verify the model through a group of verification data, and judge whether the network training is required to be stopped according to the verification result, and the embodiment of the invention is specific:
After each round of training is finished, taking the current reference model as the partition adjustment network, taking a group of verification data as input data, executing steps 101-108 in fig. 1 to obtain a global optimized route and a route total cost corresponding to the verification data after the round of training is finished, and updating an optimal route total cost corresponding to the verification data according to the route total cost corresponding to the verification data obtained after each round of training is finished, for example, when the route total cost is reduced, updating the optimal route total cost corresponding to the verification data according to the route total cost corresponding to the verification data obtained after the round of training is finished, and if the route total cost is not reduced, keeping the optimal route corresponding to the verification data unchanged. At this time, the network training ending condition may be set such that the total route cost corresponding to the verification data obtained after the end of the continuous M-turn training is not lower than the optimal route total cost corresponding to the verification data, where M is a preset integer greater than 2. Therefore, the training process can be stopped in time when the performance of the training partition adjustment network is improved limited, and the training efficiency is improved.
And step 305, finishing the training of the partition adjustment network, and outputting the reference model as the partition adjustment network obtained by final training.
In step 303, a round of training is performed by using the selected set of training data, where each round of training may include multiple iterative processes, and specifically, as shown in fig. 4, each round of training includes the following steps:
Step 3031, clustering and partitioning the customer sites according to the geographic positions of the customer sites in the training data to obtain a plurality of partitions, calculating to obtain local optimized routes and local route costs of each partition according to the maximum loading capacity of the originating sites, the delivery vehicles, the geographic positions of the customer sites and the delivery demand information of the customer sites in the training data, obtaining global optimized routes and route total cost of all the customer sites, and updating the optimal optimized routes and the optimal route total cost according to the global optimized routes and route total cost. And step 3032, utilizing the partition adjustment network to fuse and repartition two partitions in the multiple partitions to obtain two new partitions.
Step 3033, calculates the locally optimized route for the two new partitions and updates the globally optimized route and the route total cost.
And step 3034, calculating the reduction amount of the total route cost before and after updating, and using the reduction amount as a rewarding function value to guide the subarea adjustment network to carry out gradient descent so as to obtain the updated subarea adjustment network.
Step 3035, it is determined whether the updated route total cost is lower than the optimal route total cost, if yes, step 3036 is entered, otherwise step 3037 is entered.
Step 3036, updating the optimal optimized route and the optimal route total cost according to the updated global optimized route and the updated route total cost, updating the reference model according to the updated partition adjustment network, and returning to step 3032.
Step 3037, it is determined whether a preset stopping condition of each training round is satisfied, if yes, the training of the current training round is ended, and step 304 is entered, otherwise, step 3032 is returned.
Some of the above steps in the training process are similar to those associated with the workflow of fig. 1, and are not repeated here for the sake of economy.
Through the steps, the method and the device can solve the problems that a large-scale VRP model is long in training time, the training process is difficult to converge and the like, and improve performance and efficiency of solving the VRP problem.
The inventor compares the method of the embodiment of the invention with the algorithms such as ant colony optimization in the prior art, and discovers that the embodiment of the invention can greatly reduce the time required by calculation and can obtain a solution with better cost, and the advantages are more prominent especially when solving a large-scale VRP.
Based on the vehicle path planning method, the embodiment of the invention also provides a device for implementing the method.
Referring to fig. 5, a vehicle path planning apparatus 50 according to an embodiment of the present invention includes:
A data obtaining module 51, configured to obtain, as input data, an originating station at which a path planning is to be performed, a maximum load capacity of a delivery vehicle, geographic locations of a plurality of customer stations, and delivery demand information of each customer station;
The initial calculation module 52 is configured to perform clustering partition on the client sites according to the geographic locations of the plurality of client sites in the input data, so as to obtain a plurality of partitions; calculating to obtain a local optimized route and a local route cost of each partition according to the starting station, the maximum loading capacity of the delivery vehicle, the geographic position of the client station and the delivery demand information of the client station in the input data, obtaining a global optimized route and a route total cost of all the client stations, and updating an optimal optimized route and the optimal route total cost according to the global optimized route and the route total cost;
A re-partition module 53, configured to fuse and re-partition two partitions of the plurality of partitions by using a partition adjustment network obtained by training in advance, so as to obtain two new partitions;
an iterative computation module 54 for computing a locally optimized route for the two new partitions and updating the globally optimized route and the route total cost;
The updating processing module 55 is configured to determine whether the updated route total cost is lower than the optimal route total cost, if yes, update the optimal optimized route and the optimal route total cost according to the updated global optimized route and route total cost, and return to the repartitioning module;
the iteration stop judging module 56 is configured to judge whether a preset iteration stop condition is satisfied, if yes, output the optimal optimization route, otherwise, return to the repartitioning module.
Optionally, the iteration stop condition is that the total route cost after being updated for N times is not lower than the optimal route cost, and N is a preset integer greater than 2.
Optionally, the repartitioning module specifically may include:
The first calculation module is used for generating a local feature vector of each partition according to the local optimization route and the local route cost of each partition, and generating a global feature vector according to the local feature vectors of all the partitions;
the selection fusion module is used for selecting two partitions from the partitions according to the global feature vector and the local feature vector and fusing the two partitions into one partition;
The division module is used for calculating the local optimization route of the fusion partition, and re-dividing the fusion partition into two new partitions according to the local optimization route of the fusion partition.
Optionally, the first computing module may include:
The first processing module is used for inputting a client site sequence in a local optimized route of each partition into a long-short-term memory LSTM network as an input sequence to generate a primary characteristic sequence of the partition;
and the second processing module is used for averaging the local feature vectors of all the partitions to obtain the global feature vector.
Optionally, the selection fusion module is specifically configured to:
Generating selection probability values of all partitions by taking the global features as indexes and adopting an attention mechanism, and selecting one partition with the largest selection probability value as a first selected partition;
And taking the local area characteristics of the first partition as indexes, adopting an attention mechanism to generate a selection probability value of the rest partitions, and selecting one partition with the largest probability value as a selected second partition.
Optionally, the dividing module is specifically configured to:
Selecting a coordinate average point for each path in the local optimization route of the fusion partition, and carrying out principal component analysis on the coordinate average point to obtain one-dimensional characterization of the path, and dividing the paths in the local optimization route of the fusion partition into two groups according to the one-dimensional characterization of each path, wherein stations in each group of paths belong to the same new partition.
Optionally, the vehicle path planning device further includes:
and the training module is used for training to obtain the partition adjustment network.
Optionally, the training module may specifically include:
A first module for obtaining a training set, the training set comprising a plurality of sets of training data, each set of training data comprising an originating site, a maximum load of delivery vehicles, geographic locations of a plurality of customer sites, and delivery demand information for each customer site;
A second module for initializing a reference model of a partition adjustment network;
The system comprises a third module, a third module and a control module, wherein the third module is used for selecting a group of training data which is not used yet, performing one-round training by utilizing the selected training data, and training the partition adjustment network, wherein the partition adjustment network adopts a current reference model when each-round training is started;
And the fourth module is used for judging whether a preset network training ending condition is met when each round of training is ended, if yes, ending the training of the partition adjustment network, outputting the reference model as the partition adjustment network obtained by final training, and otherwise, returning to the third module.
Optionally, the third module may specifically include:
The system comprises a training data module, a first training sub-module, a second training sub-module, a third training sub-module, a first sub-module and a second training sub-module, wherein the training data module is used for acquiring a plurality of customer sites by clustering and partitioning according to the geographic positions of the customer sites in the training data, and acquiring a plurality of partitions;
the second training sub-module is used for fusing and repartitioning two partitions in the plurality of partitions by utilizing the partition adjustment network to obtain two new partitions;
The third training sub-module is used for calculating the local optimized routes of the two new partitions and updating the global optimized route and the route total cost;
A fourth training sub-module, configured to calculate a reduction amount of the total route cost before and after updating, and use the reduction amount as a reward function value to guide the partition adjustment network to perform gradient descent, so as to obtain the updated partition adjustment network;
A fifth training sub-module, configured to determine whether the updated route total cost is lower than the optimal route total cost, if yes, update the optimal optimized route and the optimal route total cost according to the updated global optimized route and the updated route total cost, and update the reference model according to the updated partition adjustment network and return to the second training sub-step;
and the sixth training sub-module is used for judging whether the preset stopping condition of each round of training is met, if yes, ending the training of the current round, and if not, returning to the second training sub-module.
Optionally, the vehicle path planning device further includes:
The system comprises an initial calculation module, a repartitioning module, an iterative calculation module, an updating processing module and an iteration stop judging module, wherein the initial calculation module, the repartitioning module, the iteration stop judging module and the updating processing module are used for obtaining a global optimization route and a route total cost corresponding to verification data;
The network training ending condition is that the total route cost corresponding to the verification data obtained after the continuous M rounds of training is ended is not lower than the optimal route total cost corresponding to the verification data, and M is a preset integer greater than 2.
Through the device, the embodiment of the invention can improve the performance and efficiency of path planning in large-scale vehicle path planning.
As shown in fig. 6, another vehicle path planning apparatus 60 is provided according to an embodiment of the present invention, and the vehicle path planning apparatus 60 specifically includes a processor 61, a memory 62, a bus system 63, a receiver 64, and a transmitter 65. Wherein the processor 61, the memory 62, the receiver 64 and the transmitter 65 are connected through the bus system 63, the memory 62 is used for storing instructions, and the processor 61 is used for executing the instructions stored in the memory 62 to control the receiver 64 to receive signals and control the transmitter 65 to transmit signals;
Wherein the processor 61 is configured to read the program in the memory, and execute the following procedures:
A data acquisition step of acquiring an originating station for path planning, a maximum loading capacity of a delivery vehicle, geographic positions of a plurality of client stations and delivery demand information of each client station as input data;
According to the maximum loading capacity of the starting station, the delivery vehicles, the geographic positions of the client stations and the delivery demand information of the client stations in the input data, calculating to obtain local optimized routes and local route costs of each zone, obtaining global optimized routes and route total cost of all the client stations, and updating optimal optimized routes and optimal route total cost according to the global optimized routes and route total cost;
a re-partitioning step, namely fusing and re-partitioning two partitions in the plurality of partitions by utilizing a partition adjustment network obtained by pre-training to obtain two new partitions;
An iterative calculation step of calculating a local optimization route of the two new partitions and updating the global optimization route and the route total cost;
An updating processing step, namely judging whether the updated route total cost is lower than the optimal route total cost, if so, updating the optimal optimized route and the optimal route total cost according to the updated global optimized route and the updated route total cost, and returning to the repartitioning step, otherwise, entering an iteration stop judging step;
And the iteration stop judging step is used for judging whether a preset iteration stop condition is met, if yes, outputting the optimal optimization route, and otherwise, returning to the repartitioning step.
It should be appreciated that in embodiments of the present invention, the processor 61 may be a central processing unit (Central Processing Unit, simply "CPU"), the processor 61 may also be other general purpose processors, digital Signal Processors (DSPs), application Specific Integrated Circuits (ASICs), off-the-shelf programmable gate arrays (FPGAs) or other programmable logic devices, discrete gate or transistor logic devices, discrete hardware components, or the like. A general purpose processor may be a microprocessor or the processor may be any conventional processor or the like.
The memory 62 may include read only memory and random access memory and provides instructions and data to the processor 61. A portion of memory 62 may also include non-volatile random access memory. For example, the memory 62 may also store information of the device type.
The bus system 63 may include a power bus, a control bus, a status signal bus, and the like, in addition to a data bus. But for clarity of illustration the various buses are labeled in the figure as bus system 63.
In implementation, the steps of the above method may be performed by integrated logic circuits of hardware in the processor 61 or by instructions in the form of software. The steps of a method disclosed in connection with the embodiments of the present invention may be embodied directly in a hardware processor for execution, or in a combination of hardware and software modules in the processor for execution. The software modules may be located in a random access memory, flash memory, read only memory, programmable read only memory, or electrically erasable programmable memory, registers, etc. as well known in the art. The storage medium is located in a memory 62 and the processor 61 reads the information in the memory 62 and in combination with its hardware performs the steps of the above method. To avoid repetition, a detailed description is not provided herein.
According to at least one embodiment of the invention, the iteration stop condition is that the total route cost after N continuous updates is not lower than the optimal route cost, and N is a preset integer greater than 2.
According to at least one embodiment of the present invention, the program when executed by the processor 61 may further implement the steps of:
generating a local feature vector of each partition according to the local optimized route and the local route cost of each partition, and generating a global feature vector according to the local feature vectors of all the partitions;
selecting two partitions from the multiple partitions according to the global feature vector and the local feature vector, and fusing the two partitions into one partition;
And calculating the local optimization route of the fusion partition, and re-dividing the fusion partition into two new partitions according to the local optimization route of the fusion partition.
According to at least one embodiment of the present invention, the program when executed by the processor 61 may further implement the steps of:
for each partition, inputting a client site sequence in a local optimized route of the partition as an input sequence to a long-short-term memory LSTM network to generate a primary characteristic sequence of the partition;
And inputting the primary characteristic sequence and the local route cost of the partition into a full convolution network to generate a local characteristic vector of the partition.
According to at least one embodiment of the present invention, the program when executed by the processor 61 may further implement the steps of:
and averaging the local feature vectors of all the partitions to obtain the global feature vector.
According to at least one embodiment of the present invention, the program when executed by the processor 61 may further implement the steps of:
Generating selection probability values of all partitions by taking the global features as indexes and adopting an attention mechanism, and selecting one partition with the largest selection probability value as a first selected partition;
And taking the local area characteristics of the first partition as indexes, adopting an attention mechanism to generate a selection probability value of the rest partitions, and selecting one partition with the largest probability value as a selected second partition.
According to at least one embodiment of the present invention, the program when executed by the processor 61 may further implement the steps of:
Selecting a coordinate average point for each path in the local optimization route of the fusion partition, and carrying out principal component analysis on the coordinate average point to obtain one-dimensional characterization of the path, and dividing the paths in the local optimization route of the fusion partition into two groups according to the one-dimensional characterization of each path, wherein stations in each group of paths belong to the same new partition.
According to at least one embodiment of the present invention, the program when executed by the processor 61 may further implement the steps of:
And before the data input step, executing a training step, and training to obtain the partition adjustment network.
According to at least one embodiment of the present invention, the program when executed by the processor 61 may further implement the steps of:
The method comprises the steps that a training set is obtained, wherein the training set comprises a plurality of groups of training data, and each group of training data comprises an originating station, the maximum loading capacity of a delivery vehicle, the geographic positions of a plurality of client stations and delivery demand information of each client station;
initializing a reference model of a partition adjustment network;
selecting a group of training data which are not used yet, and training the partition adjustment network by utilizing the selected training data for one round, wherein the partition adjustment network adopts a current reference model when each round of training is started; in the training process of each round, updating the model parameters of the partition adjusting network by utilizing the training data, and updating the reference model according to the updated partition adjusting network when the updated partition adjusting network has improved performance relative to the current reference model;
And a fourth step of judging whether a preset network training ending condition is met when each round of training is ended, if yes, ending the training of the partition adjustment network, outputting the reference model as the partition adjustment network obtained by final training, and otherwise, returning to the third step.
According to at least one embodiment of the present invention, the program when executed by the processor 61 may further implement the steps of:
According to the maximum loading capacity of the starting station, the delivery vehicle, the geographic position of the client station and the delivery demand information of the client station in the training data, calculating to obtain a local optimized route and a local route cost of each zone, obtaining global optimized routes and route total cost of all the client stations, and updating the optimal optimized route and the optimal route total cost according to the global optimized routes and the route total cost;
a second training sub-step, utilizing the partition adjustment network to fuse and repartition two partitions in the multiple partitions to obtain two new partitions;
a third training sub-step of calculating a local optimized route of the two new partitions and updating the global optimized route and the route total cost;
A fourth training sub-step of calculating the reduction amount of the total route cost before and after updating, taking the reduction amount as a rewarding function value, and guiding the subarea adjustment network to carry out gradient descent so as to obtain the updated subarea adjustment network;
a fifth training sub-step of judging whether the updated route total cost is lower than the optimal route total cost, if so, updating the optimal optimized route and the optimal route total cost according to the updated global optimized route and the updated route total cost, and updating the reference model according to the updated partition adjustment network and returning to the second training sub-step, otherwise, entering a sixth training sub-step;
and a sixth step of judging whether a preset stopping condition of each training round is met, if yes, ending the training of the current training round, otherwise, returning to the second training sub-step.
According to at least one embodiment of the present invention, the program when executed by the processor 61 may further implement the steps of:
After each round of training is finished, taking a current reference model as the partition adjustment network, taking a group of verification data as input data, and executing the initial calculation step, the repartitioning step, the iterative calculation step, the updating processing step and the iteration stop judging step to obtain a global optimized route and a route total cost corresponding to the verification data;
The network training ending condition is that the total route cost corresponding to the verification data obtained after the continuous M rounds of training is ended is not lower than the optimal route total cost corresponding to the verification data, and M is a preset integer greater than 2.
When the program is executed by the processor, all the implementation manners in the vehicle path planning method shown in fig. 1 can be realized, and the same technical effects can be achieved, so that repetition is avoided, and the description is omitted here.
Those of ordinary skill in the art will appreciate that the various illustrative elements and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, or combinations of computer software and electronic hardware. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the solution. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention.
It will be clear to those skilled in the art that, for convenience and brevity of description, specific working procedures of the above-described systems, apparatuses and units may refer to corresponding procedures in the foregoing method embodiments, and are not repeated herein.
In the embodiments provided in the present application, it should be understood that the disclosed apparatus and method may be implemented in other manners. For example, the apparatus embodiments described above are merely illustrative, e.g., the division of the units is merely a logical function division, and there may be additional divisions when actually implemented, e.g., multiple units or components may be combined or integrated into another system, or some features may be omitted or not performed. Alternatively, the coupling or direct coupling or communication connection shown or discussed with each other may be an indirect coupling or communication connection via some interfaces, devices or units, which may be in electrical, mechanical or other form.
The units described as separate units may or may not be physically separate, and units shown as units may or may not be physical units, may be located in one place, or may be distributed on a plurality of network units. Some or all of the units may be selected according to actual needs to achieve the purpose of the embodiment of the present invention.
In addition, each functional unit in the embodiments of the present invention may be integrated in one processing unit, or each unit may exist alone physically, or two or more units may be integrated in one unit.
The functions, if implemented in the form of software functional units and sold or used as a stand-alone product, may be stored in a computer-readable storage medium. Based on this understanding, the technical solution of the present invention may be embodied essentially or in a part contributing to the prior art or in a part of the technical solution, in the form of a software product stored in a storage medium, comprising several instructions for causing a computer device (which may be a personal computer, a server, a network device, etc.) to perform all or part of the steps of the method according to the embodiments of the present invention. The storage medium includes a U disk, a removable hard disk, a Read-Only Memory (ROM), a random access Memory (RAM, random Access Memory), a magnetic disk, an optical disk, or other various media capable of storing program codes.
While the invention has been described with reference to certain preferred embodiments, it will be understood by those skilled in the art that various changes and substitutions of equivalents may be made and equivalents will be apparent to those skilled in the art without departing from the scope of the invention. Therefore, the protection scope of the invention is subject to the protection scope of the claims.
Claims (10)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202011056281.4A CN114330800B (en) | 2020-09-29 | 2020-09-29 | Vehicle path planning method and device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202011056281.4A CN114330800B (en) | 2020-09-29 | 2020-09-29 | Vehicle path planning method and device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN114330800A CN114330800A (en) | 2022-04-12 |
| CN114330800B true CN114330800B (en) | 2025-03-04 |
Family
ID=81011254
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202011056281.4A Active CN114330800B (en) | 2020-09-29 | 2020-09-29 | Vehicle path planning method and device |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114330800B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115933554B (en) * | 2022-11-25 | 2025-03-14 | 百度(中国)有限公司 | Path planning method, path planning model and training method of selection model |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109323702A (en) * | 2017-07-31 | 2019-02-12 | 高德信息技术有限公司 | A kind of navigation route planning method and device |
| CN109901580A (en) * | 2019-03-13 | 2019-06-18 | 华南理工大学 | A cooperative path and obstacle avoidance system and method for unmanned aerial vehicle and unmanned ground robot |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7010425B2 (en) * | 2003-03-31 | 2006-03-07 | Deere & Company | Path planner and a method for planning a path of a work vehicle |
| CN109947098A (en) * | 2019-03-06 | 2019-06-28 | 天津理工大学 | A distance-first optimal path selection method based on machine learning strategy |
-
2020
- 2020-09-29 CN CN202011056281.4A patent/CN114330800B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109323702A (en) * | 2017-07-31 | 2019-02-12 | 高德信息技术有限公司 | A kind of navigation route planning method and device |
| CN109901580A (en) * | 2019-03-13 | 2019-06-18 | 华南理工大学 | A cooperative path and obstacle avoidance system and method for unmanned aerial vehicle and unmanned ground robot |
Also Published As
| Publication number | Publication date |
|---|---|
| CN114330800A (en) | 2022-04-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| AU2019279920B2 (en) | Method and system for estimating time of arrival | |
| US11151680B2 (en) | Systems and methods for recommending transportation means | |
| CN111366160B (en) | Path planning method, path planning device and terminal equipment | |
| CN114944059B (en) | Method and system for determining estimated arrival time | |
| TW201901116A (en) | System and method for digital route planning | |
| CN112101676B (en) | Riding path planning method and device, computer equipment and storage medium | |
| CN113682318A (en) | Vehicle running control method and device | |
| CN111833605B (en) | Road condition prediction method, road condition prediction model training device and storage medium | |
| EP3704645A1 (en) | Systems and methods for determining an estimated time of arrival for online to offline services | |
| CN111859178A (en) | A method and system for recommending a pick-up point | |
| CN116194935B (en) | Method and apparatus for determining a navigation profile of a vehicle in a geographic area | |
| CN114330800B (en) | Vehicle path planning method and device | |
| Li et al. | Fedvanet: Efficient federated learning with non-iid data for vehicular ad hoc networks | |
| CN116360426A (en) | Global path planning method, system, medium and equipment for automatic driving of vehicle | |
| US20210110326A1 (en) | Route-based digital service management | |
| US20230211692A1 (en) | Automatic Routing Through Electric Vehicle Charging Stations | |
| CN112330001A (en) | Logistics distribution vehicle route optimization method based on discrete bat algorithm | |
| CN112857382B (en) | Travel route selection method and device | |
| CN118386855A (en) | Method, device, server and storage medium for predicting energy consumption of vehicle | |
| He et al. | Heterogeneous pointer network for travelling officer problem | |
| CN117980695A (en) | Processing digital map data | |
| CN114386643B (en) | Vehicle path planning method and device | |
| CN116090589A (en) | An online scheduling method for online car-hailing driven by platform benefits under location noise disturbance | |
| CN116821525A (en) | Method and related device for determining endurance range | |
| US12247839B2 (en) | Waypoint ordering |
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 | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |