CN115062852A - 一种运输路径规划方法及装置 - Google Patents

Abstract

本申请实施例提供一种运输路径规划方法及装置，包括：接收多个订单信息，订单信息中包括运输起止站及运输要求；确定包含多个订单信息中的大仓和前置仓的初始路径；破坏算子从初始路径中删除设定数量的前置仓，得到破坏路径；修复算子确定删除前置仓的重要度，以重要度作为选取概率，依次将删除前置仓插入破坏路径最优位置得到更新路径，若其目标值不大于初始路径的目标值，将更新路径作为初始路径，返回通过破坏算子从初始路径中删除设定数量前置仓的步骤，循环直至得到最终路径；重要度是以前置仓对应的订单信息中的运输要求确定的；目标值是根据所在路径的运输成本确定的。用于实现全自动化的运输路径规划，且提高运输路径优化强度和效率。

Description

一种运输路径规划方法及装置

技术领域

本申请涉及计算机技术领域，尤其涉及一种运输路径规划方法及装置。

背景技术

随着计算机设备的不断发展，电子商务也在逐渐发展中。在电子商务业务中，人们通过线上或线下下单，由运输人员从仓库中配货将物品运输至运输目的地。该过程中，仓库存储物品的补充也极为重要。

现有技术中，仓库一般分为大仓和前置仓，由大仓向各前置仓补充存储货物。其中，可以通过运输管理系统(缩写为：TMS)提供操作页面，以使得工作人员可以在操作页面选择运输工具、大仓和前置仓，运输管理系统根据选择的运输工具、大仓和前置仓得出较优的运输路径。但是该种方式在大量订单场景下，人工操作极为耗时耗力，且得到的运输路径优化强度不够，对运输成本仍然存在一定的浪费。

现在亟需一种运输路径规划方法及装置，用于实现全自动化的运输路径规划，且提高运输路径优化强度，提高运输路径优化效率。

发明内容

本申请实施例提供一种运输路径规划方法及装置，用于实现全自动化的运输路径规划，且提高运输路径优化强度，提高运输路径优化效率。

第一方面，本申请实施例提供一种运输路径规划方法，该方法包括：

接收多个订单信息，任一订单信息中包括运输起止站及运输要求；所述运输起止站包括作为起点的大仓和作为终点的前置仓；

根据所述多个订单信息确定初始路径，所述初始路径中包含所述多个订单信息中的各大仓和各前置仓；

通过破坏算子从所述初始路径中删除设定数量的前置仓，得到破坏路径；通过修复算子确定删除的前置仓的重要度，以重要度作为选取概率，依次将所述删除的前置仓插入所述破坏路径的最优位置从而得到更新路径，若所述更新路径的目标值不大于所述初始路径的目标值，则将所述更新路径作为所述初始路径，返回通过破坏算子从所述初始路径中删除设定数量的前置仓的步骤，循环进行直至得到最终路径；其中，重要度是以前置仓对应的订单信息中的运输要求确定的；目标值是根据所在路径的运输成本确定的。

上述方法中，可以接收多个订单信息，根据多个订单信息中的运输起止站和运输要求确定最终路径，该过程中将前置仓的重要度作为初始路径优化的一个参考因素，前置仓的重要度越高，对初始路径的车辆容积和车辆所耗成本等运输要求-运输成本占用越大，在初始路径中一定的车辆容积和车辆所耗成本下，将重要度高的前置仓作为相对优先优化对象，有效提高优化程度和效率，在应用中可以加快获取最终路径的速度，提高获取最终路径的优化性。

可选的，根据所述多个订单信息确定初始路径，包括：

基于节约里程法，根据所述多个订单信息确定至少一个临时路径；

根据所述多个订单信息中的运输要求确定各临时路径的运输成本和路径可达度，所述路径可达度是根据路径中的各前置仓间距离确定的，路径中的各前置仓间距离越近路径可达度越高；

针对每个临时路径，将所述临时路径的运输成本和路径可达度代入目标函数，得到所述临时路径的目标值；

从所述至少一个临时路径中确定出目标值最低的临时路径作为初始路径。

上述方法中，在通过破坏算子和修复算子对初始路径进行优化之前，基于节约里程算法，计算多个订单信息中的各前置仓和大仓之间的距离关系确定路径较短的多个临时路径，再计算这多个临时路径中各临时路径的运输成本和路径可达度代入目标函数获取各临时路径的目标值，将目标值最低的临时路径作为初始路径。如此，使得初始路径已经是一个做完简单优化的结果，这里的简单优化可以加快后续根据修复算子和破坏算子优化的效率，且使得获得的最终路径优化效果更好，也就是使得最后得到的最后路径的运输成本低，大仓、前置仓之间的路径的路径可达度更高，便于货物运输。

可选的，根据所述多个订单信息中的运输要求确定各临时路径的运输成本，包括：

针对任一临时路径，根据路网数据确定所述临时路径中各节点之间的距离；所述各节点包括大仓与前置仓；

根据所述各订单信息中的运输要求分配车辆；

根据所述各订单信息中各前置仓的卸货时长、分配车辆的车辆类型的里程计价、所涉城市的城市里程计价、所述各节点之间的距离确定所述临时路径的运输成本。

上述方法中，根据路网数据可以准确计算临时路径中各节点的距离。根据各订单信息的运输要求分配车辆。如，可以根据货物类型、货物量等信息为订单分配车辆，保证满足各订单信息的运输要求。再根据各订单信息分别对应车辆的车辆类型的里程计价、所涉城市的城市里程计价、卸货时长和各节点之间的距离确定临时路径的运输成本。如此，综合多方面因素获得的临时路径的运输成本准确性高。

可选的，所述破坏算子包括多种；所述通过破坏算子从所述初始路径中删除设定数量的前置仓之前，还包括：

