公共自行车调度问题s

杭州电子科技大学暑期数学建模实践报告完成日期：2010.8.15公共自行车调度问题摘要本文研究的是在普通工作日早高峰之前利用公交车对公共自行车进行调度，使得每个自行车租赁点的自行车能满足市民的需求问题。

通过一辆公交车收集和分配自行车，考虑公交车经过的总路程最短，首先我们考虑街道具有的方向性，巧妙地结合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问题背景杭州市公共自行车目前共有1080个租车点，在为广大市民和游客带来出行方便的同时，随着租赁网点以及投入使用的自行车数量的不断增加，也对自行车的管理提出了更高的要求。

下表是某区域各租赁点一个普通工作日早高峰之前的自行车调度需求表（见附录1），其中+号后的数据表示多余的自行车数量，-号后的数据表示缺少的自行车数量。

租赁点位置在图中（见附录2）用带圆圈的数字所示，圆圈中数字代表租赁点序号。

直线代表允许汽车通行的双向马路，直线上的数字代表路线长度（单位：米）。

其中6号和30号租赁点紧邻公交停车场。

1.2问题重述：根据上述描述我们需要完成以下任务：（1）如果从这两个停车场中派1辆公交车去各个租赁点采集多余的自行车并分配给缺少车辆的租赁点，最后返回其中任意一个停车场，则该选择什么样的行车路径和工作顺序？（2）如果派2辆公交车去完成这一任务，又该如何分配任务，并选择何种路径和工作顺序（设一辆公交车最多可同时存放60辆自行车）？2.问题分析随着公共自行车租赁网点以及投入使用的自行车数量的不断增加，对自行车的管理提出了更高的要求。

我们要在早高峰之前用公交车对各租赁点的自行车进行调度。

在这个问题中并未提及任何的费用问题，因此，这是一个单目标规划问题，我们的目标是使公交车行驶的路程最短。

对于题中所给的自行车租赁点，有些租赁点是有多余的自行车要去收集，有些租赁点是缺少自行车需要补足。

在考虑问题时，我们把那些有多余自行车的租赁点看作是供应点，而把那些需要补足的租赁点看作是需求点。

从而，该问题转化为多辆公交车、多个供应点和多个需求点的路径优化问题，与VRP模型很类似。

在我们要建立的以公交车行驶的路程最短为目标的模型之前，我们需要先根据街道的方向和各租赁点的位置，在假设公交车可在交叉口实现1800转弯的前提下，用Floyd算法得到两两租赁点之间的可行最短路径，然后建立针对不同公交车数的模型。

对于问题一，考虑从两个停车场中派一辆公交车全程收集和分配自行车的情况，我们的目的是要找一条最短的公交车行驶路径。

我们用0-1变量来表示公交车是否从租赁点i到达租赁点j，即，并分别对供应点，需求点，公交车上自行车的数量等因素做一些约束条件，使得每个需求点只经过一次，供应点可以经过多次但进出的路径条数要相等，而且每时每刻公交车上的自行车数不得超过限载量。

并且，在这个问题中，公交车有两个停车场可以选择作为出发点，最终又可以回到任何一个停车场，所以要考虑不同的进出口对结果的影响。

同时，在公交车行驶过程中，我们还要考虑行驶方向。

这个问题类似于TSP问题，属于NP难问题，我们很难得到问题的最优解，可采用启发式算法进行搜索求解，以行驶距离最短，搬运车辆最多为目标，进行全局域范围的考虑，对公交车的可选路线进行搜索，得到最优的可行路线。

但由于随着搜索深度的加深，算法的时间复杂度呈现指数性增长，我们对搜索的深度做了相应的限制，从而得到问题的近似最优解。

对于第二个问题，需要考虑两辆公交车同时运行的情况，我们可以在一辆公交车的基础上进行改进，考虑多辆公交车这种更为一般的情况，建立适用于多辆公交车、多个供应点和多个需求点的单目标规划模型。

