快递公司送货策略优化模型

快递公司送货策略优化模型摘要快递是快递公司快速收集、运输和递送客户文件、物品或货物的一种服务.合理选择送货线路并制定业务员分派方案是极其重要的,它不仅可以加快配送速度,提高服务质量,还可以有效的降低配送成本,增加经济效益.对此,本文重点讨论的问题是快递公司如何雇佣多少业务员送货,如何确定每个业务员的运行线路以达到费用最省的目的.此问题属于中国邮递员问题.针对问题一,利用蚂蚁算法中的单回路TSP问题算出所有点最短路线，并构建TSP回路，得到30最短路线图及分段图和关于每个业务员的送货路线，所用时间，总邮件量和总路程的表格，然后按照要求进行分段，得到一种送货方案；再利用蚂蚁算法中的多回路VRP问题求出另一个送货方案，将两种方案进行比较，制定出有效合理的送货策略，为公司提供一个优化的业务员行程安排；针对问题二,是问题一的具体化.建立起以费用为目标的目标函数，将问题转化成求最少费用的TSP回路.再根据业务员的时间，携带量和路线的约束建立约束函数，运用MATLAB编程求得业务员酬金最少的第三种方案。并和问题一的方案进行比较，考虑时间均衡度,制定出业务员的最佳送货策略。针对问题三,结合前两种送货方案，进行重新组合得到了将业务员工作时间调至8小时的结合人数和费用的优化送货方案。关键词蚂蚁算法单回路TSP问题多回路VRP问题一、问题重述目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。假定所有快件在早上7点钟到达，早上9点钟开始派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位于坐标原点处（如图2），每个送货点的位置和快件重量见下表，并且假设送货运行路线均为平行于坐标轴的折线。（1）请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；（2）如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略；（3）如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？二、模型假设2.1每次业务员从一个区送货回来，再配货的时间为0，即不花时间。2.2业务员不会发生意外，即不会意外的花一些时间。2.3业务员中途不休息。2.4与业务员走的路都为横纵坐标。2.5街道平行于坐标轴。2.6业务员在中途除了送货之外没有别的时间耽搁。2.7业务员不会中转邮件，即不会中途交给另一个业务员。2.8每个送货点每天的邮件量基本相同。2.9在业务员出发后到达邮局的邮件均算入第二天的邮件量。三、符号说明3.1业务员的酬金----------Spend;3.2业务员完成某线路的时间---------Time;3.3第i个送货点的邮件量--------qi(i=1,2,3,…,30);3.4送货点i到j的距离为---------d(i,j);3.5第k个业务员去的送货点-------nk;3.6蚂蚁k下一步被允许去的送货点--------3.7第i个送货点的坐标--------（Xi,Yi）;3.8ai,若ai=1表示业务员去i号送货点送邮件，ai=0表示不去i号送货点送邮件；3.9bi,若bi=1表示i号送货点是某条线路的终点，若bi=0则表示i号不是送货的终点；四、模型分析对送货点分布图分析可知，注意到两点的位置情况主要有以下两种，设两点。（1）A，B两点有明显先后顺序，如下图1：图1不妨设A在B的后方，即X1X2,Y1Y2,业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km，A，B的邮件量分别为Ma和Mb,要送完A,B两点的邮件一共有三种方式，即单独送货，0—A—0,0—B—0,其酬金和送货时间有(算酬金时要考虑邮件量)：Spend=3*A*Ma+2*A+3*B*Mb+2*B；Time=(A+B)/12+1/3；第二种送货方式为先近后远，即0—B—A—0，则有：Spend=3*B*Mb+3*A*Ma+2*a;Time=A/12+1/3;第三种送货方式为先远后近，即0—A—B—0，则有：Spend=3*A*(Ma+Mb)+3*(A-B)*Mb+2*B;Time=(2*A-B)/30+B/20+1/3;通过比较发现，先近后远比先远后近给业务员的酬金和业务员送货花的时间都要少的多，所以在选择路径时采用先近后远的原则。（2）A,B两点没有先后顺序，如下图2：图2此时A，B到原点的距离相等，即有X1+Y1=X2+Y2，也有三种情况，第一种为单独送货，即0—A—0，0—B—0，Spend=3*A*Ma+2*A+3*B*Mb+2*B;time=(A+B)/12+1/3；第二种送货方式为0—B—A—0，则有：Spend=3*B*(Ma+Mb)+3*Ma*(A-B)+2*A;Time=(A+(A-B))/20+A/30+1/3;第三种送货方式为0—A—B—0，有：Spend=3*A*(Ma+Mb)+3*Mb*(B-A)+2*B;Time=(B+(B-A))/20+B/30+1/3;很明显这两种情况对路径和费用问题的影响是不同的，在做题时需分别考虑。4.1问题一模型分析我们考虑用MAX-MIN蚂蚁算法找出30个送货点的最短路线，适当可画出图，通过最短路线来分配每个业务员的调度。具体做法是按最短路线的顺序去派业务员派发小于25千克的邮件,将得到的单向TSP回路分成了8段，但经过分析后发现这样做根本行不通。于是我们将问题升华为蚂蚁算法在多回路应用中的VRP问题，进一步探讨问题的最优解。4.2问题二模型分析在问题二中业务员的酬金是最重要的，业务员安排，线路选择都是为了酬金的最小化提供条件，而酬金又由携带快件和不携带快件两种组成，所以在选择线路时要遵循个原则，一，选择两点先后顺序的时可按照上面关于时间的分析结果进行选择；二，携带快件时酬金要比不携带时多，在路程相同的情况下，尽量让业务员不携带行走；三，在同一条线路中，先送离业务员所在点最近的；四，线路尽量要少；五，尽量控制好每个业务员的酬金和奔走情况相似。4.3问题三模型分析问题三是建立在问题一的基础上的，初考虑时有两种解题思路，一是将问题一的8组进行组合，得到一个解；二是按照问题一的模型将6小时换成8小时重新求解，然后比较得到最优解。五、模型建立与求解5.1问题一模型分的建立与求解经过分析，本题属于VRP问题，即业务员路径问题。从本质上来说，TSP是VRP的基本问题，因此在设计VRP的算法时，可充分吸收TSP模型算法的经验，还要考虑VRP的具体要求。故此问先用TSP蚂蚁算法找出30个送货点最短路径，算法如下：在此条件下，设,(C是常数)，蚂蚁k(k=1,2,L,m)被随机放到某个送货点，然后根据每条线路的限制条件选择下一个送货点。在t时刻，其中，表示蚂蚁k下一步被允许去的送货点；和是参数，分别反映蚂蚁在运动过程中所积累的信息和蚂蚁选择路径时的相对重要性；为了避免残留的信息素过多而淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历后，要对残留信息素进行更新处理。（t+n）时刻，所有蚂蚁完成了周游，路径（i,j）上的信息素可根据以下公式做调整：用MATLAB软件编程来求解，并反复带入多次，其中部分参数情况为：m=30,α=1,β=5,ρ=0.1,Q=100,λ＝0.5,最终得出优化结果最短路线为：0-1-3-4-5-16-17-20-14-15-23-29-30-28-27-26-25-24-18-19-11-21-22-10-12-8-9-2-13-7-6-0，其总路程长度为423.7406km,然后按照邮件量小于或等于25kg将它分为8段，即分派8个业务员，如图所示：图330点最短路线图及分段图虽然用蚂蚁算法找到了最优的TSP回路，但局部并非是最优化的，所以将分成的8段按分析中的方法进行再优化，得到每个业务员的送货路线，所用时间，总邮件量和总路程如下表1：业务员经过的站号所用时间(h)总载重(kg)总路程(km)时间（h）（考虑速度）10,1,3,4,5,01.867243020,2,13,7,6,02.34724.24230,10,12,8,9,02.34722.94240,16,17,20,14,15,23,04.623.59050,19,11,21,22,03.58724.97360,18,24,25,03.2224.76870,27,26,03.173227180,29,30,28,04.3418.396总计25.49184.5512在每个业务员的工作时间不超过6小时的前提下，对表中数据分析可知，线路1和线路线路5，线路2和线路6，线路3和线路7的时间和均不足6小时，故可合二为一，派给一个业务员送邮件，这样只需要业务员5名即可完成每天的任务。在对数据的进一步分析之后发现，用蚁群算法得到的30个点的总路线虽然是最优的，分段后随做了一定优化处理，但仍不一定是最优的数据。特别是在距原点较远的地方业务员带邮件的费用较高，对第二问并没有帮助，于是我们进一步用蚁群算法在VRP问题中的应用进行探讨，以寻求最优解。设有k个业务员，每个业务员可带重量为bk(k=1,2,…,k),送货点m个，每个送货点的邮件量为qi(i=1,2,…,m),送货点i到j的距离为d(i,j),第k个业务员去的送货点为nk,Rk表示第k个业务员的行走路线，rki表示第k个业务员去的第i个送货点，rki是1到m的证书。设公司总部为0号送货点，需送0kg邮件。用蚁群算法的多回路VRP问题建立模型：s.t.采用最基本的蚁群算法算此问题，部分运行参数设为：M=60，nc=300,α=0.5,β=3,ρ=0.2,=0.5.用MATLAB软件编程来求解，并反复带入多次，得到最优解路线下表2所示：业务员经过的站号所用时间(h)总载重(kg)总路程(km)费用（元）10-1-2-5-01.7820.73263720-3-4-12-02.1824.2421330.930-6-16-17-18-20-03.15324.4581906.240-9-14-25-24-03.38722.4681979.650-7-13-19-02.6620.8541396.860--8-27-26-03.5424.3762571.570-15-23-29-30-28-04.75324.1983364.380-10-22-21-11-02.82723.6541661.8总计24.285184.548114902.1在每个业务员的工作时间不超过6小时的前提下，对表中数据分析可知，线路1和线路线路4，线路3和线路5，线路2和线路8的时间和均不足6小时，故可合二为一，派给一个业务员送邮件，这样也只需要业务员5名即可完成每天的任务。将所有线路在坐标图上表示如下：图4业务员线路安排图两种方法都只要5名业务员，但方法一中业务员行走总路程为512km,工作总时间为25.49h；方法二中业务员行走总路程为481km，工作总时间为24.285h.相比之下，第二种方案要好的多了。5.2问题二模型的建立与求解根据对模型二的分析，以给业务员的酬金最少为目标建立模型：minspend对酬金的各种约束：ai*Xi=a(i-1)*X(i-1)且ai*Yi=ai*Y(i-1)根据上面的模型，用C++编程求的相关数据如下表3：路线号所经送货点所经送货点数所用时间总重量总费用10，1，3，8，13，042.4166722.1792.920，2，4，7，14，042.524.7969.530，6，5，2