在每轮路径优化流程中，以轮盘赌方法选择本轮用于路径优化的破坏算子；

将所述更新路径作为所述初始路径之后，还包括：

在本轮路径优化结束后，根据所述更新路径更新所述破坏算子的分值，所述分值用于后续轮盘赌方法选择破坏算子的概率参数。

上述方法中，在初始路径的优化过程中，针对用于路径优化的破坏算子有多种，可以通过轮盘赌的方式选择破坏算子用于路径优化，在路径优化完成后，根据初始路径优化得到的最终路径确定破坏算子的优化效果，以对该破坏算子进行计算分值，将该破坏算子的分值作为后续轮盘赌选择该破坏算子的概率参数。如此，对路径优化效果好的破坏算子的分值高，对应的被轮盘赌方法选中的概率高，对路径优化效果差的破坏算子的分值低，对应的被轮盘赌方法选中的概率低，在路径优化过程中不止对初始路径进行优化，还在优化初始路径的优化算法，提高优化效率。

可选的，所述破坏算子包括第一随机移除算子、第二随机移除算子、成本移除算子、路径移除算子和时间移除算子中的至少一种；其中，第一随机移除算子用于随机移除所述初始路径中的前置仓，第二随机移除算子用于随机移除所述初始路径中的子路径，成本移除算子用于移除所述初始路径中运输服务需求高的前置仓，路径移除算子用于随机移除所述初始路径中子路径中的部分路径，时间移除算子用于移除所述初始路径中运输时间要求近的前置仓。

上述方法中，第一随机移除算子用于随机移除初始路径中的前置仓，利用修复算子将该随机移除的前置仓插入被破坏的初始路径中最优位置(如，可以是该随机移除的前置仓插入被破坏的初始路径中最优位置得到的更新路径的运输成本和路径可达度代入目标函数中得到的目标值最低)得到更新路径。也就是说，第一随机移除算子的优点在于针对初始路径中的每个前置仓被移除的概率相等，初始路径中的各前置仓都有被优化的机会。第二随机移除算子用于移除初始路径中的子路径，利用修复算子将该随机移除的子路径插入被破坏的初始路径中最优位置(如，可以是该随机移除的子路径插入被破坏的初始路径中最优位置得到的更新路径的运输成本和路径可达度代入目标函数中得到的目标值最低)得到更新路径。也就是说，第二随机移除算子的优点在于针对初始路径中的每个子路径被移除的概率相等，在路径优化过程中，以完整的子路径为移除单位，初始路径中的各子路径都有被优化的机会。成本移除算子用于移除初始路径中运输服务需求高的前置仓，利用修复算子将该移除的运输服务需求高的前置仓插入被破坏的初始路径中最优位置，可以将运输服务需求高的前置仓最快优化，对于初始路径的运输成本和路径可达度在目标函数中的目标值优化幅度最大，提高路径优化效率。路径移除算子用于随机移除初始路径中子路径中的部分路径，利用修复算子将该随机移除的部分子路径插入被破坏的初始路径中最优位置得到更新路径。也就是说，路径随机移除算子的优点在于以完整的子路径为移除选择对象，从移除选择对象-子路径中选择部分路径优化，适当加快优化效率。时间移除算子用于移除初始路径中运输时间要求近的前置仓，利用修复算子将该运输时间要求近的前置仓插入被破坏的初始路径中最优位置得到更新路径。使得获得的更新路径中的相邻前置仓之间的运输时间要求不会过于集中，可以有效防止工作人员卸货不及时或运输不及时等问题。

可选的，修复算子包括多种，通过修复算子确定删除的前置仓的重要度之前，还包括：

在每轮路径优化流程中，以轮盘赌方法选择本轮用于路径优化的修复算子；

将所述更新路径作为所述初始路径之后，还包括：

在本轮路径优化结束后，根据所述更新路径更新所述修复算子的分值，所述分值用于后续轮盘赌方法选择修复算子的概率参数。

上述方法中，在初始路径的优化过程中，针对用于路径优化的修复算子有多种，可以通过轮盘赌的方式选择修复算子用于路径优化，在路径优化完成后，根据初始路径优化得到的最终路径确定修复算子的优化效果，以对该修复算子进行计算分值，将该修复算子的分值作为后续轮盘赌选择该修复算子的概率参数。如此，对路径优化效果好的修复算子的分值高，对应的被轮盘赌方法选中的概率高，对路径优化效果差的修复算子的分值低，对应的被轮盘赌方法选中的概率低，在路径优化过程中不止对初始路径进行优化，还在优化初始路径的优化算法，提高优化效率。

可选的，根据所述多个订单信息确定初始路径之前，还包括：

确定所述多个订单信息中存在运输服务需求超过第一预设阈值的订单信息，将所述超过第一预设阈值的订单信息拆分为至少两个订单信息，拆分得到的各订单信息的运输服务需求均低于所述第一预设阈值；或

确定所述多个订单信息中存在运输服务需求低于第二预设阈值的订单信息，将所述低于第二预设阈值的订单信息与另外一个或多个订单信息合单为一个订单信息，合单得到的订单信息的运输服务需求均低于所述第一预设阈值。

上述方法中，若订单信息中的运输服务需求超过第一预设阈值，则当前单独的订单的运输服务能力不能较好的支持该订单信息，需要将该订单信息拆分为至少两个订单信息，使得得到的每个订单信息符合提供的运输服务能力。例如，运输服务需求可以包含运输人力、车辆运输需求等相关信息，当单个订单信息中的运输服务需求中的运输人力、车辆容积等要求高出每个订单信息分配的运输服务需求上限-第一预设阈值，则可能造成运输车辆和运输人力的调度不周的问题，拆单方案可以有效防止这种情况发生。相应的，若多个订单信息中存在运输服务需求低于第二预设阈值的订单信息，则可能发生运输资源浪费。如，订单信息中的运输服务需求低于第二预设阈值，则为每个订单信息配置的运输服务能力(运输人力、车辆容积)存在闲置现象，浪费运输资源。将低于第二预设阈值的订单信息合单为一个订单信息，可以有效防止发生这种运输资源浪费。

