CN104616070A - 一种物流配送路径规划方法及装置 - Google Patents

Abstract

本发明涉及一种物流配送路径规划方法及装置。本发明方法及装置通过以配送点和需求点作为节点，以所述配送点与需求点之间以及各需求点之间直接可达最短路径作为边，构造路径连通图；根据所述每个需求点节点的配送量以及每条边的距离划分所包含节点的总配送量不大于预设运量容限的任务子图；构造包含任务子图中所包含的全部节点的最小支撑树；从所述最小支撑树与所述配送点节点构成回路中选取包含最小支撑树路径最长的回路作为配送路径主干，所述配送路径主干之外的悬挂节点采用往返路径。能够使配送路径更加合理，采用自组织方式合理将需求点进行邻近合并划分任务子图，适用于大规模的配送路径规划，能够有效缩短配送时间以及提高配送满载率。

Description

一种物流配送路径规划方法及装置

技术领域

本发明涉及物流配送技术领域，具体涉及一种物流配送路径规划方法及装置。

背景技术

在物流领域配送路径规划问题是车辆路径问题(VRP)之一。传统的车辆路径优化问题研究包括图的遍历、最短路径、旅行商问题、欧拉回路、哈密尔顿回路和中国邮递员问题。

VRP研究方法主要分为精确算法和启发式算法两大类。精确算法以严谨的数学推导为基础，能够获得最优解，该类无法避免组合爆炸的问题，只适合于解决小规模的VRP问题，在目前VRP领域实际应用范围有限。启发式算法是从初始解出发，在邻域中搜索实现解的改进，快速得到可接受的一个解的方法。该类算法虽然能够比较快的解决有关问题,但该算法的优劣往往取决于算法设计者的实际经验以及处理的样本空间的大小。

扫描法是运输路径规划最实用的启发式算法。它假设车辆的路径位于一个几何平面上，配送点为原点，需求点以极坐标来表示，先选定一辆配送车辆，在不违反车辆容量限制的前提下，从角度最小且尚未指派的节点开始，依顺时针或逆时针的方向扫描。当车辆容量超过时，结束该条路径。重复上述步骤，生成新的路径，直到将所有的节点都被排入。最后再用求解旅行商问题(TravelingSalesman Problem，简称TSP)的算法对每一条路径分别进行优化。该方法本质是先聚类再规划的两阶段方法，能够在较短时间内求得可行的满意解，但其扫描划分路径过程中忽略道路的纵横特点，在扫描扇区内的需求点实际配送路径可能要绕远；路径内以TSP方法进行规划，以访问每个需求点仅且一次为约束；同时扫描法路径规划的路径回路覆盖的范围相对分散，不符合实际配送中的分片包干的配送管理。

发明内容

针对现有路径规划方法中忽略了道路纵横特点以及单个需求点有可能多次配送造成的路径回路覆盖范围相对分散的缺陷，本发明提供了一种物流配送路径规划方法及装置。

一方面，本发明提供的一种物流配送路径规划方法，包括：

S1，获取每个需求点的配送量和配送点与需求点之间以及各需求点之间的直接可达最短路径的距离；

S2，以配送点和需求点为节点，以所述配送点与需求点之间以及各需求点之间的直接可达最短路径为边，构造路径连通图；

S3，根据所述每个需求点节点的配送量以及每条边的距离对所述路径连通图划分任务子图，每个所述任务子图所包含的节点的配送量总和不大于预设运量容限；

S4，针对每一个所述任务子图，构造包含该任务子图中全部节点的最小支撑树；

S5，从所述最小支撑树与所述配送点节点构成的全部回路中选取包含最小支撑树路径最长的回路为配送路径主干，所述配送路径主干之外的悬挂节点采用往返路径，得到该任务子图的配送路径。

进一步地，所述S3中，根据所述每个需求点节点的配送量以及每条边的距离划分任务子图的步骤，包括：

S31，针对每一个需求点节点，若该需求点节点的配送量大于预设运量容限，则为该需求点节点划分一个任务子图，直至该需求点节点的配送量小于预设运量容限为止；

S32，选取所有配送量小于预设运量容限的需求点节点中与所述配送点的距离最大的一个需求点节点作为待合并节点；

S33，判断与所述待合并节点直接可达的需求点节点中是否存在与该待合并节点的配送量之和小于或等于运量容限的节点，若存在则执行S34，若不存在则将待合并节点单独划分为一个任务子图；

