快递公司的配送数学建模

快递公司的配送问题快递公司的配送问题 摘要摘要 配送是物流系统中非常重要的一个环节 在物流的各项成本中 配送成本占了相 当高的比例 减少配送里程以降低物流配送成本成为物流管理过程中首要考虑的问题 之一 本文在已知货运车容量 各客户所需货物重量 快递公司与客户以及客户与客 户之间的距离的条件下 建立了以单车场路径问题模型 即 VRP 模型 为基础 以车 辆总行程最短为目标函数 以货物运输量小于汽车载重量以及在客户要求的时间范围 内运送货物等为约束条件的单目标线性规划模型 对于问题一 本文建立了两个模型 模型 I 硬时间窗车辆路径规划模型 首先根据题目所给条件 对运货所需的车辆数进行预估 然后结合货物运输量小 于汽车载重量 一个客户点的货物仅由一辆车配送等约束条件 同时考虑线路的连通 性和汽车到达客户点的时间范围 采用 0 1 规划法建立使总运行里程最小的车辆路径 规划模型 模型 II 软时间窗车辆路径规划模型 在模型 I 硬时间窗车辆路径规划模型的基础上 将模型 I 中的关于时间范围的约 束条件 通过设定惩罚函数的系数 变成目标函数的一部分 本文在考虑路程最短的 目标的同时 也要求尽可能在时间范围内到达 因此 建立了以成本 包括惩罚成本 以及行驶过程中带来的成本 最小为目标的函数 以运输量小于汽车载重量以及线路 的连通性等为约束条件 建立软时间车辆路径规划模型 最后运用遗传算法求解模型 对于问题二 根据题目所提供的数据 利用硬时间窗车辆路径规划模型 首先 根 据货运车的载重量和客户点的需求总量 估计出运货所需车辆数为 3 然后 借助 Lingo 求解该模型 得到最优路径的总里程数为 910 千米 快递公司每天的配送方案应 为 每天出动 3 辆车 3 辆车的行驶路径分别为 0 3 1 2 0 0 6 4 0 0 8 5 7 0 关键词 关键词 VRPTW 遗传算法 0 1 规划法 Lingo 0 目录目录 一 问题重述 2 二 模型假设和符号说明 2 三 问题分析 3 四 模型的建立与求解 4 4 1 问题一的解答 4 4 1 1 模型的准备 4 4 1 2 模型的建立 4 4 1 3 模型的求解 7 4 2 问题二的解答 8 4 2 1 对货运车辆数的估计 8 4 2 2 路线的规划 8 五 模型的评价与改进 10 5 1 模型的优缺点分析 10 5 2 模型的改进 11 六 参考文献 11 七 附录 12 1 一 问题重述一 问题重述 某快递公司在某个地区拥有一支货运车队 每台货运车辆的载重量 吨 相同 平 均速度 千米 小时 相同 该快递公司用这样的车为若干个客户配送物品 快递公司 与客户以及客户与客户之间的公路里程 千米 为已知 每天 各客户所需物品的重 量 吨 均已知 并且每个客户所需物品的重量都小于一台货运车辆的载重量 所有 送货车辆都从快递公司出发 最后回到快递公司 快递公司每天的配送方案应当包括 当天出动多少台车 行驶路径如何 由此形成的当天总运行里程是多少 一个合格的 配送方案要求送货车辆必须在一定的时间范围内到达客户处 早到达将产生等待损失 迟到达将予以一定的惩罚 而一个好的配送方案还应该给出使配送费用最小或总运行 里程最短的车辆调度方案 该快递公司希望你们 1 建立送货车辆每天总运行里程最短的一般数学模型 并给出求解方法 2 具体求解以下算例 并给出你们实际使用的软件名称 命令和编写的全部计算 机源程序 算例 载重量为 8 吨 平均速度为 60 千米 小时 的送货车辆从快递公Q v 司 0 出发 为编号是 1 2 8 的 8 个客户配送物资 某日 第 个客户i i i 所需物品的重量为吨 在第 个客户处卸货时间为小时 第 个客户要求 i q i qQ i i si 送货车辆到达的时间范围 由表 1 给出 快递公司与各客户以及各客户间的公路 ii a b 里程 单位 千米 由表 2 给出 问当日如何安排送货车辆 包括出动车辆的台数以 及每一台车辆的具体行驶路径 才能使总运行里程最短 二 模型假设和符号说明二 模型假设和符号说明 2 1 模型假设模型假设 1 所有的货运车辆都没有超载 2 快递公司能提供充足的货运车辆 3 一个客户点只有一辆货运车进入和离开 4 每条配送路径都在货运车辆的配送范围内 5 同一个客户所需要的物品只由一辆货运车配送 6 不考虑货物的类型和货运车的车型 货物可混装 7 不考虑货运车速度及运输时间因天气 交通等因素的影响 8 快递公司与客户以及客户与客户之间的距离 每天各客户所需物品的重量均视为不 变 2 2 2 符号说明符号说明 m 派出的货运车辆总数 N 客户的数量 Q 每台送货车的载重量 第 i 个客户与第 j 个客户之间的距离 ij c 第 i 个客户所需货品的重量 i q v 每台送货车的平均速度 送货车从客户点 i 到客户点 j 所需要的时间 ij t 送货车到 i 的时间 i t 送货车在客户点 i 卸货的时间 i s 第 i 个客户要求送货车到达的时间范围的下限 i a 第 i 个客户要求送货车到达的时间范围的上限 i b 三 问题分析三 问题分析 这是一个单配送中心 多客户点 非满载 带有时间窗的车辆配送路线问题 简 称 VRPTW 问题的解决在于对一系列客户点 组织适当的行车路线 使货运车有序 地通过它们 在满足一定的约束条件 各客户点货物需求量 交货时间 车辆载重限 制等 下 达到总行程最短的目的 问题一 题目要求建立送货车辆每天总运行里程最短的一般数学模型 因为问题 要求制定的配送方案与车辆数目和时间 包括 卸货时间和送货途中所需时间 有关 所以 首先对运货所需的车辆数进行预估 通过讨论时间窗口是硬窗口还是软窗口 本 题分别建立了两个数学模型 对于硬窗口的 VRPTW 问题 送货车必须在给定的时间 范围内到达客户点 所以加入对每辆运货车到达客户点的时间限制 综合求出总里程 数最短的路线 而对于软窗口的 VRPTW 问题 没有严格的时间限制 但是 货车早 到或晚到产生的损失和惩罚会对配送公司的成本产生影响 所以 配送方案应该保证 车辆行驶里程最短 且尽可能的在客户点要求的时间范围内到达 问题二 基于问题一的模型 将具体数据代入模型 即可求出最短的路程方案 首先根据总配送量和运货车载重限制约束 求出送货运车派遣辆数 然后根据配送中 心目标和客户点之间距离等 确定目标函数即最短行程模型 根据目标函数和时间窗 约束 采用数学软件 Lingo9 0 编写程序 最终得出各货运车的行程线路 3 四 模型的建立与求解四 模型的建立与求解 4 1 问题一的解答问题一的解答 4 1 1 模型的准备模型的准备 为了安排路线 我们首先要对送货车的数量进行估计 约束条件越多 则安排线 路越难 一辆车完成的任务越少 安排的车辆越多 我们可以按下述公式 1 估计所需货 车的数量 1 q m 1i i Q N 其中 表示取整 a 为参数 且 0 a3 1 2 0 0 6 4 0 0 8 5 7 0 运行总里程 910 千米 行程规划示意图 10 5 模型的评价与改进模型的评价与改进 5 1 模型的优缺点分析模型的优缺点分析 优点 优点 一 考虑全面 通过讨论客户对送货车辆的到达是否有严格的时间限制 分别建 立带软时间窗和硬时间窗的两个模型 同时 考虑到软时间窗的成本问题 创新性的 将惩罚及损失之和作为目标函数的一部分 保证了在行程最短的情况下配送成本不会 较高 二 约束条件完整 每个约束条件都与题目的内容一一对应 且比较清楚的在论 文中对每个式子的意义做了阐述 三 遗传算法的应用 利用遗传算法解决车辆路径规划问题 有广泛的适应性与 灵活性 缺点 缺点 1 值的不同会影响估计出来的车辆数 仅用一种值来确定车辆数目局限性很 大 二 模型具有局限性 只适用于客户点数较小且配送中心单一 送货车型号相同 的情况 5 2 模型的改进模型的改进 根据估算车辆数目的公式 1 q m 1i i Q N 对进行多次赋值 在保证车辆数目大于 3 辆 Q 8 的前提下 寻找接近于 m 的值 并带入模型 22q 8 1i i QQ3q2 8 1i i 将求出的解与 m 3 时求得的结果进行对比 得到使行程最短的配送方案 11 六 参考文献六 参考文献 1 中南大学 物流车辆调度问题研究 236315959 html 2013 8 7 2 朱树人 李文彬 匡芳君 一种带软时间窗的物流配送优化遗传算法 计算机工程与 科学 27 12 108 110 2007 3 胡一萍 徐海 一种基于粗糙集的模糊数学形态学方法 J 数据采集与处理 17 3 333 336 4 李军 谢秉磊 郭耀煌 非满载车辆调度问题的遗传算法 系统工程理论与方法应用 9 3 235 239 2000 5 周屹 李海龙 王锐 遗传算法求解物流配送中带时间窗的 VRP 问题 吉林大学学报 理学版 46 2 300 303 2008 6 阎庆 邰蕾蕾 用混合遗传算法解决有时间窗的车辆路径规划为题 安徽大学学报 自然科学版 31 2 41 44 2007 7 邹彤 李宁 孙德宝 不确定车辆数的有时间窗的车辆路径问题的遗传算法 系统工 程理论与实践 第 6 期 134 138 2004 8 张钦 李辉 带有时间窗约束的车辆路径问题的一种改进遗传算法 系统管理学报 19 5 589 592 2010 9 供应链网络物流配送与车辆路径问题 2013 8 7 七 附录七 附录 1 表 1 客户i12345678 吨 i q 21 54 531 542 53 小 i s 时 121322 530 8 ii a b 1 4 4 6 1 2 4 7 3 5 5 2 5 5 8 1 5 4 2 表 2 12 3 有关程序 MODEL SETS points 0 1 2 3 4 5 6 7 8 f point aim 1 2 3 4 5 6 7 8 timea timeb q s roads points points d x1 time between cars 1 3 reach 1 2 3 4 5 6 7 8 time reach road car roads cars x task car points cars y task aim point aim cars y1 ENDSETS DATA d 0 40 60 75 90 200 100 160 80 40 0 65 40 100 50 75 110 100 60 65 0 75 100 100 75 75 75 75 40 75 0 100 50 90 90 150 90 100 100 100 0 100 75 75 100 200 50 100 50 100 0 70 90 75 100 75 75 90 75 70 0 70 100 160 110 75 90 75 90 70 0 100 i j 012345678 004060759020010016080 140065401005075110100 26065075100100757575 37540750100509090150 49010010010001007575100 520050100501000709075 61007575907570070100 716011075907590700100 88010075150100751001000 13 80 100 75 150 100 75 100 100 0 m 3 timea 1 4 1 4 3 2 5 1 5 timeb 4 6 2 7 5 5 2 5 8 4 q 2 1 5 4 5 3 1 5 4 2 5 3 s 1 2 1 3 2 2 5 3 0 8 capacity 8 time between 0 0 8 1 2 1 5 1 8 4 2 3 2 1 6 0 8 0 1 3 0 8 2 1 1 5 2 2 2 1 2 1 3 0 1 5 2 2 1 5 1 5 1 5 1 5 0 8 1 5 0 2 1 1 8 1 8 3 1 8 2 2 2 0 2 1 5 1 5 2 4 1 2 1 2 0 1 4 1 8 1 5 2 1 5 1 5 1 8 1 5 1 4 0 1 4 2 3 2 2 2 1 5 1 8 1 5 1 8 1 4 0 2 1 6 2 1 5 3 2 1 5 2 2 0 ENDDATA min sum roads i j d i j sum cars k x i j k for road car