第二方面，本申请实施例提供一种运输路径规划装置，该装置包括：

收发模块，用于接收多个订单信息，任一订单信息中包括运输起止站及运输要求；所述运输起止站包括作为起点的大仓和作为终点的前置仓；

处理模块，用于根据所述多个订单信息确定初始路径，所述初始路径中包含所述多个订单信息中的各大仓和各前置仓；

所述处理模块还用于，通过破坏算子从所述初始路径中删除设定数量的前置仓，得到破坏路径；通过修复算子确定删除的前置仓的重要度，以重要度作为选取概率，依次将所述删除的前置仓插入所述破坏路径的最优位置从而得到更新路径，若所述更新路径的目标值不大于所述初始路径的目标值，则将所述更新路径作为所述初始路径，返回通过破坏算子从所述初始路径中删除设定数量的前置仓的步骤，循环进行直至得到最终路径；其中，重要度是以前置仓对应的订单信息中的运输要求确定的；目标值是根据所在路径的运输成本确定的。

第三方面，本申请实施例还提供一种计算设备，包括：存储器，用于存储程序；处理器，用于调用所述存储器中存储的程序，按照获得的程序执行如第一方面的各种可能的设计中所述的方法。

第四方面，本申请实施例还提供一种计算机可读非易失性存储介质，包括计算机可读程序，当计算机读取并执行所述计算机可读程序时，使得计算机执行如第一方面的各种可能的设计中所述的方法。

本申请的这些实现方式或其他实现方式在以下实施例的描述中会更加简明易懂。

附图说明

为了更清楚地说明本申请实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简要介绍，显而易见地，下面描述中的附图仅仅是本申请的一些实施例，对于本领域的普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本申请实施例提供的一种运输路径规划的架构示意图；

图2为本申请实施例提供的一种运输路径规划的架构示意图；

图3为本申请实施例提供的一种运输路径规划方法的流程示意图；

图4为本申请实施例提供的一种应用运输路径规划方法对运输成本的影响趋势图；

图5为本申请实施例提供的一种运输路径规划方法的流程示意图；

图6为本申请实施例提供的一种运输路径规划装置示意图。

具体实施方式

为了使本申请的目的、技术方案和优点更加清楚，下面将结合附图对本申请作进一步地详细描述，显然，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其它实施例，都属于本申请保护的范围。

图1为本申请实施例提供的一种运输路径规划服务的系统架构，该运输路径规划服务中包括：基础数据模块、初步优化模块和优化模块。当运输路径规划系统接收多个订单信息后，根据基础数据模块中的基础数据、初步优化模块中的初步优化算法得到初始路径，将初始路径传输到优化模块，根据优化模块中的算法和基础数据模块中的基础数据得到最终路径输出。

具体的，基础数据模块中包含的基础数据可以包括运输成本计价方式、运输参数、路网数据、车辆资源、可选择性开启算法等相关基础数据。

初步优化模块用于基于节约里程法，根据运输路径规划服务接收的多个订单信息(订单信息中包括运输起止站及运输要求，运输起止站包括作为起点的大仓和作为终点的前置仓)，若确定该多个订单信息中存在运输服务需求超过第一预设阈值的订单信息，基于可选择性开启算法中的拆单算法将超过第一预设阈值的订单信息拆分为至少两个订单信息，拆分得到的各订单信息的运输服务需求均低于所述第一预设阈值；或若确定该多个订单信息中存在运输服务需求低于第二预设阈值的订单信息，基于可选择性开启算法中的拆单算法将低于第二预设阈值的订单信息与另外一个或多个订单信息合单为一个订单信息，合单得到的订单信息的运输服务需求均低于所述第一预设阈值。如此，得到多个订单信息，根据这多个订单信息确定至少一个临时路径。进一步，根据该多个订单信息中的运输要求确定各临时路径的运输成本和路径可达度(根据订单信息中的运输需求和基础数据模块中的基础数据计算得到对应临时路径的运输成本和路径可达度)。路径可达度是根据路径中的各前置仓间距离(前置仓之间的距离可以根据路网数据确定)确定的，路径中的各前置仓间距离越近路径可达度越高，理解性的，路径可达度可以理解为运输路径的便利度。如，前置仓之间运输距离比较近、前置仓之间的路段在对应运输时段的路况较好等要求。之后，再针对每个临时路径，将临时路径的运输成本和路径可达度代入目标函数，得到该临时路径的目标值。从至少一个临时路径中确定出目标值最低的临时路径作为初始路径，将该初始路径传输至优化模块。

