第6组B题快递公司送货策略.doc

快递公司送货策略摘要：目前，快递行业正蓬勃发展，为我们的生活带来更多方便。本文针对业务员的送货策略，制定了多阶段最优决策的动态优化模型。在各种运货地点，重量的确定及业务员的运输条件、工作时间等各种约束条件下，按照平行于坐标轴的折线的送货路线，为公司设计要多少业务员，每个业务员的运行线路，以及总的运行公里数。对于问题一，制定了双目标最优化模型，得到了业务员总的运行公里数最短和派送业务员人数最少的目标函数，采用最短路径的Kruskal算法，并用MATLAB软件编程计算，得到最优树图，根据C+编程得到各送货点的距离，然后根据每人所带的快递重量克数，将最优树分成八条路径，最后根据最小环路定理，制定两种送货方案，通过比较最后得到八条最优送货方案的路程分别为20,46,60,54,68,56,76,98，总路程为478，业务员总人数为；5个；问题二，根据条件可知业务员的派送费用跟快件的重量有关，在最短路的基础上优先派送重量克数最多的快件，得到派送总费用为15567.5元，业务员人数为5，具体运行路线见方案一。问题三，延长业务员的工作时间到八小时，可以对问题一的模型进行优化，得到的人数为4人；关键词： 最优化模型 Kruskal算法 C+编程1.问题的重述这是一个快递员送货问题，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。如何花费最少的派送费用，即在运送完每天必须的快递时，使用最少的业务员。该题条件：（1）在八个小时内将快件运送完毕，（2）每个业务员每天的工作时间不超过6小时，（3）每个送货点停留的时间为10分钟，途中速度为25km/h，并且每次出发最多能带25千克的重量的货物。（4）为计算简便，将快件一律用重量来衡量，平均每天收到总重量为184.5千克。（5）送货路线为平行于坐标轴的折线。（6）每个送货点的位置和快件重量如表1考虑一下问题：问题一: 运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；问题二：如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略；问题三：如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？已知各货点的横纵坐标以及各货点的快件量情况如下图表1：表1送 货点快件量T (kg)坐标(km)送货点快件量T(kg)坐标(km)xyxy1832163.521628.215175.86183654187.5111745.547197.815126308153.419954.5311216.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.228182. 问题分析本文是合理的设计业务员送快递的问题，根据题中已知设计并求出每个业务员的最佳运行路线的数学建模问题，题中已给出每个送货点的位置和快件重量，要求根据已知题意和约束条件建立一个合理的送货策略来满足个问题的需要。问题一，要求业务员合理的运行路线，即要使得在尽量使业务员总的运行公里数最短的情况下，并尽可能的使业务员的总人数最少，根据题意首先采用Kruskal算法求最短路径的原理，又根据题中 =7.38，所以可以知道至少要有8个区域，确定八条合理的运行路线，根据题中早上9点钟开始派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每个业务员每天平均工作时间不超过6小时，确定了两种方案，最终得到总的运行公里数最短且业务员人数最少的双目标最优化模型。问题二：制定了单目标最优化模型，由于业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km，因此优先考虑快件最重的送货点作为出发点，得到各条路线的运行公里数，进而得到每条路径的派送费用。问题三，如果可以延长业务员的工作时间到8小时，为避免人力浪费，且满足条件，以业务员人数最少为单目标函数对模型进行优化求解。3.模型的假设与符号说明3.1模型的假设假设一：业务员同时从公司9:00开始出发；假设二：业务员运送快件的速度相同；假设三：业务员返回公司10分钟再进行下一次任务；假设四：只在计划内的送货点停留；假设五：送货运行路线均为平行于坐标轴的折线；假设六：各个业务员之间运送快件的任务是相互独立3.2符号说明 第k条路线业务员运行路线的公里数 第i个送货点到第j个送货点之间的距离 第k条路线业务员所带的快件总重量 第k条路线业务员运货点的个数 送货点的总个数 派送总费用4.模型的建立与求解4.1 模型的建立4.1.1 目标函数的确定由问题的分析，利用VC程序得出31个坐标两点之间的折线距离，再将各个送货点抽象为一个赋权连通图，各个送货点之间都可以运行，然后根据每人所带的快递重量数，将图分成八条路径，每两个点之间的距离=，为第k条路线业务员运行路线的公里数，要使派送人数最少和总路程最短的最佳运送路线，以及总的派送费用Y最少，确定的目标函数应该为：4.1.2 确定约束条件要使总路程最短，应尽量使每个子图的边权之和最小，又边权为，则有： 根据题意要求，可以得到以下约束条件：1. 每次出发最多能带25千克的重量，即，；2. 每个业务员每天平均工作时间不超过6个小时，即；3. 早上9点钟开始派送，要求于当天17点之前必须派送完毕4.2模型的建立与分析根据最短路径的Kruskal算法，并用MATLAB软件编程计算得到最优树图，如下图所示： Y20 24 28 17 30 18 26 15 16 29 20 25 14 19 27 5 4 8 12 10 7 13 15 236 5 2 21 3 111 9 5 10 10 15 20 22 X15105 图一每个业务员都是从公司即坐标原点出发，以最近的点作为出发点，以路程最短以及每个业务员携带快件不超过25kg为原则，进行划分得到八条合理的运行路线，并且制定了两条方案，各个方案的各条路线以及详细情况如下表所示;具体程序见附属； 方案一送货线路行进次序问题一问题二业务员分配路程（km）时间（h）费用（元）6小时8小时10-1-3-4-5-0321.95767.520-2-6-7-8-9-0402.43926.730-16-17-20-14-13-0603.23211540-12-11-10-0462.341733.850-22-21-15-19-0683.392758.860-18-24-25-0683.222554.970-27-29-0763.3742301.380-29-28-30-23-0984.5873142.8总计48824.52116300.85个4个注：、为业务员编号。方案一的运送路线见下图二:方案二送货线路行进次序问题一问题二业务员分配路程（km）时间（h）费用（元）6小时8小时10-1-3-2-0201.3638.420-4-7-5-16-6-0462.6741476.130-8-14-18-17-20-0603.2342156.140-10-22-21-11-9-0542.9941822.250-19-25-24-0683.222310.260-12-15-13-0562.741698.670-27-26-0763.374246880-29-28-30-23-0984.5872997.9总计47824.12315567.55个4个注：、为业务员编号。图二 方案二的运送路线见下图三:图三方案总路程总时间总费用业务员人数理论上最少人数6小时8小时6小时8小时一48824.52116300.85人4人4.087 3.066二47824.12315567.55人4人4.0205 3.016由上表所示：方案二更优化 5. 模型的评价优点：模型具有较强的实用性，对任意给出的各边权值的图，都能分为若干个子图，简化问题，便于求解。假设合理，具有很强的应用指导意义。缺点：模型只考虑了路程与时间两种因素，未考虑其他影响因素，忽略了现实生活中对模型有很大影响的重要指标，如人力资源等，并且模型均衡度差，业务员工作时长差异较大。这样模型的实用性就降低了。参考文献1：姜启源、谢金星、叶俊编，数学模型-3版，北京，高等教育出版社，2003.8 2：韩中庚，数学建模竞赛，北京，科学出版社，20073:徐权智，杨晋浩，数学建模M，北京：高等教育出版社，20054：宋来忠，数学建模与实验M，北京：科学出版社，2005附录：求两坐标点的距离程序如下:#include#include#includeusing namespace std;typedef structint i;int j;A;int main() int n;cout请输入坐标的数目n;A *section=new An;for(int k=0;kn;k+)cout请输入第k+1个坐标sectionk.isectionk.j;int m=0;while(mn-1)for(int k=m+1;kn;k+)cout(sectionm.i,sectionm.j) 与 (sectionk.i,sectionk.j)的距离是fabs(sectionm.i-sectionk.i)+fabs(sectionm.j-sectionk.j)endl; m+;return 0;最小生成树matlab源代码如下：clear;clc;n=31;a=zeros(n);a(1,2)=5;a(1,3)=6;a(1,4)=9;a(1,5)=11;a(1,6)=14;a(1,7)=8;a(1,8)=16;a(1,9)=15;a(1,10)=12;a(1,11)=14;a(1,12)=20;a(1,13)=20;a(1,14)=21;a(1,15)=22;a(1,16)=28;a(1,17)=18;a(1,18)=24;a(1,19)=28;a(1,20)=27;a(1,21)=21;a(1,22)=27;a(1,23)=21;a(1,24)=36;a(1,25)=34;a(1,26)=29;a(1,27)=37;a(1,28)=34;a(1,29)=44;a(1,30)=41;a(1,31)=46;a(2,3)=5;a(2,4)=4;a(2,5)=6;a(2,6)=9;a(2,7)=9;a(2,8)=11;a(2,9)=10;a(2,10)=7;a(2,11)=13;a(2,12)=15;a(2,13)=15;a(2,14)=16;a(2,15)=17;a(2,16)=23;a(2,17)=15;a(2,18)=19;a(2,19)=23;a(2,20)=22;a(2,21)=16;a(2,22)=22;a(2,23)=20;a(2,24)=31;a(2,25)=29;a(2,26)=24;a(2,27)=32;a(2,28)=29;a(2,29)=39;a(2,30)=36;a(2,31)=41;a(3,4)=5;a(3,5)=5;a(3,6)=8;a(3,7)=4;a(3,8)=10;a(3,9)=9;a(3,10)=12;a(3,11)=18;a(3,12)=18;a(3,13)=14;a(3,14)=15;a(3,15)=16;a(3,16)=22;a(3,17)=12;a(3,18)=18;a(3,19)=22;a(3,20)=21;a(3,21)=15;a(3,22)=21;a(3,23)=26;a(3,24)=30;a(3,25)=18;a(3,26)=23;a(3,27)=31;a(3,28)=28;a(3,29)=38;a(3,30)=35;a(3,31)=40;a(4,5)=4;a(4,6)=9;a(4,7)=9;a(4,8)=7;a(4,9)=6;a(4,10)=7;a(4,11)=13;a(4,12)=13;a(4,13)=10;a(4,14)=12;a(4,15)=13;a(4,16)=18;a(4,17)=15;a(4,18)=15;a(4,19)=19;a(4,20)=18;a(4,21)=12;a(4,22)=18;a(4,23)=20;a(4,24)=27;a(4,25)=25;a(4,26)=20;a(4,27)=28;a(4,28)=25;a(4,29)=35;a(4,30)=32;a(4,31)=37;a(5,6)=5;a(5,7)=5;a(5,8)=5;a(5,9)=6;a(5,10)=11;a(5,11)=17;a(5,12)=17;a(5,13)=11;a(5,14)=10;a(5,15)=11;a(5,16)=17;a(5,17)=11;a(5,18)=13;a(5,19)=17;a(5,20)=16;a(5,21)=10;a(5,22)=20;a(5,23)=24;a(5,24)=25;a(5,25)=23;a(5,26)=18;a(5,27)=26;a(5,28)=23;a(5,29)=33;a(5,30)=30;a(5,31)=35;a(6,7)=6;a(6,8)=6;a(6,9)=11;a(6,10)=16;a(6,11)=22;a(6,12)=22;a(6,13)=16;a(6,14)=11;a(6,15)=8;a(6,16)=18;a(6,17)=6;a(6,18)=10;a(6,19)=14;a(6,20)=13;a(6,21)=8;a(6,22)=25;a(6,23)=29;a(6,24)=26;a(6,25)=20;a(6,26)=15;a(6,27)=25;a(6,28)=20;a(6,29)=30;a(6,30)=27;a(6,31)=32;a(7,8)=8;a(7,9)=11;a(7,10)=16;a(7,11)=22;a(7,12)=22;a(7,13)=16;a(7,14)=13;a(7,15)=14;a(7,16)=20;a(7,17)=10;a(7,18)=9;a(7,19)=20;a(7,20)=19;a(7,21)=13;a(7,22)=25;a(7,23)=29;a(7,24)=28;a(7,25)=26;a(7,26)=21;a(7,27)=29;a(7,28)=26;a(7,29)=36;a(7,30)=33;a(7,31)=38;a(8,9)=5;a(8,10)=10;a(8,11)=16;a(8,12)=16;a(8,13)=10;a(8,14)=5;a(8,15)=6;a(8,16)=12;a(8,17)=12;a(8,18)=10;a(8,19)=12;a(8,20)=11;a(8,21)=5;a(8,22)=19;a(8,23)=23;a(8,24)=20;a(8,25)=18;a(8,26)=13;a(8,27)=21;a(8,28)=18;a(8,29)=28;a(8,30)=25;a(8,31)=30;a(9,10)=5;a(9,11)=11;a(9,12)=11;a(9,13)=5;a(9,14)=6;a(9,15)=7;a(9,16)=13;a(9,17)=17;a(9,18)=15;a(9,19)=13;a(9,20)=12;a(9,21)=10;a(9,22)=14;a(9,23)=18;a(9,24)=21;a(9,25)=19;a(9,26)=14;a(9,27)=22;a(9,28)=19;a(9,29)=29;a(9,30)=26;a(9,31)=31;a(10,11)=6;a(10,12)=8;a(10,13)=8;a(10,14)=9;a(10,15)=10;a(10,16)=16;a(10,17)=22;a(10,18)=20;a(10,19)=16;a(10,20)=15;a(10,21)=15;a(10,22)=15;a(10,23)=13;a(10,24)=24;a(10,25)=22;a(10,26)=17;a(10,27)=25;a(10,28)=22;a(10,29)=32;a(10,30)=29;a(10,31)=34;a(11,12)=6;a(11,13)=6;a(11,14)=11;a(11,15)=16;a(11,16)=14;a(11,17)=28;a(11,18)=26;a(11,19)=20;a(11,20)=13;a(11,21)=21;a(11,22)=13;a(11,23)=7;a(11,24)=22;a(11,25)=20;a(11,26)=15;a(11,27)=23;a(11,28)=20;a(11,29)=30;a(11,30)=27;a(11,31)=32;a(12,13)=6;a(12,14)=11;a(12,15)=16;a(12,16)=8;a(12,17)=28;a(12,18)=26;a(12,19)=20;a(12,20)=11;a(12,21)=22;a(12,22)=7;a(12,23)=7;a(12,24)=16;a(12,25)=18;a(12,26)=13;a(12,27)=17;a(12,28)=14;a(12,29)=24;a(12,30)=21;a(12,31)=26;a(13,14)=5;a(13,15)=10;a(13,16)=8;a(13,17)=22;a(13,18)=20;a(13,19)=14;a(13,20)=7;a(13,21)=15;a(13,22)=9;a(13,23)=13;a(13,24)=16;a(13,25)=14;a(13,26)=9;a(13,27)=17;a(13,28)=14;a(13,29)=24;a(13,30)=21;a(13,31)=26;a(14,15)=5;a(14,16)=7;a(14,17)=17;a(14,18)=15;a(14,19)=9;a(14,20)=6;a(14,21)=10;a(14,22)=143;a(14,23)=18;a(14,24)=15;a(14,25)=13;a(14,26)=8;a(14,27)=16;a(14,28)=13;a(14,29)=23;a(14,30)=20;a(14,31)=25;a(15,16)=12;a(15,17)=12;a(15,18)=10;a(15,19)=6;a(15,20)=5;a(15,21)=5;a(15,22)=19;a(15,23)=23;a(15,24)=20;a(15,25)=12;a(15,26)=7;a(15,27)=15;a(15,28)=12;a(15,29)=22;a(15,30)=19;a(15,31)=24;a(16,17)=24;a(16,18)=22;a(16,19)=16;a(16,20)=7;a(16,21)=18;a(16,22)=7;a(16,23)=11;a(16,24)=8;a(16,25)=14;a(16,26)=9;a(16,27)=9;a(16,28)=6;a(16,29)=16;a(16,30)=13;a(16,31)=18;a(17,18)=6;a(17,19)=10;a(17,20)=17;a(17,21)=7;a(17,22)=21;a(17,23)=35;a(17,24)=32;a(17,25)=16;a(17,26)=15;a(17,27)=19;a(17,28)=22;a(17,29)=16;a(17,30)=13;a(17,31)=18;a(18,19)=6;a(18,20)=15;a(18,21)=5;a(18,22)=29;a(18,23)=33;a(18,24)=30;a(18,25)=10;a(18,26)=13;a(18,27)=15;a(18,28)=18;a(18,29)=20;a(18,30)=21;a(18,31)=12;a(19,20)=9;a(19,21)=7;a(19,22)=23;a(19,23)=27;a(19,24)=24;a(19,25)=6;a(19,26)=7;a(19,27)=9;a(19,28)=14;a(19,29)=16;a(19,30)=15;a(19,31)=18;a(20,21)=10;a(20,22)=14;a(20,23)=18;a(20,24)=15;