西工大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,j∈R，k∈K)约束条件与一辆调度车模型中的约束条件基本相似，但在算法实现的时候需要考虑多辆调度车先后选择要经过的最优租赁点及调度车的出发点和返回点的问题。

3.模型准备典型的VRP模型定义如下：假设已知客户网络中的客户数量、客户所在的位置、客户需求和配送车辆的最大负荷，要求在满足约束的前提下为给定的中心仓库设计车辆路径，使运输成本最小[1]传统电子商务配送模型是分区域配送模式的单一配送中心（Distribution centre ,DC）-多需求点（demands , DS）的路径优化模型，而且不考虑沿途补货的情况而针对区域广泛、客户众多且分散、业务量大且频繁的电子商务物流配送业务，需要考虑多个配送区域联合、沿途多次补货的配送策略，从而得到电子商务配送的跨区域VRP模型[2]这个思路和我们所要考虑的利用调度车收集和分配公共自行车很类似，问题中有多余自行车的租赁点即可看作电子商务问题中的配送中心DC，而缺少自行车的租赁点也可看作是需求点DS4.问题的基本假设（1）我们考虑的车辆都是靠右行驶的2）假设两个停车场就在6号和30号租赁点上，即若调度车是从6号出发，则调度车上已经存放了26辆自行车，同理于30号租赁点3）我们假设调度车不能在路上倒车，在交叉路口可以实现1800转弯4）假设自行车不能通过人力搬移过街道5）假设有自行车多余的租赁点为供应点，多余的自行车数为供应量；缺少自行车的租赁点为需求点，缺少的自行车数为需求量。

其余假设在各自模型中进行阐述）5.符号设定与说明 5.1考虑多辆公交车全程收集和分配自行车的情况 集合C:供应点 集合G：需求点 集合R=C∪G 集合K：调度车 xkij=1 ,第k辆 调度车从租赁点i到租赁点j0 , 否则 (i,j∈R，k∈K) wkij（k∈K，i,j∈R）:第k辆调度车从租赁点i到租赁点 j路段中调度车的运输量，即调度车上的自行车数 w:调度车的限载量（在题中是已知的，w=60） ckij（k∈K，i,j∈R）:第k辆调度车从租赁点i到租赁点j的路程 di:租赁点i的需求量，其中i∈G ei:租赁点i每次的供应量，其中i∈C zi:租赁点i的总供应量，其中i∈C6.模型的建立6.1 每两个租赁点之间的最短距离：在我们所要建立的以调度车经过的路程最短为目标的模型中，我们需要先根据街道的方向性寻找每两个租赁点之间的可行最短路径，我们先对公共自行车租赁点的简易地图中给每个租赁点所在方向和各个道路交点做相应的标注。

算法设计思想[2]如下图：1234567891011121829242717191314151621282526222320301210111213654317161514789222120191836322731242625304140393837232833293534图1 新公共自行车租赁点的简易地图每个租赁点都有一个最接近的入口和出口，如租赁点 的入口为8，出口为7，租赁点的入口为18，出口为17，则我们要计算租赁点到租赁点 的最短距离，只需用Floyd算法[3]先计算17到8的最短距离，再加上8至7的权可根据这种方法利用Matlab编程即可得到两两租赁点之间的最短距离（见附录4）在这个基础上建立以下模型[2] 思想参考杭州公共自行车规划路线图6.2考虑多辆公交车全程收集和分配自行车的情况 多辆公交车同时收集和分配自行车的情况是在一辆调度车全程收集和分配自行车的基础上进行改进，目的同样是使得所有调度车经过的路程总和达最小，约束条件做相应的改变，从而得到以下模型 min S=k∈Ki∈Rj∈Rxkijckij i≠j s.t.k∈Ki∈Rxkij=1 , j∈G k∈Kj∈Rxkij=1 , i∈G i∈Rxij=i∈Rxji , j∈C i∈Rxkijwkij-dj≥0 , j∈G k∈K i∈Rxkijwkij+ej≤w , j∈C k∈K k∈Ki∈Rxkijej=zj , j∈C 。