优化模块中包括多种破坏算子。如，用于随机移除该初始路径中的前置仓的第一随机移除算子、用于随机移除该初始路径中的子路径的第二随机移除算子、用于移除该初始路径中运输服务需求高的前置仓的成本移除算子、用于随机移除该初始路径中子路径中的部分路径的路径移除算子和用于移除该初始路径中运输时间要求近的前置仓的时间移除算子。还包括多种修复算子。如，用于将破坏算子移除的前置仓，或移除的子路径，或移除的子路径的部分路径插入破坏路径的最优位置，以使得获取的更新路径的路径可达度最大。以及用于将破坏算子移除的前置仓，或移除的子路径，或移除的子路径的部分路径插入破坏路径的最优位置，以使得获取的更新路径的目标值最低(将破坏算子移除的前置仓，或移除的子路径，或移除的子路径的部分路径插入破坏路径的各位置，对应得到的路径的运输成本和路径可达度代入目标函数，将得到的目标值中最低的目标值对应的路径作为更新路径)。如此，优化模块基于其破坏算子和修复算子，以及破坏算子的分值和修复算子的分值，通过轮盘赌方法分别选择破坏算子和修复算子。通过选择的破坏算子从该初始路径中删除设定数量的前置仓，得到破坏路径。通过选择的修复算子确定删除的前置仓的重要度，以重要度作为选取概率，依次将该删除的前置仓插入破坏路径的最优位置从而得到更新路径，若更新路径的目标值不大于初始路径的目标值，则将该更新路径作为初始路径；若更新路径的目标值大于初始路径的目标值，则不对初始路径进行更新。根据更新路径的优化效果对选择的破坏算子和修复算子设置分值，以便于后续优化中，作为轮盘赌方法选择破坏算子和修复算子的概率参照。返回通过轮盘赌方法分别选择破坏算子和修复算子的步骤，循环进行直至得到最终路径；其中，重要度是以前置仓对应的订单信息中的运输要求确定的；目标值是根据所在路径的运输成本确定的。如此，根据重要度将破坏算子删除的前置仓插入到破坏路径中，优先运输要求高的前置仓插入路径，使得该循环的路径优化中，路径优化效果最大(便于理解的，若将重要度比较小的前置仓优先插入破坏路径的最佳位置，此时得到的路径的目标值优化程度小，重要度比较小的前置仓会抢占重要度比较大的前置仓的最优位置，影响优化效率。若将重要度比较大的前置仓插入破坏路径的最佳位置，此时得到的路径的目标值优化程度大，重要度比较大的前置仓抢占重要度比较小的前置仓的最优位置，使得优化效果最大化，优化效率可以显著提升)。且在该路径优化过程中，通过轮盘赌方法，以及根据更新路径对破坏算子、修复算子设置分值的方式优化算法，令每一循环的路径优化算法都比上一循环的路径优化算法的优化效率高，进一步提高路径优化效率。

基于上述运输路径规划服务，本申请实施例还提供了一种运输路径规划的系统架构，如图2所示，该运输路径规划系统中包括仓储管理系统、运输管理系统、和如上述图1中所示的运输路径规划服务。其中，运输管理系统中可以安装该运输路径规划服务以提供路径优化功能，或者运输管理系统可以通过调用的方法实现提供路径优化功能，这里对运输管理系统如何通过运输路径规划服务提供路径优化功能的方式具体不做限制。

仓储管理系统(WMS)以仓库作业技术的整合为主要目标，使库存成为流水线的一个流动环节，使流水线成为库存操作的一个组成部分，可以根据前置仓和大仓等仓库的仓储属性和仓储需求的相关信息生成订单信息，将订单信息推送至运输管理系统。

运输管理系统(英文缩写“TMS”)，是一种物流“供应链”分组下的(基于网络的)操作软件。它能通过多种方法和其他相关的操作一起提高物流的管理能力；包括管理装运单位，指定企业内、国内和国外的发货计划，管理运输模型、基准和费用，维护运输数据，生成提单，优化运输计划，选择承运人及服务方式，审计和支付货运账单，处理货损索赔，安排劳力和场所，管理文件(尤其当国际运输时)和管理第三方物流等等。本申请中运输路径规划服务可以基于该运输管理系统为工作人员快速提供优化效果好的最终路径，运输管理系统可以为运输路径规划服务提供基础数据。

基于上述系统架构，本申请实施例提供了一种运输路径规划方法流程，如图3所示，包括：

步骤301、接收多个订单信息，任一订单信息中包括运输起止站及运输要求；所述运输起止站包括作为起点的大仓和作为终点的前置仓；

步骤302、根据所述多个订单信息确定初始路径，所述初始路径中包含所述多个订单信息中的各大仓和各前置仓；

此处，初始路径可以是经过初步优化的。如，计算的初始路径是多个订单信息对应的运输成本最低的路径，或计算的初始路径是多个订单信息对应的路径可达度最高的路径，或根据多个订单信息计算过运输成本和路径可达度代入目标函数得到的目标值最低的路径等等。初始路径也可以是未经过初步优化的，根据各订单信息随机排列获得的。这里对初始路径的获取方式具体不做限制。

步骤303、通过破坏算子从所述初始路径中删除设定数量的前置仓，得到破坏路径；通过修复算子确定删除的前置仓的重要度，以重要度作为选取概率，依次将所述删除的前置仓插入所述破坏路径的最优位置从而得到更新路径，若所述更新路径的目标值不大于所述初始路径的目标值，则将所述更新路径作为所述初始路径，返回通过破坏算子从所述初始路径中删除设定数量的前置仓的步骤，循环进行直至得到最终路径；其中，重要度是以前置仓对应的订单信息中的运输要求确定的；目标值是根据所在路径的运输成本确定的。

此处，重要度可以是根据前置仓对应的订单信息中的货物单个体积、货物总体体积、冷鲜或非冷鲜、搬运获取所需人力、装货时长、卸货时长、前置仓离大仓的距离等等相关运输要求信息确定的。重要度计算可以根据前述各项得加和得到，还可以对各项设置对应权重后计算加和，还可以将特殊项(如，冷鲜或非冷鲜对应不同的系数值，系数值可以根据经验或专业知识确定)作为系数计算各项对应的重要度。这里对重要度的具体计算方法不做限制。

