1、数学建模 送货问题第四届太原地区数学建模联赛承 诺 书我们仔细阅读了太原地区数学建模联赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C中选择一项填写）： C 我们的参赛报名号为： 05001
2、 参赛队员 (打印并签名) ：1. 彭琛 2. 乔冠中 3. 郝轶冬 日期： 2010 年 5 月 24 日第四届太原地区数学建模联赛我们的参赛报名号为： 05001 评阅记录评阅人:评分:备注:快递公司送货策略摘要目前，快递行业蓬勃发展，为生活带来诸多便利。对于快递公司，如何合理安排业务员的人数和派送路线，使快件在指定时间内送达目的地并且费用最省，成为一个十分重要的问题。本文通过对已知数据的分析，根据相关数学建模知识，解决了题目要求的实际问题。针对问题一：从利用人员最少，运行路程最短，人员工作时间和负重相对平均三个方面综合考虑，利用四叉树的思想划分区域确定业务员的运行路线，并建立物流配送模型
3、，用LINGO筛选出最佳路线，最后制定出公司送货策略的最佳方案。表一为所得结果：表一：最佳送货策略所需人数及运行总路程总路程总人数484km5人针对问题二，建立费用最省模型，并对结果进行优化处理，在5人负责八条总路程为484km的前提下，最后费用最少为15780.7针对问题三，在问题一的基础上，尽量保证时间的均衡，并用尽可能少的人完成投递任务。最终用四人完成投递任务关键词：四叉树 分区 物流配送模型 LINGO软件 费用最省模型 一、 问题重述目前，快递行业蓬勃发展，为生活带来更多方便。在合理条件下，用最少的人员获得最大的利润是快递公司需解决的实际问题。假设快递公司每个业务员每天平均工作时间不
4、超6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。平均每天收到快件总重量为184.5千克，假设送货运行路线均为平行于坐标轴的折线。需解决如下问题：（1）为该公司提供一个合理的送货策略；（2）如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略；（3）如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？表二为每个送货点的快件量T和坐标表二：各个送货点的快件质量及坐标 送货点快件量T (kg)坐标(km)送货点快件量T(kg)坐标(km)xy
5、xy1832163.521628.215175.86183654187.5111745.547197.815126308153.419954.5311216.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818图一为送货点的坐标分布图一：各送货点的坐标分布图一：送货点的散点分布图图一：送货点坐标分布图二、基本假设与符号说明31基本假设结合本题实际，为
6、了确保模型求解的准确性和合理性，我们排除了一些未知因素的干扰，提出了以下几点假设：1、 每个业务员每天平均工作时间、在每个送货点的停留时间和每次出发负重与题中所给条件相符，不会因任何原因发生变化；2、每个业务员送货往返途中始终维持题中给定速度，途中不会出现使速度变化的各种意外情况；3、每个业务员在送完当天货物后均需返回公司；4、每个送货点均处于平行两坐标轴的十字路口上，即业务员送货运行路线均为平行于坐标轴的折线5、每天所有快递均投递成功，不出现未签收需再次投递的情况；6、附件中所给出所有数据条件均合理，与实际相符。3.2符号说明表三；符号及其定义符号符号的意义第i个送货点的接货量第i个送货点到
7、第j个送货点的折线距离在第s区公司的费用支出三、 问题分析4.1制定合理的送货策略一个合理的送货策略是指每个业务员每天送货时间基本均匀，不会出现有的业务员每天只工作一两个小时，而有的业务员每天要工作六小时以上的情况。负责派送货物到距离较远的送货点的业务员，因为时间限制和体力耗费较大，可以每次携带较轻重量的货物。快递公司应尽量节约人力资源，从而降低成本。送货路线应安排合理，不要出现送货点的混乱，使有的送货点几个人同时送货，而有的送货点没有业务员去送货。根据这些合理性原则，我们给送货公司提供的策略中应包括需要的业务员人数，每个业务员的往返送货路线，以及总的时间和运行公里数。同时，尽量实现用最短路径
8、，最短时间和最少的人力资源。4.2费用最省策略当一个送货员的报酬是以行程和负重来来计算的时候，公司需要制定出费用最省策略，当每个送货员的送货的地点，和送货的路线都确定下来之后，一个送货员每天的报酬也就相应的得出来，所以确定送货员的个数和送货路线，即可确定最少费用。四、模型的建立与求解一般来说，配送问题主要研究如何有效地分配人员及有效的运行路线，以便在满足顾客需求的同时，尽可能地降低系统物流成本。对于运行路线的安排，在现实生活中，快递公司常把相对集中的一些点划分到一片区域，业务员负责各自固定的区域。这样的分配方式可使业务员熟悉业务，投递更加方便快捷，从而节省时间和成本。另外，合理的分区可使运行路
9、线达到最短，同样是节省时间和成本的体现。根据以上分析和准备，我们将逐步建立物流分区配送模型，进一步阐述模型的实际建立过程。4.1确定分区4.1.1配送分区的原则行车的路线可有以下两种方法确定：第一种方法是先求行车路线，再分段。即先对所有配送点利用旅行商等算法求出最优行车路线，然后根据各种约束条件(如车辆装载限制、运输时间限制等)对其路线进行分段，而在每l小段内，车辆按照确定的行车路线行驶；第二种方法是先分区，再求行车路线。即先根据各种约束条件进行配送区域的划分，然后各小区域内设计最优行车路线。两种分区方法所得结果大相径庭，有关研究表明【1】，属于第1类型的算法不能做到渐进最优，目前的研究主要集
10、中在第2种类型。因此，城市物流配送问题就简化为有装载限制的区域划分和区域内运行路线两个子问题。4.1.2分区方法的选择四叉树【2】 (qua&me)的思想由Klinger在1971年提出。很快在图象处理、空间数据结构描述等方面得到了广泛的应用。四叉树可以将地理空间进行不断的四等分，形成的网格，较好地描述了地理目标的空间位置和空间关系，具有良好的数据结构和地理目标快速检索等特点。在本模型中，运用四叉树的思想进行分区。选取地理上相对集中的送货点构造候选区位，候选区位内各送货点对快递的需求量总和等于或接近业务员最大的运送能力；对候选区位进行优化。确定结果进行分区。4.2物流分区模型的建立在运用四叉树
11、的思想建立模型时，需不断用四等分法分区并使最终每个区域内接收货物重量小于规定重量。具体方法如下：1、 平面直角坐标系的建立：建立以公司总部为原点(0，O)的平面直角坐标系，送货点采用相对坐标方式进行记录， =(，)。2、 四叉树生成：检索送货点中和最大的绝对值作为建立四叉树的最大网格边长。=max( | ，| ，|）=max(|，|，|)。以四叉树中网格包含的货物总需求量小于等于业务员最大承重量为基准进行四叉树的生成，当四叉树网格包含的需求点货物总需求量小于等于业务员最大承重量时，停止该四叉树网格的划分。则该四叉树网格为一个候选配送分区，剔除不包含需求点的四叉树网格。3、确定候选分区：选择距离
12、供给点最远端的四叉树网格，延逆时针方向进行网格中送货点的扩充。如果与之邻近网格中有方向度（四叉树与相邻8个网格连接，即为8个方向度）小于3的网格，则以邻近网格中最小方向度的网格为中心进行扩充。原网格作为次选网格。扩充的条件是：如果本网格的货物总需求量等于业务员最大承重量，则不进行扩充；如果本网格的货物总需求量小于业务员最大承重量，则延逆时针方向以最近原则选择相邻一定等级的网格内的送货点。使得配送区位的总需求量等于或接近业务员最大承重量，所选择的需求点从原从属网格中剔除。将无需求点的网格剔除后，形成非四叉树形式的配送区位。4、重复操作3，使每个送货点仅一次被选择入一个配送区位。5、将以上操作确定
13、的配送区位仍然作为候选区位，经过限定次数计算，进行配送区位优化。4.3物流分区模型的求解4.3.1.分区为便于描述，将送货点简化为坐标轴上的一个节点，用坐标表示位置。总公司位于原点。过点28和30分别做平行于X轴和Y轴的直线，作为建立四叉树最大网格的边长。X轴，Y轴，X=28，Y=20这四条直线确定四叉树的边缘。如图二所示，将此图四等分，不能满足网格包含的送货点货物总需求量小于等于业务员最大承重量。继续等分网格当将此图64等份时（如图四），可满足此条件。由于最远端四叉树网格邻近网格有方向度小于三的网格，故选择与最远点临近且方向度小于3的网格。沿逆时针方向以临近原则选择相邻网格内的点进行扩充直至
14、网格中供货点货物需求量小于或等于25，以此规则进行下一个分区直至所有点被分区完毕。图二：四叉树网格法一级图图三：四叉树网格法二级图图四：四叉树网格法三级图4.3.2.确定送货路线借助计算机工具LINGO确定各分区最佳送货路线，即总路程最短的路线，同时算出走此路线所耗时间。它们的情况分别如表四：表四：各分区路线和送货时间安排表各分区路线此分区送货时间1区0-1-4-6-2-01.71h2区0-3-8-12-9-02.47h3区0-10-22-21-11-02.82h4区0-23-60-28-29-04.59h5区0-15-27-25-03.3h6区0-17-24-26-03.62h7区0-12-
15、19-18-03.06h8区0-5-16-20-14-7-02.99h总路程484km人员安排：一人负责1区和5区的投递任务；一人负责2区和7区的投递任务；还有一人负责3区和八区的投递任务、剩下的4区和5区的邮递任务由于往返时间较长分别由一人负责完成，共五人完成投递任务，总计行程484km。具体行动路线如图五所示: 图五：四叉树配送分区路线图五、费用最省模型的建立5.1费用计算在上题中，我们由四叉树模型得出了合理的送货方案，当我们以最短路线进行送货时可以计算出各条线路的费用，例如 0 -3-8-12-9- 0 这条线路的费用= ,其他路线的费用所用计算方法与此类似将各线路费用相加得到我们这种模
16、型的总费用。如表五所示表五：费用最省模型的费用列表单位：元组数1区2区3区4区5区6区7区8区费用949.51169.11661.83241.92748.42496.81863.21989.2总费用16119.95.2.模型的改进一条线路中有n个送货点，由于费用的计算会依赖于两个点之间的距离和送货的质量，所以我们也不能很直接的说到底怎么走才能使这条线路上的费用最省。但是我们可以可定的使要将这n个点一次走完有中走法，每种走法都对应着不同费用，我们选择费用最省的一种走法，每条线路中都选择费用最省的走法，全部加起来，就是该策略下的最低费用。n个送货点条路径中任意走一条路径的费用为：=3+2，m1.2
17、,k1.2n一条路径上的最低费用为：=min()一个策略下的总费用为：=min为第i个送货点的接货量为第i个送货点到第j个送货点的折线距离为在第s区公司的费用支出m为每条路径上的各个送货点的送货量，包括原点和终点，原点和终点的质量都为0.处理这些数据，得到结果如表五所示表六：优化后的费用最省模型的费用列表费用最低路线单线路费用（元）总费用0-1-4-6-2-0949.515780.70-3-8-12-9-01169.10-10-22-21-11-01661.80-29-28-30-23-02997.90-15-27-25-02748.40-17-24-26-02496.80-13-19-18-
18、01863.20-7-14-20-16-5-01894六、 时间延长问题的解决时间由六小时延长至八小时后，公司通过安排可以由原五人完成的任务由四人完成，具体到每个人的安排如表七。表七：送货人员的送货路线组合送货路线送货用时（小时）人员安排每人工作时间（小时）1区0-1-4-6-2-01.71负责1区和4区6.34区0-23-30-28-29-04.592区0-3-8-12-9-02.26负责2区和6区5.886区0-17-24-26-03.623区0-10-22-21-11-02.82负责3区和5区6.125区0-15-27-25-03.37区0-13-19-18-03.06负责7区和8区6.
19、218区0-5-16-20-14-7-03.15七、模型评价7.1模型的优点1、本模型从业务员人数安排，路线安排，时间安排和业务员的负重等几个方面综合考虑，得出了最优的方案。安排合理且人性化；2、分区时运用四叉树的思想，没有可以寻求最优解，而是首先寻找可行解，然后进行适度优化，具有较强的普适性；3、 对于数据的筛选，依靠LINGO等软件实现，结果值得肯定。7.2模型的缺点1.在利用本模型解决问题时，难免出现时间分配不均的问题，而且时间限制越短，这种不均衡性越显著；2.本模型在处理问题时，是以每个投递点都存在十字路口为前提假设的，而在现实生活中，这种方法往往受限不能实现，存在一定的局限性。参考文献：1郭建宏，钱莲文，欧阳钟辉，彭道黎 基于GIS的城市水果物流分区配送辅助系统 中南林业科技大学学报 第27卷第4期 2007年8月2 雹亮，安敏，李欣 一种城市物流分区配送方法的研究 物流技术2003年第3期（总第126期） 2003年3Mark M.Meerschaert 数学建模方法与分析 北京 机械工业出版社 2009年4蔡锁章 数学建模 北京 中国林业出版社 2003年5胡列格 何其超 盛玉奎 物流运筹学 北京 电子工业出版社 20056袁新生 邵大宏 郁时炼 LINGO和EXCEL在数学建模中的应用 北京 科学出版社 2008
