[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN115062852A - Transportation path planning method and device - Google Patents

Transportation path planning method and device Download PDF

Info

Publication number
CN115062852A
CN115062852A CN202210718756.4A CN202210718756A CN115062852A CN 115062852 A CN115062852 A CN 115062852A CN 202210718756 A CN202210718756 A CN 202210718756A CN 115062852 A CN115062852 A CN 115062852A
Authority
CN
China
Prior art keywords
path
transportation
order information
operator
initial
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
Application number
CN202210718756.4A
Other languages
Chinese (zh)
Inventor
张涛
钟祥宜
蔡春茂
李观群
李发平
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Shanghai 100me Network Technology Co ltd
Original Assignee
Shanghai 100me Network Technology Co ltd
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Shanghai 100me Network Technology Co ltd filed Critical Shanghai 100me Network Technology Co ltd
Priority to CN202210718756.4A priority Critical patent/CN115062852A/en
Publication of CN115062852A publication Critical patent/CN115062852A/en
Pending legal-status Critical Current

Links

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/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
    • G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem
    • 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/08—Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
    • G06Q10/083—Shipping
    • G06Q10/0835—Relationships between shipper or supplier and carriers
    • G06Q10/08355—Routing methods
    • 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
    • G06Q30/00—Commerce
    • G06Q30/06—Buying, selling or leasing transactions
    • G06Q30/0601—Electronic shopping [e-shopping]
    • G06Q30/0633—Lists, e.g. purchase orders, compilation or processing
    • G06Q30/0635—Processing of requisition or of purchase orders

Landscapes

  • Business, Economics & Management (AREA)
  • Engineering & Computer Science (AREA)
  • Economics (AREA)
  • Human Resources & Organizations (AREA)
  • Strategic Management (AREA)
  • Theoretical Computer Science (AREA)
  • Marketing (AREA)
  • Physics & Mathematics (AREA)
  • General Business, Economics & Management (AREA)
  • General Physics & Mathematics (AREA)
  • Development Economics (AREA)
  • Finance (AREA)
  • Accounting & Taxation (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Operations Research (AREA)
  • Quality & Reliability (AREA)
  • Tourism & Hospitality (AREA)
  • Game Theory and Decision Science (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

The embodiment of the application provides a transportation path planning method and a transportation path planning device, and the method comprises the following steps: receiving a plurality of order information, wherein the order information comprises a transportation starting and stopping station and a transportation requirement; determining an initial path containing a big bin and a front bin in the plurality of order information; deleting a set number of pre-bins from the initial path by the destruction operator to obtain a destruction path; the repair operator determines the importance of deleting the pre-bins, the importance is used as the selection probability, the deleted pre-bins are sequentially inserted into the optimal position of the damage path to obtain an update path, if the target value of the update path is not greater than the target value of the initial path, the update path is used as the initial path, the step of deleting the pre-bins with the set number from the initial path through the damage operator is returned, and the process is circulated until the final path is obtained; the importance is determined by the transportation requirement in the order information corresponding to the front bin; the target value is determined based on the transportation cost of the path. The method is used for realizing full-automatic transportation path planning and improving the optimization strength and efficiency of the transportation path.

Description

Transportation path planning method and device
Technical Field
The application relates to the technical field of computers, in particular to a transportation path planning method and device.
Background
With the continuous development of computer equipment, electronic commerce is also developing gradually. In electronic commerce, people transport items from a warehouse to a transportation destination by allocating the items by a transportation person through an online or offline order. Replenishment of the warehouse stock is also of paramount importance in this process.
In the prior art, a warehouse is generally divided into a large warehouse and front warehouses, and goods are stored in the large warehouse in a supplementing mode to the front warehouses. Wherein, an operation page can be provided through a transportation management system (abbreviated as TMS), so that a worker can select a transportation tool, a big cabin and a front cabin on the operation page, and the transportation management system obtains a better transportation path according to the selected transportation tool, the big cabin and the front cabin. However, in the method, under the scene of a large number of orders, manual operation is time-consuming and labor-consuming, the obtained optimized strength of the transportation path is not enough, and certain waste still exists on the transportation cost.
There is a need for a transportation path planning method and apparatus for realizing full-automatic transportation path planning, and improving the optimization strength and efficiency of transportation path.
Disclosure of Invention
The embodiment of the application provides a transportation path planning method and device, which are used for realizing full-automatic transportation path planning, improving the optimization strength of a transportation path and improving the optimization efficiency of the transportation path.
In a first aspect, an embodiment of the present application provides a transportation path planning method, including:
receiving a plurality of order information, wherein any order information comprises a transportation starting and stopping station and transportation requirements; the transportation starting and stopping station comprises a large cabin as a starting point and a front cabin as a terminal point;
determining an initial path according to the plurality of order information, wherein the initial path comprises each big bin and each front bin in the plurality of order information;
deleting a set number of front bins from the initial path through a destruction operator to obtain a destruction path; determining the importance of the deleted pre-bins through a repair operator, sequentially inserting the deleted pre-bins into the optimal position of the damaged path by taking the importance as a selection probability to obtain an updated path, taking the updated path as the initial path if the target value of the updated path is not greater than the target value of the initial path, returning to the step of deleting a set number of pre-bins from the initial path through the damage operator, and circularly performing until a final path is obtained; wherein, the importance is determined by the transportation requirement in the order information corresponding to the front bin; the target value is determined based on the transportation cost of the path.
In the method, a plurality of order information can be received, a final path is determined according to the transportation starting and stopping station and the transportation requirement in the plurality of order information, the importance of the front bin is used as a reference factor for optimizing the initial path, the higher the importance of the front bin is, the larger the transportation requirement-transportation cost occupation is, such as the vehicle volume of the initial path and the vehicle cost, the higher the vehicle volume and the vehicle cost in the initial path are, the front bin with the high importance is used as a relative priority optimization object under a certain vehicle volume and vehicle cost in the initial path, the optimization degree and efficiency are effectively improved, the speed of obtaining the final path can be accelerated in application, and the optimization of obtaining the final path is improved.
Optionally, determining an initial path according to the plurality of order information includes:
determining at least one temporary path according to the plurality of order information based on a mileage-saving method;
determining the transportation cost and the route accessibility of each temporary route according to the transportation requirements in the plurality of pieces of order information, wherein the route accessibility is determined according to the distance between the front bins in the route, and the closer the distance between the front bins in the route is, the higher the route accessibility is;
for each temporary path, substituting the transportation cost and the path reachability of the temporary path into an objective function to obtain a target value of the temporary path;
and determining a temporary path with the lowest target value from the at least one temporary path as an initial path.
In the method, before the initial path is optimized through a destruction operator and a repair operator, based on a mileage-saving algorithm, distance relations between pre-bins and large bins in a plurality of order information are calculated to determine a plurality of temporary paths with short paths, then the transportation cost and the path accessibility of each temporary path in the plurality of temporary paths are calculated and substituted into a target function to obtain the target value of each temporary path, and the temporary path with the lowest target value is used as the initial path. Therefore, the initial path is a result of simply optimizing, the efficiency of subsequent optimization according to the repair operator and the damage operator can be improved through simple optimization, the obtained final path optimization effect is better, the transportation cost of the finally obtained final path is low, the path accessibility of the path between the big bin and the front bin is higher, and the goods are convenient to transport.
Optionally, determining the transportation cost of each temporary route according to the transportation requirement in the plurality of pieces of order information includes:
for any temporary path, determining the distance between each node in the temporary path according to the road network data; each node comprises a large bin and a front bin;
allocating vehicles according to the transportation requirements in each order information;
and determining the transportation cost of the temporary path according to the unloading time of each front bin, the mileage pricing of the vehicle type of the distributed vehicle, the city mileage pricing of the involved city and the distance between the nodes in the order information.
According to the method, the distance of each node in the temporary path can be accurately calculated according to the road network data. And allocating the vehicles according to the transportation requirements of each order information. For example, vehicles can be allocated to orders according to information such as cargo types and cargo quantities, and transportation requirements of each order information are guaranteed to be met. And determining the transportation cost of the temporary path according to the mileage pricing of the vehicle type of each order information corresponding to the vehicle, the city mileage pricing of the city involved, the unloading time and the distance between each node. Therefore, the accuracy of the transportation cost of the temporary path obtained by combining various factors is high.
Optionally, the destroy operator includes a plurality of kinds; before deleting the set number of pre-bins from the initial path by the destroy operator, the method further includes:
in each round of path optimization flow, selecting a damage operator of the round for path optimization by a roulette method;
after the updating path is taken as the initial path, the method further comprises the following steps:
and after the optimization of the path of the current round is finished, updating the score of the damage operator according to the updated path, wherein the score is used for selecting the probability parameter of the damage operator by a subsequent roulette method.
In the method, in the optimization process of the initial path, aiming at the damage operators for path optimization, various damage operators can be selected for path optimization in a roulette mode, after the path optimization is completed, the optimization effect of the damage operators is determined according to the final path obtained by the initial path optimization, the score of the damage operators is calculated, and the score of the damage operators is used as the probability parameter for selecting the damage operators in the subsequent roulette. Therefore, the score of the damage operator with good path optimization effect is high, the probability of the damage operator selected by the roulette method is high, the score of the damage operator with poor path optimization effect is low, the probability of the damage operator selected by the roulette method is low, the initial path is not optimized in the path optimization process, the optimization algorithm of the initial path is optimized, and the optimization efficiency is improved.
Optionally, the destruction operator includes at least one of a first random removal operator, a second random removal operator, a cost removal operator, a path removal operator, and a time removal operator; the first random removal operator is used for randomly removing the front bins in the initial path, the second random removal operator is used for randomly removing the sub-paths in the initial path, the cost removal operator is used for removing the front bins with high transportation service requirements in the initial path, the path removal operator is used for randomly removing part of paths in the sub-paths in the initial path, and the time removal operator is used for removing the front bins with the short transportation time requirements in the initial path.
In the method, the first random removal operator is configured to randomly remove the pre-bins in the initial path, and the repair operator is used to insert the randomly removed pre-bins into the optimal positions in the damaged initial path (e.g., the transportation cost and the path accessibility of the updated path obtained by inserting the randomly removed pre-bins into the optimal positions in the damaged initial path are substituted into the objective function to obtain the lowest target value) to obtain the updated path. That is, the first random removal operator has the advantage that for each pre-bin in the initial path, which has an equal probability of being removed, there is an opportunity for each pre-bin in the initial path to be optimized. The second random removal operator is used for removing the sub-paths in the initial path, and the repair operator is used for inserting the randomly removed sub-paths into the optimal positions in the damaged initial path (for example, the transport cost and the path reach of the updated path obtained by inserting the randomly removed sub-paths into the optimal positions in the damaged initial path are substituted into the objective function to obtain the lowest target value) to obtain the updated path. That is, the second random removal operator has an advantage that the probability of being removed for each sub-path in the initial path is equal, and each sub-path in the initial path has an opportunity to be optimized in the path optimization process by taking the complete sub-path as a removal unit. The cost removing operator is used for removing the front bin with high transport service requirement in the initial path, the removed front bin with high transport service requirement is inserted into the damaged optimal position in the initial path by utilizing the repairing operator, the front bin with high transport service requirement can be optimized at the fastest speed, the target value optimization amplitude of the transport cost and the path reach of the initial path in the objective function is the largest, and the path optimization efficiency is improved. And the path removing operator is used for randomly removing part of paths in the sub paths in the initial path, and the repair operator is used for inserting the randomly removed part of sub paths into the optimal position in the damaged initial path to obtain an updated path. That is to say, the advantage of the path random removal operator is that the complete sub-path is used as the removal selection object, and partial path optimization is selected from the removal selection object-sub-path, thereby suitably accelerating the optimization efficiency. And the time removing operator is used for removing the front bin with the short transportation time requirement in the initial path, and the repairing operator is used for inserting the front bin with the short transportation time requirement into the damaged optimal position in the initial path to obtain an updated path. The transportation time requirements between adjacent front-end bins in the obtained updating path can not be too concentrated, and the problems that the unloading of workers is not timely or the transportation is not timely and the like can be effectively prevented.
Optionally, the repair operator includes a plurality of types, and before determining the importance of the deleted pre-bin by the repair operator, the method further includes:
in each round of path optimization flow, selecting a current round of repair operators for path optimization by a roulette method;
after the updating path is taken as the initial path, the method further comprises the following steps:
and after the optimization of the path of the round is finished, updating the score of the repair operator according to the updating path, wherein the score is used for selecting the probability parameter of the repair operator by a subsequent roulette method.
In the method, in the optimization process of the initial path, aiming at the repair operators for path optimization, a plurality of repair operators can be selected for path optimization in a roulette mode, after the path optimization is completed, the optimization effect of the repair operators is determined according to the final path obtained by the initial path optimization, the scores of the repair operators are calculated, and the scores of the repair operators are used as the probability parameters for selecting the repair operators by subsequent roulette. Therefore, the score of the repair operator with good path optimization effect is high, the probability of the corresponding repair operator selected by the roulette method is high, the score of the repair operator with poor path optimization effect is low, the probability of the corresponding repair operator selected by the roulette method is low, the initial path is not optimized in the path optimization process, the optimization algorithm of the initial path is optimized, and the optimization efficiency is improved.
Optionally, before determining the initial path according to the plurality of order information, the method further includes:
determining that order information with transportation service requirements exceeding a first preset threshold exists in the plurality of order information, splitting the order information exceeding the first preset threshold into at least two pieces of order information, wherein the transportation service requirements of each piece of order information obtained through splitting are lower than the first preset threshold; or
Determining that order information with the transportation service requirement lower than a second preset threshold exists in the plurality of order information, combining the order information lower than the second preset threshold with one or more other order information into one order information, and enabling the transportation service requirement of the order information obtained through combination to be lower than the first preset threshold.
In the above method, if the transportation service requirement in the order information exceeds a first preset threshold, the transportation service capability of the current single order cannot support the order information well, and the order information needs to be split into at least two order information, so that each obtained order information conforms to the provided transportation service capability. For example, the transportation service requirement may include transportation manpower, vehicle transportation requirement, and other related information, and when the transportation manpower, the vehicle volume, and other requirements in the transportation service requirement in the single order information are higher than the upper limit of the transportation service requirement allocated to each order information, which is a first preset threshold, the problem of poor scheduling of the transportation vehicle and the transportation manpower may be caused, and the policy-removing scheme may effectively prevent such a situation from occurring. Accordingly, if there is order information in which the transportation service demand is lower than the second preset threshold in the plurality of order information, waste of transportation resources may occur. If the transportation service requirement in the order information is lower than the second preset threshold, the transportation service capacity (transportation manpower, vehicle volume) configured for each order information is idle, and transportation resources are wasted. The order information lower than the second preset threshold value is combined into one order information, so that the waste of the transportation resources can be effectively prevented.
In a second aspect, an embodiment of the present application provides a transportation path planning apparatus, including:
the receiving and sending module is used for receiving a plurality of order information, wherein any order information comprises a transportation starting and stopping station and a transportation requirement; the transportation starting and stopping station comprises a large cabin as a starting point and a front cabin as a terminal point;
the processing module is used for determining an initial path according to the plurality of order information, wherein the initial path comprises each big bin and each front bin in the plurality of order information;
the processing module is further used for deleting a set number of pre-bins from the initial path through a destruction operator to obtain a destruction path; determining the importance of the deleted pre-bins through a repair operator, sequentially inserting the deleted pre-bins into the optimal position of the damaged path by taking the importance as a selection probability to obtain an updated path, taking the updated path as the initial path if the target value of the updated path is not greater than the target value of the initial path, returning to the step of deleting a set number of pre-bins from the initial path through the damage operator, and circularly performing until a final path is obtained; wherein, the importance is determined by the transportation requirement in the order information corresponding to the front bin; the target value is determined based on the transportation cost of the path.
In a third aspect, an embodiment of the present application further provides a computing device, including: a memory for storing a program; a processor for calling the program stored in said memory and executing the method as described in the various possible designs of the first aspect according to the obtained program.
In a fourth aspect, embodiments of the present application further provide a computer-readable non-transitory storage medium including a computer-readable program which, when read and executed by a computer, causes the computer to perform the method as described in the various possible designs of the first aspect.
These and other implementations of the present application will be more readily understood from the following description of the embodiments.
Drawings
In order to more clearly illustrate the technical solutions in the embodiments of the present application, the drawings needed to be used in the description of the embodiments will be briefly introduced below, and it is obvious that the drawings in the following description are only some embodiments of the present application, and it is obvious for those skilled in the art to obtain other drawings based on these drawings without inventive exercise.
Fig. 1 is a schematic structural diagram of a transportation route planning according to an embodiment of the present disclosure;
fig. 2 is a schematic structural diagram of a transportation route planning according to an embodiment of the present application;
fig. 3 is a schematic flow chart of a transportation path planning method according to an embodiment of the present application;
fig. 4 is a trend chart of an influence of a transportation path planning method on transportation cost according to an embodiment of the present application;
fig. 5 is a schematic flow chart of a transportation path planning method according to an embodiment of the present application;
fig. 6 is a schematic view of a transportation path planning apparatus according to an embodiment of the present application.
Detailed Description
In order to make the objects, technical solutions and advantages of the present application clearer, the present application will be described in further detail with reference to the accompanying drawings, and it is obvious that the described embodiments are only a part of the embodiments of the present application, and not all embodiments. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present application.
Fig. 1 is a system architecture of a transportation path planning service provided in an embodiment of the present application, where the transportation path planning service includes: the device comprises a basic data module, a preliminary optimization module and an optimization module. After the transportation path planning system receives a plurality of order information, an initial path is obtained according to basic data in the basic data module and a preliminary optimization algorithm in the preliminary optimization module, the initial path is transmitted to the optimization module, and final path output is obtained according to the algorithm in the optimization module and the basic data in the basic data module.
Specifically, the basic data included in the basic data module may include related basic data such as a transportation cost pricing method, transportation parameters, road network data, vehicle resources, a selective starting algorithm, and the like.
The preliminary optimization module is used for planning a plurality of pieces of order information (the order information comprises a transportation starting and stopping station and transportation requirements, the transportation starting and stopping station comprises a large cabin serving as a starting point and a front cabin serving as a terminal point) received by service according to a transportation path based on a mileage saving method, if the order information with transportation service requirements exceeding a first preset threshold value exists in the plurality of pieces of order information, splitting the order information exceeding the first preset threshold value into at least two pieces of order information based on a splitting algorithm in a selectable opening algorithm, wherein the transportation service requirements of the split order information are lower than the first preset threshold value; or if the order information with the transportation service requirement lower than the second preset threshold value exists in the plurality of order information, combining the order information lower than the second preset threshold value and one or more other order information into one order information based on an order splitting algorithm in the selectively started algorithm, wherein the transportation service requirements of the order information obtained by combining are lower than the first preset threshold value. Thus, a plurality of order information is obtained, and at least one temporary path is determined according to the plurality of order information. Further, the transportation cost and the route accessibility of each temporary route are determined according to the transportation requirements in the plurality of order information (the transportation cost and the route accessibility of the corresponding temporary route are obtained by calculation according to the transportation requirements in the order information and the basic data in the basic data module). The route accessibility is determined according to the distance between the front bins in the route (the distance between the front bins can be determined according to road network data), the closer the distance between the front bins in the route is, the higher the route accessibility is, and the comprehensibility can be understood as the convenience of the transportation route. For example, the transportation distance between the front bins is closer, and the road conditions of the road sections between the front bins in the corresponding transportation time period are better. And then substituting the transportation cost and the route accessibility of each temporary route into an objective function to obtain a target value of the temporary route. And determining a temporary path with the lowest target value from at least one temporary path as an initial path, and transmitting the initial path to the optimization module.
The optimization module comprises a plurality of destruction operators. Such as a first random removal operator for randomly removing pre-bins in the initial path, a second random removal operator for randomly removing sub-paths in the initial path, a cost removal operator for removing pre-bins in the initial path with high transport service requirements, a path removal operator for randomly removing part of the path in the sub-path in the initial path, and a time removal operator for removing pre-bins in the initial path with near transport time requirements. A variety of repair operators are also included. E.g. for inserting the pre-bin removed by the destroy operator, or the removed sub-path, or a part of the removed sub-path, into the optimal position of the destroy path, so as to maximize the path reachability of the obtained updated path. And a pre-bin removed by the destruction operator, or the removed sub-path, or a part of the removed sub-path is inserted into the optimal position of the destruction path, so as to make the obtained target value of the update path lowest (the pre-bin removed by the destruction operator, or the removed sub-path, or the part of the removed sub-path is inserted into each position of the destruction path, the transportation cost and the path reach of the corresponding obtained path are substituted into the objective function, and the path corresponding to the lowest target value in the obtained target value is taken as the update path). Thus, the optimization module selects the damage operator and the repair operator respectively by the roulette method based on the damage operator and the repair operator thereof, and the score of the damage operator and the score of the repair operator. Deleting a set number of pre-bins from the initial path through the selected destruction operator to obtain a destruction path. Determining the importance of the deleted pre-bins through the selected repair operator, taking the importance as a selection probability, sequentially inserting the deleted pre-bins into the optimal position of the damaged path to obtain an updated path, and taking the updated path as an initial path if the target value of the updated path is not greater than the target value of the initial path; and if the target value of the updated path is larger than the target value of the initial path, not updating the initial path. And setting scores for the selected damage operator and the repair operator according to the optimization effect of the updated path so as to be used as probability references for selecting the damage operator and the repair operator in the roulette method in subsequent optimization. Returning to the step of respectively selecting a destruction operator and a repair operator by a roulette method, and circularly performing until a final path is obtained; wherein, the importance is determined by the transportation requirement in the order information corresponding to the front bin; the target value is determined based on the transportation cost of the path. Therefore, the pre-bins deleted by the destruction operators are inserted into the destruction path according to the importance, and the pre-bins with high transportation requirements are inserted into the path preferentially, so that the path optimization effect is maximum in the optimization of the circulating path (which is convenient to understand, if the pre-bins with smaller importance are inserted into the optimal position of the destruction path preferentially, the target value optimization degree of the obtained path is small, the pre-bins with smaller importance can preempt the optimal position of the pre-bins with larger importance, and the optimization efficiency is influenced. In the path optimization process, the optimization algorithm is set by a roulette method and according to the updated path, the scores of the damage operator and the repair operator, the optimization efficiency of the path optimization algorithm of each cycle is higher than that of the path optimization algorithm of the previous cycle, and the path optimization efficiency is further improved.
Based on the transportation path planning service, an embodiment of the present application further provides a system architecture for transportation path planning, as shown in fig. 2, where the transportation path planning system includes a warehousing management system, a transportation management system, and the transportation path planning service shown in fig. 1. The transportation path planning service may be installed in the transportation management system to provide a path optimization function, or the transportation management system may provide the path optimization function by using a called method, where a manner of how the transportation management system provides the path optimization function through the transportation path planning service is not particularly limited.
The Warehouse Management System (WMS) mainly aims at integrating warehouse operation technologies, so that the warehouse becomes a flowing link of a production line, the production line becomes a component of warehouse operation, order information can be generated according to the warehouse attributes of warehouses such as a front warehouse and a large warehouse and the like and the related information of the warehouse demand, and the order information is pushed to the transportation management system.
The Transportation Management System (TMS), in english acronym, is a (web-based) operating software under the logistics "supply chain" group. The logistics management capacity can be improved by various methods and other related operations; including managing shipping units, specifying shipping plans within an enterprise, domestically, and abroad, managing shipping models, benchmarks, and fees, maintaining shipping data, generating bills of lading, optimizing shipping plans, selecting carriers and service patterns, auditing and paying shipping bills, processing damage claims, scheduling labor and locations, managing documents (particularly during international shipping), and managing third party logistics, among other things. The transportation path planning service can provide a final path with a good optimization effect for workers quickly based on the transportation management system, and the transportation management system can provide basic data for the transportation path planning service.
Based on the system architecture, an embodiment of the present application provides a transportation path planning method flow, as shown in fig. 3, including:
301, receiving a plurality of order information, wherein any order information comprises a transportation starting and stopping station and a transportation requirement; the transportation starting and stopping station comprises a large cabin as a starting point and a front cabin as a terminal point;
step 302, determining an initial path according to the plurality of order information, wherein the initial path comprises each big cabin and each front cabin in the plurality of order information;
here, the initial path may be preliminarily optimized. For example, the calculated initial path is a path with the lowest transportation cost corresponding to the plurality of order information, or the calculated initial path is a path with the highest path accessibility corresponding to the plurality of order information, or a path with the lowest target value obtained by substituting the transportation cost and the path accessibility into the objective function according to the plurality of order information, and the like. The initial path can also be obtained by randomly arranging the order information without preliminary optimization. Here, the manner of acquiring the initial path is not particularly limited.
Step 303, deleting a set number of pre-bins from the initial path through a destruction operator to obtain a destruction path; determining the importance of the deleted pre-bins through a repair operator, sequentially inserting the deleted pre-bins into the optimal position of the damaged path by taking the importance as a selection probability to obtain an updated path, taking the updated path as the initial path if the target value of the updated path is not greater than the target value of the initial path, returning to the step of deleting a set number of pre-bins from the initial path through the damage operator, and circularly performing until a final path is obtained; wherein, the importance is determined by the transportation requirement in the order information corresponding to the front bin; the target value is determined based on the transportation cost of the path.
Here, the importance may be determined according to the transportation requirement information related to the individual volume of the goods, the total volume of the goods, the cold or non-cold fresh goods, the manpower required for transportation acquisition, the loading time, the unloading time, the distance between the front bin and the large bin, and the like in the order information corresponding to the front bin. The importance calculation may be obtained by summing the above items, or may be performed by summing the items after setting corresponding weights, or may calculate the importance corresponding to each item using a special item (e.g., the cold or non-cold fresh corresponds to a different coefficient value, which may be determined based on experience or professional knowledge) as a coefficient. The specific calculation method of the importance is not limited herein.
In one example, the large warehouse is O, there are 5 required front warehouses a, b, c, d, e, the initial path is Oaboced (meaning that the first vehicle starts from the large warehouse O and serves the front warehouse a first and then serves the front warehouse b, the second vehicle starts from the large warehouse O and serves the front warehouse c first and then reaches the front warehouse e and then reaches the front warehouse d. in the process, the receiving time of each front warehouse can be input as the transportation requirement in advance, or not required in advance, after the final path is obtained through subsequent calculation, the receiving time of each front warehouse is given in the final path), the initial path comprises two sub-paths Oced, distribution vehicles are arranged in the large warehouse O according to the transportation requirement of each front warehouse in the two sub-paths, the transportation cost and the importance of each front warehouse can be obtained according to the transportation requirement of each sub-path, and when necessary, the transportation cost and importance of each front warehouse can be obtained according to the type of the transportation requirement of the front warehouse in each sub-path (the information of the front warehouse can comprise the transportation requirement type in the order information of each front warehouse in the sub-path, Obtaining the relevant information of the quantity, the receiving time and the like, and determining the transportation requirement of the front bin and further determining the importance of the front bin and the transportation cost of the path and the front bin based on the information). In the path optimization process, deleting two preposed bins a and d by a destruction operator to generate a destroyed path ObObObObOce, calculating the importance of the two preposed bins a and d, if the importance of a is higher than the importance of d, selecting the preposed bins by taking the importance of the preposed bins as the probability of selecting the preposed bins and selecting the preposed bins by a roulette method, a tournament method or the like. Thus, the higher the importance degree is, the higher the probability that the pre-bin is selected is, if the pre-bin a is selected, the pre-bin a is inserted into the optimal position of the damaged path oboe through the repair operator to obtain oboe (the target value of the transportation cost and the path accessibility corresponding to the oboe path under the objective function is smaller than the target value of the oboe, and oboe path), and then the pre-bin d is inserted into the oboe to obtain the updated path oboe (the target value of the transportation cost and the path accessibility corresponding to the oboe path under the objective function is smaller than the target value of the oboe, and oboe path). And then judging whether the target value of the updated path OaOaOdCE is not larger than the target value of the initial path OaOaOaOaOcSed, if so, updating the updated path OaOaOaOaOaOaOaOaOaOaOaOaOaOaOaOaOaOaOdAs the initial path OaOaOaOaOaOaOaOaOaOaOaOaOaOaOaOaOaOaOaOaObOdE optimized by the next circular path. In addition, the manner of determining whether to update the update path oabdoce with the initial path oabdoced may be a simulated annealing strategy. It should be noted that, this example is only for ease of understanding, and in practice, the number of the big bins and the front bins (in practical application, the number of the big bins and the front bins may be very large), the number and types of the distribution vehicles (the number of the distribution vehicles may be multiple, and vehicles of corresponding types may also be distributed according to the types of the big bins and the front bins.
In the method, a plurality of order information can be received, a final path is determined according to the transportation starting and stopping station and the transportation requirement in the plurality of order information, the importance of the front bin is used as a reference factor for optimizing the initial path, the higher the importance of the front bin is, the larger the transportation requirement-transportation cost occupation is, such as the vehicle volume of the initial path and the vehicle cost, the higher the vehicle volume and the vehicle cost in the initial path are, the front bin with the high importance is used as a relative priority optimization object under a certain vehicle volume and vehicle cost in the initial path, the optimization degree and efficiency are effectively improved, the speed of obtaining the final path can be accelerated in application, and the optimization of obtaining the final path is improved.
In the step 302, determining an initial path according to the plurality of order information includes: determining at least one temporary path according to the plurality of order information based on a mileage-saving method; determining the transportation cost and the route accessibility of each temporary route according to the transportation requirements in the plurality of order information, wherein the route accessibility is determined according to the distance between each front bin in the route, and the closer the distance between each front bin in the route is, the higher the route accessibility is; for each temporary path, substituting the transportation cost and the path reachability of the temporary path into an objective function to obtain a target value of the temporary path; and determining a temporary path with the lowest target value from the at least one temporary path as an initial path.
That is to say, if the randomly obtained initial path is optimized by directly using the destroy operator and the repair operator, the solution space may be of a large scale, and the optimization efficiency is greatly affected. If the final path needs to be obtained within 5min, the optimization effect of the final path obtained at this time may be poor, and the transportation cost is greatly consumed. Therefore, at least one temporary path can be obtained through a mileage-saving method, so that the mileage of the temporary path is in a better solution. Then, the transportation cost (the transportation cost is calculated according to the distance from the big bin to the front bin, the city where the big bin and the front bin are located, the vehicle type distributed to the temporary path, the mileage pricing of the vehicle type and other related information) and the path reach (the path reach of the temporary path is calculated according to the road network data to determine the distance between the big bin and the front bin in the temporary path and the road condition and other related information) of each temporary path in each temporary path are calculated, and the transportation cost of the temporary path is summed with the path reach of the temporary pathAnd substituting the path reachability into an objective function to obtain a target value, and taking the temporary path with the lowest target value in each temporary path as an initial path. Therefore, the solution space scale can be reduced, and when the initial path is optimized by adopting a destroy operator and a repair operator, a better final path can be quickly acquired in less time. For convenience of understanding, a simple example of the objective function is given here, where the objective function is Y ═ a × 1000+ b × 1, a is transportation cost, and b is path reachability, in this example, the objective function is an integration function with transportation cost first and path reachability second, in this example, the sum of transportation costs of all vehicles in the path may be taken as the transportation cost of the path, the sum of distances from a big bin in the path to a previous bin and from the previous bin to a next previous bin may be taken as the path reachability, and it should be noted that the calculation of the example of the objective function, the transportation cost and the path reachability in the objective function, and the like is not limited here, for example, the objective function may be Y ═ a 2 + b, the transportation cost can also be increased, and road condition factors, the number of red street lamps on the path and the like can also be considered in the path reachability.
In the method flow in the optimization step 302 for the transportation path planning method flow, determining the transportation cost of each temporary path according to the transportation requirement in the plurality of order information includes: for any temporary path, determining the distance between each node in the temporary path according to the road network data; each node comprises a large bin and a front bin; allocating vehicles according to the transportation requirements in each order information; and determining the transportation cost of the temporary path according to the unloading time of each front bin, the mileage pricing of the vehicle type of the distributed vehicle, the city mileage pricing of the involved city and the distance between the nodes in the order information. In one example, the navigation distance and time-road network data for all point pairs may be obtained by calling mapping software for truck navigation. And determining the goods receiving time and the goods unloading time of the front bin according to the order information of the front bin. The pricing method of the cost can be obtained according to the mileage pricing of the vehicle type of the distributed vehicle and the city mileage pricing of the involved city. For example, according to the type of vehicle-cold chain, vehicle specification-4.2 meters, pricing means of the cost obtained by the city involved-ladder pricing means: 500 units of [0-100km ], and 700 units of [100-150km ]. The pricing method may further include labor cost, cost generated by unloading duration, and the like, and the transportation cost calculation method and the information specifically applied may be set according to specific requirements, which is not limited herein.
In step 303 of the above method flow, the destruction operator includes a plurality of kinds; before deleting the set number of pre-bins from the initial path by the destroy operator, the method further includes:
in each round of path optimization flow, selecting a damage operator of the round for path optimization by a roulette method;
after the updating path is taken as the initial path, the method further comprises the following steps:
and after the optimization of the path of the current round is finished, updating the score of the damage operator according to the updated path, wherein the score is used for selecting the probability parameter of the damage operator by a subsequent roulette method. That is to say, the damage operators in the transportation path planning method flow may be applied differently in each cycle, before path optimization is performed in each cycle, the damage operators may be optimized first, the score of the damage operator is used as a probability parameter selected by the roulette method, the damage operator is selected as the damage operator for the path optimization in the current cycle, after the path optimization in the current cycle is completed, the damage operator is scored according to the optimization degree of the updated path obtained in the current cycle, the score of the damage operator may be updated according to the scoring, and the updated score of the damage operator is used as the probability parameter for selecting the damage operator in the path optimization flow in the next cycle.
The plurality of destruction operators may include at least one of a first random removal operator, a second random removal operator, a cost removal operator, a path removal operator, and a time removal operator; the first random removal operator is used for randomly removing the front bins in the initial path, the second random removal operator is used for randomly removing the sub-paths in the initial path, the cost removal operator is used for removing the front bins with high transportation service requirements in the initial path, the path removal operator is used for randomly removing part of paths in the sub-paths in the initial path, and the time removal operator is used for removing the front bins with the short transportation time requirements in the initial path. That is, in the transportation path planning process, the algorithm may optimize the algorithm according to the initial path and the updated path obtained by the plurality of order information, so that the destruction operator most suitable for optimizing the path is selected. In one example, when the path characteristics are that each pre-bin needs an equal optimized chance, the algorithm optimization side is opposite to a first random removal operator, the pre-bins in the initial path are randomly removed under the condition that the probability of each pre-bin being removed is equal, and the randomly removed pre-bins are inserted into the optimal positions in the destroyed initial path by using a repair operator to obtain an updated path. When the path characteristics are the opportunity that each sub-path in the path needs to be optimized equally, the algorithm optimization side is opposite to the second random removal operator, the sub-paths in the initial path are removed randomly under the condition that the probability of each sub-path being removed is equal, and the repair operator is used for inserting the randomly removed sub-paths into the optimal positions in the damaged initial path to obtain the updated path. The method can also preferentially remove the front bin with high transport service demand in the initial path by using the cost removal operator according to the demand of improving optimization efficiency, insert the removed front bin with high transport service demand into the damaged optimal position in the initial path by using the repair operator, optimize the front bin with high transport service demand at the fastest speed, and improve the optimization efficiency of the path by maximizing the target value optimization range of the transport cost and the path accessibility of the initial path in the objective function. The partial path optimization can be selected from the removal selection object-sub paths according to the limitation, the optimization efficiency is properly accelerated, partial paths in the sub paths in the initial path are randomly removed by using a path removal operator, and the randomly removed partial sub paths are inserted into the optimal positions in the damaged initial path by using a repair operator to obtain an updated path. And the time removing operator removes the front bin with the short transportation time requirement in the initial path, and the repairing operator inserts the front bin with the short transportation time requirement into the damaged optimal position in the initial path to obtain an updated path. The transportation time requirements between adjacent front-end bins in the obtained updating path can not be too concentrated, and the problems that the unloading of workers is not timely or the transportation is not timely and the like can be effectively prevented. It should be noted that the above-mentioned multiple destruction operators are only an example, and do not limit the kind of the destruction operators applied in the present application, and the present application may be applied to one or more of them, and may also be applied to other destruction operators. For example, the unloading time and receiving time factors can be used as a factor for measuring the importance degree and added into the cost removal operator to obtain the cost-time removal operator.
In step 303 of the above method flow, the repair operator includes a plurality of types, and before determining the importance of the deleted pre-bin by the repair operator, the method further includes:
in each round of path optimization flow, selecting a current round of repair operators for path optimization by a roulette method;
after the updating path is taken as the initial path, the method further comprises the following steps:
and after the optimization of the path of the round is finished, updating the score of the repair operator according to the updating path, wherein the score is used for selecting the probability parameter of the repair operator by a subsequent roulette method. That is to say, the repair operators in the flow of the transportation path planning method may be applied differently in each cycle, before the repair operators are utilized in each cycle for path optimization, the repair operators may be optimized first, the score of the repair operators is used as the probability parameter selected by the roulette method, the repair operators are selected as the repair operators for path optimization in this cycle, after the path optimization in this cycle is completed, the repair operators are scored according to the optimization degree of the updated path obtained in this cycle, the score of the damage operators can be updated according to the scoring, and the updated score of the repair operators is used as the probability parameter selected in the path optimization flow of the next cycle.
In the above transportation path planning method flow, before determining the initial path according to the plurality of order information in step 302, the method further includes: determining that order information with transportation service requirements exceeding a first preset threshold exists in the plurality of order information, splitting the order information exceeding the first preset threshold into at least two pieces of order information, wherein the transportation service requirements of each piece of order information obtained through splitting are lower than the first preset threshold; or determining that order information with the transportation service requirement lower than a second preset threshold exists in the plurality of order information, combining the order information lower than the second preset threshold with one or more other order information into one order information, and enabling the transportation service requirement of the order information obtained through combination to be lower than the first preset threshold. That is to say, in order to ensure the reasonable allocation of the transportation resources, the orders with overlarge transportation service requirements can be split, and the orders with overlarge transportation service requirements can be combined, so as to ensure that the transportation resources have a better utilization rate, and the transportation cost is saved.
Based on the above method flows, the embodiment of the application provides an influence trend chart of the application of the transportation path planning method to the transportation cost, as shown in fig. 4, the average basket cost and the average piece cost are higher in the 1 st, 2 nd and 3 rd weeks before the application of the transportation path planning method, the average basket cost and the average piece cost of the freezing chain in the 4 th to 6 th weeks after the application of the transportation path planning method are obviously reduced, and the average basket cost and the average piece cost of the refrigerating chain in the 7 th to 17 th weeks after the application of the transportation path planning method are also obviously reduced. Therefore, the transportation path planning method can effectively reduce the transportation cost.
Based on the above method flow, an embodiment of the present application provides a transportation path planning method flow, as shown in fig. 5, including:
step 501, receiving a plurality of order information.
Step 502, performing a sheet splitting and/or sheet combining process on the plurality of order information to obtain a plurality of processed order information.
And 503, calculating at least one temporary path of the processed plurality of order information based on the mileage-saving method.
And step 504, calculating the transportation cost and the route reachability of each temporary route, and substituting the transportation cost and the route reachability of each temporary route into an objective function to obtain a target value corresponding to each temporary route.
In step 505, the temporary route having the lowest target value among the temporary routes is set as the initial route.
Step 506, selecting a damage operator for the path optimization of the current round from a plurality of damage operators through a roulette algorithm.
And 507, deleting a set number of pre-bins from the initial path through a destruction operator to obtain a destruction path.
Step 508, calculating the importance of the deleted pre-bin.
Step 509, select a repair operator for the path optimization of the current round from the plurality of repair operators by roulette algorithm.
And 510, by using the importance of the deleted pre-bins as selection probabilities through the repair operators, sequentially inserting the deleted pre-bins into the optimal positions of the damaged paths so as to obtain the updated paths.
Step 511, updating whether the target value of the path is not greater than the target value of the initial path, if yes, executing step 512, and if not, executing step 513.
And step 512, taking the updated path as an initial path.
Step 513, the initial path is not updated.
Step 514, return to step 506, and loop through steps 506 to 512/513 until the final path is obtained.
Here, it should be noted that the condition for setting the loop stop can be realized. For example, the conditions for stopping the circulation and obtaining the final path are not limited, and may be specifically set as required. Step 502 and/or steps 503 to 505 in the above flow may be executed or not, and when step 503 to step 505 are not executed, a path randomly determined according to a plurality of order information may be used as an initial path, that is, the above flow steps are not unique.
Based on the same concept, an embodiment of the present application provides a transportation path planning apparatus, as shown in fig. 6, the apparatus includes:
the receiving and sending module 601 is configured to receive a plurality of pieces of order information, where any piece of order information includes transportation start and stop stations and transportation requirements; the transportation starting and stopping station comprises a large cabin as a starting point and a front cabin as a terminal point;
a processing module 602, configured to determine an initial path according to the plurality of order information, where the initial path includes each big bin and each front bin in the plurality of order information;
the processing module 602 is further configured to delete a set number of pre-bins from the initial path through a destroy operator to obtain a destroy path; determining the importance of the deleted pre-bins through a repair operator, sequentially inserting the deleted pre-bins into the optimal position of the damaged path by taking the importance as a selection probability to obtain an updated path, taking the updated path as the initial path if the target value of the updated path is not greater than the target value of the initial path, returning to the step of deleting a set number of pre-bins from the initial path through the damage operator, and circularly performing until a final path is obtained; wherein, the importance is determined by the transportation requirement in the order information corresponding to the front bin; the target value is determined based on the transportation cost of the path.
Optionally, the processing module 602 is specifically configured to determine at least one temporary path according to the plurality of order information based on a mileage-saving method; determining the transportation cost and the route accessibility of each temporary route according to the transportation requirements in the plurality of order information, wherein the route accessibility is determined according to the distance between each front bin in the route, and the closer the distance between each front bin in the route is, the higher the route accessibility is; for each temporary path, substituting the transportation cost and the path reachability of the temporary path into an objective function to obtain a target value of the temporary path; and determining a temporary path with the lowest target value from the at least one temporary path as an initial path.
Optionally, the processing module 602 is specifically configured to, for any temporary path, determine a distance between each node in the temporary path according to the road network data; each node comprises a large bin and a front bin; allocating vehicles according to the transportation requirements in each order information; and determining the transportation cost of the temporary path according to the unloading time of each front bin, the mileage pricing of the vehicle type of the distributed vehicle, the city mileage pricing of the involved city and the distance between the nodes in the order information.
Optionally, the destroy operator includes a plurality of kinds; the processing module 602 is further configured to, in each round of the path optimization process, select a current round of a destruction operator for path optimization by a roulette method; the processing module 602 is further configured to, after the optimization of the current round of path is finished, update the score of the destructive operator according to the updated path, where the score is used for selecting a probability parameter of the destructive operator in a subsequent roulette method.
Optionally, the destruction operator includes at least one of a first random removal operator, a second random removal operator, a cost removal operator, a path removal operator, and a time removal operator; the first random removal operator is used for randomly removing the front bins in the initial path, the second random removal operator is used for randomly removing the sub-paths in the initial path, the cost removal operator is used for removing the front bins with high transportation service requirements in the initial path, the path removal operator is used for randomly removing part of paths in the sub-paths in the initial path, and the time removal operator is used for removing the front bins with the short transportation time requirements in the initial path.
Optionally, the repair operator includes a plurality of types, and the processing module 602 is further configured to, in each round of the path optimization process, select a round of the repair operator for path optimization by a roulette method; the processing module 602 is further configured to, after the optimization of the current round of path is finished, update the score of the repair operator according to the updated path, where the score is used for selecting a probability parameter of the repair operator in a subsequent roulette method.
Optionally, the processing module 602 is further configured to determine that there is order information in the plurality of order information that transportation service demand exceeds a first preset threshold, split the order information that exceeds the first preset threshold into at least two pieces of order information, where transportation service demand of each piece of order information obtained by splitting is lower than the first preset threshold; or determining that order information with the transportation service requirement lower than a second preset threshold exists in the plurality of order information, combining the order information lower than the second preset threshold with one or more other order information into one order information, and enabling the transportation service requirement of the order information obtained through combination to be lower than the first preset threshold.
As will be appreciated by one skilled in the art, embodiments of the present application may be provided as a method, system, or computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.
The present application is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to the application. It will be understood that each flow and/or block of the flow diagrams and/or block diagrams, and combinations of flows and/or blocks in the flow diagrams and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
It will be apparent to those skilled in the art that various changes and modifications may be made in the present application without departing from the spirit and scope of the application. Thus, if such modifications and variations of the present application fall within the scope of the claims of the present application and their equivalents, the present application is intended to include such modifications and variations as well.

Claims (10)

1. A method of transportation path planning, the method comprising:
receiving a plurality of order information, wherein any order information comprises a transportation starting and stopping station and a transportation requirement; the transportation starting and stopping station comprises a large cabin as a starting point and a front cabin as a terminal point;
determining an initial path according to the plurality of order information, wherein the initial path comprises each big bin and each front bin in the plurality of order information;
deleting a set number of pre-bins from the initial path through a destruction operator to obtain a destruction path; determining the importance of the deleted pre-bins through a repair operator, sequentially inserting the deleted pre-bins into the optimal position of the damaged path by taking the importance as a selection probability to obtain an updated path, taking the updated path as the initial path if the target value of the updated path is not greater than the target value of the initial path, returning to the step of deleting a set number of pre-bins from the initial path through the damage operator, and circularly performing until a final path is obtained; wherein, the importance is determined by the transportation requirement in the order information corresponding to the front bin; the target value is determined based on the transportation cost of the path.
2. The method of claim 1, wherein determining an initial path based on the plurality of order information comprises:
determining at least one temporary path according to the plurality of order information based on a mileage-saving method;
determining the transportation cost and the route accessibility of each temporary route according to the transportation requirements in the plurality of order information, wherein the route accessibility is determined according to the distance between each front bin in the route, and the closer the distance between each front bin in the route is, the higher the route accessibility is;
for each temporary path, substituting the transportation cost and the path reachability of the temporary path into an objective function to obtain a target value of the temporary path;
and determining a temporary path with the lowest target value from the at least one temporary path as an initial path.
3. The method of claim 2, wherein determining a cost of transportation for each temporary route based on the transportation requirements in the plurality of order information comprises:
for any temporary path, determining the distance between each node in the temporary path according to the road network data; each node comprises a large bin and a front bin;
allocating vehicles according to the transportation requirements in each order information;
and determining the transportation cost of the temporary path according to the unloading time of each front bin, the mileage pricing of the vehicle type of the distributed vehicle, the city mileage pricing of the involved city and the distance between the nodes in the order information.
4. The method of claim 1, wherein the destruction operator comprises a plurality; before deleting a set number of pre-bins from the initial path by a destroy operator, the method further comprises:
in each round of path optimization flow, selecting a damage operator of the round for path optimization by a roulette method;
after the updating path is taken as the initial path, the method further comprises the following steps:
and after the optimization of the path of the current round is finished, updating the score of the damage operator according to the updated path, wherein the score is used for selecting the probability parameter of the damage operator by a subsequent roulette method.
5. The method of claim 4, wherein the destruction operator comprises at least one of a first random removal operator, a second random removal operator, a cost removal operator, a path removal operator, and a time removal operator; the first random removal operator is used for randomly removing the front bins in the initial path, the second random removal operator is used for randomly removing the sub-paths in the initial path, the cost removal operator is used for removing the front bins with high transportation service requirements in the initial path, the path removal operator is used for randomly removing part of paths in the sub-paths in the initial path, and the time removal operator is used for removing the front bins with the short transportation time requirements in the initial path.
6. The method of claim 1, wherein the repair operator comprises a plurality of types, and before determining the importance of the deleted pre-bin by the repair operator, further comprising:
in each round of path optimization flow, selecting a current round of repair operators for path optimization by a roulette method;
after the updating path is taken as the initial path, the method further comprises the following steps:
and after the optimization of the path of the round is finished, updating the score of the repair operator according to the updating path, wherein the score is used for selecting the probability parameter of the repair operator by a subsequent roulette method.
7. The method of any of claims 1 to 6, wherein prior to determining an initial path based on the plurality of order information, further comprising:
determining that order information with transportation service requirements exceeding a first preset threshold exists in the plurality of order information, splitting the order information exceeding the first preset threshold into at least two pieces of order information, wherein the transportation service requirements of each piece of order information obtained through splitting are lower than the first preset threshold; or
Determining that order information with the transportation service requirement lower than a second preset threshold exists in the plurality of order information, combining the order information lower than the second preset threshold with one or more other order information into one order information, and enabling the transportation service requirement of the order information obtained through combination to be lower than the first preset threshold.
8. A transportation path planning apparatus, characterized in that the apparatus comprises:
the receiving and sending module is used for receiving a plurality of order information, wherein any order information comprises a transportation starting and stopping station and a transportation requirement; the transportation starting and stopping station comprises a large cabin as a starting point and a front cabin as a terminal point;
the processing module is used for determining an initial path according to the plurality of order information, wherein the initial path comprises each big bin and each front bin in the plurality of order information;
the processing module is further used for deleting a set number of pre-bins from the initial path through a destruction operator to obtain a destruction path; determining the importance of the deleted pre-bins through a repair operator, sequentially inserting the deleted pre-bins into the optimal position of the damaged path by taking the importance as a selection probability to obtain an updated path, taking the updated path as the initial path if the target value of the updated path is not greater than the target value of the initial path, returning to the step of deleting a set number of pre-bins from the initial path through the damage operator, and circularly performing until a final path is obtained; wherein, the importance is determined by the transportation requirement in the order information corresponding to the front bin; the target value is determined based on the transportation cost of the path.
9. A computing device, comprising:
a memory for storing program instructions;
a processor for calling program instructions stored in said memory to perform the method of any of claims 1 to 7 in accordance with the obtained program.
10. A computer-readable non-transitory storage medium including computer-readable instructions which, when read and executed by a computer, cause the computer to perform the method of any one of claims 1 to 7.
CN202210718756.4A 2022-06-23 2022-06-23 Transportation path planning method and device Pending CN115062852A (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202210718756.4A CN115062852A (en) 2022-06-23 2022-06-23 Transportation path planning method and device

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202210718756.4A CN115062852A (en) 2022-06-23 2022-06-23 Transportation path planning method and device

Publications (1)

Publication Number Publication Date
CN115062852A true CN115062852A (en) 2022-09-16

Family

ID=83202835

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202210718756.4A Pending CN115062852A (en) 2022-06-23 2022-06-23 Transportation path planning method and device

Country Status (1)

Country Link
CN (1) CN115062852A (en)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN117707156A (en) * 2023-12-08 2024-03-15 广州力生机器人技术有限公司 Robot collaborative task allocation method and device

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN117707156A (en) * 2023-12-08 2024-03-15 广州力生机器人技术有限公司 Robot collaborative task allocation method and device

Similar Documents

Publication Publication Date Title
CN112053117B (en) Collaborative distribution path planning method and device
CN111091328B (en) Warehouse entry management method and management device
CN111626577B (en) Vehicle scheduling method and device
CN109034481A (en) A kind of vehicle routing problem with time windows modeling and optimization method based on constraint planning
CN111768629B (en) Vehicle scheduling method, device and system
CN111932182A (en) Distribution path planning method and related device
CN113177752B (en) Route planning method and device and server
CN111428902B (en) Method and device for determining transport route
CN115062852A (en) Transportation path planning method and device
CN112418475A (en) Logistics path planning method and device, electronic equipment and storage medium
CN112801484B (en) Material distribution scheduling method and system considering batching errors
KR20110014323A (en) System and method for optimizing management of container resource
CN115619198B (en) Library displacement dynamic programming method, device, electronic equipment and storage medium
CN110097313B (en) Method for acquiring a delivery vehicle path with a time window and a first-in last-out limit
CN112415953B (en) Scheduling method and device of elevator
CN110400111A (en) Article based on automatic driving vehicle sends method, apparatus and system with charge free
CN117808384B (en) Cargo matching method, device, equipment and medium for cargo transport vehicle
CN112633587A (en) Logistics information processing method and device
CN111507662B (en) Method for planning logistics vehicle path
CN113408987A (en) Intelligent logistics distribution and management method
CN116228053A (en) Goods distribution optimization method, device, computer equipment and storage medium
CN113450055B (en) Cargo reduction method, device, equipment and storage medium based on transportation overload
CN115018412B (en) Optimization method and system for cooperative distribution scheme of clustered unmanned aerial vehicle
Kim et al. Integrated food delivery problem considering both single-order and multiple order deliveries
CN114897449B (en) Method, device and equipment for determining maximum completion time of RMFS (message format conversion System)

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