在一种示例中，大仓为O,现有5个有需求的前置仓，分别为a、b、c、d、e,初始路径为OabOced(OabOced:表示意义为第一辆车从大仓O出发，先服务前置仓a再服务前置仓b；第二辆车从大仓O出发，先服务前置仓c再到前置仓e再到前置仓d。该过程中，各前置仓的收货时间可以预先作为运输要求输入，也可以预先不做要求，后续计算得到最终路径后，在最终路径中给出各前置仓的收货时间)，初始路径中包含两个子路径Oab、Oced，根据两个子路径中各前置仓的运输要求，在大仓O为两个子路径设置分配车辆，在需要时，可以根据每个子路径中的前置仓的运输要求获得其运输成本和重要度(前置仓对应的订单信息中可以包括其运输的货物类型、获取量、收货时间等等相关信息，基于这些信息可以确定前置仓的运输要求，进而确定前置仓的重要度，以及路径、前置仓的运输成本)等信息。路径优化过程中，通过破坏算子删除a、d两个前置仓，产生破坏路径ObOce，计算a、d两个前置仓的重要度，若a的重要度高于d的重要度，以前置仓的重要度作为选取前置仓的概率，通过轮盘赌方法或锦标赛等方式选取前置仓。如此，重要度越高，前置仓被选中的概率越大，假如选中前置仓a，通过修复算子将前置仓a插入破坏路径ObOce的最优位置(OabOce路径对应的运输成本和路径可达度在目标函数下得到的目标值小于ObaOce、ObOace、ObOcae、ObOcea路径的目标值)得到OabOce，再将前置仓d插入OabOce得到更新路径OabOdce(OabOdce路径对应的运输成本和路径可达度在目标函数下得到的目标值小于OdabOce、OadbOce、OabdOce、OabOdce、OabOcde、OabOced路径的目标值)。之后，判断更新路径OabOdce的目标值是否不大于初始路径OabOced的目标值，若是，则将更新路径OabOdce更新初始路径OabOced，作为下一循环路径优化的初始路径OabOdce。另外，需要说明的是，这里判断是否将更新路径OabOdce更新初始路径OabOced的方式可以为模拟退火策略。需要说明的是，本示例只是为了便于理解，实际上并不对大仓和前置仓的数量(实际应用中大仓和前置仓的数量可以很大)、分配车辆数量和类型(分配车辆的数量可以是多个，还可以根据大仓和前置仓的类型分配对应类型的车辆。如，大仓和前置仓为冷链对应的仓库，可以为其分配对应冷链的车辆运输)、大仓和前置仓的运输成本及重要度的计算方式、破坏算子破坏初始路径的方式、修复算子修复破坏路径的方式等做限制。

上述方法中，可以接收多个订单信息，根据多个订单信息中的运输起止站和运输要求确定最终路径，该过程中将前置仓的重要度作为初始路径优化的一个参考因素，前置仓的重要度越高，对初始路径的车辆容积和车辆所耗成本等运输要求-运输成本占用越大，在初始路径中一定的车辆容积和车辆所耗成本下，将重要度高的前置仓作为相对优先优化对象，有效提高优化程度和效率，在应用中可以加快获取最终路径的速度，提高获取最终路径的优化性。

在上述步骤302中，根据所述多个订单信息确定初始路径，包括：基于节约里程法，根据所述多个订单信息确定至少一个临时路径；根据所述多个订单信息中的运输要求确定各临时路径的运输成本和路径可达度，所述路径可达度是根据路径中的各前置仓间距离确定的，路径中的各前置仓间距离越近路径可达度越高；针对每个临时路径，将所述临时路径的运输成本和路径可达度代入目标函数，得到所述临时路径的目标值；从所述至少一个临时路径中确定出目标值最低的临时路径作为初始路径。

也就是说，若直接采用破坏算子和修复算子对随机获取的初始路径进行优化，则可能会出现解空间规模巨大的情况，对优化效率影响较大。若需要在5min内获取最终路径，可能此时得到的最终路径的优化效果比较差，较大的耗费运输成本。由此可以通过节约里程法得到至少一个临时路径，使得该临时路径的里程处于一个较优解。之后，计算各临时路径中每个临时路径的运输成本(根据大仓至前置仓的距离、大仓和前置仓所在的城市、为临时路径分配的车辆类型、车辆类型的里程计价等相关信息计算运输成本)和路径可达度(根据路网数据确定临时路径中大仓与前置仓之间的距离、路况等相关信息计算临时路径的路径可达度)，将该临时路径的运输成本和路径可达度代入目标函数得到目标值，将各临时路径中目标值最低的临时路径作为初始路径。如此，可以将解空间规模缩小，在采用破坏算子和修复算子对该初始路径进行优化时，可以花费更少的时间快速获取更优的最终路径。为了便于理解，这里对目标函数做简单示例，目标函数为Y＝a*1000+b*1，a是运输成本、b是路径可达度，在本示例中，目标函数是运输成本优先，路径可达度其次的集成函数，该示例中可以将路径中所有车辆的运输成本之和作为路径的运输成本，将路径中大仓到达前置仓，还可以包括该前置仓到达下一前置仓的距离之和作为路径可达度，需要说明的是，这里对目标函数的示例、目标函数中的运输成本和路径可达度等的计算都是不做限制的，如，目标函数可以是Y＝a²+b等等，运输成本中还可以增加人力成本，路径可达度中还可以考虑路况因素、路径的红路灯数量等。

在上述针对运输路径规划方法流程的优化步骤302中的方法流程中，根据所述多个订单信息中的运输要求确定各临时路径的运输成本，包括：针对任一临时路径，根据路网数据确定所述临时路径中各节点之间的距离；所述各节点包括大仓与前置仓；根据所述各订单信息中的运输要求分配车辆；根据所述各订单信息中各前置仓的卸货时长、分配车辆的车辆类型的里程计价、所涉城市的城市里程计价、所述各节点之间的距离确定所述临时路径的运输成本。在一种示例中，可以通过调用地图软件货车导航得到的所有点对的导航距离及时间-路网数据。根据前置仓的订单信息确定前置仓的收货时间和卸货时间。可以根据分配车辆的车辆类型的里程计价、所涉城市的城市里程计价得到成本的计价方式。如，根据车辆类型-冷链，车辆规格-4.2米，所涉城市得到的成本的计价方式-阶梯定价方式：[0-100km]500元，[100-150km]700元。其中计价方式还可以包括人工费用，卸货时长产生的费用等等，运输成本计算方式和具体应用到的信息可以根据具体需求设置，这里具体不做限制。

