送货路线设计问题--数学建模-优化 联系客服

发布时间 : 星期日 文章送货路线设计问题--数学建模-优化更新完毕开始阅读

24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14

7790 4435 10860 10385 565 2580 1565 9395 14835 1250 7280 15305 12390 6410 13915 9510 8345 4930 13265 14180 3030 10915 2330 7735 885 11575 8010 9330 9525 9635 10500 9765 9865 9955 10100 10365 10900 11065 11375 11415 11510 11610 12050 12300 13650 14145 14215 15060 14235 14500 14550 14880 15160 15325 位置点2 3 8 20 4 8 4 2 15 2 1 18 1 12 14 5

表3 相互到达信息

位置点1 1 1 2 2 3 3 4 5 5 6 7 7 8 9

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

9 10 10 11 12 12 12 13 13 13 14 14 14 14 15 15 16 17 18 19 20 21 21 21 22 23 24 25 25 25 27 28 29 30 30 31 31 32 32 33 33 34 35 10 18 7 12 13 25 15 18 19 11 18 16 17 21 22 25 23 23 31 24 22 26 36 17 30 17 31 41 19 29 31 33 22 28 41 26 34 35 23 46 28 40 38 6

58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 36 36 37 38 39 40 40 41 41 41 42 42 43 44 44 45 45 46 47 48 49 49 50 O O O 45 27 40 36 27 34 45 44 37 46 43 49 38 48 50 50 42 48 40 44 50 42 40 18 21 26 快递公司送货策略

一 摘要:

本文是关于快递公司送货策略的优化设计问题,即在给定送货地点和给定设计规范的条件下,确定所需业务员人数,每个业务员的运行线路,总的运行公里数,以及费用最省的策略。 本文主要从最短路经和费用最省两个角度解决该问题,建立了两个数据模型。模型一:利用“图”的知识,将送货点抽象为“图”中是顶点,由于街道和坐标轴平行,即任意两顶点之间都有路。在此模型中,将两点之间的路线权值赋为这两点横纵坐标之和。如A(x1,y1),B(x2,y2)两点,则权值为D=|x2-x1|+|y2-y1|。并利用计算机程序对以上结果进行了校核。模型二:根据题意,建立动态规划的数学模型。然后用动态规划的知识求得最优化结果。根据所建立的两个数学模型,对满足设计要求的送货策略和费用最省策略进行了模拟,在有标尺的坐标系中得到了能够反映运送最佳路线的模拟图。最后,对设计规范的合理性进行了充分和必要的论证。 二 关键词:

快递公司送货 最优化 图模型 多目标动态规划 TSP模型

7

三 问题重述:

在快递公司送货策略中,确定业务员人数和各自的行走路线是本题的关键。这个问题可以描述为:一中心仓库(或配送调度中心) 拥有最大负重为25kg的业务员m人, 负责对30个客户进行货物分送工作, 客户i 的快件量为已知 , 求满足需求的路程最短的人员行驶路径,且使用尽量少的人数,并满足以下条件:

1) 每条送快件的路径上各个客户的需求量之和不超过个人最大负重。 2) 每个客户的需求必须满足, 且只能由一个人送货.

3)每个业务员每天平均工作时间不超过6小时,在每个送货点停留的时间为10分钟,途中速度为25km/h。 4)为了计算方便,我们将快件一律用重量来衡量,平均每天收到总重量为184.5千克。 表一为题中所给的数据:

表一 最大载重量 途中的平均速度 25kg 25km/h 重载时速 重载酬金 空载时速 空载酬金 20km/h 3元/km*kg 30km/h 2元/km 业务员工作时间上限 6h 每个送货点停留时间 10min 备注 1、快件一律用重量来衡量 2、假定街道方向均平行于坐标轴 处于实际情况的考虑, 本研究中对人的最大行程不加限制.本论文试图从最优化的角度,建立起满足设计要求的送货的数学模型,借助于计算机的高速运算与逻辑判断能力,求出满足题意要求的结果。 四 问题分析:

从公司总部配出一个人,到任意未配送的送货点,然后将这个人配到最近的未服务的送货点范围之内的邻居,并使送货时间小于6小时,各送货点总重量不超过25kg。继续上述指派,直到各点总重量超过25kg,或者送货时间大于6小时。最后业务员返回总部,记录得到的可行行程(即路线)。对另一个业务员重复上述安排,直到没有未服务的送货点。对得到的可行的行程安排解中的每一条路径,求解一个旅行商问题,决定访问指派给每一条行程的业务员的顺序,最小化运输总距离。得到可行解的行程安排解后退出。

根据题意的要求,每个人的工作时间不超过6小时,且必须从早上9点钟开始派送,到当天17点之前(即在8小时之内)派送完毕。且?列出了题中任意两配送点间的距离。

表二:任意两点间的距离矩阵

?184.5kg???8,故至少需要8条路线。表二

25kg?? 8