邮政运输中邮路的规划和邮车调度问题的研究

第38卷第14期2008年7月数学的实践与认识MATHEMATICSINPRACTICEANDTHEORYVol.38No.14July,2008邮政运输中邮路的规划和邮车调度问题的研究金钢,师群昌,刘小麟(西南财经大学经济信息工程学院,成都610074)摘要:以邮政运输网络中运输效益最优为目标,建立了分步规划的图论模型.运用Floyd算法、Kruskal算法对模型进行分步求解并逐步优化,通过Matlab、Lingo、SPSS软件求解,提出三种优化邮路、降低邮车调度成本的方法.模型对解决邮路问题、单旅行商、多旅行商等相关问题具有普遍适用性,可以推广到点数更多TSP的问题.关键词:邮路规划;分步规划图论模型;Floyd算法;Kruskal算法0引言收稿日期:2008-04-01截至2006年年底,中国邮政共有局所、代办点6.3万处,其中设在农村的有4.4万处;中国邮政覆盖全国城乡3万多个网点,邮路总长度(单程)340.6万公里,并与世界200多个国家和地区建立业务联系.如何继续发挥中国邮政的这种本土发展起来的“得天独厚”的优势,进一步降低邮路运输的成本,成为中国邮政防御快递公司和外资巨头双边竞争的首要任务.本文将以某地的邮政网点分布图为例(具体数据参见07年研究生数学建模竞赛D题),在以下假设条件下,提出三种优化邮路、降低成本的方法:图11问题假设1.1条件假设1.邮政网点分布如右图所示,假设区级两个班次邮车的行驶路线相同,要求区级邮政运输网必须至少覆盖该地市附近的16个支局Z58,Z59,…,Z73和5个县局X1,…,X5;各县级邮政运输网必须覆盖本县内区级邮车不到达的支局;从地市局到县局每天两班车,从县局到支局每天仅有一班车:区级第一班次邮车从地市局出发将邮件运送到各县局和沿途支局,并将各县局和沿途支局收寄的邮件运送回地市局;区级第一班次邮车出发时间必须在06:00之后,必须在11:00之前返回地市局;区级第二班次邮车(路径与第一班邮车相同)从地市局出发将邮件运送到各县局和沿途支局,并将各县局收寄的邮件(包括当日各县级邮车运回县局的邮件)和沿途支局收寄的邮件运送回地市局;区级第二班次邮车在县局卸装完邮件后的出发时间必须在县局的全部县级邮车返回县局并集中处理1小时以后,最终必须在18:00之前返回地市局;2.县局Xi将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理,按寄达支局装上相应的县级邮车;县局Xi对邮件的集中处理时间为1小时(包括邮件的卸装、分拣封发等处理时间).区级第二班次邮车必须在县局Xi的全部县级邮车返回县局并集中处理1小时以后才能出发,最终返回地市局D的时间必须在18:00之前;3.假设区级邮车速度为65km/h,县级邮车的速度为30km/h;邮车在各支局卸装邮件耗时5分钟,在各县局卸装邮件耗时10分钟;4.邮车的发车、到达等所有时间数据均精确到分钟.1.2符号假设D,X1,…,X5,Z1,…,Z73:标记地市局、县局和支局点;Si:寄达局为Zi点邮件量;Ri:支局Zi收寄的邮件;Ti:遍历区域i需要的时间;t1:表示邮车在支局点停留需要的时间;t2:表示邮车在县局点停留需要的时间;yij:表示邮局i与j之间邮车通过的次数;xij:0-1变量,0代表i、j点之间是否有邮车经过;qij:邮车运行在Zi到Zj路程上是的邮包数量;v1:县级邮车的速度;v2:区级邮车的速度.2优化邮路、降低成本方法综述2.1在全地区范围内,寻找满足时间约束的路径最短的邮路2.1.1问题分析及模型的准备1)问题中的目标约束实际中,采用尽可能少的、尽可能短的邮路,可减少邮政部门车辆和人员等的投入,从而降低全区邮政运输网的总成本;从而在解决问题中尽量使所有邮车走过路程之和最短为目标,即:min∑76i=1∑76j=1C·yij·Kij其中:C为每条邮路的运营成本;K为邮局间距离形成的邻接矩阵,Kij表示第i个邮局与j个邮局间的距离,具体表达为:Kij=+∞(当邮局i与邮局j不直接相连)k(当邮局i与邮局j直接相连,k即为邮局i与邮局j间的距离)2)运行时间约束对于区级邮车:每条邮路一天发车两次,并且区级邮车1运行时间必须满足在6:00-11:00范围内,则区级邮车单次运行时间T0n必在5(11-6=5)小时范围内,区级邮车2的返回时间最晚为18:00,发车顺序为区级邮车1早于区级邮车2,同时,在每一个县局邮局邮车停留10分钟,在每一个支局邮车停留5分钟,则有:T0n=D0nv2+t160·N0n+t260·M0n5其中:T0n:第n辆区级邮车单次运行时间(小时);D0n:第n辆区级邮车单次运行的路程(km);N0n:第n辆区级邮车单次运行中通过的支局个数;M0n:第n辆区级邮车单次运行中通过的县局个数;对于县级邮车:每天的出发时间最早只能在区级邮车1到达1小时后开出,同时返回县局的最晚时间必须在区级邮车2离开该县局的前1小时前,故有县局车的运行时间Tmn在1818514期金钢,等:邮政运输中邮路的规划和邮车调度问题的研究-6-1×2-T0n=10-T0n范围内,则有:T0n=Dmnv1+t160·Nmn+t260·Mmn10-T0n(m=1,2,…,5)其中:Tmn:第m地区第n辆区级邮车单次运行时间(小时);Dmn:第m地区第n辆区级邮车单次运行的路程(km);Nmn:第m地区第n辆区级邮车单次运行中通过的支局个数;Mmn:第m地区第n辆区级邮车单次运行中通过的县局个数.3)覆盖点的约束全市的所有邮局每天都必须覆盖所有的点,则有:∑5m=0∑nNmn+∑5m=0∑nMmn=78并且:∑5m=0∑nNmn=73,∑5m=0∑nMmn=52.1.2模型的建立与求解对问题二的研究仍然可以归结为多旅行商的分步图论规划模型.我们所需考虑的是在一天的调度中,在满足邮车运行时间的限制的情况下,使所有车通过的路径之和最短,则可以建立如下规划模型:min∑76i=1∑76j=1C·yij·Kijs.t∑5m=0∑nDmn=∑76i=1∑76j=1yij·KijT0n5Tmn10-T0n∑5m=0∑nNmn=73∑5m=0∑nMmn=5(m=1,2,…,5)(2.1)由于此模型不是规范的规划模型,直接求解难度会很大,故而在模型的求解中我们采用分步规划,首先考虑市局邮车的安排情况和所走的路程.1)区级邮车路径的选择模型:运用单旅行商模型分步求解首先对市区邮车所走的邮路进行规划,首先根据邮局间任意两点间的最短距离得出区车遍历所有市区点和5个县局所需通过的最短距离为Dis,初步得出所需的区车数为:n=Disv2+t1·N0n60+t2·M0n60T′(2.2)在由D,X1,…,X5,Z58,…,Z73构成的图G0中,根据克鲁斯卡尔算法求出的该图的最小支撑树,将该图分为n个子图G0k(k=1,2,…,n),在每一个子图中,相当于解决单旅行商问题,建立寻找区车的最短回路模型[1]:min∑i,j∈G0kKij·hij186数学的实践与认识38卷s.t∑j∈G0khij=1i∈G0k,(限制每一个顶点的出度为1)∑j∈G0khji=1i∈G0k,(限制每一个顶点的入度为1)ui-uj+n·hijn-1,2i≠jnxij=0,1,i,j=1,2,…,n(2.3)其中:hij=0(表示点i与点j间无连接)1(表示点i与点j间有连接)2)县级邮车路径的选择模型:在确定好区级邮车所走路径后,我们利用寻找区级邮车路径的相似方法,求出每个县邮局点构成的图Gm(m=1,2,…,5)的最小支撑树,并将图Gm划分成适当个数的子图Gmk(k为图Gm划分出的子图个数).同样利用解决单旅行商问题的方法,建立寻找县车最短路径模型:2.1.3问题的求解问题中,寻求最优的邮路路径实际上相当于解决一个多旅行商的问题,多旅行商问题的最优解旅行路线的总路程达到最小,但是路线的均衡性可能相当差.因此,当要求均衡性较好的解还需要做大量的调整工作.对于本题的规模(包括邮局共有79个点)要想求得真正的最优解是不现实的.为此在求解中,我们采用分步图论规划方法求解.1.邮车数量的确定1)区级邮车数量的确定根据邮局间任意两点间的最短距离得出区车遍历所有市区点和5个县局所需通过的最短距离为721km,初步得出所需的区车数为2.57辆.则初步取3辆区车运行.2)县级邮车数量的确定根据县内邮局点构成图的最小支撑树,在使每个县尽量使用较少邮车以及全区运行总路程最小的约束下,进行邮路区间的划分,划分后,使每一个邮路区间内一辆邮车能够覆盖完所有的邮局并且邮路路程尽量短.图2各地市局区域内支局点与县局点生成的最小支撑树在这种情况下得到的县内邮路区间的个数即为该县所需县级邮车的数量.2.最小支撑树的求解使用克鲁斯卡尔(Kruskal)算法[2],利用Matlab求解,得到最小支撑树.1)区内邮局与各县局构成图的最小支撑树对于由邮局D,X1,…,X5,Z58,…,Z73构成的图G0,通过matlab求解,求得其最小生成树见图2(左).2)各县局内邮局构成图形成的最小支撑树对于由各县邮局分布图,通过matlab求解,求得18714期金钢,等:邮政运输中邮路的规划和邮车调度问题的研究其最小生成树见图2(右).3.邮车邮路路径及邮车调度1)单旅行商问题求解车辆的数量最少是三辆,当车数为三辆时.问题转化为单旅行商问题的求解,应用Lingo软件,程序建模求解:Min∑i,j∈Adij·xijs.t.∑j∈Vxij=1,i∈V,(每个点出度为1)∑j∈Vxji=1,i∈V,(每个点入度为1)ui-uj+nxijn-1,2i≠jnxij=0,1,i,j=1,2,…,n(1.4)在求单个旅行商的最短路径时,首先假设该最短路径不包含辐射型邮路,第二步,将所有节点的数据代入lingo单旅行商最短路径算法,求解;若无法求得可行解,则说明最短路径一定含有辐射形邮路,通过matlab求节点度算法求得度的节点,将度为1的节点筛出并剔除,并将其它数据重新代入步骤二的操作.经过六次调整以后发现三辆车在限定的时间内无法完成到达五个支县的任务.改用四辆车运行初次规划可求得的区级邮车最短路径.2)逐步寻优对求出的路径根据如下规则进行局部调整:A、调整区车的行走区间,看能否减少县车的数量;B、调整区车,使区车经过其行走路径附近邮局,看能否减少总的行使路径.3)求解结果求解得所需区级邮车为4辆,县级邮车11辆,最小运营路程为2272km/天,最小运营成本为6816元/天.①邮车行使路径图图3邮车行使路径②最短路径长度及其所耗时间(由于行使路径图中已提及,考虑篇幅原因略)③邮车时间调度188数学的实践与认识38卷表7问题二中各县车发车时间约束表该邮局最早发车时间X1X2X3X4X5邮车最晚返回初始点时间10:118:478:2110:228:21邮车最多运行时间(分钟)272296273316305邮车最晚发车时间10:358:479:299:579:13假设上表为第一辆区级邮车在6:00发车,且县级邮车按照顺时针方向行驶的时间约束表,邮车逆时针方向运行的时间约束表按照相同方法也可求得.此表仅反映县车按照顺时针方向发车时的约束时间,旨在反映县车最早发车时间与最晚发车时间的时间间隔.2.2调整县局负责区域2.2.1问题的分析为了优化现有邮路,在全区范围内,重新划分县域不失为一个有效的途径.首先运用聚类分析的方法判断哪些点是有可能需要调整的点.如果聚类结果中的某些点被划到其他县,说明这些县支局划入原县相比于划入新县后,其内部聚核的总和增加更少.可以认为这些点是需要调整的,然后结合在模型下求得的最优路径以及各县最小支撑数来确定需要调整的点.运用情况一中模型求解,计算求得调整后的路径长度,取可以改进的点即为最终调整点.通过聚类分析,寻找可调整的边界点,,将这些点记录下来.将不同的分县区的情况依据图论分布求解方法求解,从中选择更优的结果.2.2.3聚类模型的求解聚类目标就是把离各县局最近的点聚集在一起,我们聚类的变量是各支点到各县局和区局的最短路