试谈快递公司送货策略

快递公司送货策略一 摘要：本文是关于快递公司送货策略的优化设计问题，即在给定送货地点和给定设计标准的条件下，确定所需业务员人数，每个业务员的运行线路，总的运行公里数，以及费用最省的策略。 本文主要从最短路经和费用最省两个角度解决该问题，建立了两个数据模型。模型一：利用“图的知识，将送货点抽象为“图中是顶点，由于街道和坐标轴平行，即任意两顶点之间都有路。在此模型中，将两点之间的路线权值赋为这两点横纵坐标之和。如Ax1，y1，Bx2，y2两点，那么权值为D=|x2-x1|+|y2-y1|。并利用计算机程序对以上结果进行了校核。模型二：根据题意，建立动态规划的数学模型。然后用动态规划的知识求得最优化结果。根据所建立的两个数学模型，对满足设计要求的送货策略和费用最省策略进行了模拟，在有标尺的坐标系中得到了能够反映运送最正确路线的模拟图。最后，对设计标准的合理性进行了充分和必要的论证。二 关键词：快递公司送货 最优化 图模型 多目标动态规划 TSP模型三 问题重述：在快递公司送货策略中，确定业务员人数和各自的行走路线是此题的关键。这个问题可以描述为:一中心仓库(或配送调度中心) 拥有最大负重为25kg的业务员m人, 负责对30个客户进行货物分送工作, 客户i 的快件量为 , 求满足需求的路程最短的人员行驶路径,且使用尽量少的人数,并满足以下条件:1) 每条送快件的路径上各个客户的需求量之和不超过个人最大负重。2) 每个客户的需求必须满足, 且只能由一个人送货.3每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h。4为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克。表一为题中所给的数据： 表一最大载重量25kg重载时速20km/h途中的平均速度25km/h重载酬金3元/km*kg业务员工作时间上限6h空载时速30km/h每个送货点停留时间10min空载酬金2元/km备注1、快件一律用重量来衡量 2、假定街道方向均平行于坐标轴处于实际情况的考虑, 本研究中对人的最大行程不加限制.本论文试图从最优化的角度，建立起满足设计要求的送货的数学模型，借助于计算机的高速运算与逻辑判断能力，求出满足题意要求的结果。四 问题分析：从公司总部配出一个人，到任意未配送的送货点，然后将这个人配到最近的未效劳的送货点范围之内的邻居，并使送货时间小于6小时，各送货点总重量不超过25kg。继续上述指派，直到各点总重量超过25kg，或者送货时间大于6小时。最后业务员返回总部，记录得到的可行行程即路线。对另一个业务员重复上述安排，直到没有未效劳的送货点。对得到的可行的行程安排解中的每一条路径，求解一个旅行商问题，决定访问指派给每一条行程的业务员的顺序，最小化运输总距离。得到可行解的行程安排解后退出。根据题意的要求，每个人的工作时间不超过6小时，且必须从早上9点钟开始派送，到当天17点之前即在8小时之内派送完毕。且，故至少需要8条路线。表二列出了题中任意两配送点间的距离。表二：任意两点间的距离矩阵因为距离是对称的，即从送货点i到送货点j的距离等于从j到i的距离。记作：dij.表三给出了客户的需求，为了完成送快递的任务，每个人在工作时间范围内，可以承当两条甚至更多的线路。表中给出了送货点序号，送货点编号，快件量T，以及送货点的直角坐标。 表三序号送货点快件量T坐标km序号送货点快件量T坐标kmxyxY1183216163.5216228.21517175.86183365418187.51117445.54719197.815125630820153.4199654.531121326.2225777.27922226.8210882.39623232.4279991.410224247.6151910106.514025259.6151411114.11732626102017121212.7146272712211313135.812928286.02242014143.8101229298.1251615204.671430304.22818五 模型假设：1街道方向均平行于坐标轴，且在该前提下，业务员可以任意选择路线。2无塞车现象，即业务员送快递途中不受任何外界因素影响，且业务员的休息时间不包括在最大工作时间6个小时内。3业务员人数不限制。4每个业务员的路线一旦确定，便不再更改。5每个业务员送快递是独立的，每人之间互不影响。6业务员到某送货点后必须把该送货点的快件送完。7每个业务员每天的工作时间不超过6个小时。8业务员回到快递公司后停留一个小时。六 主要符号说明：Ti：序号为i的送货点的快件重量xi ，yi序号为i的送货点的坐标M重：业务员送货总重载费用M空：业务员送货总空载费用M总：业务员送货总费用N：业务员送货的总次数m：业务员人数mj：第j个业务员送货的次数七 模型建立与求解：7.1问题一模型本模型考虑用多目标动态规划求解。由于问题一中只要求给出一个合理的方案，且未涉及到业务员工资问题，故只要满足条件业务员的工作时间上限是6个小时以及每条路线的最大载重量不大于25kg即可，本模型中追加两个目标路程最短和人员最少。可以通过以下两种方法实现：1每一个行程的第一个送货点是距离总部最近的未效劳的送货点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用。2每一个行程的第一个送货点是距离总部最远的未效劳的送货点。然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。然后比拟两组结果，通过函数拟合即可得到最优化结果。本模型中以满足需求的路程最短的人员行驶路径,且使用尽量少的人数，即 且 约束条件为： 时间约束： 载重量约束：方法一：每一个行程的第一个送货点是距离总部最近的未效劳的送货点。开始找离原该点最近的点v，且该点的访问标志设为被访问，该点快递重量为w，输出该点。找点v最近的点，快递重量为w1，且w1+w25，当其不成立时找次远点。NY找不到符合条件的点 时找到符合条件的点，且不止一个时选择快递重量最重的那个点，访问标志设为被访问，并输出该点，赋值给v，且w=w+w1；第一条行程中访问了节点0-1-3-4-5-0，是因为1距离原点最近，因此由1出发，3是距离1点最近的点，而且两处快件量之和为14kg，小于每个人最大负重量，可以继续指配。接着，4是距离3最近的点，而且三处快件量之和为19.5kg，仍小于25kg,还可以继续指配。在剩下的未效劳送货点中，5距离4最近其实距离4最近的点有2，5，6，7四个点，然后考虑该点需求的快件量，将其从大到小依次排列，快件量需求大者优先，但超过25kg上限的点舍去。这里2，7被舍去，应选择了5总快件量之和为24kg。再继续扩充，发现就会超出“25kg这个上限，因此选择返回，所以0-1-3-4-5就为第一条路线所含有的送货点。用该算法得到的各路线为：1013450 20 2 6 7 13 030 9 8 12 10 040 16 17 20 14 15 23 050 11 22 32 19 060 27 26 070 18 24 25 080 29 28 30 0 现在0-1-3-4-5这四个送货点之间的最优访问路径安排就是一个典型的单回路问题。可以通过单回路运输模型-TSP模型求解。一般而言，比拟简单的启发式算法求解TSP模型求解有最邻近法和最近插入法两种。由RosenkrantzStearns等人在1977年提出的最近插入法，能够比最近邻点法，取得更满意的解。由于0-1-3-0 已经先构成了一个子回路，现在要将节点4 插入，但是客户4有三个位置可以插入，现在分析将客户4插入到哪里比拟适宜:1.插入到0，1间，C总= 7+4+5+1+4+9=30。2.插入到1，3间，C总=5+6+4+9=24。3.插入到3，0间，C总=5+4+4+11=24。比拟上述三种情况的增量，插入到3，0间和1，3间增量最小，考虑到下一节点插入时路程最小问题，所以应当将4插入到送货点3和总部0之间。接下来，用同样的方法，将5插到4和0之间，能使该条路线总路程最小，该路线总路程为32km，历时1.9467h。结果子回路为T=0-1-3-4-5-0.因为街道平行于坐标轴方向，所以它就是最优化路线。第二条行程这中，由于所剩下节点中，2距离0点最近，因此由2出发，就可以找到最近点6，接着是7，然后13.这样，第二条优化路线0-2-6-7-13-0就确定了。用这种方法，依次可确定以下剩余六条路线。得到总的送货路线为：101345020 2 6 7 13 030 10 12 8 9 040 16 17 20 14 15 23 050 19 11 32 22 060 18 24 25 070 27 26 080 29 30 28 0运输员序号所经站数最近点所用时间(小时)总载重kg总路程km1413，21.946724322421，52.506724.24634910，21.866422.93046162，164.600023.590541117，34.213424.972631811，173.750024.768722721，133.70672276832925，164.840018.396合计3028.2699184.5506改良前和改良后的路程，时间比拟如下：然后，根据所经历的时间进行划分，确定运送人数。在工作时间小于6小时的前提下，最终只需要六名运输员，第一条线路和第二条线路有一人完成，第三条和第七条线路由一人完成，那么各运输员到达各站点时间的情况如下：路线站点编号到各站点时间出发时间路线站点编号到各站点时间出发时间119：129：0051910：059：0039：321110：4149：523211：08510：142211：322212：0211：5861810：079：001312：482410：31713：102510：53613：3972713：4512：233109：349：002614：07129：5882910：389：00810：203011：00910：442811：244169：439：001710：072010：291410：511511：302311：59路径为：方法二：每一个行程的第一个送货点是距离总部最远的未效劳的送货点。分析方法如一：得到的路径为：10 30 29 28 23 15 020 26 27 8 030 24 25 14 9 040 18 17 20 16 6 050 32 22 11 10 060 19 13 7 070 12 4 3 080 5 2 1 0同方法一，用最近插入法修改路径可以得到更优的解，改良后的路径为：1 02830292315 02 0 26 27 8 03 0 24 25 14 9 04 0 20 18 17 16 6 05 0 11 32 22 10 06 0 19 13 7 07 0 4 12 3 08 0 2 5 1 0运输员序号所经站数最远点所用时间小时总载重km总路程km153028，184.833324.1100232620，173.540024.376342415，193.386722.468451811，173.153024.458543222，52.826723.6546319(15, 12 )2.660020.8547312(14, 6 )2.180024.242835 (3, 11)1.620020.728合计3024.1997184.5480改良前后路程和时间的比拟如下：然后，根据所经历的时间进行划分，确定运送人数。在工作时间小于6小时的前提下，最终只需要五名运输员，第三条线路和第八条线路由一人完成 第四条线路和第七条线路由一人完成，第五条线路和第六条线路由一人完成，那么各运输员到达各站点时间的情况如下：路线站点编号到各站点时间出发时间路线站点编号到各站点时间出发时间12810：469：005119：489：003011：113210：152911：332210：392312：051011：061512：3461913：5512：5022610：299：001314：312710：51714：53811：477413：3613：1032410：229：001214：122510：44314：481411：118213：4813：34911：45514：074209：509：00114：391810：171710：411611：07611：41路径图为：由上面得图表知改良后的方法二的路线的总的距离为480km，时间为24.1997；比改良后的方法一的距离短，时间短，所以假设是只考虑时间和路程，改良后的方法二为最优解。7.2 问题二模型问题二中由于业务员所得的费用是最主要的，业务员安排、路线选择都是为了总费用的最小化提供条件，所以应首先考虑路费，之后再考虑业务员的安排。为了使总能够费用最少，总的思路是先送货给离快递公司最近切块间最重的送货点，以此类推，在保证时间、载重量有限的前提下，沿途把快递送完，最终让业务员最远点空载返回。根据这一思路，全部路线业务员的重载费用可表示为：从上式可以看出，业务员的重载费用是恒定的，又由于总费用为重载与空载费用之和，所以总费用确实定就可以转化为满足一定条件下的各路线的最远点的选择问题。某路线业务员经过的路径选择应遵循以下原那么：一是，近者优先原那么。某业务员最近起始送货点的选择直接关系到费用的多少，所以该业务员在沿途往送货终点站中应尽量把较近点的快件送完，不让下一条路线再把较近点作为起始送货站。二是，不走冤枉路原那么即只能向上或者向右走。一方面，离原点快递公司较远的送货点坐标应分别大于离原点较近送货点的坐标，在各个坐标上均不走回头路，即按图a中的路线前进，而不按路线前进：图a业务员行走路线约定另一方面，由于在路途相等的条件下，重载费用要比空载费用大得多，因此，尽量让业务员空载行走。三是，坐标贴近原那么。在同一条路线中，离原点较近送货点的坐标仅次于较远点的坐标。四是，路线较少原那么。路线多，一方面，相对最远点的选择多，跑的空路多，费用就多；另一方面，过分地强调短暂效益，出动路线多，会引起业务员的反感，不利于以后的人员控制。根据上述分析及根本假设，业务员送货的费用可以表示如下：重载费用：空载费用：总费用：应该满足以下要求： 时间约束： 载重量约束: 路线约束：根据路线约束条件以及表二知：送货点13，2、21，5首先必须作为某路线的最近起始送货点，再结合时间约束条件、载重量约束条件以及上述分析的有关内容，依次选出各路线的次近点，并做统筹兼顾，一直到满足约束条件的最大值为止。随后又选出60，8、910，2、1014，0、162，16、2221，0、1519，9、2515，14为某条路线的最近点，分别确定次近点等，最后确定各路线如图b所示：第一条路线：快递公司13，235，489，61312，9出发线返回线第二条路线：快递公司21，544，777，91410，12出发线返回线第三条路线：快递公司60，853，11207，141811，17出发线返回线3028，18第四条路线：快递公司910，21214，61915，12出发线返回线第五条路线：快递公司1014，01117，33222，52327，9出发线返回线第六条路线：快递公司162，16176，182415，192824，20出发线返回线第七条路线：快递公司2221，02925，16出发线返回线第八条路线：快递公司1519，92721，13出发线返回线第九条路线：快递公司2515，142620，17出发线返回线 图b业务员行走路线根据上面确定的路线，把个业务员所经过的送货点数、最近点、所用时间、总载重量进行归纳，并用C+编程求出各业务员送货所得费用以及总费用，如下表：路线号所经送货点数最近送货点所用时间小时总载重量kg费用元1413，22.4166722.1792.92421，52.524.7969.53560，84.6666723.81852.443910，22.7521.91498.2541014，03.6666719.21352.464162，164.3333322.92261.8722221，03.7514.91506.7821519，93.1666715.41577.6922515，143.4266719.62021.2合计30184.513830.7根据时间约束，最少要8个业务员送快件，其中把路线1和2合并，让业务员A执行任务，其余的分别由其他7个业务员送货。同时，为了便于统筹业务员，可以得出各业务员到各送货点的时间各业务员的出发时间为0以及各路线从快递公司出发的参考时间从9：00开始工作。第一个人：0-1-3-8-13-0和0-2-4-7-14-0第二个人：0-6-5-20-18-30-0第三个人：0-9-12-19-0第四个人：0-10-11-32-23-0第五个人：0-16-17-24-28-0第六个人：0-22-29-0第七个人：0-15-27-0第八个人：0-25-26-0根据上述分析，得到各路线的行走路线如下列图所示：假设根据问题一的求解方法，可得以下8条路线：第一条路线：快递公司13，235，444，753，11出发线返回线第二条路线：快递公司21，51312，977，960，8第三条路线：快递公司1014，01214，689，6910，2第四条路线：快递公司162，16176，18207，141410，12第五条路线：快递公司2221，03222，52327，91519，91117，3第六条路线：快递公司1915，122515，142415，19第七条路线：快递公司1811，172620，172824，20第八条路线：快递公司2721，132925，163028，18 图b业务员行走路线根据上面确定的路线，把个业务员所经过的送货点数、最近点、所用时间、总载重量进行归纳，并用C+编程求出各业务员送货所得费用以及总费用，如下表：路线号所经送货点数最近送货点所用时间小时总载重量kg费用元1413，22.0333324767.52421，52.7333324.21390.6341014，02.5666722.91357.544162，163.117.71438.4552221，05.222.92680.6631915，123.33333252310.2731811，174.1666723.52620832721，134.3333324.32891.9合计3027.46666184.515456.7合并那么有以下人员分配：第一个人：0-1-3-4-5-0和0-19-25-24-0第二个人：0-2-13-7-6-0和0-10-12-8-9-0第三个人：0-16-17-20-14-0第四个人：0-22-32-23-15-11-0第五个人：0-18-26-28-0第六个人;0-27-29-30-0八 模型评价1、模型的优点：1模型系统的给出了业务员的调配方案，便于指导工作实践。2模型简单明了，容易理解与灵活应用。3模型的方法和思想对其他类型也适合，易于推广到其他领域。4本模型方便、直观，易于在计算机上实现和推广。2、模型的缺点：1模型给出的约束条件可能也有不太现实的。2对街道的方向，客户的快件量的假设有待进一步改良。3、 模型的推广1本模型不但适合于快递公司送货问题，还是用于一般的送货以及运输问题，只需要稍微改动模型即可。2模型方便、直观，可以实现计算机模拟。3建模的方法和思想可以推广到其他类型，如车辆调度问题等。 参考文献：1：姜启源、谢金星、叶俊编，数学模型-3版，北京，高等教育出版社，2003.8 2：吴建国、汪名杰、李虎军、刘仁云编，数学建模案例精编-1版，北京，中国水利水电出版社，2005.53：唐焕文、贺明峰编，数学模型引论-3版，北京，高等教育出版社，2005.3 注释：C+源码求解路线及其相关内容：问题一之方法一：#include#include#include#define max 1000 using namespace std;struct verint x;int y;int num;float weight;bool visited31;ver v31;int next1()int k,min=max,tag=0;float w;for(int i=1;i31;i+)if(visitedi=false&vi.x+vi.yw)k=i; w=vi.weight;tag=1; if(tag)return k;else return 0;int next2(int k,float w) int min=max,tag=0,m,i; for(i=1;i31;i+)if(visitedi=false&fabs(vk.x-vi.x)+fabs(vk.y-vi.y)min&w+vi.weight=25) min=fabs(vk.x-vi.x)+fabs(vk.y-vi.y); m=i; tag=1; if(visitedi=false&fabs(vk.x-vi.x)+fabs(vk.y-vi.y)=min&w+vi.weightvm.weight)m=i;tag=1;if(tag)return m;else return 0;void way()int k;float w;k=next1(); while(k!=0) float time;int num_of_station=0,distance,tag; visitedk=true;w=vk.weight;distance=vk.x+vk.y;time=(vk.x+vk.y)/25.0;cout0vk.num;tag=next2(k,w);while(tag!=0) num_of_station+;visitedtag=true;coutvtag.num;w=w+vtag.weight;time=time+(fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y)/25.0;if(time+(vtag.x+vtag.y)/25.0+(num_of_station+1)/6.0=6)distance=distance+fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y);k=tag;tag=next2(tag,w);elsetime=time-(fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y)/25.0;break; time=time+(vk.x+vk.y)/35.0+(num_of_station+1)/6.0; distance=distance+vk.x+vk.y; cout0 time distancekm wendl; k=next1();int main()int i; ifstream infile(1.txt);cout各站点的坐标及相关信息是：endl;for(i=0;ivi.numvi.xvi.yvi.weight; coutvi.num(vi.x,vi.y):vi.weightt;coutendl;coutn各条送快递的线路 所用时间 该线路总路程endl; way();return 0;问题一之方法二：#include#include#include#define max 1000 using namespace std;struct verint x;int y;int num;float weight;bool visited31;ver v31;int next1()int k,max1,tag=0;float w;for(int i=1;imax1)max1=vi.x+vi.y; k=i; w=vi.weight;tag=1; if(visitedi=false&vi.x+vi.y=max1&vi.weightw)k=i; w=vi.weight;tag=1; if(tag)return k;else return 0;int next2(int k,float w) int min=max,tag=0,m,i; for(i=1;i31;i+)if(visitedi=false&fabs(vk.x-vi.x)+fabs(vk.y-vi.y)min&w+vi.weight=25) min=fabs(vk.x-vi.x)+fabs(vk.y-vi.y); m=i; tag=1; if(visitedi=false&fabs(vk.x-vi.x)+fabs(vk.y-vi.y)=min&w+vi.weight=25&vi.weightvm.weight)m=i;tag=1;if(tag)return m;else return 0;void way()int k;float w;k=next1(); while(k!=0) float time;int num_of_station=0,distance,tag; visitedk=true;w=vk.weight;distance=vk.x+vk.y;time=(vk.x+vk.y)/25.0;cout0vk.num;tag=next2(k,w);while(tag!=0) num_of_station+;visitedtag=true;coutvtag.num;w=w+vtag.weight;time=time+(fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y)/25.0;if(time+(vtag.x+vtag.y)/25.0+(num_of_station+1)/6.0=6) distance=distance+fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y); k=tag; tag=next2(tag,w);elsetime=time-(fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y)/25.0;break;time=time+(vk.x+vk.y)/25.0+(num_of_station+1)/6.0;distance=distance+vk.x+vk.y;cout0 time distancekm wendl;k=next1();int main()int i; ifstream infile(1.txt);cout各站点的坐标及相关信息是：endl;for(i=0;ivi.numvi.xvi.yvi.weight; coutvi.num(vi.x,vi.y):vi.weightt;coutendl;coutn各条送快递的线路 所用时间 该线路总路程endl; way();return 0;问题二：#include#include#include#define M 1000using namespace std;struct nodeint x;int y;int num;float weight;node v31;int mindis31;bool vd31;void create(ifstream &in,int n)int i;for(i=0;ivi.numvi.xvi.yvi.weight; coutvi.num(vi.x,vi.y) vi.weightt;int d(node a,node b)return (abs(a.x-b.x)+abs(a.y-b.y);void dis()int i,j;for(i=0;i31;i+)coutvi.num到各点的距离：n;for(j=0;j31;j+) coutd(vi,vj) ;coutendlendl;int next1()int k,min=M,tag=0;float w;for(int i=1;i31;i+)if(vdi=false&d(v0,vi)w) k=i; w=vi.weight;tag=1; if(tag) return k;else return 0;int next2(int k,float w) int min=M,tag=0,m,i; for(i=1;i31;i+)if(vdi=false&d(vk,vi)min&w+vi.weightvk.x&vi.yvk.y) min=d(vk,vi); m=i; tag=1; if(vdi=false&d(vk,vi)=min&w+vi.weightvm.weight&vi.xvk.x&vi.yvk.y)m=i;tag=1;if(tag) return m;else return 0;void way()int k;float w;k=next1(); while(k!=0) float time,money;int num_of_station=0,distance,tag; vdk=true;w=vk.weight;distance=vk.x+vk.y;money=3.0*w*distance;time=(vk.x+vk.y)/20.0;cout0vk.num;tag=next2(k,w);while(tag!=0) num_of_station+;vdtag=true;coutvtag.num;w=w+vtag.weight;time=time+(d(vk,vtag)/20.0;if(time+(vtag.x+vtag.y)/20.0+(num_of_station+1)/6.0=6)distance=distance+d(vk,vtag);money=money+3.0*distance*vtag.weight;k=tag;tag=next2(tag,w);else time=time-(fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y)/20.0;break;time=time+(vk.x+vk.y)/30.0+(num_of_station+1)/6.0;distance=distance+vk.x+vk.y;money=money+(vk.x+vk.y)*2.0;cout0 time distancekm money wendl;k=next1();int main()ifstream infile(1.txt);create(infile,31);coutendlendl;way();system(PAUSE);return 0;