在上述方法流程的步骤303中，所述破坏算子包括多种；所述通过破坏算子从所述初始路径中删除设定数量的前置仓之前，还包括：

在每轮路径优化流程中，以轮盘赌方法选择本轮用于路径优化的破坏算子；

将所述更新路径作为所述初始路径之后，还包括：

在本轮路径优化结束后，根据所述更新路径更新所述破坏算子的分值，所述分值用于后续轮盘赌方法选择破坏算子的概率参数。也就是说，上述运输路径规划方法流程中的破坏算子在每循环中的应用可以不同，每循环进行路径优化前，可以先对破坏算子进行优化，以破坏算子的分值的为轮盘赌方法选择的概率参数，选择破坏算子作为本轮路径优化的破坏算子，在本轮路径优化结束后，根据本轮得到的更新路径的优化程度对破坏算子打分，可以根据打分更新破坏算子的分值，将更新后的该破坏算子的分值作为下一循环的路径优化流程中，选择破坏算子的概率参数。

上述多种破坏算子可以包括第一随机移除算子、第二随机移除算子、成本移除算子、路径移除算子和时间移除算子中的至少一种；其中，第一随机移除算子用于随机移除所述初始路径中的前置仓，第二随机移除算子用于随机移除所述初始路径中的子路径，成本移除算子用于移除所述初始路径中运输服务需求高的前置仓，路径移除算子用于随机移除所述初始路径中子路径中的部分路径，时间移除算子用于移除所述初始路径中运输时间要求近的前置仓。也就是说，在运输路径规划过程中，算法可以根据多个订单信息得到的初始路径和更新路径的，优化算法，使得选择出最适合用于优化路径的破坏算子。在一种示例中，当路径特征为各前置仓需要同等被优化的机会时，算法优化侧向于第一随机移除算子，以每个前置仓被移除的概率相等条件，随机移除初始路径中的前置仓，利用修复算子将该随机移除的前置仓插入被破坏的初始路径中最优位置得到更新路径。当路径特征为路径中各子路径需要同等被优化的机会时，算法优化侧向于第二随机移除算子，以每个子路径被移除的概率相等条件，随机移除初始路径中的子路径，利用修复算子将该随机移除的子路径插入被破坏的初始路径中最优位置得到更新路径。还可以根据提高优化效率的需求，使用成本移除算子优先移除初始路径中运输服务需求高的前置仓，利用修复算子将该移除的运输服务需求高的前置仓插入被破坏的初始路径中最优位置，可以将运输服务需求高的前置仓最快优化，对于初始路径的运输成本和路径可达度在目标函数中的目标值优化幅度最大，提高路径优化效率。可以根据限定从移除选择对象-子路径中选择部分路径优化，适当加快优化效率，使用路径移除算子随机移除初始路径中子路径中的部分路径，利用修复算子将该随机移除的部分子路径插入被破坏的初始路径中最优位置得到更新路径。还可以根据卸货时间，收货时间等因素做参考，时间移除算子移除初始路径中运输时间要求近的前置仓，利用修复算子将该运输时间要求近的前置仓插入被破坏的初始路径中最优位置得到更新路径。使得获得的更新路径中的相邻前置仓之间的运输时间要求不会过于集中，可以有效防止工作人员卸货不及时或运输不及时等问题。需要说明的是，上述多种破坏算子只是一种示例，并不对本申请应用的破坏算子种类做限制，本申请方案可以应用到其中的一个或多个，还可以应用到其它破坏算子。如，还可以将卸货时间，收货时间因素作为衡量重要度的一个因子加入成本移除算子，得到成本-时间移除算子。

在上述方法流程的步骤303中，修复算子包括多种，通过修复算子确定删除的前置仓的重要度之前，还包括：

在每轮路径优化流程中，以轮盘赌方法选择本轮用于路径优化的修复算子；

将所述更新路径作为所述初始路径之后，还包括：

在本轮路径优化结束后，根据所述更新路径更新所述修复算子的分值，所述分值用于后续轮盘赌方法选择修复算子的概率参数。也就是说，上述运输路径规划方法流程中的修复算子在每循环中的应用可以不同，每循环利用修复算子进行路径优化前，可以先对修复算子进行优化，以修复算子的分值的为轮盘赌方法选择的概率参数，选择修复算子作为本轮路径优化的修复算子，在本轮路径优化结束后，根据本轮得到的更新路径的优化程度对修复算子打分，可以根据打分更新破坏算子的分值，将更新后的该修复算子的分值作为下一循环的路径优化流程中，选择修复算子的概率参数。

在上述运输路径规划方法流程中，在步骤302、根据所述多个订单信息确定初始路径之前，还包括：确定所述多个订单信息中存在运输服务需求超过第一预设阈值的订单信息，将所述超过第一预设阈值的订单信息拆分为至少两个订单信息，拆分得到的各订单信息的运输服务需求均低于所述第一预设阈值；或确定所述多个订单信息中存在运输服务需求低于第二预设阈值的订单信息，将所述低于第二预设阈值的订单信息与另外一个或多个订单信息合单为一个订单信息，合单得到的订单信息的运输服务需求均低于所述第一预设阈值。也就是说，为了保证运输资源的合理分配，可以将运输服务需求过大的订单拆分，将运输服务需求过小的订单合单，以保证运输资源有一个较好地利用率，节省运输成本。

