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

WO2021135208A1 - 考虑订单聚合度的配送路径规划方法与系统 - Google Patents

考虑订单聚合度的配送路径规划方法与系统 Download PDF

Info

Publication number
WO2021135208A1
WO2021135208A1 PCT/CN2020/105914 CN2020105914W WO2021135208A1 WO 2021135208 A1 WO2021135208 A1 WO 2021135208A1 CN 2020105914 W CN2020105914 W CN 2020105914W WO 2021135208 A1 WO2021135208 A1 WO 2021135208A1
Authority
WO
WIPO (PCT)
Prior art keywords
distance
path
order
aggregation
operator
Prior art date
Application number
PCT/CN2020/105914
Other languages
English (en)
French (fr)
Inventor
戚成亮
曹晖
尹梦蕤
Original Assignee
苏宁云计算有限公司
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 苏宁云计算有限公司 filed Critical 苏宁云计算有限公司
Priority to CA3166341A priority Critical patent/CA3166341A1/en
Publication of WO2021135208A1 publication Critical patent/WO2021135208A1/zh

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

Definitions

  • the present invention relates to route planning technology, in particular to a distribution route planning method and system considering the degree of order aggregation.
  • the actual problems are mostly multi-objective problems, but how to convert multi-objectives into single-objectives, currently there is no general strategy that can guarantee that the determined weights can cover multiple scenarios and are not affected by multiple objective dimensions.
  • the purpose of the present invention is to provide a distribution route planning method and system considering the degree of order aggregation.
  • the technical solution for achieving the objective of the present invention is: a distribution route planning method considering the degree of order aggregation, including:
  • the shortest total distance and the shortest total aggregation distance are optimized, and the optimal path is updated.
  • the distance between all orders and warehouses refers to the two-way navigation distance, which obtains vehicle travel speeds at different times and on different road sections, and calculates the two-way navigation time between all orders and warehouses.
  • the current path is processed, and the order points that can be rescheduled are removed;
  • the orders in the order set are processed one by one in the order of the arrival time of the request, traversing all vehicles, and finding the car and route with the least insertion cost for the order;
  • the insertion cost is equal to the route cost of the optimal route inserted into the order minus the uninserted route The path cost of the original path before the order;
  • the adaptive large-scale neighborhood search algorithm uses a variety of removal and insertion operators in the search process.
  • the removal operators include random removal operators, worst removal operators, and Shaw removal operators.
  • Insertion operators include random insertion operators, greedy insertion operators, Regret-2 insertion operators, and Regret-3 insertion operators;
  • a roulette method is used to select a set of removal operators and insertion operators in a certain iteration process respectively in the removal operator and the insertion operator.
  • the weight is automatically adjusted during the algorithm process through the data obtained from the previous iterations, and the entire search process is divided into multiple segments. Every 100 iterations constitute a segment, and the operator is updated according to the score of the operator at the end of each segment. At the beginning of each segment, the score of the initialization operator is 0; when each segment is updated, the scores of the removal operator and the insertion operator used increase accordingly; obtain the removal of the next segment according to the following formula
  • the selected weight of the operator and the insertion operator is the selected weight of the operator and the insertion operator:
  • ⁇ g and ⁇ g are the score and use times of the operator g in this segment, and the parameter r is used to control the speed of the weight adjustment strategy for the feedback of the operator's effectiveness.
  • the calculation method of the target fitness value of the new solution aggregation degree is as follows:
  • Step 5.1 select a path in order
  • Step 5.2 Calculate the virtual aggregation center of the path
  • the j-th order coordinate of the i-th car is (x ij , y ij ), and its position is:
  • i 1,2, ..., N
  • j 1,2, ..., M i
  • the first car i calculate an average M i coordinate all orders
  • Step 5.3 Select the order closest to its virtual aggregation center in the path as the actual aggregation center; calculate the Euclidean distance between all orders of the path and the virtual center in turn, and record the shortest order t ⁇ 1, 2, ..., M i ⁇ , remember its position P it as:
  • Step 5.4 The sum of the navigation distances of all orders in the route and their actual aggregation center is used as the aggregation distance;
  • Step 5.5 traverse all paths
  • Step 5.6 Calculate the sum of the aggregation distances of all paths, that is, the total aggregation distance:
  • two objectives are optimized at the same time, which are the shortest total distance S and the shortest total aggregate distance C;
  • ⁇ 1 and ⁇ 2 are two target weight coefficients
  • T new replaces T best ;
  • T new replaces T best with a certain probability.
  • a distribution route planning system that considers the degree of order aggregation, including:
  • Distance acquisition module to acquire the distance between all orders and warehouses
  • the initial path generation module uses the best insertion heuristic algorithm to generate the initial path
  • a feasible path generation module which uses an adaptive large-scale neighborhood search algorithm to generate a new feasible path
  • the optimal path generation module is used to calculate the new solution aggregation degree target fitness value and the new solution total distance target fitness value, while optimizing the shortest total distance and the shortest total aggregation distance to generate the optimal path.
  • the present invention Compared with the prior art, the present invention has significant advantages as follows: (1) The present invention considers the degree of order aggregation, can ensure that the distance between all orders on each path is relatively close, and can increase the total distance, total time, and total cost as much as possible. When there is less possibility, the demand for secondary delivery is fulfilled; (2) The present invention proposes a new weighted single-target strategy based on solution performance increment. This strategy does not need to re-select weights according to different environments, and at the same time, it is not affected by the target. The impact of different quantities and target dimensions can solve the two drawbacks of the common practice of multi-target weighted transfer targets.
  • Figure 1 is an example diagram of a path that does not contain the degree of aggregation.
  • Figure 2 is an example diagram of the generation path with the degree of aggregation.
  • FIG. 3 is a flow chart of the complete technical solution of the present invention.
  • Fig. 4 is a comparison diagram of navigation distance and Euclidean distance of the present invention.
  • Fig. 5 is a flowchart of updating the target fitness of the new disaggregation degree of the present invention.
  • Fig. 6 is a schematic diagram of the path virtual center of the present invention.
  • Fig. 7 is a schematic diagram of the actual center of the path of the present invention.
  • Fig. 8 is a schematic diagram of all path neighborhoods before updating according to the present invention.
  • Fig. 9 is a schematic diagram of all the path neighborhoods of the present invention after being updated.
  • Figure 10 is a schematic diagram of the results of the present invention in a certain area of a certain city.
  • Figure 11 is a schematic diagram of the scheduling results of the original route planning system in a certain area of a certain city.
  • the present invention proposes a new weighted single-target strategy based on the solution performance increment.
  • the strategy does not need to re-select weights according to different environments, and at the same time, is not affected by different target numbers and target dimensions.
  • the strategy includes: Step1, put forward the concept of aggregation distance describing the degree of order aggregation for each route, and use the sum of the aggregation distance of all paths as the total aggregation distance; Step2, optimize the shortest total distance and the shortest total aggregation distance at the same time; Step3, use adaptive The large-scale neighborhood search algorithm generates a new feasible path; Step4, a new type of weighted single-objective strategy based on the increment of solution performance is proposed to update the path; Step5, the logistics business end distributes according to the recommended path of the system.
  • the distribution route planning method includes the following steps:
  • Step 1 The system receives order information
  • Order information includes order latitude and longitude, volume, quality, and required delivery time.
  • Available vehicle information includes vehicle working time constraints, maximum load constraints, and maximum volume constraints.
  • the warehouse information includes the warehouse latitude and longitude.
  • Step 2 Get the navigation distance between all orders and warehouses
  • Step 3 Use the best insertion heuristic algorithm to generate the initial path
  • the Best Insertion Heuristic is a commonly used heuristic algorithm, which is fast and simple. This method processes all orders one by one in chronological order, considers all feasible paths, and finds the path with the least insertion cost for insertion.
  • the current path is processed, and the order points that can be rescheduled are removed.
  • the orders in the order set are processed one by one in the order of the arrival time of the request, and all vehicles are traversed to find the vehicle and route with the least cost for the order.
  • the insertion cost is equal to the path cost of the optimal path to insert the order (satisfying the constraints) minus the path cost of the original path before the order is inserted. If there is no feasible route for all vehicles, the order request is rejected.
  • the order is accepted and inserted by the path.
  • Step 4 Use an adaptive large-scale neighborhood search algorithm to generate a new feasible path
  • the adaptive large-scale neighborhood search algorithm (An adaptive large neighborhood search heuristic, ALNS) evolved from the large-scale neighborhood search algorithm (Large neighborhood search, LNS). In the process of each iteration, LNS first removes some orders from the current solution, then reinserts them to generate a new solution, and continues to iterate according to this process until a specific stopping condition is met.
  • ALNS uses a variety of removal and insertion operators in the search process. The use probability of these operators corresponds to its historical performance, while LNS only uses one removal operator and one insertion operator. .
  • the present invention uses three removal operators, including random removal operator, worst removal operator, and Shaw removal operator. At the same time, it uses random insertion operator, greedy insertion operator, Regret-2 insertion operator, Four kinds of insertion operators, including Regret-3 insertion operator, are used to obtain high-quality feasible solutions.
  • the present invention assigns weights to different operators, and then uses roulette to select the four removal operators and the four removal operators. Insert the operator to make a selection.
  • the core idea is to track the score of each operator during the iteration process.
  • the score measures the performance of the operator. The better the operator, the higher the score.
  • the entire search process is divided into many fragments, and every 100 iterations constitute a fragment, and the weight of the operator is updated according to the score of the operator at the end of each fragment.
  • the score of the initialization operator is 0.
  • the scores of the removal operator and the insertion operator used increase accordingly. According to the formula, the selected weight of each removal operator and insertion operator of the next segment can be obtained.
  • ⁇ g and ⁇ g are the score and use times of the operator g in this segment, and the parameter r is used to control the speed of the weight adjustment strategy for the feedback of the operator's effectiveness.
  • Step 5 Calculate the target fitness value of the new solution aggregation degree
  • Step 5.1 Select a path in order
  • Step 5.2 Calculate the virtual aggregation center of the path
  • the j-th order coordinate of the i-th car is (x ij , y ij ), and its position is:
  • i 1,2, ..., N
  • j 1,2, ..., M i.
  • the first car i calculate an average M i coordinate all orders
  • Step 5.3 Select the order closest to the virtual aggregation center of the path as the actual aggregation center. Calculate the Euclidean distance between all orders of the path and the virtual center in turn, and record the shortest order t ⁇ ⁇ 1,2,..., M i ⁇ , remember its position P it as:
  • Step 5.4 The sum of the navigation distances of all orders in the route and their actual aggregation center is used as the aggregation distance
  • Step 5.6 Calculate the sum of the aggregation distance of all paths, that is, the total aggregation distance
  • Step 5.7 The shortest total aggregation distance is used as the optimization goal
  • the sum of the aggregation distances of all paths is used as the algorithm optimization target, namely
  • Step 6 Calculate the target fitness value of the new solution total distance
  • the driving distance of each path (including the distance to the warehouse) is S i
  • the shortest total distance is used as the algorithm optimization goal, namely
  • Step 7 Calculate the algorithm optimization goal
  • the present invention needs to optimize two targets at the same time, which are the shortest total distance S and the shortest total aggregation distance C.
  • the present invention proposes a new type of weighted single-objective strategy based on solution performance increment.
  • ⁇ 1 ⁇ 2 are two target weight coefficients, and the sum of the two weight coefficients is 1.
  • S best and C best are the sum of all path distances of the current optimal solution and the sum of the aggregation distances of all paths, and S new and C new are the sum of all path distances and the sum of the aggregation distances of all paths of the new solution.
  • This strategy does not need to re-select weights according to different environments, and at the same time, it is not affected by different target numbers and target dimensions.
  • Step 8 Update the optimal path
  • T new replaces T best ;
  • T new replaces T best with a certain probability.
  • Step 9 When the termination conditions are met, the system outputs all paths
  • Step 10 The logistics business end distributes according to the route recommended by the system.
  • the present invention also provides a distribution path planning system, including:
  • Distance acquisition module to acquire the distance between all orders and warehouses
  • the initial path generation module uses the best insertion heuristic algorithm to generate the initial path
  • a feasible path generation module which uses an adaptive large-scale neighborhood search algorithm to generate a new feasible path
  • the optimal path generation module is used to calculate the new solution aggregation degree target fitness value and the new solution total distance target fitness value, while optimizing the shortest total distance and the shortest total aggregation distance to generate the optimal path.
  • the present invention innovatively proposes the degree of aggregation as a path planning goal, defines a corresponding objective function, solves the problem of single-objective and multi-objective vehicle path planning considering the degree of aggregation, and forms a method and system to support distribution operations.
  • the system receives vehicle information, a total of 7 vehicles with different sizes and loading capacities; the system receives order information, a total of 110 orders, there are multiple orders at the same address.
  • the batch of orders are scheduled by the path planning system of the present invention and the original path planning system respectively.
  • the two system distribution diagrams are shown in Figure 10 and Figure 11 respectively.
  • Each point on the path represents the same latitude and longitude. However, there are multiple orders in the same latitude and longitude. Therefore, the number of displayed points is less than 110.
  • the fitness value of each target of the calculation algorithm is 388.8km, which is better than the 405.2km of the original system, and the total distance target of the present invention is increased by 4%; the total aggregation distance is 305km of the present invention, which is better than 461.8km of the original system , The total polymerization distance of the present invention is increased by 34%. Therefore, the system of the present invention can shorten the total distance to a certain extent and shorten the total aggregation distance to a large extent.
  • Non-volatile memory may include read only memory (ROM), programmable ROM (PROM), electrically programmable ROM (EPROM), electrically erasable programmable ROM (EEPROM), or flash memory.
  • Volatile memory may include random access memory (RAM) or external cache memory.
  • RAM is available in many forms, such as static RAM (SRAM), dynamic RAM (DRAM), synchronous DRAM (SDRAM), double data rate SDRAM (DDRSDRAM), enhanced SDRAM (ESDRAM), synchronous chain Channel (Synchlink) DRAM (SLDRAM), memory bus (Rambus) direct RAM (RDRAM), direct memory bus dynamic RAM (DRDRAM), and memory bus dynamic RAM (RDRAM), etc.

