西工大14数模三等奖公共自行车调度问题.doc

西北工业大学数学建模 王睿 07031301 自动化王璐 07031301 自动化程路佳 07031301 自动化 完成日期：2014.5.3西安市经开区公共自行车服务系统设计摘要本文研究的是在普通工作日早高峰之前利用公交车对公共自行车进行调度，使得每个自行车租赁点的自行车能满足市民的需求问题。通过两辆调度车收集和分配自行车，考虑调度车经过的总路程最短，首先我们考虑街道具有的方向性，巧妙地结合floyd算法，编程得到每两个租赁点之间的最短路径（见附录3）。然后根据调度车经过的路程最短这个目标，建立单目标非线性规划模型，这是一个类似于tsp问题的模型，属于np难问题，我们无法得到最优解，因此采用启发式算法进行搜索求得问题的近似最优解，即一辆调度车收集和分配自行车的近似最优路径为：30-15-14-3-21-23-16-15-4-17-28-27-29-19-18-15-11-9-7-6-8-1-10-5-22-26-2-13-12-20-24-30经过租赁点的次数：31；调度车所经过的总路程为：57100。具体路线见附录4中的一辆公调度车行驶路线图。对于两辆调度车的情况，我们直接考虑多辆调度车进行收集和分配的情况，在一辆调度车问题的基础上对模型和算法进行稍微的改变，可以得到两辆调度车收集和分配的近似最优路径为：第1辆车路线为：30-23-6-16-15-17-21-23-22-15-4-2-12-10-20-26-30经过租赁点的次数：16，调度车经过的总路程：33000；第2辆车路线为：6-8-7-1-9-29-24-28-19-15-14-3-13-27-18-11-26-30经过的总站点数为17，调度车经过的总路程为：31550；所以两辆车的总路程为64550。具体路线描述详见附录5虽然总路程比一辆调度车的情况差，但是大大节约了总时间。关键词：启发式搜索 floyd算法 非线性0-1规划 1.问题背景与重述1.1问题背景西安市经开区公共自行车服务系统于2011年4月开始建设，到目前为止，已建成租赁点30个，自行车总量达到850辆。目前正在筹备第三期建设。 （1）租赁点设置。租赁点通常设在地铁出口、城市中心等人员密集的地方，根据经开区车辆需求调查、地理位置等实际情况，有关部门事先确定了100个位置作为备选租赁点，前期的30个租赁点在其中选出，第三期需要建设一定数目的租赁站点，位置亦在其中选出；（2）由于需求及位置限制，每个租赁点能够放置的车辆数目有限，不能超过40辆；为了更好满足居民对车辆的租赁要求、简化调度、提高车辆使用率，通常车辆总数至少应超出需求量的10%；（3）附录1列出了各个租赁点（或备选租赁点）在不同时间段的车辆需求情况。为了简化问题，附录1将实时观测到的数据归结到3个车辆使用需求最多的时间段，并进行了平均（可以认为每天的需求量不变）；（4）居民可以在任意一个租赁点还车，在某个租赁点还车的概率与租车点和还车点的距离成反比，且假设居民的骑行距离不超过2km；（5）假设车辆调度只在附件2中车辆需要最多的时间段进行，经开区目前用于运送公共自行车的调度车有2辆，每辆每次可运50辆自行车，调度车平均时速30km/h，每辆自行车装（或卸）平均耗时1min；（6）假设建设一个租赁服务网点需要50000元，在使用周期内，购买、养护一辆自行车需要1000元。1.2问题重述：根据上述描述我们需要完成以下任务：（1） 根据目前经开区网点自行车需求情况等信息，若要求调度平均耗时尽量少，请针对已有的30个租赁点设计最优车辆分配方案、调度方案，并给出完成调度所耗费的间。（2）假设经开区公共自行车服务系统三期建设准备投入建设经费200万元，据此建立数学模型，确定新增租赁点数目、位置以及合适的放置车辆数目。（3）针对问题（2），进一步研究，如果要求在150min内完成调度，是否需要增加调度车辆（购置调度车辆费用由其它项目经费解决，不包含在三期建设提供的200万元经费中间）？并给出该情形下的自行车调度方案。2.问题分析随着公共自行车租赁网点以及投入使用的自行车数量的不断增加，对自行车的管理提出了更高的要求。我们在要车辆需要最多的时间段用调度车对各租赁点的自行车进行调度。在这个问题中并未提及任何的费用问题，因此，这是一个单目标规划问题，我们的目标是使调度车行驶的路程最短。对于题中所给的自行车租赁点，有些租赁点是有多余的自行车要去收集，有些租赁点是缺少自行车需要补足。在考虑问题时，我们把那些有多余自行车的租赁点看作是供应点，而把那些需要补足的租赁点看作是需求点。从而，该问题转化为两辆调度车、多个供应点和多个需求点的路径优化问题，与vrp模型很类似。在我们要建立的以调度车行驶的路程最短为目标的模型之前，我们需要先根据街道的方向和各租赁点的位置，在假设公交车可在交叉口实现1800转弯的前提下，用floyd算法得到两两租赁点之间的可行最短路径，然后建立针对不同公交车数的模型。对于第一个问题，需要考虑两辆调度车同时运行的情况，考虑多辆调度车这种更为一般的情况，建立适用于多辆调度车、多个供应点和多个需求点的单目标规划模型。采用0-1变量xkij来表示第k辆调度车是否从租赁点i到达租赁点j，即 xkij=1 , 第k辆调度车从租赁点i到租赁点j0 , 否则 (i,jr，kk)约束条件与一辆调度车模型中的约束条件基本相似，但在算法实现的时候需要考虑多辆调度车先后选择要经过的最优租赁点及调度车的出发点和返回点的问题。3.模型准备典型的vrp模型定义如下：假设已知客户网络中的客户数量、客户所在的位置、客户需求和配送车辆的最大负荷，要求在满足约束的前提下为给定的中心仓库设计车辆路径，使运输成本最小1。传统电子商务配送模型是分区域配送模式的单一配送中心（distribution centre ,dc）-多需求点（demands , ds）的路径优化模型，而且不考虑沿途补货的情况。而针对区域广泛、客户众多且分散、业务量大且频繁的电子商务物流配送业务，需要考虑多个配送区域联合、沿途多次补货的配送策略，从而得到电子商务配送的跨区域vrp模型2。这个思路和我们所要考虑的利用调度车收集和分配公共自行车很类似，问题中有多余自行车的租赁点即可看作电子商务问题中的配送中心dc，而缺少自行车的租赁点也可看作是需求点ds。4.问题的基本假设（1）我们考虑的车辆都是靠右行驶的。（2）假设两个停车场就在6号和30号租赁点上，即若调度车是从6号出发，则调度车上已经存放了26辆自行车，同理于30号租赁点。（3）我们假设调度车不能在路上倒车，在交叉路口可以实现1800转弯。（4）假设自行车不能通过人力搬移过街道。（5）假设有自行车多余的租赁点为供应点，多余的自行车数为供应量；缺少自行车的租赁点为需求点，缺少的自行车数为需求量。（其余假设在各自模型中进行阐述）5.符号设定与说明 5.1考虑多辆公交车全程收集和分配自行车的情况 集合c:供应点 集合g：需求点 集合r=cg 集合k：调度车xkij=1 ,第k辆 调度车从租赁点i到租赁点j0 , 否则 (i,jr，kk) wkij（kk，i,jr）:第k辆调度车从租赁点i到租赁点 j路段中调度车的运输量，即调度车上的自行车数 w:调度车的限载量（在题中是已知的，w=60） ckij（kk，i,jr）:第k辆调度车从租赁点i到租赁点j的路程 di:租赁点i的需求量，其中ig ei:租赁点i每次的供应量，其中ic zi:租赁点i的总供应量，其中ic6.模型的建立6.1 每两个租赁点之间的最短距离：在我们所要建立的以调度车经过的路程最短为目标的模型中，我们需要先根据街道的方向性寻找每两个租赁点之间的可行最短路径，我们先对公共自行车租赁点的简易地图中给每个租赁点所在方向和各个道路交点做相应的标注。算法设计思想2如下图：1234567891011121829242717191314151621282526222320301210111213654317161514789222120191836322731242625304140393837232833293534图1 新公共自行车租赁点的简易地图每个租赁点都有一个最接近的入口和出口，如租赁点 的入口为8，出口为7，租赁点的入口为18，出口为17，则我们要计算租赁点到租赁点 的最短距离，只需用floyd算法3先计算17到8的最短距离，再加上8至7的权可。根据这种方法利用matlab编程即可得到两两租赁点之间的最短距离（见附录4）。在这个基础上建立以下模型。2 思想参考杭州公共自行车规划路线图6.2考虑多辆公交车全程收集和分配自行车的情况多辆公交车同时收集和分配自行车的情况是在一辆调度车全程收集和分配自行车的基础上进行改进，目的同样是使得所有调度车经过的路程总和达最小，约束条件做相应的改变，从而得到以下模型 min s=kkirjrxkijckij ij s.t.kkirxkij=1 , jg kkjrxkij=1 , ig irxij=irxji , jc irxkijwkij-dj0 , jg kk irxkijwkij+ejw , jc kk kkirxkijej=zj , jc 0eizi , ic 0wkijw , i,jr xkij0,1 其中：目标函数使各辆调度车经过的路程总和最短。约束条件表示进入需求点 j 的路径只有一条；约束条件表示从需求点 j 出来的路径只有一条；保证了一个需求点只经过一次，即由一辆调度车一次性满足需求点缺少的自行车；约束条件保证进出供应点的路径条数相同，使得每个供应点持有一辆调度车可以调度；约束条件表示当调度车经过一个需求点时，调度车上的自行车数要足够满足需求点缺少的，也保证了一个需求点只经过一次；约束条件表示当调度车经过供应点的时候，收集的自行车加上调度车上原来有的车不能超过限载量；约束条件表示从一个供应点收集的自行车总数为该供应点能供应的总量；约束条件保证每次从供应点收集的自行车数不能超过该供应点的总供应数；约束条件限制的是调度车的容纳量；约束条件表示xkij是0-1变量，当xkij=1时说明第k辆调度车从租赁点i到租赁点j，否则xkij=0。7.模型的求解7.1启发式搜索算法：7.1.1算法内容以指定站点为初始站点，对该站点的下一站点，搜索路径，搜索规则如下：（1）查找与该站点距离最近的n个站点，排序；（2）依次遍历这n个站点，如果这个租赁点为需求点且满足需求量大于车上的剩余自行车，则删除该节点，并重新得到新的n个站点。（3）计算搬运车辆最多与初始点到该站点的距离之比。（4）以这n个站点分别为初始点，重复第1步。搜索深度为n。（5）将每一层车辆-距离最大比值的站点返回。（6）计算全部返回站点组成的车辆-距离之和，取最大值那个站点为初始点的下一个站点。（7）以下一个站点为起始点，重复第1步，直到所有的车辆都被搬运完毕。如下图所示：。搜索至第n层后返回图2 搜索图7.1.2算法的时间复杂度该算法的时间复杂度为o（n2）7.1.4多辆公交车情况下算法中考虑的约束递归深度为5；当调度车到达需求站点时，每辆车装载的自行车必须大于租赁点需求数。当调度车到达多余站点时，每辆车尽力取得最大装载量。两辆车不能同时到达某一站点。每次查找前5个满足条件的站点，作为下一个站点的搜索目标；7.2算法流程图：图3 算法流程图8.结果分析由附录4中的一辆调度车的行驶路线图可知，在整条路线中总共出现了12次在交叉路口1800转弯的情况，这种情会况在现实生活中有可能无法达到，这个问题主要是要在用floyd算法中我们是在假设调度车可以在交叉口处实现1800转弯的情况下求的两两租赁点之间的最短路径。而且很多地方为了到达街道对面，往往需要开车绕行，如果需要绕行的租赁点处需要收集或者分配的自行车数比较少，我们可以考虑采取人工搬运的方式过街道实现，从而减少公交车的行驶路程。 9.算法的优缺点以及改进方向总的来说，在求解中小规模的车辆调度问题时，启发式算法与精确算法相比，在精度上不占优势。但在求解大规模车辆调度问题时，启发式算法总可以在有限的时间内，找到满意的次优解，这是精确算法难以做到的。因此，在实际应用中，启发式算法使用的要更广泛一些。本文中我们采用的floyd算法求解两两租赁点之间的最短路径时，为解决在实际情况中很难在每个交叉路口都实现1800转弯的问题，我们考虑一种不允许1800转弯的求最短路的思路：我们将街道的建筑区路口标注，每个矩形的建筑可以设置4个标注点。如图所示：123456789101112131415516图4 路口标注图假定汽车是沿着建筑物的边在行驶时通过标注点，根据交通规则，可以得到汽车在城市中任意一点的可行路线。此时每个标注点之间最多有两个可以选择的路线：(1)过街道；(2)沿着建筑物向右转。如图：123456789101112131415516图5 选择方向图如图5中的2号标注点，可行的路线有2-3和2-5。因为2-1处于左行方向，违背交通规则，所以2-1为不可行。在这种规则下，汽车有且仅有一种情况会发生后转弯，即汽车连续三次穿过街道。如图中的8号标注点，从8号标注点出发，经8-3,3-10，10-13之后，汽车便做了一个后转弯。由此可以观察到，汽车在任意十字路口，进行三次穿过街道，便是后转弯。不穿过街道是右转，穿过一次为直走，穿过两次为左转。由于标注点之间的距离是给定的，忽略过街时走的路程，只要满足调度车每次不穿过街道两次以上，所得到的最短距离就是满足不在交叉路口进行1800转弯要求的最短距离。由于时间的限制没有做进一步的实现，但是这是一个比较好的改进方向。10.参考文献1 lenstra j k，nemhauser g l handbooks in 0perations research and management science m amsterdam：e1sevier19952 刘向，李延晖 电子商务配送的跨区域vrp模型及其启发式算法 第46卷，第s1期，20063 陈光亭，裘哲勇 数学建模 北京市 高等教育出版社 2010.2附录附录1 自行车调度需求表编号网点位置7:008:30车辆需求数11:0012:30车辆需求数17:3019:00车辆需求数1经发大厦1522302可口可乐北门2324353经发国际会馆3828314昆仑银行3832225赛高街区1723286西安中学西门3212107运动公园东门1335348运动公园南门4022169管委会26191910出口加工区广场18313711鼎新花园18242712西安外国语学校35203313雅荷花园7272814御道华城12191315天地时代广场38161216市图书馆1722617文景观园21392318长庆电视台23383219移动公司28202020凤城五路23212021凤城六路15333422中登家园北门357623万华园15203824粤华凤城家园3491025市人大2191326市委23212027政务大厅35303528首创国际城18212029中登广场13221730运动公园北门183038附录2公共自行车租赁点地图附录3两两租赁点之间距离（直线）附录4两两租赁点之间的最短路程表l附录5各时间段需要调度的车数附录6两辆调度车的详细路线描述-第一辆车：从30号出发，途经23，16，15号，到达17号；从17号前方路口后转弯，到达23号；在23号前方路口后转弯，至22号，沿着22号前方路口右转，经14号（不取、放车），到达15号租赁点路口；后转弯到达15号，再开车至4号；从4号前方路口后转弯，直走至2号；从2号再开车经10号至12号，在12号前方路口后转弯后，开车至20号；从20号开车经过21号，开车到达26号，在26号前方路口左转弯开至16号，最后从16号路口后转弯，开车到达终点站30号。第二辆车：从6号出发，途经8号，在8号左转，到达7号，在前方路口后转弯后，开车到达1号；在1号前方路口后转弯，开车到达9号；再后转弯，开车至24号；行驶至28号前方路口，后转弯至28号；再从28出发直走至19号，开车至15好前方路口后转弯到达15号，再直走到达14号；从14号出发，开车至3号，后转弯后开车至13号；再继续前进，至27号；从27号出发，开车至18号，继续前行车至11号；在11号路口后转弯，开车至26号，后转弯后开车至30号终点。附录7计算两两租赁点之间最短距离的floyd算法matlab代码：-%floyd.m%采用floyd 算法计算图1 中每对顶点最短路%d 是距离矩阵function d,r=floyd(a) n=size(a,1); d=a; for i=1:n for j=1:n r(i,j)=j; end end for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j)d(i,j) d(i,j)=d(i,k)+d(k,j); r(i,j)=r(i,k); end end endenda = ;%路口之间的距离矩阵;b = ;%各个租赁点处于路口的位置d,r = floyd(a);c = ;%租赁点之间的最短距离for i=1:1:30 for j=1:1:30 if(i=j) c(i,j) = 0; else c(i,j) = d(b(i,3),b(j,2) + b(j,1); end endend附录7启发式搜索算法计算公交车行驶近似最有路线的c语言代码-#include#include#define zd 29 /定义站点数 zd = zhan dian#define de 5 /搜索深度int distancezdzd; /各个站点之间的距离int numzd;/各个站点相应的多余、缺少的车辆的数目static int route10*zd; /车行走的路径bool isend(int num)/判断是否所有的车都已经调度完毕for(int i=0; izd; i+)if(numi!=0)return false;return true;int pathfinding(int first,int vol,int depth)/寻路 找到下一个路径最优的站点if(depth =0)return -1;int temp_distancezd;int i,j,k;for(i=0;izd;i+)temp_distancei = i;/存储站点号码for(i=0;izd;i+)for(j=i;jdistancefirsttemp_distancej)k = temp_distancei;temp_distancei = temp_distancej;temp_distancej = k;/排序 保留的是距离从小到大的站点号码int bound = de;/设置边界int temp_sitede;int next_sitede;j=0;for(i=0;i= 0 & numtemp_distancei!=0 & temp_distancei!=first)if(vol=60 & numtemp_distancei 0)continue;temp_sitej = temp_distancei;next_sitej = pathfinding(temp_sitej,vol+numtemp_distancei,depth-1);if(bound=1)break;bound-;j+;/从i+1的原因是，第一个点是first点/搜索first节点的下一个和下下个节点int changezd;/搬运车的总数int lenthzd;/开车的距离for(i=0;ide;i+)/计算first站点到搜索站点的距离和总搬运数changei=0;lenthi=0;int voll = vol;if(temp_sitei=0)break;if(numtemp_sitei numtemp_sitei)changei += numtemp_sitei;voll += numtemp_sitei;elsechangei += numtemp_sitei - 60 + vol;voll = 60;lenthi += distancefirsttemp_sitei;if(next_sitei0)if(numnext_sitei