基于上述各方法流程，本申请实施例提供了一种应用本申请运输路径规划方法对运输成本的影响趋势图，如图4所示，在使用本申请的运输路径规划方法前第1、2、3周时的筐均成本和件均成本比较高，冷冻链使用本申请的运输路径规划方法第4-6周时的筐均成本和件均成本明显下降，冷藏链使用本申请的运输路径规划方法第7-17周时的筐均成本和件均成本也明显下降。由此可知，本申请的运输路径规划方法可有效降低运输成本。

基于上述方法流程，本申请实施例提供了一种运输路径规划方法流程，如图5所示，包括：

步骤501、接收多个订单信息。

步骤502、对多个订单信息进行拆单和/或合单处理，得到处理后的多个订单信息。

步骤503、基于节约里程法计算处理后的多个订单信息的至少一个临时路径。

步骤504、计算每个临时路径的运输成本和路径可达度，将临时路径的运输成本和路径可达度代入目标函数得到该临时路径对应的目标值。

步骤505、将各临时路径中目标值最低的临时路径作为初始路径。

步骤506、通过轮盘赌算法从多个破坏算子中选择用于本轮路径优化的破坏算子。

步骤507、通过破坏算子从初始路径中删除设定数量的前置仓得到破坏路径。

步骤508、计算该删除的前置仓的重要度。

步骤509、通过轮盘赌算法从多个修复算子中选择用于本轮路径优化的修复算子。

步骤510、通过修复算子，以删除的前置仓的重要度作为选取概率，依次将删除的前置仓插入破坏路径的最优位置从而得到更新路径。

步骤511、更新路径的目标值是否不大于初始路径的目标值，若是，则执行步骤512，若否，则执行步骤513。

步骤512、将更新路径作为初始路径。

步骤513、不对初始路径更新。

步骤514、返回通过步骤506，循环执行步骤506至步骤512/513直至得到最终路径。

此处，需要说明的是，可以实现设定循环停止的条件。如，循环轮次限制、循环时间限制的，这里对循环停止，得到最终路径的条件不做限制，可以根据需要具体设置。上述流程中步骤502和/或步骤503-步骤505可以执行，也可以不执行，步骤503-步骤505不执行时，可以将根据多个订单信息随机确定的路径作为初始路径，也就是说，上述流程步骤并不唯一。

基于相同构思，本申请实施例提供了一种运输路径规划装置，如图6所示，所述装置包括：

收发模块601，用于接收多个订单信息，任一订单信息中包括运输起止站及运输要求；所述运输起止站包括作为起点的大仓和作为终点的前置仓；

处理模块602，用于根据所述多个订单信息确定初始路径，所述初始路径中包含所述多个订单信息中的各大仓和各前置仓；

所述处理模块602还用于，通过破坏算子从所述初始路径中删除设定数量的前置仓，得到破坏路径；通过修复算子确定删除的前置仓的重要度，以重要度作为选取概率，依次将所述删除的前置仓插入所述破坏路径的最优位置从而得到更新路径，若所述更新路径的目标值不大于所述初始路径的目标值，则将所述更新路径作为所述初始路径，返回通过破坏算子从所述初始路径中删除设定数量的前置仓的步骤，循环进行直至得到最终路径；其中，重要度是以前置仓对应的订单信息中的运输要求确定的；目标值是根据所在路径的运输成本确定的。

可选的，所述处理模块602具体用于，基于节约里程法，根据所述多个订单信息确定至少一个临时路径；根据所述多个订单信息中的运输要求确定各临时路径的运输成本和路径可达度，所述路径可达度是根据路径中的各前置仓间距离确定的，路径中的各前置仓间距离越近路径可达度越高；针对每个临时路径，将所述临时路径的运输成本和路径可达度代入目标函数，得到所述临时路径的目标值；从所述至少一个临时路径中确定出目标值最低的临时路径作为初始路径。

可选的，所述处理模块602具体用于，针对任一临时路径，根据路网数据确定所述临时路径中各节点之间的距离；所述各节点包括大仓与前置仓；根据所述各订单信息中的运输要求分配车辆；根据所述各订单信息中各前置仓的卸货时长、分配车辆的车辆类型的里程计价、所涉城市的城市里程计价、所述各节点之间的距离确定所述临时路径的运输成本。

可选的，所述破坏算子包括多种；所述处理模块602还用于，在每轮路径优化流程中，以轮盘赌方法选择本轮用于路径优化的破坏算子；所述处理模块602还用于，在本轮路径优化结束后，根据所述更新路径更新所述破坏算子的分值，所述分值用于后续轮盘赌方法选择破坏算子的概率参数。

可选的，所述破坏算子包括第一随机移除算子、第二随机移除算子、成本移除算子、路径移除算子和时间移除算子中的至少一种；其中，第一随机移除算子用于随机移除所述初始路径中的前置仓，第二随机移除算子用于随机移除所述初始路径中的子路径，成本移除算子用于移除所述初始路径中运输服务需求高的前置仓，路径移除算子用于随机移除所述初始路径中子路径中的部分路径，时间移除算子用于移除所述初始路径中运输时间要求近的前置仓。

可选的，修复算子包括多种，所述处理模块602还用于，在每轮路径优化流程中，以轮盘赌方法选择本轮用于路径优化的修复算子；所述处理模块602还用于，在本轮路径优化结束后，根据所述更新路径更新所述修复算子的分值，所述分值用于后续轮盘赌方法选择修复算子的概率参数。

可选的，所述处理模块602还用于，确定所述多个订单信息中存在运输服务需求超过第一预设阈值的订单信息，将所述超过第一预设阈值的订单信息拆分为至少两个订单信息，拆分得到的各订单信息的运输服务需求均低于所述第一预设阈值；或确定所述多个订单信息中存在运输服务需求低于第二预设阈值的订单信息，将所述低于第二预设阈值的订单信息与另外一个或多个订单信息合单为一个订单信息，合单得到的订单信息的运输服务需求均低于所述第一预设阈值。

本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本申请是参照根据本申请的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

