公共自行车调度问题-数学建模论文

目录 一、问题引入 .3 二、问题分析 .3 2.1 第一问分析 .4 2.2 第二问分析 .4 2.3 第三问分析 .4 三、模型假设和符号说明 .5 3.1 模型假设 .5 3.2 符号系统 .6 四、模型建立 .6 4.1 模型分类 .6 4.2 租赁点分配方案建模 7 4.3 调度车调度方案建模 8 4.3.1 一辆调度车调度方案 .8 4.3.2 多辆调度车调度方案 .9 4.4 租赁点数目和位置的确定 .11 4.5 调度时间的模型 12 五、 模型的求解 .13 5.0 经纬度转换为横纵坐标 .13 5.1 求解最短路径 13 5.2 模型一次运行后的单车重分配求解 14 5.3 求解分配方案的预估 校正算法 16 5.4 求解调度方案的启发式算法 16 5.4.1 算法简介 .16 5.4.2 算法内容 .17 5.4.3 约束条件 .18 5.4.4 算法流程图 .19 5.5 租赁点位置 .20 5.6 计算结果 .20 5.6.1 第一问结果 .20 5.6.2 第二问结果 .21 5.6.3 第三问结果 .23 六、模型检验 .26 七、模型优缺点以及改进 .26 7.1 分配方案的优点 .27 7.2 调度方案的缺优点 .27 7.3 新增节点模型的优缺点 .27 7.4 模型和算法的改进 .28 - 2 - 7.4.1 算法的改进 .28 7.4.2 模型的改进 .28 八、参考文献 .30 附录 .30 - 3 - 一、问题引入 近年来，随着经济的发展，我国各级城市的机动车保有量都进入了持续高 速增长时期，但由此所引发的道路拥堵、空气污染也引起了政府以及百姓的极 大关注。众所周知，建立快速、便捷的城市公共交通体系是解决这一问题的有 效手段之一。然而，居民居住地和交通站点通常都有一段距离，这段不远的距 离以及现实存在的公共交通拥挤现象则使居民乘坐公共交通的意愿降低，而将 公共自行车租赁服务系统纳入城市公共交通体系，能够从一定程度上缓解这一 现象。 西安市经济开发区公共自行车服务系统于 2011 年 4 月开始建设，到目前为止， 已建成租赁点 30 个，自行车总量达到 850 辆。目前正在筹备第三期建设，请你 针对如下问题建模： （1）根据目前经开区网点自行车需求情况等信息，要求调度平均耗时尽量少， 针对已有的 30 个租赁点设计最优车辆分配方案、调度方案，给出完成调度所耗 费的时间。 （2）假设经开区公共自行车服务系统三期建设准备投入建设经费 200 万元， 据此建立数学模型，确定新增租赁点数目、位置以及合适的放置车辆数目。 （3）针对问题（2） ，进一步研究，如果要求在 150min 内完成调度，确定是否 需要增加调度车辆（购置调度车辆费用由其它项目经费解决，不包含在三期建 设提供的 200 万元经费中间） ，并给出该情形下的自行车调度方案。 二、问题分析 首先，题目给出的初始条件为经度和纬度，我们利用地球的坐标系统将其 转换为平面坐标，后续的计算都在平面坐标的基础上进行。 - 4 - 2.1 第一问分析 第（1）问对对应前两期工程，30 个租赁点已知，因此在已知的点上根据需 求量确定自行车的分配方案和调度方案。这个问题是在已知节点具体的位置的 条件下求解两个问题：每个节点的自行车分配问题和调度问题。这两个问题可 以分开来求解。 第(1)问要求调度时间尽量少，我们从计算两点的最短路径入手，将最短路 径计算出后考虑将早中晚三个时间段内的高峰期取平均值后再最初计算。我们 建立反比例函数关系式：p=Kd，再根据归一化条件求得 2km 内的概率系数 K。 随后，算出每个点以需求量的数目的前提下会向 2km 内的各个租赁点送出多少 辆单车，并以负反馈的方式经多次计算得出一个稳定解，即大部分租赁点的单 车数量满足 110%的要求，少部分租赁点单车数目远远超出需求量，还有少部分 单车数目几乎为零（奇点） 。最后，将计算所得的几个奇点分块，从单车数量超 出 40 或大量超出需求量的地点运送单车至奇点并计算运送时间。 2.2 第二问分析 第（2）问对应第三期工程，根据投入的建设费用等确定新增的租赁点的数 目和每个租赁点的分配方案。这些新增的租赁点是在规定的 70 个点中选取的， 而且每个待选点的需求量是给定的，因此在需求量和工程费用的限制下，求实 现服务系统最优的选点方案和分配方案。 建立新的一定数目的租赁点，我们首先将另外 70 个点的数据列出，考虑到 是否选择一个点与这个点的平均需求量和最大需求量均有关，所以将早中晚三 个时间段的需求量的平均值和三个时间段需求量的最大值列出，然后将这两个 数据以一定比例加权平均，最后得出的数字排序，由上到下计算出每个点的需 求金额，截止到 2000000 元时。租赁点即为截止前的点，相对应的数目即为每 个点对应的数目。 2.3 第三问分析 第（3）问建立在第（2）问的基础上，同第（1）问，类似，在解第（3） - 5 - 问前，租赁点的具体位置和需求量已知了，并且，这些租赁点的分配方案也已 将求得，很容易求得每一个租赁点需要调度的具体数值，在这些已知条件下， 要求在给定时间内完成调度，给出调度方案。如调度车辆不够，则给出增加的 车辆数目和调度方案。问题类似于第（1）问的给出分配方案后求调度的问题。 根据以上分析，我们要解决的问题主要有以下几个部分： 1、求出任意两个租赁点之间的最短路径。 2、求出给定租赁点的分配方案。 3、求出给定租赁点的系统的自行车调度方案。 4、在给定约束下求租赁点的数目和位置。 解决以上三个问题，本题所要求的问题就可以解决了。 三、模型假设和符号说明 3.1 模型假设 1、每个租赁点调度需求量为负，有多余的自行车可以提供给调度车则为正数； 2、假设两个停车场就在某两个租赁点上，则选取的两个租赁点必须是有自行车 盈余的点，并且调度车出发后，车上装载的自行车的数量就是租赁点的调度量。 由于每个租赁点的自行车最大分配量小于调度车的最大装载量，所以总是能够 将盈余量全部装在调度车上； 3、每辆调度车从固定的某租赁点出发，最后又回到原来的点，以方便下次调度 但是回到原点的时间可以不计。因为只有在调度完成后才会回到原点，此时不 需要调度，不再受时间限制； 4、同一辆调度车只能经过同一个租赁点一次（除了作为车站的租赁点） ； 5、每次到达下一个租赁点时，调度车上的自行车数量满足该租赁点需求，即对 于需求点来说，只需用调度一次就完成调度；对于盈余点来说，调度车到达这 些点要尽量多装。如果未达到调度车的限量就将该租赁点所有的盈余自行车装 - 6 - 载，如果多出，则装满。 3.2 符号系统 G-租赁点的集合 -调度总时间（不包括完成调度后调度车返回原点的时间） 。T -调度车编号k -租赁点间的最短距离ijd -第 k 辆车调度完 i 后是否再调度 jkijx -是否使用调度车 kku -租赁点 j 的需要调度的量jl -i 和 j 间的距离是否大于 M 千米ijB -t 时间段内租赁点 j 的需求量tjZ -j 点的需求量占总需求量的比例j -从 i 点出发到达 j 租赁点的自行车数量ijF -i 点的单车数量i a-建立一个租赁点耗资 b-维护每辆自行车耗资 p-每一个租赁点的耗资数 P-新增租赁点的耗资总数 四、模型建立 4.1 模型分类 在租赁点的分配方案确定后，只剩下调配问题，属于VRP问题，该问题是 - 7 - 著名的问题TSP（旅行商问题）的一个特例，因而也是NP-hard问题。 典型的VRP模型定义如下：假设已知客户网络中的客户数量、客户所在的位 置、客户需求和配送车辆的最大负荷，要求在满足约束的前提下为给定的中心 仓库设计车辆路径，使运输成本最小。 传统电子商务配送模型是分区域配送模式的单一配送中心（Distribution centre ,DC）-多需求点（demands , DS）的路径优化模型，而且不考虑沿途补 货的情况。而针对区域广泛、客户众多且分散、业务量大且频繁的电子商务物 流配送业务，需要考虑多个配送区域联合、沿途多次补货的配送策略，从而得 到电子商务配送的跨区域VRP模型。 这个思路和我们所要考虑的利用公交车收集和分配公共自行车很类似，问 题中有多余自行车的租赁点即可看作电子商务问题中的配送中心DC，而缺少自 行车的租赁点也可看作是需求点DS。 我们的问题和电子商务问题的一个不同点是，在调度时，如果调度点由盈 余的自行车且数量加上调度车上已有的自行车时其总量会可能会超过调度车的 最大装载量，因此有可能导致这些点的二次调度，这和电子商务配送模型中一 次性完成调度有所区别，但是可以经过是党的改正后得到正确的模型。 4.2 租赁点分配方案建模 影响租赁点自行车分配的因素有：各租赁点的需求量、从租赁点离开的自 行车、从其他租赁点起来的自行车等。若仅考虑需求量对租赁点分配自行车数 目的影响，有如下模型： )124(jtjZy-1njttjj （1）式确定按照最终的需求量，以按比例分配的方式确定租赁点的分配量。 （2）式给出需求量占总需求量的比例。 以仅考虑需求量的方式确定的分配方式显然不是最佳方案。分配方案还和租赁 点之间的距离有关。由题意可知，从在某个租赁点还车的概率与租车点和还车 - 8 - 点的距离成反比，且假设居民的骑行距离不超过 M km，由此可得出下式： )3-24(,1,1)()1( ijnjijinijkjkj Bxxy )-()(Rkjj 式（4-2-3）首先按照（ 4-2-1）式的方式产生一组分配方案，然后让其按照自行 车间行驶的规则再次分配，产生新的一组分配方案，然后用（4-2-4）式校正， 最终得到优化了的分配方案。 4.3 调度车调度方案建模 4.3.1 一辆调度车调度方案 在我们的求解问题中，第一问中调度车辆问 2 辆，为了问题是建模化简， 我们先考虑调度车为一辆的情况，然后推广到多量的情况，这样就可以给对第 一问和第三问的调度问题建立实际的解题模型。 设拥有最大负荷为 Q 的调度车从指定的节点出发，对集合为 G 的节点进行 调度。完成任务后返回原点。调度需求量和租赁点间的距离已经求得。整个调 度方案可以由下列一组方程和约束条件确定： )1-34(|min1, ijiijjxlvdT)2-(11njijix)3-4(1nij )-(1njix5340Qrl ijj)6-(1ijnjiBFZ - 9 - )7-34()(11ijnjinjiijj BxyZl )8-()(11ijnjinjiijjl （4-3-1）式为目标函数，求出最短距离； （4-3-2）确定了出发点，即必须从出发点出发，然后再回到出发点； （4-3-3）-（4-3-4 ）确定了调度车对特定节点只能调度 1 次，不能重复经过一 个节点； （4-3-5）式保证调度车调度时调度车上的数量能够满足任意节点的调度需求量， 同时装载量不能超过调度车的最大载重； （4-3-6）式确定了某一节点的总需求量就是从该租赁点离开去往其他租赁点的 自行车的数量之和； （4-3-7）式确定了每一节点的调度量； （4-3-8）式给出总需求量、分配量、调度量从该节点出发的自行车数目和到达 该节点的自行车的数量之间的关系。 4.3.2 多辆调度车调度方案 设拥有最大负荷为 Q 的 k 调度车从指定的节点出发，对集合为 G 的节点进 行调度。完成任务后返回原点。调度需求量和租赁点间的距离已经求得。整个 调度方案可以由下列一组方程和约束条件确定： )9-34(|min1, kijniijjjk xlvdT)10-3(1kui )-4(11njkinjkix)12-3(1,knijk - 10 - )13-4(11,knijkx0Qrlkijj)15-34(1ijnjiBFZ )6-()(11ijnjkinjkiijj xyl )71-34()(11ijnjkinjkiij BlZ)8-( 2010zjitkjitx （3-4-9）式为目标函数，求出最短距离； （3-4-10）式确定调度车的数目； （3-4-11）确定了出发点； （3-4-12）-（3-4-13 ）确定了每辆调度车对特定节点只能调度 1 次，不能重复 经过一个节点； （3-4-14）式保证每次调度时调度车上的数量能够满足任意节点的调度需求量， 同时装载量不能超过调度车的最大载重； （3-4-15）式确定了某一节点的总需求量就是从该租赁点离开去往其他租赁点 的自行车的数量之和； （3-4-16）式确定了每一节点的调度量； （3-4-17）式给出总需求量、分配量、调度量从该节点出发的自行车数目和到 达该节点的自行车的数量之间的关系。 （3-4-18）式保证不同的调度车不能再同一时刻到达同一个租赁点。 根据以上一组方程和约束条件，就可以将调度问题相对完整的描述出来。 这是一个优化问题，在求解过程中由众多的算法可以采用，但是考虑到算法的 复杂性可标称的简洁性，我们采用的算法是启发式算法，这将在模型求解中详 细讨论。 - 11 - 4.4 租赁点数目和位置的确定 题目中新增的租赁点是在已知的若干点中选取的，因此，分析清楚选取租 赁点的约束条件，就可以从最优解的角度得到新增的节点。 建立租赁点时首先考虑的是各个点的需求量（已知） ，由于在不同时段的需 求量不同，所以应当考虑平均需求、不同时段需求。所以首先我们应当确定加 权平均比例，一保证确定的租赁点在全天达到最优。在这里引入一个加权平均 比，取决于我们实际问题的要求和调度问题的特点。 首先将数据加权平均，有： 再将每一个租赁点的耗资数额按照公式（4-4-1）求出 ）（加 权 需 求 量 1-4bXaY 最后将耗资数额加和，即求得满足式（5-2-2）的最大 k 值。 ）（ 2-k1iip 考虑了需求量对新租赁点的影响之后，我们还需要考虑骑行规律对租赁点 选取的影响。所谓运输规律就是：居民可以在任意一个租赁点还车，在某个租 赁点还车的概率与租车点和还车点的距离成反比，且假设居民的骑行距离不超 过 M。于是仅考虑运输规律，我们引入一个方便因数，定义如下： ）（ 3-41SPyConii Con 用来衡量新设置的租赁点的合理程度，它与租赁点的分配量、常数 、iP 的乘积之和有关，其中，常数 的定义如下：iSi ）（ 4-1njijiBP 的定义如下：iS ）（ 5-41ijnjidS 表示 i 租赁点能够到达其他节点的数目之和， 越大表明该节点的辐射能力iS iS - 12 - 越强，也越合理。 在路程不超过 M 的范围内，租赁点 i 能够到达的节点越多，则常数 越大。iP 还要保证新增的节点数 k 尽可能地少。 在新增租赁点的过程中不考虑随后的调度方案，因此在总建设经费的限制下， 可以按照优化的方法求出方便因数的最小值。 4.5 调度时间的模型 在三期建设中，为了实现经开区更大的网点覆盖面积，进一步增设站点，新 增了一批租赁站点并购进自行车。然而，更多的站点可能会导致部分租赁点的 自行车短缺或堆积现象，从而降低了资源利用效率。为了探讨这个问题，我们 必须对现有调度方案进行检验和矫正，更好的实现资源利用最大化。故对调度 时间进行了计算，发现用两辆调度车进行自行车调度很难满足调度需求,调配时 间超过限制时间，必须购置更多的调度车辆，虽然会增加一定成本，但对整体 的统筹有很大的意义。 将原有的站点与新增站点进行混合，重新根据密集度，自行车需求量等因素 进行分组，根据分组情况配备调度车辆。若所分组数增多，则增加调度车辆的 数目可以更快捷地实现调度需求。然后对每一组的调度方案进行独立分析，即 求解 kijniijjk xlvdt1, |mi 则总调度时间： ktT1in （k 代表组数） 具体建模思想与第一问的求解相似。 - 13 - 五、 模型的求解 5.0 经纬度转换为横纵坐标 5.1 求解最短路径 思想描述： 我们将最短路径的计算作为一个函数。而经过讨论我们决定计算采用 Floyd-Warshall 计算方法（以下简称 Floyd 算法） 。Floyd 算法是以动态规划为手 段，以解决任意两点间的最短路径为目的的一种算法,该算法的时间复杂度为 )(3NO ，空间复杂度为 )(2NO。它可以正确处理有向图或负权的最短路径问题， 故该方法适用于我们的问题(在实际算法中，为了节约空间，我们直接在原来空 间上进行了迭代，这样空间可降至二维)。 Floyd 算法的描述如下： 设 kjiD,为从 i 到 j 的只以 ).1(k集合中的节点为中间节点的最短路径的长度。 若最短路径经过点 k，则 1,1, kjkiji D； 若最短路径不经过点 k，则 ,jiji。 因此， )min(1,1, kjikjikjiD。30;11 iii;1 jjj if ( jijkiD,) jiji , 综上,最短路径矩阵为：（单位：km） - 14 - 图 5-1-1 5.2 模型一次运行后的单车重分配求解 依据题意不难得知，在租赁点还车的概率与租车点和还车点的距离成反比，且 居民的骑行距离不超过 2km。 据骑行距离此可得出筛选算法： 1 30;1 iii k=1; ;1 jjj if i if 20,jid;,ji else ;0,jid k=k+1; 根据反比例关系不难得出每个租赁点向 2km 内的各个租赁点发送的单车数量 2 为： jijidKF, - 15 - 根据归一化条件： 11,njjijidKF 综上可得出求得 2km 内的概率系数 K 的算法：30;1 iii s=0; ;1 jjj if 0,jid ji s,1 ;s ； K=K s; 根据各个租赁点发送出的单车概率可求得运行一次后的各个租赁点单车数目： 3 nijjF1, 据此可得出求解运行一次后的各个租赁点单车数目的算法： 30;1 jjj t=0; ;1 iii if 0,jid jiKFt, ；tj ; 模型运行一次后的结果如图所示： - 16 - 图 5-2-1 5.3 求解分配方案的预估校正算法 每个租赁点的单车数量可以以预估计算的方式经多次计算得出一个稳定解。即 大部分租赁点的单车数量满足 110%的要求，少部分租赁点单车数目远远超出需 求量，还有少部分单车数目几乎为零（奇点） 。最后，将计算所得的几个奇点分 块，从自行车数量超出 40 或大量超出需求量的地点运送单车至奇点（用启发算 式法计算运送路线及运送时间） 。 5.4 求解调度方案的启发式算法 5.4.1 算法简介 启发式算法是依据有限的知识在短时间内找到问题解决方案的一种技术。 在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例 的一个可行解。 在搜寻问题中，每个节点都有 b 个选择以及到达目标的深度 d，一个毫无技 巧的算法通常都要搜寻 bd 个节点才能找到答案。启发式算法借由使用某种切割 机制降低了分叉率(branching factor)以改进搜寻效率，由 b 降到较低的 b。分叉 率可以用来定义启发式算法的偏序关系，例如：若在一个 n 节点的搜寻树上， - 17 - h1(n)的分叉率较 h2(n)低，则 h1(n) 27-7-8-9-28-10-24-22-6 早上 B：5-20-18-11-12-13-14-3-4 中午 A：9-10-24-22-4-17 中午 B：26-7-30-8-21-20-18-12-11 晚上 A；25-26-27-7-30-9-28-10-24-23-3 晚上 B：19-5-20-21-18-11-12-14-2 图 5-5-1 - 21 - 图 5-5-2 图 5-5-3 消耗时间为： 早上：t =7.9834e+003 s=133.1min 中午：t =5.4157e+003 s=90.3min 晚上：t =7.7568e+003 s=129.3min 平均：t=117.6min 5.6.2 第二问结果 如表 5-6-1 所示： 网点编 号 7:008:30车 辆需求数 11:0012:3 0车辆需求 数 17:3019:0 0车辆需求 数 均值 最大值 加权均值 耗资 56 40 40 40 40 40 40.0 90000 - 22 - 50 38 37 32 36 38 36.0 86000 72 23 39 34 32 39 34.0 84000 60 33 32 37 34 33 34.0 84000 77 33 36 28 32 36 34.0 84000 73 20 37 36 31 37 33.0 83000 90 23 32 37 31 37 33.0 83000 88 25 33 35 31 35 32.0 82000 47 23 36 32 30 36 32.0 82000 87 13 38 36 29 38 32.0 82000 69 39 21 23 28 39 32.0 82000 46 8 37 39 28 37 31.0 81000 62 7 37 38 27 38 31.0 81000 49 33 18 35 29 35 31.0 81000 31 40 27 8 25 40 30.0 80000 63 24 28 33 28 33 30.0 80000 84 21 29 33 28 33 30.0 80000 80 18 36 22 25 36 29.0 79000 36 15 37 22 25 37 29.0 79000 91 32 22 20 25 32 27.0 77000 76 19 27 29 25 29 26.0 76000 33 8 27 33 23 33 26.0 76000 45 18 26 23 22 26 24.0 74000 41 32 12 12 19 32 23.0 73000 1939000 表 5-6-1 综上所述，我们得出的答案： 新增租赁点数目为 23 个，租赁点编号和相对应的放置车辆数目如表所 示： 表 5-6-2 网点位置如图 5-6-1 所示： 租赁点编号 31 33 36 45 46 47 49 50 56 60 62 63 放置车辆数目 34 29 32 26 36 36 34 41 44 39 35 33 租赁点编号 69 72 73 76 77 80 84 87 88 90 91 放置车辆数目 35 38 37 30 37 32 33 36 36 37 30 - 23 - 图 5-6-1 5.6.3 第三问结果 若只有两辆车，那么结果为： - 24 - 早上 A：25-41-52-40-39-30-8-6-22-38 早上 B：29-19-5-20-4-17-3-31-51-12-49-47-43 中午 A：23-36-9-30-39-28-10-37-38-34-22-4-33-32 中午 B：16-15-1-31-13-14-51-12-48-50-11-49-47-46-45- 52 晚上 A：8-21-16-15-50-51-2-32-33-34-38-10 晚上 B：25-26-42-7-30-28-39-40-52-53-41-45-46-47-49 早上：t=9.6054e+003 s=160.1min 中午：t=1.2808e+004 s=213.5min 晚上：t=1.3061e+004 s=217.7min 平均：t=197.1min150min 综上，仅有两辆运输车是不够的，所以我们就三辆运输车的情形进行了分 块计算。计算结果如下： - 25 - 上午 A：35-38-28-39 上午 B：21-20-5-19-31-3-4-22-6-8-40 上午 C：42-52-41-43-44-12-51-50-49-47 中午 A；37-24-34-38-36-10-28-39 中午 B：8-23-22-6-4-33-32-31-51-50-48 中午 C：26-25-52-45-46-47-49 晚上 A：24-35-9-28-40-39-10-38-34 - 26 - 晚上 B：16-15-50-2-32-33-23-21 晚上 C：18-43-25-41-53-52-45-46-47-49 早上：t=6.3253e+003 s=105.4min #include #include #include #define ZD 20/定义站点数 ZD = Zhan Dian #define DE 3/搜索深度 - 32 - using namespace std; int numZD;/各个站点相应的多余、缺少的车辆的数目 int route10*ZD; /车行走的路径 bool I