公共自行车租赁

光电 26 队数模模拟训练 1 对“城市公共自行车租赁服务系统规划” 问题的研究 学院：光电工程学院 队员：浦文丽 杨昌华 聂丽霞 指导教师：杨春德 西安市经开区公共自行车服务系统设计 摘 要 本文研究的是西安市经开区公共自行车的分配和调度优化问题，通过建立 01 整 数规划模型，线性规划模型以及自行车分配调度模型，设置合理的分配方案和调度方 案，以满足所有租赁点对自行车的数量需求，同时车辆调度花费时间力求最短。最后， 通过最小生成树算法得到最优路径和最短时间。 对于第一问，根据目前经开区网点自行车需求情况，若要求调度平均耗时尽 量少，请针对已有的 30 个租赁点设计最优车辆分配方案、调度方案，并给出完成调度 所耗费的时间。 依据租赁点的需求和约束条件对自行车进行初始；依据经纬度和 Floyd 算法求出 各租赁点之间的距离，引入 01 变量表示租赁点间是否发生调度、，采用最小生成树 算法，经过租赁点的时间及装卸自行车的时间为权重，通过 MATLAB 编程采用避圈法求 解最小生成树，求得的路径就是最佳行车路线，其中每辆车调度一次平均用时 135 分 钟，完成一天的调度总时间为 806 分钟。 对于第二问，约束为投入经费总数和租赁点自行车需求，目标是设置的租赁点能 够覆盖更大的面积，而且整个调度花费时间较少，用 excel 将备选租赁点需求量由大 到小排序，选取自行车需求较多的网点，应用动态规划算法，设新增租赁点数为 k,代 入经费约束即可得到 k 值不大于 25，通过调整新增租赁点采用启发式搜索求新增网点 和车辆的合适分配方案，编程得出新增网点为 24 个，自行车总数 751 辆 ，总耗资 195.1 万。 对于第三问，通过增加调度车来减少调度时间，首先，我们同问题一一样确定了 调度车的路线，考虑到最大限度提高调度的效率，于是，同时对应着附件所给的地图 做出了相应的调整，尽量让一辆调度车在某一个区域中调度，从而覆盖全范围。新增 调度车 k 辆，根据问题二的分配结果用问题一的模型计算调度花费的时间，各分区内 都采用最小生成树算法求解最优调度路线，改变 k 值和分区，直到所有分区都能满足 150 分钟内调度完毕，即为新增调度车数。 关键词：最优分配 VRP 模型 最小生成树避圈法 启发式搜索 0-1 变量 一、问题背景与重述 近年来，随着经济的发展，我国各级城市的机动车保有量都进入了持续高速增长 时期，但由此所引发的道路拥堵、空气污染也引起了政府以及百姓的极大关注。众所 周知，建立快速、便捷的城市公共交通体系是解决这一问题的有效手段之一。然而， 居民居住地和交通站点通常都有一段距离，这段不远的距离以及现实存在的公共交通 拥挤现象则使居民乘坐公共交通的意愿降低，公共自行车服务系统已被证明能够从一 定程度上缓解这一现象。西安市经开区前两期建设的租赁点有 30 个，出租自行车达 850 辆，而且每个租赁点放置车不超过 40 辆，车辆总数超过需求量的 10%。调度车有 2 辆，每次运载 50 辆自行车。目前正筹备第三期租赁点的建设，请你就如下问题建模： （1）根据目前经开区网点自行车需求情况等信息，若要求调度平均耗时尽 量少，请针对已有的 30 个租赁点设计最优车辆分配方案、调度方案，并给出完成调度 所耗费的时间。 （2）假设经开区公共自行车服务系统三期建设准备投入建设经费 200 万元， 据此建立数学模型，确定新增租赁点数目、位置以及合适的放置车辆数目。 （3）针对问题（2），进一步研究，如果要求在 150min 内完成调度，是否需 要增加调度车辆（购置调度车辆费用由其它项目经费解决，不包含在三期建设提供的 200 万元经费中间）？并给出该情形下的自行车调度方案。 附加问：（如有时间，参赛者可以选作，在评阅时作为附加分参考） （4）经开区计划建设公共自行车借还在线查询网站（参考神木县公共自行 车网站 /map.asp 或其它类似网站），实现借还数据的实时更 新。届时，自行车调度专员需要根据系统实时数据进行实时调度。如果要求站点自行 车数量超过 90%就必须下架一部分车，站点自行车数量不足 20%时，就要补车，保证用 户任何时间都能取车还车。请考虑动态的车辆调度方案设计，给出此时的自行车调度 模型并模拟计算。 二、问题分析 针对以上问题，我们首先要根据题目给出的经纬度与位置坐标，通过 MATLAB 计 算出两两之间的距离。 问题一分析：本问题可以看成是单目标规划问题，我们的目标是使公交车行驶的 路程最短，再将路程转换成时间来进行计算求解。考虑到在一次调度车全程收集和分 配自行车总数不相上下的情况，即在一次调度中，不管你选择的路径如何，其装载或 卸载的自行车的时间可以看做一个常数。从而目的是要找到一条最短的公交行驶路径。 我们用 0-1 变量来表示公交车是否从租赁点 i 到达租赁点 j，而且每时每刻调度车上 的自行车数不得超过限载量 50 辆。通过对本问题的分析，根据结论要保证调度平均 耗时最少，则在每个时间段内调度车行驶时间和装卸自行车总时间要最少，先求解出 租赁点之间的实际车行距离和居民还车的概率，也相继可以确定居民还车数目，根据 每个租赁点的需求数,通过建立相应的数学模型。因此可以根据已知的道路连通图， 首先通过 Floyd 算法算出任意两个租赁点间的距离，其次以时间为权重建立最小生成 树模型，先得到一辆调度车的最短时间，在此基础上进行叠加，找出能使调度车耗时 最少的行驶路线和调度车的分配方案 。 问题二分析：对于新增租赁点的位置，我们不妨按照居民需求来确定。依据西安 经济技术开发区公共自行车网点车辆需求信息。不难确定除了前期 30 个网点之外， 其他网点需求量的大小，进而对其按照需求大小排序。然后我们再利用 200 万元建设 经费的限制及自行车购买维护费用、租赁网点费用等，便可以确定出来新增服务点的 数目。 问题三分析：150min 内完成调度是否需要增加调度车。这个问题的求解显然可以 在问题一的基础上得到结果。如若得到的时间大于 150，就对问题一进行修改，问题 一是求两辆调度车完成调度的一个最短时间问题，而问题三是一个最大时间不超过 150min 问题。不难看出两者具有一定的相似性，只是对问题一目标方程上对调度车的 一个叠加上有所变化。 三、 模型假设 1、同一辆调度车只能经过同一个租赁点一次（车站租赁点除外）； 2、假设车辆行驶中无安全事故，遵守交通规则，十字路口遇红路灯的情况忽略不计； 3、假设自行车不能通过人力挪移过街道； 4、假设多余自行车的租赁点为供应点，多余的自行车数为富余量；缺少自行车的租 赁点为需求点，缺少的自行车数为缺省量。 四、符号说明 - 调度总时间（不包括完成调度后调度车返回原点的时间）T - 调度车编号k - 租赁点间的最短距离ijd -i 和 j 间的距离是否大于 2kmX -租赁点 j 的需要调度的量jL -i 和 j 间的是否需要调度iB -第 j 租赁点需要分配的自行车数量jZ -第-j 租赁点点的需求量占总需求量的比例W -第-j 租赁点的初始分配jY -第-j 租赁点借走后送还的车辆X -从 i 点出发到达 j 租赁点的自行车数量ijF -i 点的单车数量i 五、模型建立与求解 5.1 模型建立 5.1.1 最优分配方案的确立 对于问题一，由于需要求解的最短时间与租赁点之间的距离有一定的关系，于是 通过题目给出的经纬度找到坐标位置，然后由 MATLAB 软件中的 distance(lat1,lon1,lat2,lon2,6378.1)语句计算出任意两点之间的距离矩阵，其结 果见附页。 应题目要求，我们先设计最优分配方案，即每个租赁点的需求概率如下： = (n=30) （1）WjnjjZj1 则初始分配的租赁点自行车数量为： （2）Yajj 其中 a 为已知的 850 辆。由于不同的租赁点市民还车的概率不同，就此在（1）、 （2）式的基础上做以修改。 经过一段时间，原来分配好的租赁点的自行车数量由于市民的需求，不断的骑走 与归还，租赁点车数变为： （3）XjjZ 其中 为该租赁点借走后送还的车辆，计算公式为：Xj （4）YjjP P 为在 2km 的条件下，租赁点市民归还自行车的概率 （5）dK d 为自行车行驶路程，K 为比例系数且可由线性规划计算得到。 5.1.2 点的分配方案级调度车的路径确定 在问题一中，我们已经求解出来最优车辆分配方案，在此基础上就可以确定各个 租赁网点的需要调度的车辆。问题一中，根据题目要求，我们运用了启发式算法求解 最优化问题。启发式算法（heuristic algorithm)是相对于最优化算法提出的。一个 问题的最优算法求得该问题每个实例的最优解。其定义为一个基于直观或经验构造的 算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例 的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。它的图册如下： 此外我们还运用到了 01 规划，01 型整数规划模型要求决策变量的取值仅为 0 或 1，该模型也对应着大量的最优决策的活动与安排讨论。本问题中讨论了当取值 为 0 时，表示不需要调度车辆；取值为 1 时，表示需要调度车辆。 在问题一中，我们已经求解出来最优车辆分配方案，在此基础上就可以确定各个 租赁网点的需要调度的车辆。故而现只需求解出需要调度租赁点之间的最短路径即可。 根据最短路径的需求，运用了最小生成树避圈法来得到这些租赁点之间的最短距离。 根据模型分析中的计算公式以及针对题目提出的时间最短问题，把以上对路程的 求解转换成对时间的求解，最短时间计算目标方程如下： （6） 301301min2ijjjiLBdT 表示第 j 个租赁点需要调度自行车的数量， 表示从 到 所需要的调度Lj ijij （7）QRLjj0 其中 表示在第 j 个租赁点调度后已有的自行车数目，Q 为 50Rj （8） 不 需 要 调 度需 要 调 度01ijB （9）YXLMjjj j （10）Aijij 10 （11）40%1Zjjjj 表示自行车租赁网点的放置的自行车数目应超过需求的 1.1 倍但不能过 40 以上的计算只考虑了第一辆调度车的情况，而第二辆调度车的调度方式与第一辆 的调度方式大体相同，相当于叠加原理。 5.1.3 新增租赁点数目、位置以及合适的放置车辆数目的确定 根据附件中的的公共自行车租赁网点需求数据按照需求量的大小进行排序，对于 新增的网点位置的确定就根据需求量来确定，又由于经开区公共自行车服务系统三期 建设准备投入建设经费不超过 200 万元。 从而可得限制条件： （12）bXhPii （13） 20301ii 其中 h 表示建设一个租赁服务网点需要的费用； 表示第 i 个租赁点的应投放的自行车数目；iX b 表示在使用周期内，购买、养护一辆自行车需要的费用。 5.1.4 在 150min 内是否能完成任务及增加调度车数目确定 对于问题三，在问题一、二的基础上，不难求解。其大体思路只是对问题一作以 修改。 首先我们依然依据方程 对两辆调度车的最 301301min2ijjjiLBdT 短时间及车辆的调度方案进行求解。得到的最短时间为 由前面的结果，显然可知这个时间是大于 150 的，自然需要增加调度车。由题意 得到的约束条件为 knijjknijiLBdT/1/12 （14）50max 其中 n 表示增加租赁点后网点的数量， k 表示增加租赁点后需要的调度车的数量 对于目标方程的约束条件与问题一的（7）（9）（11）并无差异 5.2 模型求解 5.2.1 各个网点需求量的求解 由附页所给的西安经济技术开发区公共自行车网点车辆需求信息我们便可以确定 初始分配，其结果如下： 5.2.2 系数 K 的求解 依据题意不难得知，在租赁点还车的概率与租车点和还车点的距离成反比，且居民的 骑行距离不超过 2km。 （1）据骑行距离此可得出筛选算法思路如下： （2）根据反比例关系不难得出每个租赁点向 2km 内的各个租赁点发送的单车数量为：jijidF, 根据归一化条件： 11,njjijiK 综上可得出求得 2km 内的概率系数 K 其中 K 的结果为 租赁点 1 2 3 4 5 6 需求量 27 32 37 36 26 25 租赁点 7 8 9 10 11 12 需求量 32 34 25 34 26 34 租赁点 13 14 15 16 17 18 需求量 25 17 30 19 34 36 租赁点 19 20 21 22 23 24 需求量 26 23 32 25 32 26 租赁点 25 26 27 28 29 30 需求量 18 23 36 22 20 25 （3）根据各个租赁点发送出的单车概率可求得运行一次后的各个租赁点单车数目： nijjF1, 据此可得出求解运行一次后的各个租赁点单车数目的思路如下所示： for（j=1;j28=9=30=7=8=23=6=4=17=3=2=14 车二路线：11=12=13=1=15=16=29=19=5=20=21=25=26=27 两辆调度车分别用时为 租赁 点 最优分配数 租赁 点 最优分配数 租赁 点 最优分配数 1 18 11 24 21 26 2 27 12 40 22 39 3 40 13 16 23 18 4 40 14 16 24 37 5 20 15 40 25 26 6 40 16 20 26 29 7 16 17 24 27 40 8 40 18 30 28 24 9 30 19 34 29 20 10 23 20 28 30 25 5.3，1 新增租赁点数目、位置以及合适的放置车辆数目 对于新增的租赁点的数目、位置及合适放置的自行车数目，我们首先利用了 Excel 对附件 2 中经开区公共自行车租赁需求数据按照需求量的大小做了排序，用来 确定新增的租赁点的位置，进而再利用经费的限制条件来确定新增租赁点的数目。投 放的车辆的求解与问题一中的分配方案大体相同，其决定的租赁点及分配结果如下： 4、新增网点之后，两辆调度车完成调度的最短时间，这个的求解过程跟问题一并 不差异，只是把新增的网点经纬度等数据添加进去，再结合地图中具体的情况作分析， 于是可以得到时间 T=？ 5、需要增加的调度车的数量及调度方案 新增租赁点之后，调度车的最优调度方案自然也会随之而改变，但是其求解思路 与问题一大体相同。 knijjknijiLBdT/1/12 新增租赁点 31 33 36 41 45 46 47 49 设置车辆 31 27 30 24 24 32 33 31 新增租赁点 50 56 60 62 63 69 72 73 设置车辆 37 40 35 32 30 32 35 33 新增租赁点 76 77 80 84 87 88 90 91 设置车辆 27 34 30 30 33 33 33 28 若要满足时间 T20=5=19=29=16=1=13=12=88=14=3=17=4=4=6=22=23=8 车二路线： 84=81=80=18=72=77=76=69=25=26=27=63=7=30=60=90=91=73=62 车三路线：31=33=36=45=41=24=49=46=50=10=56=28 以及三辆调度车一次耗时 六、模型的分析和检验 6、1 模型检验： 这三个问题的模型检验均要通过实际的分配调度实现，在一、三问题中，我们利 用了 Floyd 算法和最小生成树模型，在问题一、二中的分配方案，按照需求做了一个 初始分配，然后按照还车概率做了一个修正方案，其合理性可以通过题目中要求分配 的数量达到需求的 1.1 倍条件来实现。 我们利用模型一得到的自行车分配方案，将各网点的需求量与实际分配量相比较， 各网点都能够满足需求，代入约束条件后，符合要求，并且得到的配送路线花费的时 间能够使租赁系统正常运行，所以认为模型一比较可靠。 七、模型检验 在确定自行车的分配方案和调度方案时，这个问题是在已知节点具体的位置的条 件下求解两个问题。我们对两个问题分开求解，即先确定最分配方案，再根据最优分 配方案确定对应的最优调度方案。然而根据数学模型和实际情况得这两者并不是相互 独立的，即问题最优解并非简单地两者最优解的结合。因此，我们的最优结果可能和 实际情况存在偏差。 为了方便问题的求解，我们在利用经纬度求解任意两点之间的距离时，并没有考 虑若任意两点之间的距离还与街道布局等有关。 最小生成树算法，目前看来该算法比较成熟，程序易实现，把时间作为权值，得 到的结果也相对准确。 最小生成树模型在很多方面都能够应用，譬如城市之间的通信之间的网点 n 个， 快递服务点的网点等运输优化方案和资源配置优化的问题中。 八、参考文献 【1】赵静，但琦，严尚安 杨秀文 数学建模与数学实验 北京：高等教育出版社， 2014.1 【2】李学文，李炳照，王宏洲 数学建模优秀论文精选与点评. 北京：清华大学出版 社 2011.9 【2】刘登涛, 方文道, 章坚民, 等. 公共自行车交通系统调度算法J. 计算机系统 应用, 2011, 20(9): 112-116. 【】 崔宏志, 龚加安. 带时间窗车辆路径问题的改进节约算法J. 纯粹数学与应用 数学, 2011, 27(5): 688-693 【】 柳祖鹏, 丁卫东, 程逸旻. 公共自行车系统站间调度优化研究J. 城市公共交 通, 2011 (1): 39-42 【】卓金武，魏永生，李必文. MATLAB 在数学建模中的应用 北京：北京航天航空大学， 2011.4 九、附录 （1） 距离计算： N= 108.952954 34.324828 108.948562 34.323762 108.943199 34.32634 108.943387 34.333265 108.953161 34.334874 108.944636 34.338787 108.952532 34.350865 108.950232 34.347572 108.945525 34.353369 108.936075 34.362644 108.966896 34.321862 108.958515 34.320289 108.954131 34.320766 108.953233 34.319536 108.954643 34.325223 108.95502 34.326699 108.94336 34.327779 108.959745 34.332914 108.953439 34.333272 108.954014 34.336238 108.954176 34.339934 108.940288 34.339114 108.944591 34.342825 108.932985 34.34673 108.962386 34.347557 108.959018 34.347512 108.95617 34.34784 108.945435 34.362294 108.953287 34.330239 108.95017 34.353466 ; for i=1:30 for j=1:30 D(i,j)=distance(N(i,2),N(i,1),N(j,2),N(j,1),6378.1); end end D （2） 系数 K 的求解： K=; for i=1:1:30 s=0; for j=1:1:30 if z(i,j)=0 s=s+1/z(i,j);%输出概率的 K end end s=1/s; K=K s; end （3） 最小生成树的程序 function b,u,w=mintrees(a,k)%最小生成树 ，a 邻接矩阵，k 起点 if nargout=1 k=1; end m,n=size(a); for i=1:m for j=1:n if a(i,j)=0 a(i,j)=inf; end end end b=zeros(n); u(1)=k; j=1; v=zeros(1,n); v(k)=1; for o=1:n-1 sn=ones(3,n)*inf; for xk=1:j k=u(xk); p=max(a(k,:); for i=1:n if v(i)1 end end for i=1:n if v(i)1 end end sn(1 2 3,k)=i,p,u(xk); end w(j),k=min(sn(2,:); j=j+1; u(j)=sn(1,k); b(sn(1,k),sn(3,k)=sn(2,k); v(u(j)=1; end （4） 最小生成树结果： 结果一（30 个网点）： u = Columns 1 through 15 30 7 8 9 27 26 25 23 6 22 4 17 3 2 1 Columns 16 through 30 15 16 29 19 5 20 21 13 14 12 18 11 28 10 24 w = Columns 1 through 9 0.3619 0.4232 0.4270 0.4745 0.2643 0.3096 0.7403 0.4495 0.4013 Columns 10 through 18 0.6253 0.6107 0.1609 0.5705 0.4208 0.1614 0.1679 0.4251 0.3379 Columns 19 through 27 0.1802 0.1709 0.4117 0.4649 0.1599 0.4065 0.5810 0.7902 0.9936 Columns 28 through 29 0.8610 1.0814 结果二（54 个网点）： u = Columns 1 through 19 54 42 46 25 26 27 43 7 30 8 9 37 23 6 22 34 4 17 3 Columns 20 through 38 2 1 15 16 29 19 5 20 21 13 14 52 12 51 31 49 18 45 36 Columns 39 through 54 38 24 35 32 33 11 50 53 44 47 48 39 41 28 40 10 w = Columns 1 through 11 0.6337 0.3928 0.4616 0.3096 0.2643 0.2753 0.2610 0.3619 0.4232 0.4270 0.5887 Columns 12 through 22 0.5397 0.4495 0.4013 0.4678 0.6253 0.6107 0.1609 0.5705 0.4208 0.1614 0.1679 Columns 23 through 33 0.4251 0.3379 0.1802 0.1709 0.4117 0.4649 0.1599 0.2716 0.4065 0.5292 0.5546 Columns 34 through 44 0.5644 0.5077 0.0929 0.6473 0.3444 0.3616 0.6476 0.6671 0.6025 0.6775 0.6865 Columns 45 through 53 0.6928 0.7274 0.8255 0.8453 0.8652 0.9394 0.9936 0.8243 0.8610 （5） 网点 编号 网点 位置 车辆 需求 数 还车概 率 还车 数 初始 配置 还后数 量 1.1 需求 调度 车辆 最优 配置 1 经发大厦 15 0.0235 0 18 18 17 -1 18 2 可口 可乐 北门 23 0.0328 1 28 27 25 -2 27 3 经发 国际 会馆 38 0.0399 2 46 44 42 -2 40 4 昆仑银行 38 0.0378 1 46 45 42 -3 40 5 赛高街区 17 0.0201 0 20 20 19 -1 20 6 西安 中学 西门 32 0.1163 4 38 34 35 1 40 7 运动 公园 东门 13 0.0246 0 16 16 14 -2 16 8 运动 公园 南门 40 0.0446 2 48 46 44 -2 40 9 管委会 26 0.029 1 31 30 29 -1 30 10 出口 加工 区广 场 18 0.1121 2 22 20 20 0 23 11 鼎新花园 18 0.0608 1 22 21 20 -1 24 12 西安 外国 语学 校 35 0.047 2 42 40 39 -1 40 13 雅荷花园 7 0.0412 0 8 8 8 0 16 14 御道华城 12 0.0464 1 14 13 13 0 16 15 天地 时代 广场 38 0.0223 1 46 45 42 -3 40 网 点 编 号 网点 位置 车辆 需求 数 还车概 率 还车 数 初始 配置 还后 数量 1.1需 求 调度 车辆 最优 配置 16 市图书馆 17 0.0166 0 20 20 19 -1 20 17 文景观园 21 0.0371 1 25 24 23 -1 24 18 长庆 电视 台 23 0.0259 1 28 27 25 -2 30 19 移动公司 28