内容发布更新时间 : 2024/5/1 22:18:17星期一 下面是文章的全部内容请认真阅读。
2008高教社杯全国大学生数学建模竞赛
承 诺 书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）： 中原工学院信息商务学院 参赛队员 (打印并签名) ：1. 程欢欢 2. 郭亚楠 3. 宋响 指导教师或指导教师组负责人 (打印并签名)：
日期： 年 月 日
1
编 号 专 用 页
评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
2
快递公司送货策略
摘 要
本文是解决业务员送快件路程安排的问题。业务员至少经过每个送货点一次，为合理安排业务员的工作，建立一个双目标最优化模型和一个单目标最优化模型。
对于问题一,建立了双目标最优化模型。将问题一转化为八个售货员的最佳旅行售货员问题，采用最短路径的Dijkstra算法，并用matlab软件编程计算，得到最优树图，然后按送货点的快件质量总和25kg标准将最优树分成八块，最后根据最小环路定理，利用lingo编程。得到八组的路线。根据送货点位置特点进一步优化
对于问题二，根据费用最少建立单目标最优化模型，确定约束条件。利用
microsoftvisual软件c??6.0求得较优的方案
对于问题三, 在问题一的双目标最优化模型的基础上，结合实际。重新安排业务员
的工作。
关键词：双目标最优化模型 单目标最优化模型 Dijkstra算法 最佳旅行售货员
最优哈密顿圈 最小生成树
1. 问题的重述
目前，快递行业正蓬勃发展，为我们的生活带来更多方便。对于快递公司，保证快件能够在指定的时间内送达目的地的前提下，如何才能使业务员人数最少，派送费用最低
1：所有快件在早上7点钟到达，早上9点钟开始派送，要求于当天17点之前必须派送完毕
2：每个业务员每天平均工作时间不超过6小时
3：在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。
为计算简便，快件一律用重量来衡量，平均每天收到总重量为184.5千克。公司总部位于坐标原点处（如图表1），每个送货点的位置和快件重量见下表，并且假设送货运行路线均为平行于坐标轴的折线。
本文需要解决的问题：
1：请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；
2：如果业务员携带快件时的速度是20km/h，获得酬金3元/km?kg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略；
3：如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？
表一
3
送货点 1 2 3 4 6 5 7 8 9 10 11 12 13 14 20 快件量T (kg) 8 8.2 6 5.5 3 4.5 7.2 2.3 1.4 6.5 4.1 12.7 5.8 3.8 4.6 坐标(km) x y 3 2 1 5 5 4 4 7 0 8 3 11 7 9 9 6 10 2 14 0 17 3 14 6 12 9 10 12 7 14 送货点 16 17 18 19 15 21 22 23 24 25 26 27 28 29 30 快件量T (kg) 3.5 5.8 7.5 7.8 3.4 6.2 6.8 2.4 7.6 9.6 10 12 6.0 8.1 4.2 坐标(km) x y 2 16 6 18 11 17 15 12 19 9 22 5 21 0 27 9 15 19 15 14 20 17 21 13 24 20 25 16 28 18 2.问题的分析
若将每个公司总部和送货点看成一个图的顶点，各送货点与送货点，送货点与公司总部的连线看作此图对应顶点间的边，每两个地点的行走距离（横纵坐标差的绝对值之和）看作对应边上的权，所给送货点就转化为加权网络图，问题就转化图论中一类称之为旅行售货员的问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权（路程或时间）最小. 本题所求的业务员的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又可使边上的权之和达到最小的闭链（闭迹）,即最佳旅行售货员问题。
针对问题一：在平均时间、重量的约束条件下建立了一个双目标最优化的模型，求出一个合理的运货策略，使得业务员的人数尽量少并且使每个业务员平均路程尽量接近。 由每天送快件的总重量和每位业务员每次所能携带总重量的限制得：每天收到货的总重量／出发最多带的重量?184.5?7.38，即至少送快件八次才能将所有的快件送完。于是问
25题转换为8名售货员的最佳路线问题。
针对问题二：在问题一的基础上求出业务员的数目num，由于业务员携带与不携带快件的酬金不同，为使费用最低即使发费在每位业务员的费用最低。因此建立求费用最省的单目标最优化模型。通过方案的对比，求出最省的费用策略。
针对问题三：若把业务员平均每天六个小时的工作时间改为八个小时，在原来的基础上把六小时的约束条件改为八小时，再根据每组所得的时间合理的组合起来，使每个业务员的工作时间尽量相同。 模型假设：
3.模型的假设与符号说明
3.1模型的假设
4
1. 每次业务员从一个区送货回来，再配货的时间为0，即不花时间。 2. 街道平行于坐标轴。
3. 业务员中途不休息，运货途中快件没有损坏，业务员运送过程也十分安全，没有堵
车等问题，并且业务员很敬业，即一切顺利。
4. 业务员不会中转邮件，即不会中途交给另一个业务员。 5. 每个送货点每天的邮件量基本相同。
6. 在业务员出发后到达邮局的邮件均算入第二天的邮件量。
7. 业务员送完货后必须到公司报到，各个业务员之间运送快件的任务是相互独立。 8. 每个业务员每天的工作时间不超过6小时。
9. 每个送货点停留的时间为10分钟，途中速度为25km/h，并且每次出发最多能带25
千克的重量的货物。
10. 快件一律用重量来衡量，平均每天收到总重量为184.5千克。 3.2符号说明
G(V,E):赋权连通图; W(ei):边ei的边权; W(vi)：点vi的点权; lk: Lj的各边权之和; V：邮递员的速度; V0:邮局所在地;
m(j):第j个区域送货的地点数目； M(j):第j个区域送货的地点数目；
Wp(i):第j个区域到第i个点时快件剩余重量；
V(m(j) o):第i个区域最后一个送货点到快递公司的距离； V0:带快递时的速度；
mo:带快递时的每千米每千克的费用； v1:不带快递时的速度；
m1: 不带快递时的每千米每千克的费用； we(j):第j个区域送货总重量; num:业务员的数目
其他符号在文中用到时给出说明.
4.模型的建立与求解
问题一
1模型的建立
由各送货点的坐标，按照与坐标轴平行行走的方法利用Microsoft Visual C++ 6.0软件得到每条边的权。由问题的分析，将送货路线抽象为一个赋权连通图G(V,E)，再
j=1,2,3，j=1,2，把图G分成八个子图G（4,5,6,7,8）,在每个子图中寻找最佳回路L（jj 5