需求点随机的分批配送VRP模型与算法研究
1. 研究背景与意义
1.1 研究背景
1.1.1 城市配送的需求点不确定性
- 在城市配送中，需求点的需求量、位置和服务时间等因素往往存在不确定性。
- 连锁超市、便利店、大型卖场等配送问题中，部分需求点在配送过程中可能不产生需求。
- 这种需求点的不确定性给配送路径的规划与优化带来了挑战。
1.1.2 分批配送的必要性
- 分批配送可以有效应对需求点的不确定性，提高配送效率，降低配送成本。
- 分批配送允许同一需求点由多辆车进行配送，使车辆对被分割需求点的配送量成为一个变量。
- 研究表明，允许分批配送在大部分算例中的费用低于不允许分批配送的情形。
1.2 研究意义
1.2.1 理论意义
- 建立需求点随机的分批配送车辆路径问题(SDVRPSC)模型，为相关领域的研究提供理论支持。
- 设计改进的自适应大邻域搜索算法进行求解，丰富车辆路径问题的求解方法。
1.2.2 实际意义
- 提高城市配送的效率和成本效益，满足企业对物流配送的需求。
- 为物流企业提供一种应对需求点不确定性的有效方法，提升其市场竞争力。
2. 文献综述
2.1 SDVRP研究现状
2.1.1 SDVRP的定义与特点
- SDVRP允许需求点需求量大于车容量，允许多辆车对同一需求点进行配送。
- SDVRP在报纸配送、食品配送、零售物品配送等领域得到了广泛应用。
2.1.2 SDVRP的研究进展
- SDVRP扩展问题方面，主要有带时间窗的、集货与配送混合的、多车型的、随机的等。
- SDVRP求解算法主要借鉴VRP算法并加以改进，包括精确求解算法和启发式算法。
2.2 需求点随机的VRP研究现状
2.2.1 需求点随机的VRP定义
- 需求点随机的VRP是指需求点位置、需求量等存在不确定性的车辆路径问题。
- 此类问题在实际运作中较为常见，如连锁超市、便利店等配送问题。
2.2.2 需求点随机的VRP研究进展
- 对需求点随机的VRP已有一定的研究，主要集中在求解算法方面。
- 常见的研究方法包括精确算法、启发式算法等。
3. 问题描述与模型建立
3.1 问题描述
3.1.1 问题定义
- SDVRPSC定义在无向图G = (V, E) 上，其中V = {0, 1, ..., N} 代表节点集合，0 代表车场，其余节点代表需求点。
- 需求点位置确定，但部分需求点以一定的概率产生需求，称为潜在需求点。
3.1.2 问题特点
- 各个潜在需求点是否产生需求是相互独立的，产生需求的概率用pi 表示。
- 一旦产生需求，需求量就是确定的，记为di, di > 0。
- 车辆数不限制且所有车辆容量相同，记为Q。
- 在配送过程中，允许分批配送，每个需求点可由多辆车进行配送。
3.2 模型建立
3.2.1 符号说明
- a为车辆固定费用，使用每辆车的固定费用；
- b为车辆可变费用，单位路径行驶费用；
- K = {1, 2, ..., m} 表示车辆集，车场内有m 辆车；
- Ω 表示所有需求点出现与否的组合情况的集合；
- ξ 为包含所有需求点的伯努利随机变量的向量；
- 解R = {r1, ..., rm} 的路径期望费用为；
- x 和 yik 为决策变量。
3.2.2 模型构建
- 目标函数：考虑车辆使用费用和与行驶路径长度有关的期望费用；
- 约束条件：包括流平衡约束、子路径消减约束、需求点配送约束等；
- 决策变量：x 表示车辆k从需求点i直接行驶到需求点j的情况，yik 表示车辆k对需求点i的配送量。
4. 问题求解与算法设计
4.1 先验优化策略
4.1.1 先验优化策略概述
- 第1阶段，不考虑随机因素，计算出一个先验路径；
- 第2阶段，考虑随机因素的影响，对先验路径进行修正。
4.1.2 先验优化策略的实施
- 对不产生需求的潜在需求点采用直接跳过的策略；
- 仿照确定性SDVRP性质，假定任意两条路径中最多只有一个相同的需求点。
4.2 自适应大邻域搜索算法
4.2.1 算法概述
- ALNS是由 Shaw[26] 提出的LNS的一种扩展，由 Ropke等[27] 将其应用于求解车辆路径问题。
- 基本思想是通过破坏现有解的一部分，以不同的方式重新构建新的解，以得到更好的解。
4.2.2 算法设计
- 初始解构造：改进的插入算法；
- 删除算子：随机删除、相似性删除、确定性最差删除和期望最差删除；
- 插入算子：贪婪插入、后悔插入和分割插入；
- 自适应选择规则：算子权重动态更新。
5. 实验与分析
5.1 实验设计
5.1.1 实验数据
- 使用调整的Solomon算例进行测试；
- 调整后的算例包含不同规模、不同需求分布的情况。
5.1.2 实验目的
- 验证所提出的模型和算法的有效性；
- 分析不同算子对求解结果的影响。
5.2 实验结果
5.2.1 模型有效性
- 在大部分算例中，允许分批配送的费用低于不允许分批配送的情形；
- 表明分批配送是一种有效应对需求点不确定性的方法。
5.2.2 算法分析
- 确定性最差删除算子和随机删除算子在求解此类问题时表现较好；
- 贪婪插入算子和后悔插入算子表现较好；
- 分割插入算子虽然权重较低，但能对解产生质的影响。
6. 结论与展望
6.1 结论
- 建立了需求点随机的分批配送车辆路径问题(SDVRPSC)模型；
- 设计了改进的自适应大邻域搜索算法进行求解；
- 实验结果表明，所提出的模型和算法在应对需求点不确定性方面具有有效性。
6.2 展望
- 在未来研究中，可以进一步探讨其他类型的车辆路径问题，如带时间窗的、多车型的等；
- 可以尝试将其他优化算法应用于求解SDVRPSC，以提高求解效率和质量；
- 可以结合实际应用场景，对模型和算法进行进一步的改进和优化。
