公共自行车调度问题

1、最新精品文档，知识共享!最新精品文档，知识共享!杭州电子科技大学暑期数学建模实践报告卢园08052201软件工程倪俊芳08073205数学与应用数学周凌霄08052241软件工程完成日期： 2010.8.15公共自行车调度问题摘要本文研究的是在普通工作日早高峰之前利用公交车对公共自行车进行调度， 使得每个自行车租赁点的自行车能满足市民的需求问题。通过一辆公交车收集和分配自行车，考虑公交车经过的总路程最短，首先我们考虑街道具有的方向性， 巧妙地结合Floyd算法，编程得到每两个租赁点之间的最短路径（见附录3）。然后根据公交车经过的路程最短这个目标，建立单目标非线性规划模型，这是一个类似于TSP问

2、题的模型，属于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辆车路线为

3、：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;所以两辆车的总路程为 645500具体路线描述详见附录5虽然总路程比一辆公交车的情况差，但是大大 节约了总时间。关键词：启发式搜索 Floyd算法非线性0-1规划1问题背景与重述1.1问题背景杭州市公共自行车目前共有1080个租车点，在为广大市民和游客带来出行 方便的同时，随着

4、租赁网点以及投入使用的自行车数量的不断增加，也对自行车的管理提出了更高的要求。下表是某区域各租赁点一个普通工作日早高峰之前的 自行车调度需求表（见附录 1），其中+号后的数据表示多余的自行车数量，-号 后的数据表示缺少的自行车数量。租赁点位置在图中（见附录2）用带圆圈的数字所示，圆圈中数字代表租赁点序号。直线代表允许汽车通行的双向马路，直线 上的数字代表路线长度（单位：米）。其中6号和30号租赁点紧邻公交停车场。1.2问题重述:根据上述描述我们需要完成以下任务：（1）如果从这两个停车场中派1辆公交车去各个租赁点采集多余的自行车 并分配给缺少车辆的租赁点，最后返回其中任意一个停车场，则该选择什么

5、样的 行车路径和工作顺序？（2）如果派2辆公交车去完成这一任务，又该如何分配任务，并选择何种 路径和工作顺序（设一辆公交车最多可同时存放 60辆自行车）？2问题分析随着公共自行车租赁网点以及投入使用的自行车数量的不断增加，对自行车的管理提出了更高的要求。我们要在早高峰之前用公交车对各租赁点的自行车进 行调度。在这个问题中并未提及任何的费用问题，因此，这是一个单目标规划问题，我们的目标是使公交车行驶的路程最短。 对于题中所给的自行车租赁点，有 些租赁点是有多余的自行车要去收集， 有些租赁点是缺少自行车需要补足。 在考 虑问题时，我们把那些有多余自行车的租赁点看作是供应点，而把那些需要补足的租赁点

6、看作是需求点。从而，该问题转化为多辆公交车、多个供应点和多个需 求点的路径优化问题，与 VRP模型很类似。在我们要建立的以公交车行驶的路程最短为目标的模型之前， 我们需要先根 据街道的方向和各租赁点的位置，在假设公交车可在交叉口实现 180转弯的前 提下，用Floyd算法得到两两租赁点之间的可行最短路径， 然后建立针对不同公 交车数的模型。对于问题一，考虑从两个停车场中派一辆公交车全程收集和分配自行车的情况，我们的目的是要找一条最短的公交车行驶路径。我们用0-1变量Xij来表示公交车是否从租赁点i到达租赁点j，即1 ,公交车从租赁点i到租赁点j0 ,否则(i,j R)，并分别对供应点，需求点，

7、公交车上自行车的数量等因素做一些约束条件，使得每个需求点只经过一次，供应点可以经过多次但进出的路径条数要相等，而且每时每刻公交车上的自行车数不得超过限载量。 并且，在这个问题中，公交车有两 个停车场可以选择作为出发点，最终又可以回到任何一个停车场， 所以要考虑不 同的进出口对结果的影响。同时，在公交车行驶过程中，我们还要考虑行驶方向。 这个问题类似于TSP问题，属于NP难问题，我们很难得到问题的最优解，可采 用启发式算法进行搜索求解，以行驶距离最短，搬运车辆最多为目标，进行全局 域范围的考虑，对公交车的可选路线进行搜索，得到最优的可行路线。但由于随 着搜索深度的加深，算法的时间复杂度呈现指数性