Landscapes

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

Abstract

本发明公开了一种考虑订单聚合度的配送路径规划方法与系统，方法包括：提取描述每条路径订单聚合程度的聚合距离，将所有路径的聚合距离之和作为总聚合距离；同时优化总距离最短与总聚合距离最短；使用自适应大规模邻域搜索算法生成新的可行路径；通过基于解性能增量的加权单目标策略更新路径。本发明可以保证每条路径上所有订单之间距离较近，能够在总距离、总时间、总成本增加尽可能少的情况下，完成二次送货的需求，该方法无需根据环境不同重新选择权重，同时，不受目标数量、目标量纲不同的影响，能够解决多目标加权转单目标这一普遍做法的弊端。

Description

考虑订单聚合度的配送路径规划方法与系统 技术领域
本发明涉及路径规划技术，尤其涉及一种考虑订单聚合度的配送路径规划方法与系统。
背景技术
快递配送在整个商品物流环节中处于极其重要的地位。在明确待派订单列表后，由配送专员将操作工单分派给合适的承运商及其车辆的过程。大部分公司的派工和车辆排程环节由人工完成，存在耗时长、错误率高、造成后续拣选和装车环节的等待和总体作业时长上的浪费问题。
目前，部分公司已经采用算法代替人工完成派工与排程。但是，当前路径规划多以总距离最短、总时间最短、总收入成本最低等作为优化目标。而实际应用场景非常复杂，突发事件出现频率高，如某客户不在，配送人员首次达到却无法配送，必须进行二次送货。此时，根据上述目标所规划的最优短路径已不再最优，且总距离、总时间、总成本极有可能大大增加。
同时，实际问题多为多目标问题，但是如何将多目标转为单目标，目前没有一个通用策略能够保证所确定的权重可以覆盖多个场景、且不受多个目标量纲不同影响。
发明内容
本发明的目的在于提供一种考虑订单聚合度的配送路径规划方法与系统。
实现本发明目的的技术方案为：一种考虑订单聚合度的配送路径规划方法，包括：
获取所有订单及仓库之间的距离；
使用最佳插入启发式算法生成初始路径；
使用自适应大规模邻域搜索算法生成新的可行路径；
计算新解聚合度目标适应值和新解总距离目标适应值；
同时优化总距离最短与总聚合距离最短，更新最优路径。
进一步的，所有订单及仓库之间的距离是指双向导航距离，获取不同时间、不同路段的车辆行进速度，计算所有订单及仓库之间的双向导航时间。
进一步的，使用最佳插入启发式算法生成初始路径，具体为：
初始化时对当前路径运行的路径进行处理，除去其中可以被重新安排的订单点；
对订单集合中的订单按照请求到达时间的先后顺序逐一处理，遍历所有车辆，找到其中对于该订单插入成本最小的车与路径；插入成本等于插入该订单的最优路径的路径 成本减去未插入该订单之前原路径的路径成本；
若对所有车辆来说均不存在可行的路径，则拒绝该订单请求；
只有当该订单最佳路径的插入成本小于该订单带来的收益时，接受该订单并以该路径插入。
进一步的，自适应大规模邻域搜索算法在搜索过程中采用多种移除和插入的算子，移除算子包括随机移除算子、最坏移除算子、Shaw移除算子，插入算子包括随机插入算子、贪婪插入算子、Regret-2插入算子、Regret-3插入算子；
通过给不同的算子赋予权重，采用轮盘赌的方式分别在移除算子和插入算子中选择在某次迭代过程中采用的一组移除算子和插入算子。
进一步的，权重在算法过程中通过之前迭代得到的数据进行自动调整，将整个搜索过程分为多个片段，每100次迭代构成一个片段，在每个片段的结尾根据算子的得分更新算子的权重；在每个片段的开始，初始化算子的得分为0；每个片段内更新时，所采用的移除算子和插入算子得分相应增加；根据下式获取下一片段各移除算子、插入算子的被选择权重：
Figure PCTCN2020105914-appb-000001
其中，π g和θ g分别为算子g在本片段中的得分与使用次数，参数r用于控制权重调整策略对于算子有效性反馈的快慢。
进一步的，新解聚合度目标适应值计算方法如下：
步骤5.1、按序选择一条路径
整个路径规划共N辆车，第i辆车负责配送M i个订单，假设选择第i辆车，即第i条路径；
步骤5.2计算该路径的虚拟聚合中心
首先，获取该路径上所有订单地图坐标，第i辆车的第j个订单坐标为(x ij，y ij)，记其位置为：
P ij＝(x ij，y ij)
其中，i＝1，2，…，N，j＝1，2，…，M i；
然后，定义导航距离与欧几里得距离；
记两个位置P j与P k之间的导航距离为G(P j，P k)
记两个位置P j与P k之间的欧几里得距离为E(P j，P k)
最后，将该条路径上所有的坐标平均值作为该路径的虚拟中心；
计算第i辆车所有M i个订单的平均坐标
Figure PCTCN2020105914-appb-000002
称
Figure PCTCN2020105914-appb-000003
为该路径的虚拟中心，记为
Figure PCTCN2020105914-appb-000004
步骤5.3、选择该路径中距离其虚拟聚合中心最近的订单作为实际聚合中心；依次计算该路径的所有订单与虚拟中心的欧几里得距离，并记录距离最短的订单t∈{1，2，…，M i}，记其位置P it为：
Figure PCTCN2020105914-appb-000005
称P it为该路径的实际中心；
步骤5.4、该路径中所有订单与其实际聚合中心的导航距离之和作为其聚合距离；
计算该路径的聚合距离C i，即所有订单与实际中心订单的导航距离之和；因实际中心订单与自身距离为0，因此，取剩余M i-1个订单的平均导航距离，即
Figure PCTCN2020105914-appb-000006
步骤5.5、遍历所有路径
步骤5.6、计算所有路径的聚合距离之和，即总聚合距离：
Figure PCTCN2020105914-appb-000007
进一步的，新解总距离目标适应值的计算方法为：
每条路径行驶距离为S i，所有路径的距离之和，即
Figure PCTCN2020105914-appb-000008
进一步的，基于解性能增量的加权单目标策略，同时优化两个目标，分别为总距离S最短、总聚合距离C最短；
对于一个新解T new，是否能够替换当前最优解T best取决于下式：
Figure PCTCN2020105914-appb-000009
其中，ω 1、ω 2为两个目标权重系数；
若ΔT≤0，T new代替T best；
若ΔT＞0，结合模拟退火，T new以一定概率代替T best。
进一步的，当算法运行到最大迭代次数或者连续未更新代数到达阈值，则算法终止，系统输出最优解的所有路径。
一种考虑订单聚合度的配送路径规划系统，包括：
距离获取模块，获取所有订单及仓库之间的距离；
初始路径生成模块，使用最佳插入启发式算法生成初始路径；
可行路径生成模块，使用自适应大规模邻域搜索算法生成新的可行路径；
最优路径生成模块，用于计算新解聚合度目标适应值和新解总距离目标适应值，同时优化总距离最短与总聚合距离最短，生成最优路径。
本发明与现有技术相比，其显著优点为：(1)本发明考虑订单聚合度，可以保证每条路径上所有订单之间距离较近，能够在总距离、总时间、总成本增加尽可能少的情况下，完成二次送货的需求；(2)本发明提出一种新型的基于解性能增量的加权单目标策略，该策略无需根据环境不同重新选择权重，同时，不受目标数量、目标量纲不同的影响，能够解决多目标加权转单目标这一普遍做法的两个弊端。
附图说明
图1为不含聚合度生成路径示例图。
图2为含聚合度生成路径示例图。
图3为本发明的完整技术方案流程图。
图4为本发明的导航距离与欧几里得距离对比图。
图5为本发明的新解聚合度目标适应值更新流程图。
图6为本发明的路径虚拟中心示意图。
图7为本发明的路径实际中心示意图。
图8为本发明的所有路径邻域更新前示意图。
图9为本发明的所有路径邻域更新后示意图。
图10为某城市某区域本发明结果示意图。
图11为某城市某区域原路径规划系统排程结果示意图。
具体实施方式
目前，已有公司采用算法代替人工完成派工与排程。但是，当前路径规划多以总距离、总时间、总成本为优化目标。而实际应用场景非常复杂，突发事件出现频率高，如某客户不在，配送人员首次达到却无法配送，必须进行二次送货。此时，根据上述目标 所规划的最优短路径已不再“最优”，且总距离、总时间、总成本极有可能大大增加。如图1所示，1个仓库(矩形)、12个订单(圆形)、2条路径，其中一条路径订单记为P 11～P 16，配送顺序P 11→P 16。若P 11需要二次送货，则必须进行长距离折返。
因此，如果可以保证每条路径上所有订单之间距离较近，则可避免上述问题。如图2所示，所有图像信息同图1，2条路径所有订单聚合度较好，任一订单需要二次送货，仅需进行短距离折返即可。
另外，若将多目标加权生成单目标，通常做法为，直接将各个目标加权求和。但是，该做法存在很大的风险，即应用场景不同，所确定的权重需要重新选择。
基于上述问题，本发明提出一种新型的基于解性能增量的加权单目标策略，该策略无需根据环境不同重新选择权重，同时，不受目标数量、目标量纲不同影响。该策略包括：Step1，提出描述每条路径订单聚合程度的聚合距离概念，将所有路径的聚合距离之和作为总聚合距离；Step2，同时优化总距离最短与总聚合距离最短；Step3，使用自适应大规模邻域搜索算法生成新的可行路径；Step4，提出一种新型的基于解性能增量的加权单目标策略，用于更新路径；Step5，物流业务端根据系统推荐路径进行配送。
下面对本发明考虑订单聚合度的配送路径规划方法的具体步骤进行详细说明。
如图3所示，该配送路径规划方法包括如下步骤：
步骤1：系统接收订单信息
明确待派订单列表，将订单信息、可用车辆信息、仓库信息输入系统，订单信息包括订单经纬度、体积、质量、要求配送时间，可用车辆信息包括车辆工作时间约束、最大载重约束、最大容积约束，仓库信息包括仓库经纬度。
步骤2：获取所有订单及仓库之间的导航距离
通过专用软件，获取所有订单及仓库之间的双向导航距离；通过历史经验积累的配送速度预测系统，获取不同时间、不同路段的车辆行进速度，从而计算所有订单及仓库之间的双向导航时间。
现实环境中存在河流、铁路等特殊情况，两点间的导航距离远远大于欧几里得距离，如图4，因此，本发明中所有订单及仓库之间的距离均采用导航距离。
步骤3：使用最佳插入启发式算法生成初始路径
最佳插入启发式算法(Best insertion heuristic,BIS)是一种常用的启发式算法，快速简单。该方法对所有订单按照时间先后顺序逐一进行处理，考虑了所有可行的路径并找到其中插入成本最小的路径进行插入。
初始化时对当前路径运行的路径进行处理，除去其中可以被重新安排的订单点。之后对订单集合中的订单按照请求到达时间的先后顺序逐一处理，遍历所有车辆，找到其中对于该订单插入成本最小的车与路径。插入成本等于插入该订单的最优路径(满足各项约束)的路径成本减去未插入该订单之前原路径的路径成本。若对所有车辆来说均不存在可行的路径，则拒绝该订单请求。最后，在本发明中只有当该订单最佳路径的插入成本小于该订单带来的收益时，接受该订单并以该路径插入。
步骤4：使用自适应大规模邻域搜索算法生成新的可行路径
自适应大规模邻域搜索算法(An adaptive large neighborhood search heuristic,ALNS)由大规模邻域搜索算法(Large neighborhood search,LNS)演变而来。LNS在每次迭代的过程中首先从当前解中移除某些订单，随后将他们重新插入生成一个新的解，按此过程不断迭代直到满足特定的停止条件。ALNS算法的不同之处主要在于ALNS在搜索过程中采用多种移除和插入的算子，这些算子的使用概率与其历史表现相对应，而LNS只采用一个移除算子和一个插入算子。
本发明使用了随机移除算子、最坏移除算子、Shaw移除算子等3种移除算子，同时使用了随机插入算子、贪婪插入算子、Regret-2插入算子、Regret-3插入算子等4种插入算子，以获得高质量的可行解。
为了选择在某次迭代过程中采用的一组移除算子和插入算子，本发明通过给不同的算子赋予权重，然后采用轮盘赌的方式分别在四种移除算子和四种插入算子中进行选择。
权重在算法过程中如何通过之前迭代得到的数据进行自动调整，核心思想为跟踪每个算子在迭代过程中的得分，该得分衡量该算子的表现，算子的表现越好得分越高。
将整个搜索过程分为许多片段，每100次迭代构成一个片段，在每个片段的结尾根据算子的得分更新算子的权重。在每个片段的开始，初始化算子的得分为0。每个片段内更新时，所采用的移除算子和插入算子得分相应增加。根据公式，可获取下一片段各移除算子、插入算子的被选择权重。
Figure PCTCN2020105914-appb-000010
其中，π g和θ g分别为算子g在本片段中的得分与使用次数，参数r用于控制权重调整策略对于算子有效性反馈的快慢。
步骤5：计算新解聚合度目标适应值
聚合度目标适应值更新流程图如图5所示，包括以下步骤：
步骤5.1按序选择一条路径
整个路径规划共N辆车，第i辆车负责配送M i个订单，假设选择第i辆车，即第i条路径
步骤5.2计算该路径的虚拟聚合中心
首先，获取该路径上所有订单地图坐标，第i辆车的第j个订单坐标为(x ij，y ij)，记其位置为：
P ij＝(x ij，y ij)
其中，i＝1，2，…，N，j＝1，2，…，M i。
然后，定义导航距离与欧几里得距离。
记两个位置P j与P k之间的导航距离为G(P j，P k)
记两个位置P j与P k之间的欧几里得距离为E(P j，P k)，则
Figure PCTCN2020105914-appb-000011
最后，将该条路径上所有的坐标平均值作为该路径的虚拟中心。
计算第i辆车所有M i个订单的平均坐标
Figure PCTCN2020105914-appb-000012
称
Figure PCTCN2020105914-appb-000013
为该路径的虚拟中心，如图6，记
Figure PCTCN2020105914-appb-000014
步骤5.3选择该路径中距离其虚拟聚合中心最近的订单作为实际聚合中心依次计算该路径的所有订单与虚拟中心的欧几里得距离，并记录距离最短的订单t∈{1，2，…，M i}，记其位置P it为：
Figure PCTCN2020105914-appb-000015
称P it为该路径的实际中心，如图7。
步骤5.4该路径中所有订单与其实际聚合中心的导航距离之和作为其聚合距离
计算该路径的聚合距离C i，即所有订单与实际中心订单的导航距离之和。因实际中心订单与自身距离为0，因此，取剩余M i-1个订单的平均导航距离代替之，即
Figure PCTCN2020105914-appb-000016
步骤5.5遍历所有路径
步骤5.6计算所有路径的聚合距离之和，即总聚合距离；
所有路径的聚合距离之和，即
Figure PCTCN2020105914-appb-000017
步骤5.7总聚合距离最短作为优化目标
所有路径的聚合距离之和作为算法优化目标，即
minC
步骤6：计算新解总距离目标适应值
每条路径行驶距离(含返回仓库距离)为S i
所有路径的距离之和，即
Figure PCTCN2020105914-appb-000018
总距离最短作为算法优化目标，即
minS
步骤7：计算算法优化目标
本发明需要同时优化两个目标，分别为总距离S最短、总聚合距离C最短。
通常而言，若将多目标加权生成单目标，直接在各个目标前增加相应的权重。如ω 1S+ω 2C。但是，该做法存在很大的风险，即应用场景不同、所确定的权重需要重新选择。
因此，本发明提出一种新型的基于解性能增量的加权单目标策略。
对于一个新解T new，是否能够替换当前最优解T best取决于下式：
Figure PCTCN2020105914-appb-000019
其中，ω 1～ω 2为两个目标权重系数，两个权重系数相加为1。S best、C best为当前最优解的所有路径距离之和、所有路径的聚合距离之和，S new、C new为新解的所有路径距离之和、所有路径的聚合距离之和。
该策略无需根据环境不同重新选择权重，同时，不受目标数量、目标量纲不同的影响。
步骤8：最优路径更新
若ΔT≤0，T new代替T best；
若ΔT＞0，结合模拟退火，T new以一定概率代替T best。
以总聚合距离为例，解的更新过程如图8、图9所示，更新后的路径更加合理。
步骤9：满足终止条件，系统输出所有路径
当算法运行到最大迭代次数或者连续未更新代数到达阈值，则算法终止，系统输出最优解的所有路径。
步骤10：物流业务端根据系统推荐路径进行配送。
基于上述考虑订单聚合度的配送路径规划方法，本发明还提供一种配送路径规划系统，包括：
距离获取模块，获取所有订单及仓库之间的距离；
初始路径生成模块，使用最佳插入启发式算法生成初始路径；
可行路径生成模块，使用自适应大规模邻域搜索算法生成新的可行路径；
最优路径生成模块，用于计算新解聚合度目标适应值和新解总距离目标适应值，同时优化总距离最短与总聚合距离最短，生成最优路径。
本发明创新性地提出聚合度作为路径规划目标，定义了相应的目标函数，解决了考虑聚合度的单目标及多目标车辆路径规划问题，形成方法和系统支持配送作业。创新性的提出一种新型的基于解性能增量的加权单目标策略，形成通用型多目标转单目标方法。
下面结合实施例和附图对本发明作进一步说明。
实施例
以某城市某区域大件家电配送为例：系统接收车辆信息，共7辆车且大小、装载能力不同；系统接收订单信息，共110单，存在同一地址多个订单的情况。
为便于对比，该批订单分别由本发明路径规划系统与原路径规划系统进行排程。两个系统配送示意图分别如图10、图11所示，其中，路径上每一个点表示一个相同经纬度，但是，存在同一经纬度中含有多个订单情况，因此，所展示出来的点数小于110个。
计算算法各目标适应值：总距离，本发明为388.8km，优于原系统的405.2km，本发明的总距离目标提升4％；总聚合距离，本发明为305km，优于原系统的461.8km，本发明总聚合距离目标提升34％。所以，本发明系统可以在一定程度上缩短总距离，很大程度上缩短总聚合距离。
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引 用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。易失性存储器可包括随机存取存储器(RAM)或者外部高速缓冲存储器。作为说明而非局限，RAM以多种形式可得，诸如静态RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双数据率SDRAM(DDRSDRAM)、增强型SDRAM(ESDRAM)、同步链路(Synchlink)DRAM(SLDRAM)、存储器总线(Rambus)直接RAM(RDRAM)、直接存储器总线动态RAM(DRDRAM)、以及存储器总线动态RAM(RDRAM)等。
以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。
以上所述实施例仅表达了本申请的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本申请构思的前提下，还可以做出若干变形和改进，这些都属于本申请的保护范围。因此，本申请专利的保护范围应以所附权利要求为准。

