数学建模

兰州交通大学2009年大学生数学建模竞赛论文题目：快递公司送货策略（B题）参赛人1：姓名学院班级参赛人2：姓名学院班级参赛人3：姓名学院班级论文编号：摘要本文是关于运输问题的优化设计问题。

该题我们的主要解题思路分三个阶段:第一阶段：我们先根据题设条件和基本假设画出该题的图。

第二阶段，我们根据图和点的位置关系结合题设，归纳出一些最基本的确定路线的原则：在仔细分析该题后，我们认为，该题为一个单目标规划题。

我们先抛开不携带快件时费用，若要把所有的邮件送到客户手中，，只要我们能够保证不携带快件路线最小，则所花费的时间和费用都是最小，因此解题的关键在于找出一个调度方案，使不携带快件的路线最少。

第三阶段则是编制程序阶段，我们结合下山法住店搜索，并引进随机生成器，在出现后继点权值相等难以判断以那点继续搜索时，由随机生成器确定。

为了让算法更接近人的思维，我们让更靠近都父点的子点有更高的几率被作为下一个将去的垃圾点，这也与我们的算法原则对应。

问题的解答如下：求得需要六个业务员；求的所需的总费用为1404.86元；所需时间为28.12小时。

路线分配图见正文。

快递公司送货问题的解决一、问题的重述目前，快递行业正蓬勃发展，为我们的生活带来更多方便。

一般地，所有快件到达某地后，集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。

假定所有快件在早上7点钟到达，早上9点钟开始派送，要求与当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。

为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位于坐标原点，每个送货点的位置和快件重量如下表所示，并且假设街道平行于坐标轴方向。

1.请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（需要多少业务员，每个业务员的运行线路，以及总的运行公里数）。

2.如果业务员负重时的速度是20km/h，获得酬金是3元/km*kg；而不携带快件时的速度是30km/h，酬金是2元/km，请为公司设计一个费用最省的策略。

点的分布如下图：二、基本假设1．送货人员路上的拐弯时间，意外事故耽搁的时间忽略 2．所有的货物必须在当天及时送完，不允许滞留。

3．工作时间内不堵车4．在每个送货点停留的时间都为10分三、基本变量，符号和用语|A| 表示A点到原点的距离，恒正|B| 表示B点到原点的距离，恒正|A-B| 表示A,B两点之间的距离,恒正Ta 表示A点所在地的快件量Spend 花费钱的数量Time 花费的时间序数号所在点的编号父点本点的上一点子点本点的下一点四、问题分析和数学模型的建立送货问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，不能直接套用Krusal，Prim等现成算法，于是根据具体问题设计出随机下山法，用计算模拟搜索，可以搜寻到令人满意的可行解。

先注意到两点的情况，设两点分别为A(x1,y1),B(x2,y2)。

主要有以下两种情况：4.1 A、B明显有先后次序。

--递减状态（如图1）不妨设x1>x2, y1>y2,不难看出A在B的后方,即A比B远。

对于前方参考点O,要将A,B对应垃圾点的垃圾全部取回再返回O,一共有三种方式：4.2 OàAàO, OàBàO单独运输。

这种情况下，总的路程消费等于不携带快件时(2元/km)与负重时的费用（3元/km*kg）的总和。

所需的总时间等于业务员所走过的总路程与速度（负重时的速度是20km/h，不携带快件时的速度是30km/h）的比值再加上在A,B两点停留的时间(每个送货点点上停留了10分钟，1/6小时)，于是有：Spend = 2*|A| + 3*|A|*Ta + 2*|B| + 3*|B|*TbTime = (|A| +|B|)/20+ (|A| +|B|)/30+1/6*24.3 OàAàBàO先远点再近点，即先负载至最远处，送完A点后再返回至B,再回O点，有： Spend =2*|A| + 2*|A-B|*Ta +3*|B|*(Ta+Tb)+2*|B|Time = |A+B|/20 + |B|/30+1/6*24.5 OàBàAàO先近点在远点，即先送B点快件，然后载着A点的快件奔至A点，再回O点，有：Spend = 2*|B| + 2*|A-B|*Tb + 3*|A|*(Ta+Tb)+ 2*|A|Time = |A|/20 + 1/6*2+|A|/30比较以上三种情况，远近点的遍历顺序，可以看出，“先近后远”绝对比“先远后近”在花费钱的数量上要少的多，省出部分的钱主要是车载着B点的快件奔到A点再返回B点。

而又注意到两者的时间花费是相等的。

所以在其余同等的情况下选择“先近后远”，这也符合人的做法。

考虑到时间上单独运输比其余的两种运输要大的多，而且花费的钱仍不比“先近后远”省，所以一般情况下，不采用单独运输。

4.6 A，B两点没有明显先后顺序。

并邻状态（如图2）还是一共有三种情况：1．OàAàO, OàBàO单独运输。

这种情况下，跟A,B两点有先后顺序中的情况完全相同，即有：spend = 2*|A| + 3*|A|*Ta + 2*|B| +3*|B|*Tbtime = (|A| + |B|)/20 +(|A| + |B|)/30+1/6*22．OàAàBàOSpend = 2*|A| + 3*|A-B|*Ta + 3*|B|*(Ta+Tb) ----〈1〉Time = (|A| + |A-B| + |B|)/20 +(|A| + |A-B|+|B|)/30+ 1/6*23. OàBàAàOSpend = 2*|B| + 3*|A-B|*Tb +3*|A|*(Ta+Tb) ----〈2〉Time = (|A| + |A-B| + |B|)/20+|A-B|+|B|)/30+ 1/6*2相比之下，清晰可见并邻状态下的单独运输所花的费用最少，所以在不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱。

