快递公司送货.doc

PAGE PAGE PAGE PAGE 1 PAGE PAGE 1 快递公司送货策略 指导教员：贺天宇 组员 吴鑫志 戴孟刚 韦伟 曹俊 摘要 本文通过建立模拟退火、遍历搜索和规划分析模型从不同角度出发，给出了合理的送货路线模型和策略。 对于问题一，本文建立了模拟退火模型。针对不同的要求，考虑了最短路径、最小载重方差和最短运送时间总和，利用模型分别求解出最优方案。经过对不同最优方案比较发现，当最短路径时，各方面的因素都达到较优水平。方案需要5个邮递员，路线分别为：路线一、 和，路线二、和，路线三、，路线四、，路线五、。总的行运公里数为490km。 对于问题二，通过0—1规划模型，通过编程得到费用最少的路径。又兼顾了路程、时间的约束，建立优化方案，最终得到路径的总距离为542km酬金为13895.6元，至少需要5个邮递员。 对于问题三、工作时间调至八小时时，无论对总公里数还是总酬金都没有影响，本文通过建立规划模型，得到了在工作时间8小时的约束下最优的路径。通过对结果改进，至少需要4个邮递员，总路线长为498km。 关键字： 模拟退火 0-1规划 广度搜索 一 问题重述 目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。 假定所有快件在早上7点钟到达，早上9点钟开始派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位于坐标原点处（如图1），每个送货点的位置和快件重量见下表，并且假设送货运行路线均为平行于坐标轴的折线。 （1）请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）； （2）如果业务员携带快件时的速度是20km/h，获得酬金3元/km?kg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略； （3）如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？ 表1 送货点的信息 送货点 快件量T (kg) 坐标(km) 送货点 快件量T (kg) 坐标(km) x y x y 1 8 3 2 16 3.5 2 16 2 8.2 1 5 17 5.8 6 18 3 6 5 4 18 7.5 11 17 4 5.5 4 7 19 7.8 15 12 6 3 0 8 15 3.4 19 9 5 4.5 3 11 21 6.2 22 5 7 7.2 7 9 22 6.8 21 0 8 2.3 9 6 23 2.4 27 9 9 1.4 10 2 24 7.6 15 19 10 6.5 14 0 25 9.6 15 14 11 4.1 17 3 26 10 20 17 12 12.7 14 6 27 12 21 13 13 5.8 12 9 28 6.0 24 20 14 3.8 10 12 29 8.1 25 16 20 4.6 7 14 30 4.2 28 18 图1 送货点分布图 二 符号说明 ：第个点与第个点之间的距离； ：第个送货点的横坐标； ：第个送货点的纵坐标； ：第条路线； ：第个送货点的货物重； ：实数对数矩阵； ：零点与第m条路线上的第i个点之间的距离； ：第条路线上的第个点； ：第个点的排序位置。 ：路线排序点集 三 模型假设 1、邮递员在公司滞留的时间不进行考虑，即假设在公司的时间为0； 2、送货员在任意两点间的送货距离为任意两点间横纵坐标差的和； 3、数据真实固定，即每一送货点的坐标、货物重量永久恒定； 4、邮递员在送货过程中只受工作时间、载货重量、路径长短和酬金的影响，其它因素忽略。 四 问题分析 本文要求建立合理的数学模型，针对不同的问题要求，求解出合理的邮递路线。 问题一要求建立模型，给出合理的邮递路线。对于30个邮递点，假设有且仅有一次通过，建立合理的模型，从时间最短、路途最短和邮递次数最少三方面的约束，给出最优路线后再进行比较。本文选择模拟退火的算法，建立类似于TSP最短路径的模型求解。对于时间，每个邮递员最多的工作时间为6小时，可以用工作时间对路线进行合并，以优化模型结果，并且节约人力资源。本文就三方面时间最少、路径最短载重量多，建立模型。通过模型求解，分别得到了