送货最优问题
摘要
本文是关于快递公司送货策略的优化设计问题,即在给定送货地点和给定设
计规范的条件下,确定所需业务员人数,每个业务员的运行线路,总的运行公
里数,以及费用最省的策略。
本文主要从最短路经和费用最省两个角度解决该问题,建立了两个数据模型。
模型一:利用“图”的知识,将送货点抽象为“图”中是顶点,由于街道和坐标
轴平行,即任意两顶点之间都有路。在此模型中,将两点之间的路线权值赋为
这两点横纵坐标之和。如 A(x1,y1),B(x2,y2)两点,则权值为 Q=|
x2-x1|+|y2-y1|。并利用计算机程序对以上结果进行了校核。经典的 Dijkstra
算法和Floyd 算法思路清楚、方法简便,但随着配送点数的增加,计算的复杂性
以配送点数的平方增加,并具有一定的主观性. 所以本研究在利用动态规划法的
基础上引入扑食搜索法的原理,提高辆车的装载率,从而减少车辆的需求,达到降
低成本的目的.
模型二:根据题意(B 题),建立动态规划的数学模型。然后用动态规划
的知识求得最优化结果。
根据所建立的两个数学模型,对满足设计要求的送货策略和费用最省策略
进行了模拟,在有标尺的坐标系中得到了能够反映运送最佳路线的模拟图。最
后,对设计规范的合理性进行了充分和必要的论证。
1 问题的提出
在快递公司送货策略中,确定业务员人数和各自的行走路线是本题的关键。这
个问题可以描述为:一中心仓库(或配送调度中心) 拥有最大负重为 25kg 的业务
员 m 人, 负责对 30 个客户进行货物分送工作, 客户 i 的货物需求为
以知
, 求满
足需求的路程