显然，本领域的技术人员可以对本申请进行各种改动和变型而不脱离本申请的精神和范围。这样，倘若本申请的这些修改和变型属于本申请权利要求及其等同技术的范围之内，则本申请也意图包含这些改动和变型在内。

Claims (10)

1.一种运输路径规划方法，其特征在于，所述方法包括：

接收多个订单信息，任一订单信息中包括运输起止站及运输要求；所述运输起止站包括作为起点的大仓和作为终点的前置仓；

根据所述多个订单信息确定初始路径，所述初始路径中包含所述多个订单信息中的各大仓和各前置仓；

通过破坏算子从所述初始路径中删除设定数量的前置仓，得到破坏路径；通过修复算子确定删除的前置仓的重要度，以重要度作为选取概率，依次将所述删除的前置仓插入所述破坏路径的最优位置从而得到更新路径，若所述更新路径的目标值不大于所述初始路径的目标值，则将所述更新路径作为所述初始路径，返回通过破坏算子从所述初始路径中删除设定数量的前置仓的步骤，循环进行直至得到最终路径；其中，重要度是以前置仓对应的订单信息中的运输要求确定的；目标值是根据所在路径的运输成本确定的。

2.如权利要求1所述的方法，其特征在于，根据所述多个订单信息确定初始路径，包括：

基于节约里程法，根据所述多个订单信息确定至少一个临时路径；

根据所述多个订单信息中的运输要求确定各临时路径的运输成本和路径可达度，所述路径可达度是根据路径中的各前置仓间距离确定的，路径中的各前置仓间距离越近路径可达度越高；

针对每个临时路径，将所述临时路径的运输成本和路径可达度代入目标函数，得到所述临时路径的目标值；

从所述至少一个临时路径中确定出目标值最低的临时路径作为初始路径。

3.如权利要求2所述的方法，其特征在于，根据所述多个订单信息中的运输要求确定各临时路径的运输成本，包括：

针对任一临时路径，根据路网数据确定所述临时路径中各节点之间的距离；所述各节点包括大仓与前置仓；

根据所述各订单信息中的运输要求分配车辆；

根据所述各订单信息中各前置仓的卸货时长、分配车辆的车辆类型的里程计价、所涉城市的城市里程计价、所述各节点之间的距离确定所述临时路径的运输成本。

4.如权利要求1所述的方法，其特征在于，所述破坏算子包括多种；所述通过破坏算子从所述初始路径中删除设定数量的前置仓之前，还包括：

在每轮路径优化流程中，以轮盘赌方法选择本轮用于路径优化的破坏算子；

将所述更新路径作为所述初始路径之后，还包括：

在本轮路径优化结束后，根据所述更新路径更新所述破坏算子的分值，所述分值用于后续轮盘赌方法选择破坏算子的概率参数。

5.如权利要求4所述的方法，其特征在于，所述破坏算子包括第一随机移除算子、第二随机移除算子、成本移除算子、路径移除算子和时间移除算子中的至少一种；其中，第一随机移除算子用于随机移除所述初始路径中的前置仓，第二随机移除算子用于随机移除所述初始路径中的子路径，成本移除算子用于移除所述初始路径中运输服务需求高的前置仓，路径移除算子用于随机移除所述初始路径中子路径中的部分路径，时间移除算子用于移除所述初始路径中运输时间要求近的前置仓。

6.如权利要求1所述的方法，其特征在于，修复算子包括多种，通过修复算子确定删除的前置仓的重要度之前，还包括：

在每轮路径优化流程中，以轮盘赌方法选择本轮用于路径优化的修复算子；

将所述更新路径作为所述初始路径之后，还包括：

在本轮路径优化结束后，根据所述更新路径更新所述修复算子的分值，所述分值用于后续轮盘赌方法选择修复算子的概率参数。

7.如权利要求1至6任一项所述的方法，其特征在于，根据所述多个订单信息确定初始路径之前，还包括：

确定所述多个订单信息中存在运输服务需求超过第一预设阈值的订单信息，将所述超过第一预设阈值的订单信息拆分为至少两个订单信息，拆分得到的各订单信息的运输服务需求均低于所述第一预设阈值；或

确定所述多个订单信息中存在运输服务需求低于第二预设阈值的订单信息，将所述低于第二预设阈值的订单信息与另外一个或多个订单信息合单为一个订单信息，合单得到的订单信息的运输服务需求均低于所述第一预设阈值。

8.一种运输路径规划装置，其特征在于，所述装置包括：

收发模块，用于接收多个订单信息，任一订单信息中包括运输起止站及运输要求；所述运输起止站包括作为起点的大仓和作为终点的前置仓；

处理模块，用于根据所述多个订单信息确定初始路径，所述初始路径中包含所述多个订单信息中的各大仓和各前置仓；

所述处理模块还用于，通过破坏算子从所述初始路径中删除设定数量的前置仓，得到破坏路径；通过修复算子确定删除的前置仓的重要度，以重要度作为选取概率，依次将所述删除的前置仓插入所述破坏路径的最优位置从而得到更新路径，若所述更新路径的目标值不大于所述初始路径的目标值，则将所述更新路径作为所述初始路径，返回通过破坏算子从所述初始路径中删除设定数量的前置仓的步骤，循环进行直至得到最终路径；其中，重要度是以前置仓对应的订单信息中的运输要求确定的；目标值是根据所在路径的运输成本确定的。

9.一种计算设备，其特征在于，包括：

存储器，用于存储程序指令；

处理器，用于调用所述存储器中存储的程序指令，按照获得的程序执行权利要求1至7任一项所述的方法。

10.一种计算机可读非易失性存储介质，其特征在于，包括计算机可读指令，当计算机读取并执行所述计算机可读指令时，使得计算机执行如权利要求1至7任一项所述的方法。

Images