Claims (10)

  1. 一种考虑订单聚合度的配送路径规划方法，其特征在于，包括：
    获取所有订单及仓库之间的距离；
    使用最佳插入启发式算法生成初始路径；
    使用自适应大规模邻域搜索算法生成新的可行路径；
    计算新解聚合度目标适应值和新解总距离目标适应值；
    同时优化总距离最短与总聚合距离最短，更新最优路径。
  2. 根据权利要求1所述的考虑订单聚合度的配送路径规划方法，其特征在于，所有订单及仓库之间的距离是指双向导航距离，获取不同时间、不同路段的车辆行进速度，计算所有订单及仓库之间的双向导航时间。
  3. 根据权利要求1所述的考虑订单聚合度的配送路径规划方法，其特征在于，使用最佳插入启发式算法生成初始路径，具体为：
    初始化时对当前路径运行的路径进行处理，除去其中可以被重新安排的订单点；
    对订单集合中的订单按照请求到达时间的先后顺序逐一处理，遍历所有车辆，找到其中对于该订单插入成本最小的车与路径；插入成本等于插入该订单的最优路径的路径成本减去未插入该订单之前原路径的路径成本；
    若对所有车辆来说均不存在可行的路径，则拒绝该订单请求；
    只有当该订单最佳路径的插入成本小于该订单带来的收益时，接受该订单并以该路径插入。
  4. 根据权利要求1所述的考虑订单聚合度的配送路径规划方法，其特征在于，自适应大规模邻域搜索算法在搜索过程中采用多种移除和插入的算子，移除算子包括随机移除算子、最坏移除算子、Shaw移除算子，插入算子包括随机插入算子、贪婪插入算子、Regret-2插入算子、Regret-3插入算子；
    通过给不同的算子赋予权重，采用轮盘赌的方式分别在移除算子和插入算子中选择在某次迭代过程中采用的一组移除算子和插入算子。
  5. 根据权利要求4所述的考虑订单聚合度的配送路径规划方法，其特征在于，权重在算法过程中通过之前迭代得到的数据进行自动调整，将整个搜索过程分为多个片段，每100次迭代构成一个片段，在每个片段的结尾根据算子的得分更新算子的权重；在每个片段的开始，初始化算子的得分为0；每个片段内更新时，所采用的移除算子和插入算子得分相应增加；根据下式获取下一片段各移除算子、插入算子的被选择权重：
    Figure PCTCN2020105914-appb-100001
    其中，π g和θ g分别为算子g在本片段中的得分与使用次数，参数r用于控制权重调整策略对于算子有效性反馈的快慢。
  6. 根据权利要求1所述的考虑订单聚合度的配送路径规划方法，其特征在于，新解聚合度目标适应值计算方法如下：
    步骤5.1、按序选择一条路径
    整个路径规划共N辆车，第i辆车负责配送M i个订单，假设选择第i辆车，即第i条路径；
    步骤5.2计算该路径的虚拟聚合中心
    首先，获取该路径上所有订单地图坐标，第i辆车的第j个订单坐标为(x ij，y ij)，记其位置为：
    P ij＝(x ij，y ij)
    其中，i＝1，2，…，N，j＝1，2，…，M i；
    然后，定义导航距离与欧几里得距离；
    记两个位置P j与P k之间的导航距离为G(P j，P k)
    记两个位置P j与P k之间的欧几里得距离为E(P j，P k)
    最后，将该条路径上所有的坐标平均值作为该路径的虚拟中心；
    计算第i辆车所有M i个订单的平均坐标
    Figure PCTCN2020105914-appb-100002
    称
    Figure PCTCN2020105914-appb-100003
    为该路径的虚拟中心，记为
    Figure PCTCN2020105914-appb-100004
    步骤5.3、选择该路径中距离其虚拟聚合中心最近的订单作为实际聚合中心；
    依次计算该路径的所有订单与虚拟中心的欧几里得距离，并记录距离最短的订单t∈{1，2，…，M i}，记其位置P it为：
    Figure PCTCN2020105914-appb-100005
    称P it为该路径的实际中心；
    步骤5.4、该路径中所有订单与其实际聚合中心的导航距离之和作为其聚合距离；
    计算该路径的聚合距离C i，即所有订单与实际中心订单的导航距离之和；因实际中心订单与自身距离为0，因此，取剩余M i-1个订单的平均导航距离，即
    Figure PCTCN2020105914-appb-100006
    步骤5.5、遍历所有路径
    步骤5.6、计算所有路径的聚合距离之和，即总聚合距离：
    Figure PCTCN2020105914-appb-100007
  7. 根据权利要求1所述的考虑订单聚合度的配送路径规划方法，其特征在于，新解总距离目标适应值的计算方法为：
    每条路径行驶距离为S i，所有路径的距离之和，即
    Figure PCTCN2020105914-appb-100008
  8. 根据权利要求1所述的考虑订单聚合度的配送路径规划方法，其特征在于，基于解性能增量的加权单目标策略，同时优化两个目标，分别为总距离S最短、总聚合距离C最短；
    对于一个新解T new，是否能够替换当前最优解T best取决于下式：
    Figure PCTCN2020105914-appb-100009
    其中，ω ω、ω 2为两个目标权重系数；
    若ΔT≤0，T new代替T best；
    若ΔT＞0，结合模拟退火，T new以一定概率代替T best。
  9. 根据权利要求8所述的考虑订单聚合度的配送路径规划方法，其特征在于，当算法运行到最大迭代次数或者连续未更新代数到达阈值，则算法终止，系统输出最优解的所有路径。
  10. 一种基于权利要求1-9任意一项所述考虑订单聚合度的配送路径规划方法的系统，其特征在于，包括：
    距离获取模块，获取所有订单及仓库之间的距离；
    初始路径生成模块，使用最佳插入启发式算法生成初始路径；
    可行路径生成模块，使用自适应大规模邻域搜索算法生成新的可行路径；
    最优路径生成模块，用于计算新解聚合度目标适应值和新解总距离目标适应值，同时优化总距离最短与总聚合距离最短，生成最优路径。