采用0-1变量来表示第k 辆公交车是否从租赁点i到达租赁点j，即约束条件与一辆公交车模型中的约束条件基本相似，但在算法实现的时候需要考虑多辆公交车先后选择要经过的最优租赁点及公交车的出发点和返回点的问题。

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考虑一辆公交车全程收集和分配自行车的情况即公交车上的自行车数5.2考虑多辆公交车全程收集和分配自行车的情况的运输量，即公交车上的自行车数6.模型的建立6.1 每两个租赁点之间的最短距离：在我们所要建立的以公交车经过的路程最短为目标的模型中，我们需要先根据街道的方向性寻找每两个租赁点之间的可行最短路径，我们先对公共自行车租赁点的简易地图中给每个租赁点所在方向和各个道路交点做相应的标注，如下图：图1 新公共自行车租赁点的简易地图每个租赁点都有一个最接近的入口和出口，如租赁点○1的入口为8，出口为7，租赁点○9的入口为18，出口为17，则我们要计算租赁点○9到租赁点○1的最短距离，只需用Floyd算法[3]先计算17到8的最短距离，再加上8至7的权可。

根据这种方法利用Matlab编程即可得到两两租赁点之间的最短距离（见附录3）。

在这个基础上建立以下模型。

6.2考虑一辆公交车全程收集和分配自行车的情况我们考虑公交车在收集与分配过程中经过的路程最短，从而建立如下模型：○1其中:目标函数○1使公交车经过的路程最短；约束条件○2表示进入需求点j的路径只有一条；约束条件○3表示从需求点j出来的路径只有一条；○2○3保证了一个需求点只经过一次，即一次性满足需求点缺少的自行车；约束条件○4表示进出供应点j的路径条数相同，即保证了公交车经过的上一个租赁点如果是供应点则该供应点的自行车全部被收集，且公交车还能装下其他车，否则就不会经过该供应点，同时该供应点的下一个租赁点如果是需求点会被一次性满足；约束条件○5表示当公交车经过一个需求点时，公交车上的自行车数要足够满足需求点缺少的，也保证了一个需求点只经过一次；约束条件○6表示当公交车经过供应点的时候，收集的自行车加上公交车上原来有的车不能超过限载量；约束条件○7表示从一个供应点收集的自行车总数为该供应点能供应的总量；约束条件○8保证每次从供应点收集的自行车数不能超过该供应点的总供应数；约束条件○9限制的是公交车的容纳量。

约束条件○10表示是0-1变量，当时说明公交车从租赁点i到租赁点j，否则。

6.3考虑多辆公交车全程收集和分配自行车的情况多辆公交车同时收集和分配自行车的情况是在一辆公交车全程收集和分配自行车的基础上进行改进，目的同样是使得所有公交车经过的路程总和达最小，约束条件做相应的改变，从而得到以下模型○11其中：目标函数○11使各辆公交车经过的路程总和最短。

约束条件○12表示进入需求点的路径只有一条；约束条件○13表示从需求点出来的路径只有一条；保证了一个需求点只经过一次，即由一辆公交车一次性满足需求点缺少的自行车；约束条件保证进出供应点的路径条数相同，使得每个供应点持有一辆公交车可以调度；约束条件表示当公交车经过一个需求点时，公交车上的自行车数要足够满足需求点缺少的，也保证了一个需求点只经过一次；约束条件○16表示当公交车经过供应点的时候，收集的自行车加上公交车上原来有的车不能超过限载量；约束条件表示从一个供应点收集的自行车总数为该供应点能供应的总量；约束条件保证每次从供应点收集的自行车数不能超过该供应点的总供应数；约束条件限制的是公交车的容纳量；约束条件○20表示是0-1变量，当时说明第k辆公交车从租赁点i到租赁点j，否则。

7.模型的求解7.1启发式搜索算法：7.1.1算法内容以指定站点为初始站点，对该站点的下一站点，搜索路径，搜索规则如下：（1）查找与该站点距离最近的N个站点，排序；（2）依次遍历这N个站点，如果这个租赁点为需求点且满足需求量大于车上的剩余自行车，则删除该节点，并重新得到新的N个站点。