S34，选取与待合并节点的配送量之和小于运量容限的节点中与待合并节点距离最近的一个节点待合并节点合并；

S35，对于剩余未参与合并的需求点节点重复S32至S34；

S36，对于合并得到的子图重复S32至S35，直至所有需求点节点都划分得到对应的任务子图为止。

进一步地，所述S4包括：

针对每一个任务子图，采用避圈法构造包含该任务子图所包含的全部节点的最小支撑树。

进一步地，所述方法还包括：

S6，采用单步法对所述单个任务子图内的配送路径进行优化。

进一步地，所述S6包括：

S61，针对每一个悬挂节点，判断所述最小支撑树中与该悬挂节点连接节点的上一个节点或下一个节点是否存在与该悬挂节点直接可达路径；

S62，若存在，则判断该悬挂节点与所述上一个节点或下一个节点之间的距离是否小于该悬挂节点经所述最小支撑树到达所述上一个节点或下一个节点的距离；

S63，若小于，则采用该悬挂节点与所述上一个节点或下一个节点之间的路径替换该悬挂节点经所述最小支撑树到达所述上一个节点或下一个节点的路径。

另一方面，本发明还提供一种物流配送路径规划装置，包括：

获取模块，用于获取每个需求点的配送量和配送点与需求点之间以及各需求点之间的直接可达最短路径的距离；

第一构造模块，用于以配送点和需求点为节点，以所述配送点与需求点之间以及各需求点之间的直接可达最短路径为边，构造路径连通图；

划分模块，用于根据所述每个需求点节点的配送量以及每条边的距离对所述路径连通图划分任务子图，每个所述任务子图所包含的节点的配送量总和不大于预设运量容限；

第二构造模块，用于针对每一个所述任务子图，构造包含该任务子图中全部节点的最小支撑树；

选取模块，用于从所述最小支撑树与所述配送点节点构成的全部回路中选取包含最小支撑树路径最长的回路为配送路径主干，所述配送路径主干之外的悬挂节点采用往返路径，得到该任务子图的配送路径。

进一步地，所述划分模块具体用于：

针对每一个需求点节点，若该需求点节点的配送量大于预设运量容限，则为该需求点节点划分一个任务子图，直至该需求点节点的配送量小于预设运量容限为止；

选取所有配送量小于预设运量容限的需求点节点中与所述配送点的距离最大的一个需求点节点作为待合并节点；

判断与所述待合并节点直接可达的需求点节点中是否存在与该待合并节点的配送量之和小于或等于运量容限的节点，若存在则选取与待合并节点的配送量之和小于运量容限的节点中与待合并节点距离最近的一个节点待合并节点合并，若不存在则将待合并节点单独划分为一个任务子图；

对于剩余未参与合并的需求点节点重复上述操作；

对于合并得到的子图重复上述操作，直至所有需求点节点都划分得到对应的任务子图为止。

进一步地，所述第二构造模块具体用于：

针对每一个任务子图，采用避圈法构造包含该任务子图所包含的全部节点的最小支撑树。

进一步地，所述装置还包括：

优化模块，用于采用单步法对所述单个任务子图内的配送路径进行优化。

进一步地，所述优化模块具体用于：

针对每一个悬挂节点，判断所述最小支撑树中与该悬挂节点连接节点的上一个节点或下一个节点是否存在与该悬挂节点直接可达路径；

若存在，则判断该悬挂节点与所述上一个节点或下一个节点之间的距离是否小于该悬挂节点经所述最小支撑树到达所述上一个节点或下一个节点的距离；

若小于，则采用该悬挂节点与所述上一个节点或下一个节点之间的路径替换该悬挂节点经所述最小支撑树到达所述上一个节点或下一个节点的路径。

本发明提供的一种物流配送路径规划方法及装置，与现有方法相比，优先考虑路程较远的配送任务，采用自组织方式合理将需求点进行邻近合并划分任务子图，降低了组合优化问题的规模，大大提高处理速度，使配送路径更加合理，适于大规模的配送优化问题；任务子图内采用生成最小支撑树，快速获取任务内的满意解。可以有效缩短配送路径，降低配送时间，提高车辆装载率，降低企业的运营成本，减少温室气体排放，具有巨大的经济效益、社会效益和环境效益。

附图说明

通过参考附图会更加清楚的理解本发明的特征和优点，附图是示意性的而不应理解为对本发明进行任何限制，在附图中：