PCT/CN2020/105914 2019-12-31 2020-07-30 考虑订单聚合度的配送路径规划方法与系统 WO2021135208A1 (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CA3166341A CA3166341A1 (en) 2019-12-31 2020-07-30 Delivery path planning method and system taking order aggregation degree into consideration

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN201911425008.1 2019-12-31
CN201911425008.1A CN111191847B (zh) 2019-12-31 2019-12-31 考虑订单聚合度的配送路径规划方法与系统

Publications (1)

Publication Number Publication Date
WO2021135208A1 true WO2021135208A1 (zh) 2021-07-08

Family

ID=70710698

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2020/105914 WO2021135208A1 (zh) 2019-12-31 2020-07-30 考虑订单聚合度的配送路径规划方法与系统

Country Status (3)

Country Link
CN (1) CN111191847B (zh)
CA (1) CA3166341A1 (zh)
WO (1) WO2021135208A1 (zh)

Cited By (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN113780745A (zh) * 2021-08-16 2021-12-10 华中科技大学 一种上门服务需求驱动的it人员调度方法和系统
CN113935528A (zh) * 2021-10-13 2022-01-14 广州市钱大妈农产品有限公司 智能调度方法、装置、计算机设备及存储介质
CN114021883A (zh) * 2021-09-28 2022-02-08 淮阴工学院 一种高峰时期地铁接驳共享单车的调度方法
CN115081788A (zh) * 2022-03-21 2022-09-20 上海圆徕科技有限公司 一种物流调度方法
CN116341781A (zh) * 2023-03-28 2023-06-27 暨南大学 基于大规模邻域搜索算法的路径规划方法及存储介质
CN116523433A (zh) * 2023-07-03 2023-08-01 常州唯实智能物联创新中心有限公司 基于双向动态边权重的四向车调度方法及系统
CN117273592A (zh) * 2023-11-22 2023-12-22 成都运荔枝科技有限公司 一种物流场景下的门店配送方法
CN117288206A (zh) * 2023-11-23 2023-12-26 四川国蓝中天环境科技集团有限公司 一种基于自适应大邻域搜索的无人机路线规划方法
CN117455199A (zh) * 2023-12-21 2024-01-26 聊城大学 基于变邻域搜索算法求解矩阵制造车间agv调度的方法
CN117556967A (zh) * 2024-01-11 2024-02-13 宁波安得智联科技有限公司 调度方法、装置、设备及存储介质
CN117592898A (zh) * 2023-12-14 2024-02-23 南京航空航天大学 一种汽车零部件入厂物流同步循环取货方法及系统
CN117933869A (zh) * 2024-03-21 2024-04-26 中国科学技术大学 一种基于机器学习的考虑司机异质性的路径规划方法
CN113657790B (zh) * 2021-08-24 2024-05-24 北京百度网讯科技有限公司 配送路径确定方法、装置、电子设备及可读存储介质

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111798067B (zh) * 2020-07-17 2021-06-25 大连理工大学 基于自适应大邻域搜索算法的自动驾驶汽车配送路径规划方法
CN112013829B (zh) * 2020-08-12 2023-05-26 西安工业大学 基于多目标优化的多uav/ugv协同长时作业路径规划方法
CN113469471A (zh) * 2021-09-02 2021-10-01 北京邮电大学 聚类方法、运输车辆路径规划方法、电子设备及存储介质
CN115130858B (zh) * 2022-06-27 2024-01-26 上海聚水潭网络科技有限公司 一种基于多目标启发式的订单聚合方法及系统
CN116136990B (zh) * 2023-04-04 2024-03-05 中国石油大学(华东) 一种考虑三维装箱问题的车辆路径规划方法

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20130159206A1 (en) * 2011-12-14 2013-06-20 International Business Machines Corporation Dynamic vehicle routing in multi-stage distribution networks
CN103413209A (zh) * 2013-07-17 2013-11-27 西南交通大学 多客户多仓库物流配送路径选择方法
CN104616070A (zh) * 2015-01-15 2015-05-13 北京农业信息技术研究中心 一种物流配送路径规划方法及装置
CN108268959A (zh) * 2016-12-30 2018-07-10 广东精点数据科技股份有限公司 基于主次种群蚁群算法的物流配送路径规划方法
CN109389239A (zh) * 2017-08-14 2019-02-26 顺丰科技有限公司 一种随机路径摧毁重建方法、系统、设备

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
AU2003900776A0 (en) * 2003-02-20 2003-03-13 Eis Pathfinder Pty Ltd Executive information reporting system and method
MY159347A (en) * 2007-04-27 2016-12-30 Deutsche Post Ag Method and system for facilitating shipping
CN108596469B (zh) * 2018-04-19 2021-11-30 中南大学 一种面向大规模车辆路径问题的快速自适应大规模邻域搜索方法
CN108985597B (zh) * 2018-06-29 2021-11-19 华南理工大学 一种动态物流调度方法
CN109978447A (zh) * 2019-03-06 2019-07-05 北京三快在线科技有限公司 一种物流配送线路规划方法和装置
CN110530388B (zh) * 2019-09-05 2021-08-27 苏宁云计算有限公司 多agv的路径规划方法及系统

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20130159206A1 (en) * 2011-12-14 2013-06-20 International Business Machines Corporation Dynamic vehicle routing in multi-stage distribution networks
CN103413209A (zh) * 2013-07-17 2013-11-27 西南交通大学 多客户多仓库物流配送路径选择方法
CN104616070A (zh) * 2015-01-15 2015-05-13 北京农业信息技术研究中心 一种物流配送路径规划方法及装置
CN108268959A (zh) * 2016-12-30 2018-07-10 广东精点数据科技股份有限公司 基于主次种群蚁群算法的物流配送路径规划方法
CN109389239A (zh) * 2017-08-14 2019-02-26 顺丰科技有限公司 一种随机路径摧毁重建方法、系统、设备

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
CHEN SHIFENG: "Research on Dynamic Vehicle Routing Problems:Modeling and Optimization Algorithms", DALIAN MARITIME UNIVERSITY DOCTORAL DISSERTATIONS, 1 June 2018 (2018-06-01), XP055826759 *

Cited By (22)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN113780745B (zh) * 2021-08-16 2024-05-14 华中科技大学 一种上门服务需求驱动的it人员调度方法和系统
CN113780745A (zh) * 2021-08-16 2021-12-10 华中科技大学 一种上门服务需求驱动的it人员调度方法和系统
CN113657790B (zh) * 2021-08-24 2024-05-24 北京百度网讯科技有限公司 配送路径确定方法、装置、电子设备及可读存储介质
CN114021883A (zh) * 2021-09-28 2022-02-08 淮阴工学院 一种高峰时期地铁接驳共享单车的调度方法
CN113935528A (zh) * 2021-10-13 2022-01-14 广州市钱大妈农产品有限公司 智能调度方法、装置、计算机设备及存储介质
CN113935528B (zh) * 2021-10-13 2023-07-21 广州市钱大妈信息科技有限公司 智能调度方法、装置、计算机设备及存储介质
CN115081788A (zh) * 2022-03-21 2022-09-20 上海圆徕科技有限公司 一种物流调度方法
CN116341781B (zh) * 2023-03-28 2024-07-23 暨南大学 基于大规模邻域搜索算法的路径规划方法及存储介质
CN116341781A (zh) * 2023-03-28 2023-06-27 暨南大学 基于大规模邻域搜索算法的路径规划方法及存储介质
CN116523433A (zh) * 2023-07-03 2023-08-01 常州唯实智能物联创新中心有限公司 基于双向动态边权重的四向车调度方法及系统
CN116523433B (zh) * 2023-07-03 2023-09-01 常州唯实智能物联创新中心有限公司 基于双向动态边权重的四向车调度方法及系统
CN117273592A (zh) * 2023-11-22 2023-12-22 成都运荔枝科技有限公司 一种物流场景下的门店配送方法
CN117273592B (zh) * 2023-11-22 2024-01-26 成都运荔枝科技有限公司 一种物流场景下的门店配送方法
CN117288206B (zh) * 2023-11-23 2024-02-02 四川国蓝中天环境科技集团有限公司 一种基于自适应大邻域搜索的无人机路线规划方法
CN117288206A (zh) * 2023-11-23 2023-12-26 四川国蓝中天环境科技集团有限公司 一种基于自适应大邻域搜索的无人机路线规划方法
CN117592898B (zh) * 2023-12-14 2024-09-17 南京航空航天大学 一种汽车零部件入厂物流同步循环取货方法及系统
CN117592898A (zh) * 2023-12-14 2024-02-23 南京航空航天大学 一种汽车零部件入厂物流同步循环取货方法及系统
CN117455199A (zh) * 2023-12-21 2024-01-26 聊城大学 基于变邻域搜索算法求解矩阵制造车间agv调度的方法
CN117455199B (zh) * 2023-12-21 2024-03-22 聊城大学 基于变邻域搜索算法求解矩阵制造车间agv调度的方法
CN117556967B (zh) * 2024-01-11 2024-05-03 宁波安得智联科技有限公司 调度方法、装置、设备及存储介质
CN117556967A (zh) * 2024-01-11 2024-02-13 宁波安得智联科技有限公司 调度方法、装置、设备及存储介质
CN117933869A (zh) * 2024-03-21 2024-04-26 中国科学技术大学 一种基于机器学习的考虑司机异质性的路径规划方法

Also Published As

Publication number Publication date
CN111191847A (zh) 2020-05-22
CA3166341A1 (en) 2021-08-07
CN111191847B (zh) 2022-10-14

Similar Documents

Publication Publication Date Title
WO2021135208A1 (zh) 考虑订单聚合度的配送路径规划方法与系统
CN113692609B (zh) 通过订单车辆分布匹配以订单派发的多代理增强学习
Li-ying et al. Multiple charging station location-routing problem with time window of electric vehicle.
Cheung et al. Dynamic routing model and solution methods for fleet management with mobile technologies
Cordeau et al. Simulation-based optimization for housekeeping in a container transshipment terminal
Wang et al. Towards delivery-as-a-service: Effective neighborhood search strategies for integrated delivery optimization of E-commerce and static O2O parcels
CN107909228B (zh) 基于模因计算的动态车辆收发货路径规划方法及装置
CN109934405A (zh) 基于模拟退火算法的有时限的多车型多车次路径规划方法
CN114444809A (zh) 一种数据驱动下的多目标露天矿卡路径优化方法
CN111208815A (zh) 将多个搬运任务分配至多个自动搬运车的方法及相关装置
Alaia et al. Optimization of the multi-depot & multi-vehicle pickup and delivery problem with time windows using genetic algorithm
Liang et al. Online crowdsourced delivery for urban parcels using private cars under time-dependent travel times
Sze et al. An adaptive variable neighbourhood search approach for the dynamic vehicle routing problem
CN109635998B (zh) 一种求解带时间窗车辆路径问题的自适应多目标优化方法
Kim et al. Two-echelon collaborative routing problem with heterogeneous crowd-shippers
CN114037380A (zh) 一种取送货问题的车辆路径规划方法
Niroomand et al. Vehicle routing with time window for regional network services—Practical modelling approach
CN113408906A (zh) 一种高速列车停站与客流分配的联合优化方法
CN112016750A (zh) 一种改进的解决带约束车辆路径问题的方法
CN112488358A (zh) 一种电动汽车充电路径规划方法和存储介质
Narayanan et al. A Reinforcement Learning Approach for Electric Vehicle Routing Problem with Vehicle-to-Grid Supply
Phiboonbanakit et al. Knowledge-based learning for solving vehicle routing problem
CN115755953A (zh) 基于综合赋权的无人机任务规划方法、系统及存储介质
CN114492999A (zh) 一种考虑随机需求与时间窗的电动车辆配送路线生成方法
Li et al. An integrated route planning approach for driverless vehicle delivery system

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 20908802

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 3166341

Country of ref document: CA

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 20908802

Country of ref document: EP

Kind code of ref document: A1