8、增长，我们对搜索的深度做了 相应的限制，从而得到问题的近似最优解。对于第二个问题，需要考虑两辆公交车同时运行的情况，我们可以在一辆公 交车的基础上进行改进，考虑多辆公交车这种更为一般的情况， 建立适用于多辆 公交车、多个供应点和多个需求点的单目标规划模型。采用0-1变量Xkj来表示第k辆公交车是否从租赁点i到达租赁点j，即(i,j R, k K)但在算法实现的时候需要考1 ,第k辆公交车从租赁点i到租赁点jxkij =0 ,否则约束条件与一辆公交车模型中的约束条件基本相似, 虑多辆公交车先后选择要经过的最优租赁点及公交车的出发点和返回点的问题3.模型准备典型的VRP模型定义如下：假设已知客户网

9、络中的客户数量、客户所在的位 置、客户需求和配送车辆的最大负荷，要求在满足约束的前提下为给定的中心仓 库设计车辆路径，使运输成本最小。传统电子商务配送模型是分区域配送模式的单一配送中心(Distributioncen tre ,DC )-多需求点(dema nds , DS )的路径优化模型，而且不考虑沿途补 货的情况。而针对区域广泛、客户众多且分散、业务量大且频繁的电子商务物流 配送业务，需要考虑多个配送区域联合、 沿途多次补货的配送策略，从而得到电 子商务配送的跨区域VRP模型我们考虑的车辆都是靠右行驶的。 假设两个停车场就在6号和30号租赁点上，即若公交车是从6号出发，则 公交车上已经存

10、放了 26辆自行车，同理于30号租赁点。 我们假设公交车不能在路上倒车，在交叉路口可以实现1800转弯。 假设自行车不能通过人力搬移过街道。这个思路和我们所要考虑的利用公交车收集和分配公共自行车很类似，问题中有多余自行车的租赁点即可看作电子商务问题中的配送中心DC而缺少自行车的租赁点也可看作是需求点 DS4问题的基本假设假设有自行车多余的租赁点为供应点，多余的自行车数为供应量；缺少自 行车的租赁点为需求点，缺少的自行车数为需求量。(其余假设在各自模型中进行阐述)5.符号设定与说明5.1考虑一辆公交车全程收集和分配自行车的情况集合C:供应点集合G:需求点集合R= CUG1 ,公交车从租赁点i到租

11、赁点j0 ,否则(i,j R)Wj i,j R :从租赁点i到租赁点j路段中公交车的运输量，即公交车上的自 行车数w:公交车的限载量(在题中是已知的， w = 60)Gj i,j R :从租赁点i到租赁点j的路程 di：租赁点i的需求量，其中i G ei：租赁点i每次的供应量，其中i C Zi：租赁点i的总供应量，其中i C5.2考虑多辆公交车全程收集和分配自行车的情况集合C:供应点 集合G:需求点 集合R= C UG 集合K:公交车(i, j R, k K)1 ,第k辆公交车从租赁点i到租赁点j0 ,否则wkij (k K，i,j R):第k辆公交车从租赁点i到租赁点j路段中公交车的 运输量

