一种配送路线优化方法、系统、电子设备及存储介质与流程
本技术涉及物流配送,特别是涉及一种配送路线优化方法、配送路线优化系统、计算机可读存储介质、计算机程序产品及电子设备。
背景技术:
1、随着物流配送业务规模扩大,配送任务数量和复杂程度不断提高,车辆路线规划对物流配送效率及车辆资源利用率具有重要影响。在多门店配送场景中,不同配送任务在货量、期望接货时间及收货时间窗等方面存在差异,需要合理确定车辆与配送任务之间的分配关系。
2、现有车辆路线规划方法通常需要同时考虑车辆数量、路线时长及路线负载等多个优化目标,不同优化目标之间可能相互制约。同时,在配送任务合并过程中,若仅依据距离或时间等条件判断是否能够合并,可能难以保证合并后的路线满足各配送任务的时间窗约束。此外,完成初始排程后,若缺少路线之间的任务调整,容易出现不同车辆路线之间任务分布不均、部分路线利用率较低等情况。
3、因此,如何在满足配送任务时间窗约束的基础上,对初始路线进行进一步优化,并协调车辆数量、路线时间利用情况及路线负载之间的关系,仍是车辆路线规划中需要解决的问题。
技术实现思路
1、鉴于以上所述现有技术的缺点,本技术的目的在于提供一种配送路线优化方法,用于解决现有车辆路线规划过程中多个优化目标难以协调、任务合并后的时间窗约束不足以及初始排程后缺乏跨路线任务调度优化的问题。
2、为实现上述目的及其他相关目的,本技术的第一方面提供一种配送路线优化方法,包括:获取初始路线集合;按预定顺序对所述初始路线集合执行多阶段顺序优化,所述多阶段顺序优化的首个阶段以所述初始路线集合作为输入,后一阶段以前一阶段处理后的路线集合作为输入。所述多阶段顺序优化包括路线压缩阶段、任务整合阶段、间隙填补阶段和负载均衡阶段;其中,在所述路线压缩阶段,在该阶段输入的路线集合中确定源路线,将所述源路线中的任务重新分配至该阶段输入的路线集合中的其他路线,并在所述源路线的全部任务成功分配后删除所述源路线;在所述任务整合阶段,在该阶段输入的路线集合中确定待优化路线,将所述待优化路线中的任务插入该阶段输入的路线集合中的其他路线;在所述间隙填补阶段,在该阶段输入的路线集合中确定任务提供路线和任务接收路线,将所述任务提供路线中的任务迁移至所述任务接收路线,以填补所述任务接收路线中的空闲时间;在所述负载均衡阶段,在该阶段输入的路线集合中确定任务迁出路线和任务迁入路线,将所述任务迁出路线中的任务迁移至所述任务迁入路线,以均衡路线负载。其中,各阶段中的任务处理在通过时间窗可行性验证后执行;输出处理后的路线方案。
3、于本技术的第一方面的一些实施例中,所述获取初始路线集合包括:获取配送任务;对于不具有同步配送要求的配送任务,判断其与已有车辆任务是否满足合并条件,若满足所述合并条件,则执行合并,否则新建车辆任务。其中,所述合并条件包括:合并后总货量不超过车辆装载能力、独立门店数量不超过门店数量上限、各配送停靠点的期望接货时间差满足时间差要求,以及各门店的收货完成时间不超出各自的收货时间窗。对于具有同步配送要求的门店,配置用于执行该门店对应配送任务的车辆组,所述车辆组包含至少一辆车辆,在执行所述同步配送任务期间,不向所述车辆组中的车辆分配其他门店的配送任务。在完成各配送任务的车辆任务分配后,生成所述初始路线集合。
4、于本技术的第一方面的一些实施例中,所述路线压缩阶段还包括:将任务数量最少的一或多个路线确定为源路线;确定各所述源路线中各待重新分配任务的候选分配路线,并排除会引起同步配送冲突的候选分配路线;其中,所述同步配送冲突为将所述待重新分配任务重新分配至候选分配路线后,所述待重新分配任务对应门店的配送任务不满足同步配送要求;依据时间利用率从剩余的候选分配路线中确定目标分配路线,并将所述待重新分配任务分配至所述目标分配路线;在任一所述源路线的全部任务均成功重新分配后,删除该源路线并更新路线集合;重复执行所述路线压缩阶段,直至不存在可删除的源路线。
5、于本技术的第一方面的一些实施例中,所述任务整合阶段还包括:确定待插入任务的候选插入方案,所述候选插入方案包括候选插入路线及不改变所述候选插入路线中已有任务执行顺序的插入位置;依据时间利用率确定目标插入方案,并按照所述目标插入方案插入所述待插入任务;在所述待优化路线的全部任务均完成插入后,删除所述待优化路线。
6、于本技术的第一方面的一些实施例中,所述间隙填补阶段还包括:根据任务提供路线中的待迁移任务及其在任务接收路线中的插入位置确定多个迁移方案;确定各所述迁移方案对应的最长路线时长和路线时长极差,其中,所述路线时长极差为最长路线时长与最短路线时长之差;根据所述最长路线时长和所述路线时长极差评估各所述迁移方案,并依据评估结果确定目标迁移方案。
7、于本技术的第一方面的一些实施例中,所述路线负载均衡阶段还包括:获取所述任务迁出路线中的各任务,分别生成各任务向所述任务迁入路线的迁移方案;基于各所述迁移方案进行路线重建,并根据路线重建结果确定对应的多维度评分;将各所述迁移方案的多维度评分与任务迁移前路线方案的多维度评分进行比较,若存在评分结果优于所述任务迁移前路线方案的迁移方案,则依据比较结果确定目标迁移方案并执行。
8、为实现上述目的及其他相关目的,本技术的第二方面提供一种配送路线优化系统,包括初始路线获取模块、路线压缩模块、任务整合模块、间隙填补模块、负载均衡模块、时间窗验证模块和方案输出模块。
9、所述初始路线获取模块用于获取初始路线集合;所述路线压缩模块用于确定源路线,将所述源路线中的任务重新分配至其他路线,并在所述源路线的全部任务成功分配后删除所述源路线;所述任务整合模块用于确定待优化路线,并将所述待优化路线中的任务插入其他路线;所述间隙填补模块用于确定任务提供路线和任务接收路线,并将所述任务提供路线中的任务迁移至所述任务接收路线,以填补所述任务接收路线中的空闲时间;所述负载均衡模块用于确定任务迁出路线和任务迁入路线,并将所述任务迁出路线中的任务迁移至所述任务迁入路线,以均衡路线负载;所述时间窗验证模块用于对各模块中的任务处理进行时间窗可行性验证,并在验证通过后执行对应的任务处理;所述方案输出模块用于输出处理后的路线方案。
10、其中,所述路线压缩模块、所述任务整合模块、所述间隙填补模块和所述负载均衡模块按照预定顺序进行处理,所述路线压缩模块以所述初始路线集合作为输入,后一模块以前一模块处理后的路线集合作为输入。
11、为实现上述目的及其他相关目的,本技术的第三方面提供一种计算机可读存储介质,其上存储有计算机程序,所述计算机程序被处理器执行时,实现本技术第一方面中任一实施例所述的配送路线优化方法。
12、为实现上述目的及其他相关目的,本技术的第四方面提供一种计算机程序产品,包括计算机程序,所述计算机程序被处理器执行时,实现本技术第一方面所述的配送路线优化方法。
13、为实现上述目的及其他相关目的,本技术的第五方面提供一种电子设备,包括处理器和存储器,所述存储器中存储有计算机程序,所述处理器执行所述计算机程序,以实现本技术第一方面所述的配送路线优化方法。
14、如上所述,本技术的配送路线优化方法、系统、计算机可读存储介质、计算机程序产品及电子设备,至少具有以下有益效果:
15、第一,本技术按照预定顺序依次执行路线压缩、任务整合、间隙填补及负载均衡,且后一阶段以前一阶段处理后的路线集合作为输入,将车辆数量减少和路线负载均衡等优化目标分阶段处理,降低不同优化目标相互制约的影响。同时,各阶段具有明确的处理对象和处理逻辑,便于追踪路线方案的调整过程。
16、第二,本技术在生成初始路线集合时,将车辆装载能力、独立门店数量、配送停靠点的期望接货时间差以及各门店的收货时间窗作为配送任务合并的判断条件,并针对具有同步配送要求的门店配置相应车辆组;在后续各优化阶段中,对任务处理进行时间窗可行性验证,并检查同步配送要求。由此,可以减少因任务合并后不满足收货时间窗产生的无效操作,提高处理后路线方案的执行可行性。
17、第三,本技术通过路线压缩和任务整合减少低效路线及车辆使用数量,通过间隙填补减少碎片化空闲时间,通过负载均衡改善路线间任务分布,从而改善路线时间利用情况及负载分布,提高车辆资源利用效率。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com