3,4,5,6,7,8），lj为回路Lj的各边权之和。从公司角度考虑应使业务员尽量少，针对业务员每位走的路线应尽量接近，则确定的双目标最优化的目标函数应该为：
?minnum? ?8
minl?lkk?1???i?2 由问题一的分析知道此题属于NP问题，对于大型网络（赋权图），目前还没有一个求解旅行售货问题的有效算法，因此只能找一种求出相当好（不一定是最优）的解. 一个有效的方法是，根据最短路径的Dijkstra原理，用MATLAB软件编程计算得到图的最优树。如下图所示：
图一
由于在最优树上,各边权接近,要使最优树分解时, 分解结果尽量均衡，则各子图包含的顶点就应尽量接近4个，通过增环、扩环等方法，对子图内部进行适当调整优化，由此得到最优树的分解原则如下：
（1）每个分区点权的和?25
（2）分解点为O点或尽可能接近O点；
（3）分解所得的三个子图包含的顶点数尽可能接近4个； （4）尽量使分解所得的子图为连通图；
（5）尽量使子图与O的最短路上的点在该子圈内，尽量使各子图内部形成环路。 根据以上原则，得到分解后的结果如下图所示：
寻找出每个分支的最佳哈密尔顿（Hamilton）回路，运用LINGO软件编程计算得到结果如下表：
表2 分八组的路线 问题一
6
问题一 问题三
路线 0-1-3-2-0 0-6-16-5-7-4-0
经过点数 路程（km） 重量（kg） 时间（h） 业务员（6h） 业务员（8h）
3 5 5 4 3 4 3 3 30
20 45 60 46 68 62 96 86 483
22.2 23.7 24 24.7 25 22.2 20.2 22.5 184.5
1.3 2.63 3.23 2.51 3.22 3.15 4.34 3.94 24.32
① ③ ① ② ③ ② ④ ⑤ 5
① ② ② ③ ④ ④ ① ③
0-8-14-18-17-20-0 0-9-12-11-10-0 0-19-25-24-0 0-13-15-21-22-0 0-26-28-30-0 0-27-29-23-0
8
合计 4
注：1,2,3，……,30表示送货地点;①②……⑤表示业务员编号。编号相同表示同一业务员。
由表可知，每个业务员的运行路线、经过点数、携带重量，工作时间和费用。在工作时
间6h时需要5名业务员，总的时间为24.32h,总的路程为483km。 方案二 模型的建立 目标函数的确定
由图分析，坐标分布呈现弧形。首先通过弧形的方案，对临近点的连接，把30个地点分成八个区域如表三，且每个区域的重量都小于等于25kg，然后使用MATLAB软件找到每个回路的最优哈密顿圈。最后计算出业务员到每个区域送货需要的时间，把几个区域的时间相加接近6h的由一个业务员去送，即min num(num表示业务员总人数)。题目中给的送货点如下：
y2015105 510152025x 30个送货地点在坐标平面上坐标
模型的求解与分析
假设有八个业务员，算出每个业务员的时间，而总的时间为24.66h，这样的话，每个业务员的工作时间大约三个小时，不管是从公司的利益还是从现实的情况都不合理，
7
由此猜测，这八个业务员肯定有同一个人送不同路径的快件，而约束条件给定，每个业务员每天的平均工作时间小于六个小时，现在不管怎样组合总的时间一定，若为四个业务员，平均时间为6.15，大于6小时，不符题意。若为六个业务员，平均时间为4.1，与给出的六小时相差较多，故从公司利益来看，选择5个业务员较合理。具体的各项数据见下表。
表三
问题一 问题一 问题三
合计
路线 0-1-3-4-0 0-2-5-17-16-6-0 0-26-28-30-9-0 0-8-27-29-23-0 0-12-11-10-0 0-18-24-25-0 0-7-20-14-13-0
8
经过路程重量时间点数 （km） （kg） （h） 业务员（6h） 业务员（8h） 3 5 4 4 3 3 4 30
24 48 96 86 46 68 68 52
19.5 25 21.6 24.8 23.3 24.2 24.7 21.4
1.63 2.75 4.51 4.07 2.34 3.39 3.22 2.75
① ② ③ ④ ⑤ ① ③ ② 5
① ③ ② ④ ④ ③ ① ②
0-19-15-21-22-0 4
488 184.5 24.66 4
注：1,2,3，……,30表示送货地点;①②……⑤表示业务员编号。编号相同表示同一业务员。
由表可知，每个业务员的运行路线、经过点数、携带重量，工作时间和费用。在工作时
间6h时需要5名业务员，总的时间为24.66h,总的路程为488km, 根据算得路径可得出下图：
8
通过对比，发现方案一比较优越，所用时间短，路程也最短。所用时间为24.32h，路程为483km.所以该公司应采用模型一，每位业务员走的路线为表2 问题二： 建立模型
这是一个优化问题，由于业务员携带快件时速度为20km/h,酬金为3元/km*kg, 不携带快件时速度为30km/h,酬金为2元/km*kg,求费用最省策，即建立单目标最优化模型
?mj?1???lv,0?m??1?m?j??1???wp?i??w?ei??m0??min???? ???v0v1j?1???i?1?????确定约束条件 约束条件
8????s.t:
m0?3m1?2v0?20v1?30?we?j??184.5j?18wp?i??we?j???w?ek?k?1i?1
lvm?j??1,0vvm?j?i?1???i??l?0,v?m??1??m?j??j?v060?6?w?e??25 针对方案一和方案二利用Microsoft Visual C++ 6.0编程求出费用分别是15566.3，16203.5元。可知采用方案一费用较省。但费用还可以进一步优化，例如在满足条件的前提下改变业务员的行走路线或者改变业务员的人数以减少公司的费用 问题三
问题三建立在问题一的基础上，有计算和方案对比可知，如果业务员每天工作时间有6小时延长到8小时，在总时间和路径不变的3.075情况下，故需要四个业务员更合理而且算得这样的费用最省，具体情况如下表 ：
问题三
路线 0-2-3-1-0 0-4-7-5-16-6-0 0-8-14-18-17-0 0-10-11-12-9-0
路程
（km） 时间(h) 20 45 60 46
1.3 2.63 3.23 2.51
费用(元) 638.4 1476.1 2156.1 1676.4
业务员 ① ② ② ③
9
合计
0-19-15-25-24-0 0-22-21-15-13-0 0-26-28-30-0 0-27-29-23-0
8
68 62 96 86 483
3.22 3.15 4.34 3.94 24.32
2310.2 2032.8 2624 2652.3 15566.3
④ ④ ① ③
4
1. 模型的评价
1、模型的优点：
（1）本模型能够直观地看出各种策略的优缺点，便于决策。
（2）通过各种策略的横向比较，能直观地选出较优的解。而且模型简单易懂，便于理
解。
（3）模型系统的给出了业务员的行走方案，便于指导工作实践。 2、模型的缺点：
模型给出的约束条件可能有不太现实的，忽略了很多因素，这些因素在实际中不可忽略。问题一可以看到虽然模型一的总路线较短，但是每位业务员行走的路程差大，从业务员角度缺乏公平性
5参考文献
[1]：姜启源、谢金星、叶俊编，《数学模型》-3版，北京，高等教育出版社，2003.8 [2]：吴建国、汪名杰、李虎军、刘仁云编，《数学建模案例精编》-1版，北京，中国水利水电出版社，2005.5
[3]：邓微，MATLAB函数速查手册：人民邮电出版社，2008. 附录一： v1=20; v2=30; v3=25;
tm=input('猜输入题目序号（如第一题：1）：') if tm==1
fa=input('猜输入方案序号（如第一方案：1）：'); elseif tm==2
fa=input('猜输入方案序号（如第一方案：1）：'); end
X=[3 1 5 4 3 0 7 9 10 14 17 14 12 10 19 2 6 11 15 7 22 21 27 15 15 20 21 24 25 28];
Y=[2 5 4 7 11 8 9 6 2 0 3 6 9 12 9 16 18 17 12 14 5 0 9 19 14 17 13 20 16 18]; m=[8 8.2 6 5.5 4.5 3 7.2 2.3 1.4 6.5 4.1 12.7 5.8 3.8 3.4 3.5 5.8 7.5 7.8 4.6 6.2 6.8 2.4 7.6 9.6 10 12 6.0 8.1 4.2];
L1=[];L2=[];L3=[];L4=[];L5=[];L6=[];L7=[];L8=[];
sm=zeros(1,8);t=zeros(1,8);L=[];d=zeros(1,8);Q=zeros(1,8);jm=zeros(1,8); PX=[];PY=[];
s=['L1';'L2';'L3';'L4';'L5';'L6';'L7';'L8'];
10