公共自行车调度问题s

《公共自行车调度问题s》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、无法得到最优解，因此采用启发式算法进行搜索求得问题的近似最优解，即一辆公交车收集和分配自行车的近似最优路径为：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；公交车所经过的总路程为：57100o貝体路线见附录4屮的一辆公交车行驶路线图。对丁•两辆公交车的情况，我们直接考虑多辆公交车进行收集和分配的情况，在一辆公交车问题的基础上对模型和算法进行稍微的改变，可以得到两

3、辆公交车收集和分配的近似最优路径为：第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算法非

4、线性0-1规划1•问题背景与重述1.1问题背景杭州市公共自行车目前共冇1080个租车点，在为广大市民和游客带来出行方便的同时，随着租赁网点以及投入使用的自行车数量的不断增加，也对自行车的管理提出了更高的要求。下表是某区域各租赁点一•个普通工作日早高峰之前的自行车调度需求表（见附录1）,其中+号后的数据表示多余的自行车数量，-号后的数据表示缺少的口行车数量。租赁点位置在图中（见附录2）用带I员I圈的数字所示，圆圈中数字代表租赁点序号。直线代表允许汽车通行的双向马路，直线上的数字代表路线氏度（单位：米）。其中6号和30号租赁点紧邻公交停车场。1.2问题重述：根据上述描述我们

5、需要完成以下任务：（1）如果从这两个停车场中派1辆公交车去各个租赁点采集多余的自行车并分配给缺少车辆的租赁点，最后返冋其屮任意一个停车场，则该选择什么样的行车路径和工作顺序？（2）如果派2辆公交车去完成这一任务，又该如何分配任务，并选择何种路径和工作顺序（设一辆公交车最多可同时存放60辆自行车）？2•问题分析随着公共自行车租赁网点以及投入使用的口行车数量的不断增加，对自行车的管理提出了更高的要求。我们要在早高峰之前用公交车对各租赁点的自行车进行调度。在这个问题中并未提及任何的费用问题，因此，这是一个单目标规划问题，我们的目标是使公交车行驶的路程最短。对于题中所给的门行车

6、租赁点，有些租赁点是冇多余的自行车耍去收集，冇些租赁点是缺少自行车需要补足。在考虑问题时，我们把那些有多余自行车的租赁点看作是供应点，而把那些需要补足的租赁点看作是需求点。从而，该问题转化为多辆公交车、多个供应点和多个需求点的路径优化问题，与VRP模型很类似。在我们要建立的以公交车行驶的路程最短为目标的模型2前，我们需耍先根据街道的方向和各租赁点的位置，在假设公交车可在交叉口实现180°转弯的前提下，用Floyd算法得到网两租赁点之间的可行最短路径，然后建立针对不同公交车数的模型。对于问题一，考虑从两个停车场中派-•辆公交车全程收集和分配自行车的情况，我们的目的是耍找一

7、条最短的公交车行驶路径。我们用0-1变量殉來表示公交车是否从租赁点i到达租赁点j,即1,公交车从租赁点i到租赁点j0,否则并分别对供应点，需求点，公交车上门行车的数量等因素做一些约束条件，使得每个需求点只经过一次，供应点可以经过多次但进出的路径条数要相等，而冃每时每刻公交车上的自行车数不得超过限载量。并但，在这个问题中，公交车冇两个停车场可以选择作为出发点，最终乂可以冋到任何一个停车场，所以要考虑不同的进出口对结果的影响。同吋，在公交车行驶过程屮，我们还要考虑行驶方向。这个问题类似于TSP问题，属于NP难问题，我们很难得到问题的最优解，可