图1是本发明一个实施例中物流配送路径规划方法流程示意图；

图2是本发明一个实施例中任务子图划分示意图；

图3是本发明一个实施例中单个任务子图内配送路径示意图；

图4是本发明一个实施例中物流配送路径规划装置结构示意图。

具体实施方式

现结合附图和实施例对本发明技术方案作进一步详细阐述。

图1示出了本实施例中物流配送路径规划方法流程示意图，如图1所示，本实施例提供的一种物流配送路径规划方法，包括：

S1，获取每个需求点的配送量和配送点与需求点之间以及各需求点之间的直接可达最短路径的距离；

S2，以配送点和需求点为节点，以所述配送点与需求点之间以及各需求点之间的直接可达最短路径为边，构造路径连通图。

在现实当中，由于道路交通纵横交错四通八达，在一个区域内的两点之间可以有多条通路，而本实施例中所述直接可达路径则是指任意两个需求点之间或者配送点与人一个需求点之间的通路上不会经过其它需求点的路径。

在构造路径连通图时，对于任意两个节点之间，寻找距离最短的那条路径进行判断，如果最短的路径是直接可达路径，则这两个节点之间存在一条边，否则这两个节点在构造的连通图中不存在边。

S3，根据所述每个需求点节点的配送量以及每条边的距离对所述路径连通图划分任务子图，每个所述任务子图所包含的节点的配送量总和不大于预设运量容限。

本实施例中所称的运量容限，是指该区域配送点所使用的配送工具进行一趟配送所能携带的最大配送量。同时，将配送工具进行的一趟配送过程看作是一个任务，也就是说一个任务所能完成的最大配送量不大于所述运量容限。

对于在配送过程中，不同的任务可以采用不同的配送工具同时进行配送，也可以由同一个配送工具依次完成多个配送任务。不管采用上述哪种配送方式，完成每个任务的路径的出发点以及终点都是配送点，因此，在规划整个区域的配送路径时，即可将其等同为分别规划每一个任务的配送路径，如果每个任务的配送路径达到最优那么整个区域的配送路径也将是最优的。

进一步地，所述S3中，根据所述每个需求点节点的配送量以及每条边的距离划分任务子图的步骤，包括：

S31，针对每一个需求点节点，若该需求点节点的配送量大于预设运量容限，则为该需求点节点划分一个任务子图，直至该需求点节点的配送量小于预设运量容限为止；

S32，选取所有配送量小于预设运量容限的需求点节点中与所述配送点的距离最大的一个需求点节点作为待合并节点；

S33，判断与所述待合并节点直接可达的需求点节点中是否存在与该待合并节点的配送量之和小于或等于运量容限的节点，若存在则执行S34，若不存在则将待合并节点单独划分为一个任务子图；

S34，选取与待合并节点的配送量之和小于运量容限的节点中与待合并节点距离最近的一个节点待合并节点合并；

S35，对于剩余未参与合并的需求点节点重复S32至S34；

S36，对于合并得到的子图重复S32至S35，直至所有需求点节点都划分得到对应的任务子图为止。

举例来说，设定预设运量容限为200，假设所有需求点中，有一个第一需求点的配送量为420，剩余其它需求点的配送量都小于200。那么，首先为该第一需求点划分两个任务子图，每一个任务子图都只包含该第一需求点一个节点，并且上述所划分的两个任务子图内的配送路径就是该第一需求点与配送点之间距离最短的路径。

然后，该第一需求点划分两个任务子图之后还剩余20的配送量需要配送，则将该第一需求点基于配送量20与其它配送量小于运量容限的所有需求点通过合并的方法进行任务子图划分。

具体的，选取所述需求点节点中与所述配送点的距离最大的一个需求点节点作为待合并节点，判断与该待合并节点直接可达的需求点节点中是否存在与该待合并节点的配送量之和小于运量容限的节点，若存在则选取与待合并节点的配送量之和小于运量容限的节点中与待合并节点距离最近的一个节点待合并节点合并；若不存在则将待合并节点单独划分为一个任务子图。

例如，将所有待合并的需求点节点按照与配送点距离从大到小的顺序存入待合并队列Q1中，首先选取排在队首与配送点距离最远的节点R1，并将与R1存在可达路径的节点按照与R1距离从小到大的顺去存入相邻节点队列Q3中，依次判断节点R1与Q3中节点配送量之和与运量容限的大小，将第一次出现配送量之和不大于运量容限对应的Q3中的节点与节点R1合并，并存入队列Q4中，若Q3中所有节点与R1的配送量之和都大于运量容限，则将R1存入任务队列Q2中，作为一个任务子图，不再参与下次合并。