12、，即公交车上的自行车数w:公交车的限载量(在题中是已知的，w = 60)Ckij(k K，i,j R):第k辆公交车从租赁点i到租赁点j的路程di：租赁点i的需求量，其中i Gei：租赁点i每次的供应量，其中i CZi：租赁点i的总供应量，其中i C6.模型的建立6.1每两个租赁点之间的最短距离：在我们所要建立的以公交车经过的路程最短为目标的模型中，我们需要先根据街道的方向性寻找每两个租赁点之间的可行最短路径，我们先对公共自行车租赁点的简易地图中给每个租赁点所在方向和各个道路交点做相应的标注，如下图:217141591(14 d二I5Ia1617* * R22fc273：(3363?3456k

13、M13112c31 e22i *3L2Ir9 J2汇315 Q2r3L53(4183940图1新公共自行车租赁点的简易地图每个租赁点都有一个最接近的入口和出口，如租赁点 的入口为8,出口为7, 租赁点的入口为18，出口为17,则我们要计算租赁点 到租赁点 的最 短距离，只需用Floyd算法先计算17到8的最短距离，再加上8至7的权可。 根据这种方法利用Matlab编程即可得到两两租赁点之间的最短距离（见附录3）。 在这个基础上建立以下模型。6.2考虑一辆公交车全程收集和分配自行车的情况我们考虑公交车在收集与分配过程中经过的路程最短，从而建立如下模型: TOC o 1-5 h z min S=

14、i R j RXijGj(i 丰 j)辽i R Xij=1 ,j G(2j R Xij=1 ,i G(3i R Xij= iR Xji,jC3i R Xij(wij -dj) 0,j G(55s.t. i RXj Wj + e w w , j C(6i RXj ej = zj ,j C0 0 ,j G k KS” i Rxkij wkij + ej w , j C k K k K i RXkij ej = Zj ,j C0 ?Zi, iC0 wkijw w , i,j Rxkij 0,1其中:目标函数使各辆公交车经过的路程总和最短约束条件表示进入需求点j的路径只有一条；约束条件 表示从需求点

15、j出来的路径只有一条；d2保证了一个需求点只经过一次，即由一辆公交车 一次性满足需求点缺少的自行车；约束条件 保证进出供应点的路径条数相同，使得每个供应点持有一辆公 交车可以调度；约束条件 表示当公交车经过一个需求点时，公交车上的自行车数要足够 满足需求点缺少的，也保证了一个需求点只经过一次；约束条件 表示当公交车经过供应点的时候，收集的自行车加上公交车上 原来有的车不能超过限载量；约束条件表示从一个供应点收集的自行车总数为该供应点能供应的总量；约束条件 保证每次从供应点收集的自行车数不能超过该供应点的总供应 数；约束条件(19限制的是公交车的容纳量；约束条件 表示乂灿是0-1变量，当Xkj

16、= 1时说明第k辆公交车从租赁点i到租赁点j，否则Xkij = 0。模型的求解7.1启发式搜索算法: 7.1.1算法内容以指定站点为初始站点，对该站点的下一站点，搜索路径，搜索规则如下：查找与该站点距离最近的N个站点，排序；依次遍历这N个站点，如果这个租赁点为需求点且满足需求量大于车上的 剩余自行车，贝U删除该节点，并重新得到新的 N个站点。计算搬运车辆最多与初始点到该站点的距离之比。以这N个站点分别为初始点，重复第1步。搜索深度为No将每一层车辆-距离最大比值的站点返回。计算全部返回站点组成的车辆-距离之和，取最大值那个站点为初始点的下 一个站点。以下一个站点为起始点，重复第1步，直到所有的

17、车辆都被搬运完毕。 如下图所示：图2搜索图7.1.2算法的时间复杂度该算法的时间复杂度为0(n2)7.1.3 一辆公交车情况下算法中考虑的约束递归深度为5；当公交车到达需求站点时，每辆车装载的自行车必须大于租赁点需求数 当公交车到达多余站点时，每辆车尽力取得最大装载量。每次查找前5个满足条件的站点，作为下一个站点的搜索目标；7.1.4多辆公交车情况下算法中考虑的约束递归深度为5；当公交车到达需求站点时，每辆车装载的自行车必须大于租赁点需求数当公交车到达多余站点时，每辆车尽力取得最大装载量。两辆车不能同时到达某一站点。每次查找前5个满足条件的站点，作为下一个站点的搜索目标；7.2算法流程图:图3

18、算法流程图结果分析由附录4中的一辆公交车的行驶路线图可知，在整条路线中总共出现了12次在交叉路口 1800转弯的情况，这种情会况在现实生活中有可能无法达到，这 个问题主要是要在用Floyd算法中我们是在假设公交车可以在交叉口处实现1800转弯的情况下求的两两租赁点之间的最短路径。而且很多地方为了到达街道 对面，往往需要开车绕行，如果需要绕行的租赁点处需要收集或者分配的自行车 数比较少，我们可以考虑采取人工搬运的方式过街道实现，从而减少公交车的行驶路程。算法的优缺点以及改进方向总的来说，在求解中小规模的车辆调度问题时，启发式算法与精确算法相比， 在精度上不占优势。但在求解大规模车辆调度问题时，启

19、发式算法总可以在有限 的时间内，找到满意的次优解，这是精确算法难以做到的。因此，在实际应用中， 启发式算法使用的要更广泛一些。本文中我们米用的Floyd算法求解两两租赁点之间的最短路径时， 为解决在 实际情况中很难在每个交叉路口都实现 1800转弯的问题，我们考虑一种不允许 1800转弯的求最短路的思路：我们将街道的建筑区路口标注，每个矩形的建筑可以设置4个标注点。如图所示：图4路口标注图假定汽车是沿着建筑物的边在行驶时通过标注点，根据交通规则，可以得到 汽车在城市中任意一点的可行路线。此时每个标注点之间最多有两个可以选择的 路线：(1)过街道；(2)沿着建筑物向右转。如图：25643 871

20、r910131411121615图5选择方向图如图5中的2号标注点，可行的路线有2-3和2-5。因为2-1处于左行方向， 违背交通规则，所以2-1为不可行。在这种规则下，汽车有且仅有一种情况会发 生后转弯，即汽车连续三次穿过街道。如图中的8号标注点，从8号标注点出发， 经8-3,3-10，10-13之后，汽车便做了一个后转弯。由此可以观察到，汽车在任 意十字路口，进行三次穿过街道，便是后转弯。不穿过街道是右转，穿过一次为 直走，穿过两次为左转。由于标注点之间的距离是给定的，忽略过街时走的路程，只要满足公交车每次不穿过街道两次以上，所得到的最短距离就是满足不在交叉路口进行1800转弯要求的最短距

21、离。由于时间的限制没有做进一步的实现， 但是这是一个比较好 的改进方向。参考文献Lenstra J K， Nemhauser G L. Handbooks in Operations Research andManagement scienee M . Amsterdam: E1sevier . 1995.刘向，李延晖 电子商务配送的跨区域VR模型及其启发式算法 第46卷，第 S1 期，2006陈光亭，裘哲勇 数学建模 北京市 高等教育出版社2010.2附录附录1自行车调度需求表租赁点序号12345678910自行车需求+12 :+16-20-42-25 1+26+31-12-20-13租赁点

22、序号11121314151617181920自行车需求-20-18-7-19+62+22-18-11-1+2租赁点序号21 :2223；2425 12627：28：2930自行车需求-21+15+17-160-14+32+6-19+55附录2公共自行车租赁点简易地图附录3两两租赁点之间的最短路程表租赁点1234561040003800410046002300216000220025003000210032800200001300180033004410025001300050046005410025001300160004600623004500430046005100072300450043

23、0046005100180082700490047005000550022009180040003800410046001300103700210019002200270032001125003300310034003900200009091,2090982099097Z09091,209098209909比09820991，09820920900990209920曲0992091,20980眈6L09920曲0992091,20980眈81，009200怦009200比00800吒L00Z009200Z00龙006戶00射9L006200006200陀00巾00Z91，00620000620

24、0陀00巾00ZPi006200006200陀00巾00Z0009 L00陀006 L00900龙即0000000即00陀00021400陀009 L0006 L00900龙0L006 L00氏006 L00000即60082000P008200乙00022800龙00如00龙00Z200即0L00龙00如00龙00Z200即0081，900加00吒00900巾0009009900加00吒00900巾0009009P0000比00008200Z0000比0000比009 L009200比乙00Z006戶00Z00龙00600乙140L68L0929091,209209620909Z900000

25、06戶00如00巾002P0096200眇00Z00龙006200氏001P82000006戶00如00巾002P0091Z09如096209PZ091,2090969200600P00620092008200如9200600P00620092008200如陀0029009 L00龙006200巾00Z9乙090992091,20981，0900997Z090992091,20981，090099比0990池09920920992090209P096209PZ091,20920966L09P096209PZ091,209209681，00P006200陀00比00乙006IX009P00怦00

26、92002200P200099L00Z00220000怦009200眇91，00Z00220000怦009200眇Pi00Z00220000怦009200眇00龙00Z20022006 L00比00Z00如00Z909290990909曲陀乙乙026L00眇0981，0沏0991，0991，0900961，000000P00曲00曲00射620池0081，008200氏00氏00820961，000000P00曲00曲00射1Z00吒0901，090209209209929209820091，0092008200820009209820091，009200820082000陀090081，00

27、Z0091，0091，00乙00氏09Z090902090209227Z00氏09Z09090209020922比00920沏09220992099209Z20200陀0901，090209209209926L00901，0902092092099281，0眈0000200乙00乙0092IX0960091，000即00即00929L0池00Z00即0009 L0081，91，0池00Z00即009 L00081，Pi0池00Z00即009 L009 L0099200即0081，00比00比00乙即0曲00陀000000000914099200即0081，00比00比00乙0L091,200氏

28、00Z000P000P00眇6090000P00加006戶006戶001,980眈00如000900900900HL0眈00如000900900900H909800陀00怦000000909800陀00怦000000P09900比00Z200000000怦0920000600眇00眇0092乙096006戶00990089008900眇81，L9L91，怦09如09209如096099909290002200P200220000P20006200P2002200P20062009P00眇82002200P200220000P20001Z09909PZ0990池098P09如9200氏006 L

29、00氏009200曲0069200氏006 L00氏0092002P006陀00如00龙00如00600990029乙0992002200140022098200即即0980001，00乙00吒0900092140992002200140022098200即0L09射0000000巾09H00龙609900920060009099900巾8098900000曲00西090900射L098900000曲00西090900射9092200如0000如0眈0099092200如0000如0眈009P09900氏000200氏09Z002209H006 L00龙00曲0砂00吒乙09900900前00

30、6909990009062821Z92920妙099001400比000P0081，00091，000980922090961，6200Z200比09920901，096209Z820091，000980922090961，1Z0眈0斜006 L00即00龙0001，9200陀0081，09209Z09920M9200081，09209Z09920M陀00眇00901，090209609乙0池0901，00001，006200Z7Z0池0901，009 L0006200Z比09920991，00比00600090209820900乙00Z009206L09820900乙00Z0092OOP81

31、，00620081，09209Z09920MIX00如00Z0沏0922090961，9L0090091，09020曲09091491，0090091，09020曲090914Pi0090091，09020曲09091400氏000209920960982099即006 L00龙09Z091,20991，0981，1400氏000209920960982099OL009200609如09820920992600900前09909Z09209P8006002909Z909099098L006002909Z9090990989009009 L091,20池090909829009009 L091,

32、20池09090982P000P00620眈0981，09Z0991，008200巾099090099209Z2乙最新精品文档，知识共享!最新精品文档，知识共享!131800235027001600270021501418002350270016002700215015180023502700160027002150162600155035002400350013501711002650200090020002450181050260019508501950240019105026001950850195024002085024001750650175022002113501900225011

33、5022501700221350190022501150225017002324001350330022003300115024600265015004001500195025026501500400150019502611500205085025501400271500365001300600285028400245013000180016502915003650240013000285030195014002850165033500附录4一辆公交车行驶路线图最新精品文档，知识共享!o(J)佐）O（22）卄ifG)|附录5两辆公交车的详细路线描述 第一辆车：从30号出发，途经23，16，15

34、号，到达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号；再后转弯

35、，开车至24号；行驶至28 号前方路口，后转弯至28号；再从28出发直走至19号，开车至15好前方路口后转弯到达15 号,再直走到达14号；从14号出发，开车至3号，后转弯后开车至13号；再继续前进，至27号；从27号出发，开车至18号，继续前行车至11号；在11号路口后转弯，开车至26号，后转弯后开车至30号终点。附录6计算两两租赁点之间最短距离的 Floyd算法Matlab代码: %Floyd.m%采用floyd算法计算图1中每对顶点最短路 %d是距离矩阵fun cti on d,r=floyd(a)n=size(a,1);d=a;for i=1: nfor j=1: n r(i,j)=j

36、;endendfor k=1: nfor i=1: nfor j=1: nif d(i,k)+d(k,j)vd(i,j) d(i,j)=d(i,k)+d(k,j);r(i,j)=r(i,k);endendendendA = ；%路口之间的距离矩阵；B = ；%各个租赁点处于路口的位置D,R = floyd(A);C = ;%租赁点之间的最短距离 for i=1:1:30for j=1:1:30if(i=j)C(i,j) = 0;elseC(i,j) = D(B(i,3),B(j,2) + B(j,1); endendend附录7启发式搜索算法计算公交车行驶近似最有路线的C语言代码 #i ncl

37、ude#in clude#defi ne ZD 29 /定义站点数 ZD = Zha n Dia n#defi ne DE 5 /搜索深度int dista nceZDZD; /各个站点之间的距离int numZD;各个站点相应的多余、缺少的车辆的数目static in t route10*ZD; /车行走的路径判断是否所有的车都已经调度完毕bool IsE nd(int num) for(int i=0; i!：0=!)JOj量却阴多丑 /：az屮uoi u 嫌貝阴多I3J /!az96ueqo u字丄&丄丄豐丄阴字丄isu辜讪/ 字isjij者字少蚩者13旨阴/!+-punoq !|e8j

38、q(|/=punoq)ji屮 dop!ooueis!pdiuoiiu nu 4-|0A,f81!S_diu8i)6u!pu!jqiec|f81!S_lX8U !8oueis!p_diu8i = f81!S_diu8i 9nunuoo(0 !8oueis!p_diu8iiunu 資 09=|OA)ji Qs!冃gouBQpdiu 巩斎 0=i!8oueis!p_diu8iiunu 慨 0 =!：0=!)JOj:0= !3a!S_lX8U U :口 G巩!sdwoHU!苗/畐强 /：3a = Punoq u咸菩字真関丫底W/W量却者関思制/ _ !l = f8oueis!p_diu8i!f8oueis!p_diu8i = !8oueis!p_diu8i !8oueis!p_diu8i = ”_ _ (2ueis!p_diu8i