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

摘要

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

主权项

一种物流配送路径规划方法，其特征在于，所述方法包括：S1，获取每个需求点的配送量和配送点与需求点之间以及各需求点之间的直接可达最短路径的距离；S2，以配送点和需求点为节点，以所述配送点与需求点之间以及各需求点之间的直接可达最短路径为边，构造路径连通图；S3，根据所述每个需求点节点的配送量以及每条边的距离对所述路径连通图划分任务子图，每个所述任务子图所包含的节点的配送量总和不大于预设运量容限；S4，针对每一个所述任务子图，构造包含该任务子图中全部节点的最小支撑树；S5，从所述最小支撑树与所述配送点节点构成的全部回路中选取包含最小支撑树路径最长的回路为配送路径主干，所述配送路径主干之外的悬挂节点采用往返路径，得到该任务子图的配送路径。