直到Q1中所有节点都参与过一次合并之后，将Q4中合并得到的节点组存入Q1中，进行下次合并判断，直至所有节点都被划分到任务子图当中为止。

如图2所示，R_i为进过多次合并后排在队列Q1队首的节点组，R_j和R’_j为与直接可达的两个节点组，与R_i的距离分别为500和700，则R_j和R’_j排列顺序为R_j<R’_j，因此首先判断R_i与R_j的配送量之和是否小于或等于运量容限，即150+50＝200满足小于或等于运量容限的条件，所以将R_i与R_j合并为一个新的节点组R_new，由于R_new的配送量已经达到运量容限无法再与其它节点合并，因此将R_new存入队列Q2中，作为一个任务子图。

S4，针对每一个所述任务子图，构造包含该任务子图中全部节点的最小支撑树；具体的，可采用避圈法构造包含该任务子图所包含的全部节点的最小支撑树。

例如，如图3所示，图中虚线区域内黑色粗线连接的所有节点即为任务子图R_new的最小支撑树。其中，图中每个节点旁边括号内的数字表示该节点的配送量，每条边旁边的数字表示该边的长度即两个节点之间的距离。

S5，从所述最小支撑树与所述配送点节点构成的全部回路中选取包含最小支撑树路径最长的回路为配送路径主干，所述配送路径主干之外的悬挂节点采用往返路径，得到该任务子图的配送路径。

如图3所示，在任务子图R_new的最小支撑树中，需求点节点{3,4,7,10,11}与配送点节点之间存在直接可达路径，经过判断节点4与节点11之间的路径{4-3-1-2-5-6-7-8-10-11}为最小支撑树中距离最长的路径，因此选取路径{0-4-3-1-2-5-6-7-8-10-11-0}作为任务子图R_new的配送路径主干。

需求点9作为主干回路的悬挂节点，其配送路径为按原路折返的方式，因此得到任务子图R_new的最终配送路径为{0-4-3-1-2-5-6-7-8-9-8-10-11-0}，整个路径的长度L＝1397+399+432+446+463+500+422+387+469+469+443+372+1987＝8186。

进一步地，根据最小支撑树形成的配送回路针对主回路的悬挂点采用原路返回的方式，会存在一定的配送浪费，为了使得配送路径更加合理，本实施例方法还包括步骤S6：采用单步法对所述单个任务子图内的配送路径进行优化。

具体的，包括以下步骤：

S61，针对每一个悬挂节点，判断所述最小支撑树中与该悬挂节点连接节点的上一个节点或下一个节点是否存在与该悬挂节点直接可达路径；

S62，若存在，则判断该悬挂节点与所述上一个节点或下一个节点之间的距离是否小于该悬挂节点经所述最小支撑树到达所述上一个节点或下一个节点的距离；

S63，若小于，则采用该悬挂节点与所述上一个节点或下一个节点之间的路径替换该悬挂节点经所述最小支撑树到达所述上一个节点或下一个节点的路径。

以图3所示为例，其中悬挂节点9在最小支撑树中与节点8连接，而在整个任务子图中，节点9与节点8的下一个节点10存在直接可达路径，并且路径{9-10}的距离为584明显小于路径{9-8-10}的距离469+443＝912。因此，删掉原配送路径中节点9的返回路径{9-8}以及主干路径{8-10}，增加路径{9-10}，优化后的路径为{0-4-3-1-2-5-6-7-8-9-10-11-0}，优化后的路径总长度为L＝1397+399+432+446+463+500+422+387+469+584+372+1987＝7858，相比优化前的路径节省的路径距离为328。

本实施例提供的一种物流配送路径规划方法，与现有方法相比，优先考虑路程较远的配送任务，采用自组织方式合理将需求点进行邻近合并划分任务子图，降低了组合优化问题的规模，大大提高处理速度，使配送路径更加合理，适于大规模的配送优化问题；任务子图内采用生成最小支撑树，快速获取任务内的满意解。可以有效缩短配送路径，降低配送时间，提高车辆装载率，降低企业的运营成本，减少温室气体排放，具有巨大的经济效益、社会效益和环境效益。

另一方面，如图4所示，本实施例还提供一种物流配送路径规划装置，包括：