用<1>式与<2>式相减除以1.8，得到如下判断式：|A-B|*(Ta-Tb) + (Ta+Tb)*(|B|-|A|) ----<3>上式 < 0时，选0àAàBàO;上式 > 0时，选OàBàAàO;上式 = 0时，任意选上述两路线。

4.7 两点选择趋势的讨论。

（如图3）由图中看到B,C两点没有明显的先后顺序，属于并邻点。

因为当业务员负重时费用会成倍的增长，比其不携带快件时所花费用要大的多，所以排除AàBàC或AàCàB这样的一次经过3点的往返路线，仅选择B,C中的某一点与A完成此次运输，将另一点留到下次。

那么A点选择B还是C呢？不妨假设|B|>|C|,即B点离原点的距离比C点的更远，因为A在B,C之后，所以也就是B点离A点更近。

这样，此次的运输我们更趋向于选择AàB,因为就这三点而论，A无论是选B还是C，三点的快件总要送完，所以花费的钱是一样的。

但选择AàB后，下次业务员送C点快件时就无需跑的更远。

五、基于人的心理问题的讨论业务员在送快件时会选择先送近点再送远点，这与我们算出的一致的。

综上所述，得出搜索的基本原则：1．在两点递减的情况下，不采用单独送货；2．在其余同等的情况下选择“先近后远”；3．不要求时间的情况下对于并邻两点，采用单独送货的方式最节约钱；一般情况下用式<3〉作判断；4。

每一次布局和每条线路的搜索不妨由剩下未搜点中的最大值开始。

六、计算机随机搜索算法的编制和实现根据上面确立的几个搜索原则做出相应的随机算法应用计算机搜索出最优可行解。

七、算法中点的数据结构简述1.用数组表示链表结构根据30个点状态做出一个36*5的大数组，如下表序数号父点子点快件量(kg) 权值1 9 -1 1.5 82 0 -1 1.5 8.23 13 -1 0.6 6。

29 18 7 1.5 8.130 0 23 1.3 4.2规定，搜索方向由近到远（由上到下），其中序数号表示的是当前点的位置，父点即当前环中当前点的上点，子点即当前环中当前点的下一点，快件量即表示该点中要送的快件数，权值表示该点被修改过的次数。

一个表与一个固定的布局（即一个搜索结果）一一对应，称这样的表为布局表。

算法的最终目的就是要找到最好的布局表，使得花费的钱和时间最少，达到我们的目的。

布局表表示了一个布局中各点的状态，它们的父点和子点以及权值，这样就能确定具体的连接路线。

这样的叙述方式跟链表一致，这里是借助数组来建立链表关系，在搜索数目较少的情况下还是可行的。

2.基本信息的数组存放为了搜索方便，此处将题目给的地理坐标数据表中各点的具体位置信息用数组的形式储存。

用MAP来表示，MAP是一个30*20的大矩阵，如MAP(3,2) = 1就表示表示点1的X坐标为3，Y坐标为2，又如MAP(27,9) = 23就表示点23的X 坐标为27，Y坐标为9；特别的在没有的点的地方一律用31来表示，即除了原点MAP(0,0)=31,外，在(4，8)这里也没有点，则有MAP(4,8)=31。

八、随机搜索算法具体叙述1．基本思想。

问题要求搜索出一条最短路线，但又与业务员员等问题有所区别，本问题搜索的不完全是最优回路问题，而更像是单支路覆盖问题，也是NP难问题，没有现成的多项式次数的算法，所以自行设计了一种随机搜索算法。

基本思想是结合下山法逐点搜索，并尝试引入随机生成器剪枝提高搜索速度，整个算法利用链表结构实现。

2．算法流程一次布局开始à 确定搜索点总集P ，判断集P非空：若空，则一次布局结束；非空，则M=max(|P|),即M为P集中距离原点(0,0)的最远点。

L=M,。

（具体见下面的流程图，图4）图4九、问题的搜索结果1.在不考虑其他因素的情况下 --问题的解答。

业务员的最优路线如下：（见图5）图52. 路径第一组最短路径为：0→6→16→17→24第二组最短路径为：0→18→26→28第三组最短路径为：0→5→20→25第四组最短路径为：0→2→4→7→14第五组最短路径为：0→3→8→13 →19第六组最短路径为：0→15→27→29第七组最短路径为：0→12→21→23→30第八组最短路径为：0→5→9→11第九组最短路径为：0→15→223.最终送货路径经计算需要五个业务员即可，其各自的送货路径是第一个业务员路径为：0→6→16→17→240→5→20→25（即走第一、三路径）第二个业务员路径为：0→12→21→23→30 →0→15→22（即走第七、九路径）第三个业务员路径为：0→2→4→7→14→0→3→8→13 →19（即走第四、五路径）第四个业务员路径为：0→15→27→29→0→5→9→11（即走第六、八路径）第五个业务员路径为：0→18→26→28（即走第二路径）4.结果总时间28.12小时，总费用1404.86元十、模型的优缺点该模型优点是算法简单，容易实现，精度特别是后两个模型的精度不是很高，十一、模型的改进方向1．随机生成器的设计；2．可以引入专家系统，增强算法的灵活性，更人性化；3．若用模拟退火法或遗传算法，能更快地搜到较好的结果。