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

西北工业大学 数学建模 王睿 自动化 王璐 自动化 程路佳 自动化 完成日期：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.问题分析 随着公共自行车租赁网点以及投入使用的自行车数量的不断增加，对自行车的管理提出了更高的要求。我们在要车辆需要最多的时间段用调度车对各租赁点的自行车进行调度。在这个问题中并未提及任何的费用问题，因此，这是一个单目标规划问题，我们的目标是使调度车行驶的路程最短。对于题中所给的自行车租赁点，有些租赁点是有多余的自行车要去收集，有些租赁点是缺少自行车需