获取模块101，用于获取每个需求点的配送量和配送点与需求点之间以及各需求点之间的直接可达最短路径的距离；

第一构造模块102，用于以配送点和需求点为节点，以所述配送点与需求点之间以及各需求点之间的直接可达最短路径为边，构造路径连通图；

划分模块103，用于根据所述每个需求点节点的配送量以及每条边的距离对所述路径连通图划分任务子图，每个所述任务子图所包含的节点的配送量总和不大于预设运量容限；

第二构造模块104，用于针对每一个所述任务子图，构造包含该任务子图中全部节点的最小支撑树；

选取模块105，用于从所述最小支撑树与所述配送点节点构成的全部回路中选取包含最小支撑树路径最长的回路为配送路径主干，所述配送路径主干之外的悬挂节点采用往返路径，得到该任务子图的配送路径。

进一步地，所述划分模块103具体用于：

针对每一个需求点节点，若该需求点节点的配送量大于预设运量容限，则为该需求点节点划分一个任务子图，直至该需求点节点的配送量小于预设运量容限为止；

选取所有配送量小于预设运量容限的需求点节点中与所述配送点的距离最大的一个需求点节点作为待合并节点；

判断与所述待合并节点直接可达的需求点节点中是否存在与该待合并节点的配送量之和小于或等于运量容限的节点，若存在则选取与待合并节点的配送量之和小于运量容限的节点中与待合并节点距离最近的一个节点待合并节点合并，若不存在则将待合并节点单独划分为一个任务子图；

对于剩余未参与合并的需求点节点重复上述操作；

对于合并得到的子图重复上述操作，直至所有需求点节点都划分得到对应的任务子图为止。

进一步地，所述第二构造模块104具体用于：

针对每一个任务子图，采用避圈法构造包含该任务子图所包含的全部节点的最小支撑树。

进一步地，所述装置还包括：

优化模块，用于采用单步法对所述单个任务子图内的配送路径进行优化。

进一步地，所述优化模块具体用于：

针对每一个悬挂节点，判断所述最小支撑树中与该悬挂节点连接节点的上一个节点或下一个节点是否存在与该悬挂节点直接可达路径；

若存在，则判断该悬挂节点与所述上一个节点或下一个节点之间的距离是否小于该悬挂节点经所述最小支撑树到达所述上一个节点或下一个节点的距离；

若小于，则采用该悬挂节点与所述上一个节点或下一个节点之间的路径替换该悬挂节点经所述最小支撑树到达所述上一个节点或下一个节点的路径。

本实施例提供的一种物流配送路径规划装置，优先考虑路程较远的配送任务，采用自组织方式合理将需求点进行邻近合并划分任务子图，降低了组合优化问题的规模，大大提高处理速度，使配送路径更加合理，适于大规模的配送优化问题；任务子图内采用生成最小支撑树，快速获取任务内的满意解。可以有效缩短配送路径，降低配送时间，提高车辆装载率，降低企业的运营成本，减少温室气体排放，具有巨大的经济效益、社会效益和环境效益。

虽然结合附图描述了本发明的实施方式，但是本领域技术人员可以在不脱离本发明的精神和范围的情况下做出各种修改和变型，这样的修改和变型均落入由所附权利要求所限定的范围之内。

Claims (10)

1.一种物流配送路径规划方法，其特征在于，所述方法包括：

S1，获取每个需求点的配送量和配送点与需求点之间以及各需求点之间的直接可达最短路径的距离；

S2，以配送点和需求点为节点，以所述配送点与需求点之间以及各需求点之间的直接可达最短路径为边，构造路径连通图；

S3，根据所述每个需求点节点的配送量以及每条边的距离对所述路径连通图划分任务子图，每个所述任务子图所包含的节点的配送量总和不大于预设运量容限；

S4，针对每一个所述任务子图，构造包含该任务子图中全部节点的最小支撑树；

S5，从所述最小支撑树与所述配送点节点构成的全部回路中选取包含最小支撑树路径最长的回路为配送路径主干，所述配送路径主干之外的悬挂节点采用往返路径，得到该任务子图的配送路径。

2.根据权利要求1所述的方法，其特征在于，所述S3中，根据所述每个需求点节点的配送量以及每条边的距离划分任务子图的步骤，包括：

S31，针对每一个需求点节点，若该需求点节点的配送量大于预设运量容限，则为该需求点节点划分一个任务子图，直至该需求点节点的配送量小于预设运量容限为止；

