出餐时间不确定的外卖车辆启发式调度算法

发布时间：2023-03-09 18:35

　　随着外卖市场的的繁荣,网上订餐的消费模式日益深入人心,已经成为上班族用餐的主要形式,网上订餐订单量越来越大。然而,订单配送成本一直居高不下,一个重要原因是,传统车辆调度问题通常将商户生产餐品的时间(出餐时间)作为一个确定值考虑,而实际场景中,商户的出餐时间具有很强的不确定性。车辆到达商户时,若商户未出餐,则要等待;若商户早已出餐,则餐品送达顾客时口感可能已经发生改变,均会降低顾客满意度。因此,有必要考虑出餐时间不确定的情况下,如何规划车辆配送路线的问题。本文对多商户的、商户出餐时间不确定的车辆路径问题进行研究,该问题具有以下三个特点:(1)商户出餐时间是随机变量,这具有随机车辆路径问题的特征;(2)安排车辆配送路线时要考虑商户和对应顾客的配送顺序限制,这具有带取送货的车辆路径问题的特征;(3)顾客有服务时间窗的要求,规划车辆配送路线时要保证一定的顾客满意度。本文的研究目标是规划出期望物流成本最小的配送路线,且满足相关约束条件。本文对该问题进行了详细定义和假设,建立了该问题的两阶段随机规划数学模型,并基于问题特征,设计了商户的插入策略,采用多空间采样算法(Multi-space Samp...

【文章页数】：59 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 研究背景及意义
    1.2 国内外研究综述
        1.2.1 车辆路径问题综述
        1.2.2 随机车辆路径问题及求解算法研究
        1.2.3 带取送货的车辆路径问题及求解算法研究
    1.3 本文的主要研究工作和结构
2 问题模型研究
    2.1 问题描述
        2.1.1 问题定义
        2.1.2 问题难度
    2.2 相关假设和数学模型
        2.2.1 相关假设
        2.2.2 数学模型
3 出餐时间不确定的外卖车辆路径问题的启发式算法
    3.1 基于问题特征的插入算法
    3.2 基于问题特征的MSH算法
        3.2.1 算法总体结构
        3.2.2 采样启发式
        3.2.3 路线分割算法
        3.2.4 集合分区
4 实验和结果分析
    4.1 算例描述
    4.2 参数设置
    4.3 结果分析
        4.3.1 比较插入算法和MSH算法的实验结果
        4.3.2 相关参数对解的影响分析
        4.3.3 MSH算法组成成分分析
结论
参考文献
致谢



本文编号：3758089