S32，选取所有配送量小于预设运量容限的需求点节点中与所述配送点的距离最大的一个需求点节点作为待合并节点；

S33，判断与所述待合并节点直接可达的需求点节点中是否存在与该待合并节点的配送量之和小于或等于运量容限的节点，若存在则执行S34，若不存在则将待合并节点单独划分为一个任务子图；

S34，选取与待合并节点的配送量之和小于运量容限的节点中与待合并节点距离最近的一个节点待合并节点合并；

S35，对于剩余未参与合并的需求点节点重复S32至S34；

S36，对于合并得到的子图重复S32至S35，直至所有需求点节点都划分得到对应的任务子图为止。

3.根据权利要求1所述的方法，其特征在于，所述S4包括：

针对每一个任务子图，采用避圈法构造包含该任务子图所包含的全部节点的最小支撑树。

4.根据权利要求1至3任一项所述的方法，其特征在于，所述方法还包括：

S6，采用单步法对所述单个任务子图内的配送路径进行优化。

5.根据权利要求4所述的方法，其特征在于，所述S6包括：

S61，针对每一个悬挂节点，判断所述最小支撑树中与该悬挂节点连接节点的上一个节点或下一个节点是否存在与该悬挂节点直接可达路径；

S62，若存在，则判断该悬挂节点与所述上一个节点或下一个节点之间的距离是否小于该悬挂节点经所述最小支撑树到达所述上一个节点或下一个节点的距离；

S63，若小于，则采用该悬挂节点与所述上一个节点或下一个节点之间的路径替换该悬挂节点经所述最小支撑树到达所述上一个节点或下一个节点的路径。

6.一种物流配送路径规划装置，其特征在于，所述装置包括：

获取模块，用于获取每个需求点的配送量和配送点与需求点之间以及各需求点之间的直接可达最短路径的距离；

第一构造模块，用于以配送点和需求点为节点，以所述配送点与需求点之间以及各需求点之间的直接可达最短路径为边，构造路径连通图；

划分模块，用于根据所述每个需求点节点的配送量以及每条边的距离对所述路径连通图划分任务子图，每个所述任务子图所包含的节点的配送量总和不大于预设运量容限；

第二构造模块，用于针对每一个所述任务子图，构造包含该任务子图中全部节点的最小支撑树；

选取模块，用于从所述最小支撑树与所述配送点节点构成的全部回路中选取包含最小支撑树路径最长的回路为配送路径主干，所述配送路径主干之外的悬挂节点采用往返路径，得到该任务子图的配送路径。

7.根据权利要求6所述的装置，其特征在于，所述划分模块具体用于：

针对每一个需求点节点，若该需求点节点的配送量大于预设运量容限，则为该需求点节点划分一个任务子图，直至该需求点节点的配送量小于预设运量容限为止；

选取所有配送量小于预设运量容限的需求点节点中与所述配送点的距离最大的一个需求点节点作为待合并节点；

判断与所述待合并节点直接可达的需求点节点中是否存在与该待合并节点的配送量之和小于或等于运量容限的节点，若存在则选取与待合并节点的配送量之和小于运量容限的节点中与待合并节点距离最近的一个节点待合并节点合并，若不存在则将待合并节点单独划分为一个任务子图；

对于剩余未参与合并的需求点节点重复上述操作；

对于合并得到的子图重复上述操作，直至所有需求点节点都划分得到对应的任务子图为止。

8.根据权利要求6所述的装置，其特征在于，所述第二构造模块具体用于：

针对每一个任务子图，采用避圈法构造包含该任务子图所包含的全部节点的最小支撑树。

9.根据权利要求6至8任一项所述的装置，其特征在于，所述装置还包括：

优化模块，用于采用单步法对所述单个任务子图内的配送路径进行优化。

10.根据权利要求9所述的装置，其特征在于，所述优化模块具体用于：

针对每一个悬挂节点，判断所述最小支撑树中与该悬挂节点连接节点的上一个节点或下一个节点是否存在与该悬挂节点直接可达路径；

若存在，则判断该悬挂节点与所述上一个节点或下一个节点之间的距离是否小于该悬挂节点经所述最小支撑树到达所述上一个节点或下一个节点的距离；

若小于，则采用该悬挂节点与所述上一个节点或下一个节点之间的路径替换该悬挂节点经所述最小支撑树到达所述上一个节点或下一个节点的路径。