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

1 目录目录 一 问题引入一 问题引入 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 12 1 第一问分析第一问分析 第 1 问对对应前两期工程 30 个租赁点已知 因此在已知的点上根据需 求量确定自行车的分配方案和调度方案 这个问题是在已知节点具体的位置的 条件下求解两个问题 每个节点的自行车分配问题和调度问题 这两个问题可 以分开来求解 第 1 问要求调度时间尽量少 我们从计算两点的最短路径入手 将最短路 径计算出后考虑将早中晚三个时间段内的高峰期取平均值后再最初计算 我们 建立反比例函数关系式 p Kd 再根据归一化条件求得 2km 内的概率系数 K 随后 算出每个点以需求量的数目的前提下会向 2km 内的各个租赁点送出多少 辆单车 并以负反馈的方式经多次计算得出一个稳定解 即大部分租赁点的单 车数量满足 110 的要求 少部分租赁点单车数目远远超出需求量 还有少部分 单车数目几乎为零 奇点 最后 将计算所得的几个奇点分块 从单车数量超 出 40 或大量超出需求量的地点运送单车至奇点并计算运送时间 2 22 2 第二问分析第二问分析 第 2 问对应第三期工程 根据投入的建设费用等确定新增的租赁点的数 目和每个租赁点的分配方案 这些新增的租赁点是在规定的 70 个点中选取的 而且每个待选点的需求量是给定的 因此在需求量和工程费用的限制下 求实 现服务系统最优的选点方案和分配方案 建立新的一定数目的租赁点 我们首先将另外 70 个点的数据列出 考虑到 是否选择一个点与这个点的平均需求量和最大需求量均有关 所以将早中晚三 个时间段的需求量的平均值和三个时间段需求量的最大值列出 然后将这两个 数据以一定比例加权平均 最后得出的数字排序 由上到下计算出每个点的需 求金额 截止到 2000000 元时 租赁点即为截止前的点 相对应的数目即为每 个点对应的数目 2 32 3 第三问分析第三问分析 第 3 问建立在第 2 问的基础上 同第 1 问 类似 在解第 3 5 问前 租赁点的具体位置和需求量已知了 并且 这些租赁点的分配方案也已 将求得 很容易求得每一个租赁点需要调度的具体数值 在这些已知条件下 要求在给定时间内完成调度 给出调度方案 如调度车辆不够 则给出增加的 车辆数目和调度方案 问题类似于第 1 问的给出分配方案后求调度的问题 根据以上分析 我们要解决的问题主要有以下几个部分 1 求出任意两个租赁点之间的最短路径 2 求出给定租赁点的分配方案 3 求出给定租赁点的系统的自行车调度方案 4 在给定约束下求租赁点的数目和位置 解决以上三个问题 本题所要求的问题就可以解决了 三 模型假设和符号说明三 模型假设和符号说明 3 13 1 模型假设模型假设 1 每个租赁点调度需求量为负 有多余的自行车可以提供给调度车则为正数 2 假设两个停车场就在某两个租赁点上 则选取的两个租赁点必须是有自行车 盈余的点 并且调度车出发后 车上装载的自行车的数量就是租赁点的调度量 由于每个租赁点的自行车最大分配量小于调度车的最大装载量 所以总是能够 将盈余量全部装在调度车上 3 每辆调度车从固定的某租赁点出发 最后又回到原来的点 以方便下次调度 但是回到原点的时间可以不计 因为只有在调度完成后才会回到原点 此时不 需要调度 不再受时间限制 4 同一辆调度车只能经过同一个租赁点一次 除了作为车站的租赁点 5 每次到达下一个租赁点时 调度车上的自行车数量满足该租赁点需求 即对 于需求点来说 只需用调度一次就完成调度 对于盈余点来说 调度车到达这 些点要尽量多装 如果未达到调度车的限量就将该租赁点所有的盈余自行车装 6 载 如果多出 则装满 3 23 2 符号系统符号系统 G 租赁点的集合 调度总时间 不包括完成调度后调度车返回原点的时间 T 调度车编号k 租赁点间的最短距离 ij d 第 k 辆车调度完 i 后是否再调度 j k ij x 是否使用调度车 k k u 租赁点 j 的需要调度的量 j l i 和 j 间的距离是否大于 M 千米 ij B t 时间段内租赁点 j 的需求量 t j Z j 点的需求量占总需求量的比例 j 从 i 点出发到达 j 租赁点的自行车数量 ij F i 点的单车数量 i F a 建立一个租赁点耗资 b 维护每辆自行车耗资 p 每一个租赁点的耗资数 P 新增租赁点的耗资总数 四 模型建立四 模型建立 4 14 1 模型分类模型分类 在租赁点的分配方案确定后 只剩下调配问题 属于VRP问题 该问题是 7 著名的问题TSP 旅行商问题 的一个特例 因而也是NP hard问题 典型的VRP模型定义如下 假设已知客户网络中的客户数量 客户所在的位 置 客户需求和配送车辆的最大负荷 要求在满足约束的前提下为给定的中心 仓库设计车辆路径 使运输成本最小 传统电子商务配送模型是分区域配送模式的单一配送中心 Distribution centre DC 多需求点 demands DS 的路径优化模型 而且不考虑沿途补 货的情况 而针对区域广泛 客户众多且分散 业务量大且频繁的电子商务物 流配送业务 需要考虑多个配送区域联合 沿途多次补货的配送策略 从而得 到电子商务配送的跨区域VRP模型 这个思路和我们所要考虑的利用公交车收集和分配公共自行车很类似 问 题中有多余自行车的租赁点即可看作电子商务问题中的配送中心DC 而缺少自 行车的租赁点也可看作是需求点DS 我们的问题和电子商务问题的一个不同点是 在调度时 如果调度点由盈 余的自行车且数量加上调度车上已有的自行车时其总量会可能会超过调度车的 最大装载量 因此有可能导致这些点的二次调度 这和电子商务配送模型中一 次性完成调度有所区别 但是可以经过是党的改正后得到正确的模型 4 24 2 租赁点分配方案建模租赁点分配方案建模 影响租赁点自行车分配的因素有 各租赁点的需求量 从租赁点离开的自 行车 从其他租赁点起来的自行车等 若仅考虑需求量对租赁点分配自行车数 目的影响 有如下模型 124 j t jj Zy 2 2 4 1 n j t j t j j Z Z 1 式确定按照最终的需求量 以按比例分配的方式确定租赁点的分配量 2 式给出需求量占总需求量的比例 以仅考虑需求量的方式确定的分配方式显然不是最佳方案 分配方案还和租赁 点之间的距离有关 由题意可知 从在某个租赁点还车的概率与租车点和还车 8 点的距离成反比 且假设居民的骑行距离不超过 M km 由此可得出下式 3 2 4 1 1 1 ij n jii ijji n ijj ji k j k j BxBxyy 4 2 4 1 Ryy k jj 式 4 2 3 首先按照 4 2 1 式的方式产生一组分配方案 然后让其按照自行 车间行驶的规则再次分配 产生新的一组分配方案 然后用 4 2 4 式校正 最终得到优化了的分配方案 4 34 3 调度车调度方案建模调度车调度方案建模 4 3 14 3 1 一辆调度车调度方案一辆调度车调度方案 在我们的求解问题中 第一问中调度车辆问 2 辆 为了问题是建模化简 我们先考虑调度车为一辆的情况 然后推广到多量的情况 这样就可以给对第 一问和第三问的调度问题建立实际的解题模型 设拥有最大负荷为 Q 的调度车从指定的节点出发 对集合为 G 的节点进行 调度 完成任务后返回原点 调度需求量和租赁点间的距离已经求得 整个调 度方案可以由下列一组方程和约束条件确定 1 3 4 min 1 1 ij n iijj j ij xl v d T 2 3 4 1 11 n j ji n j ij xx 3 3 4 1 1 n i ij x 4 3 4 1 1 n j ij x 5 3 4 0Qrl ijj 6 3 4 1 ij n j iji BFZ 9 7 3 4 11 ij n j ij n j jiijj BxxyZl 8 3 4 11 ij n j ij n j jiijj BxxylZ 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 24 3 2 多辆调度车调度方案多辆调度车调度方案 设拥有最大负荷为 Q 的 k 调度车从指定的节点出发 对集合为 G 的节点进 行调度 完成任务后返回原点 调度需求量和租赁点间的距离已经求得 整个 调度方案可以由下列一组方程和约束条件确定 9 3 4 min 1 11 k ij n iijj j ij k k xl v d T 10 3 4 1 ku k i i 11 3 4 1 11 n j k ji n j k ij xx 12 3 4 1 1 1 k k n iji k ij x 10 13 3 4 1 1 1 k k n ijj k ij x 14 3 4 0Qrl k ijj 15 3 4 1 ij n j iji BFZ 16 3 4 11 ij n j k ij n j k jiijj BxxyZl 71 3 4 11 ij n j k ij n j k jiijj BxxylZ 18 3 4 2010 z jit k jit xx 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 44 4 租赁点数目和位置的确定租赁点数目和位置的确定 题目中新增的租赁点是在已知的若干点中选取的 因此 分析清楚选取租 赁点的约束条件 就可以从最优解的角度得到新增的节点 建立租赁点时首先考虑的是各个点的需求量 已知 由于在不同时段的需 求量不同 所以应当考虑平均需求 不同时段需求 所以首先我们应当确定加 权平均比例 一保证确定的租赁点在全天达到最优 在这里引入一个加权平均 比 取决于我们实际问题的要求和调度问题的特点 首先将数据加权平均 有 再将每一个租赁点的耗资数额按照公式 4 4 1 求出 加权需求量 1 4 4bXaY 最后将耗资数额加和 即求得满足式 5 2 2 的最大 k 值 2 4 4 k 1i i bXap 考虑了需求量对新租赁点的影响之后 我们还需要考虑骑行规律对租赁点 选取的影响 所谓运输规律就是 居民可以在任意一个租赁点还车 在某个租 赁点还车的概率与租车点和还车点的距离成反比 且假设居民的骑行距离不超 过 M 于是仅考虑运输规律 我们引入一个方便因数 定义如下 3 4 4 1 SPyCon i n i i Con 用来衡量新设置的租赁点的合理程度 它与租赁点的分配量 常数 i P 的乘积之和有关 其中 常数的定义如下 i S i P 4 4 4 1 n j iji BP 的定义如下 i S 5 4 4 1 ij n j iji dBS 表示 i 租赁点能够到达其他节点的数目之和 越大表明该节点的辐射能力 i S i S 12 越强 也越合理 在路程不超过 M 的范围内 租赁点 i 能够到达的节点越多 则常数越大 i P 还要保证新增的节点数 k 尽可能地少 在新增租赁点的过程中不考虑随后的调度方案 因此在总建设经费的限制下 可以按照优化的方法求出方便因数的最小值 4 54 5 调度时间的模型调度时间的模型 在三期建设中 在三期建设中 为了实现经开区更大的网点覆盖面积 进一步增设站点 新 增了一批租赁站点并购进自行车 然而 更多的站点可能会导致部分租赁点的 自行车短缺或堆积现象 从而降低了资源利用效率 为了探讨这个问题 我们 必须对现有调度方案进行检验和矫正 更好的实现资源利用最大化 故对调度 时间进行了计算 发现用两辆调度车进行自行车调度很难满足调度需求 调配时 间超过限制时间 必须购置更多的调度车辆 虽然会增加一定成本 但对整体 的统筹有很大的意义 将原有的站点与新增站点进行混合 重新根据密集度 自行车需求量等因素 进行分组 根据分组情况配备调度车辆 若所分组数增多 则增加调度车辆的 数目可以更快捷地实现调度需求 然后对每一组的调度方案进行独立分析 即 求解 k ij n iijj j ij k k xl v d t 1 11 min 则总调度时间 k k k tT 1 min k 代表组数 具体建模思想与第一问的求解相似 13 五 五 模型的求解模型的求解 5 05 0 经纬度转换为横纵坐标经纬度转换为横纵坐标 5 15 1 求解最短路径求解最短路径 思想描述 思想描述 我们将最短路径的计算作为一个函数 而经过讨论我们决定计算采用 Floyd Warshall 计算方法 以下简称 Floyd 算法 Floyd 算法是以动态规划为手 段 以解决任意两点间的最短路径为目的的一种算法 该算法的时间复杂度为 3 NO 空间复杂度为 2 NO 它可以正确处理有向图或负权的最短路径问题 故该方法适用于我们的问题 在实际算法中 为了节约空间 我们直接在原来空 间上进行了迭代 这样空间可降至二维 Floyd 算法的描述如下 设 kji D 为从 i 到 j 的只以 1 k 集合中的节点为中间节点的最短路径的长度 若最短路径经过点 k 则 1 1 kjkkkikji DDD 若最短路径不经过点 k 则 1 kjikji DD 因此 min 1 1 1 kjikjkkkikji DDDD 30 1 1 kkk kk 30 1 1 iii ii 30 1 1 jjj jj if jijkki DDD jkkiji DDD 综上 最短路径矩阵为 单位 km 14 图 5 1 1 5 25 2 模型一次运行后的单车重分配求解模型一次运行后的单车重分配求解 依据题意不难得知 在租赁点还车的概率与租车点和还车点的距离成反比 且 居民的骑行距离不超过 2km 据骑行距离此可得出筛选算法 1 30 1 1 iii ii k 1 30 1 1 jjj jj if ji if 2000 ji d 0 ji d else 0 ji d k k 1 根据反比例关系不难得出每个租赁点向 2km 内的各个租赁点发送的单车数量 2 为 ji ji ji d K F 15 根据归一化条件 1 1 n j ji ji ji d K F 综上可得出求得 2km 内的概率系数 K 的算法 30 1 1 iii ii s 0 30 1 1 jjj jj if 0 ji d ji d ss 1 s s 1 K K s 根据各个租赁点发送出的单车概率可求得运行一次后的各个租赁点单车数目 3 n i jij FF 1 据此可得出求解运行一次后的各个租赁点单车数目的算法 30 1 1 jjj jj t 0 30 1 1 iii ii if 0 ji d ji ii d KF tt tFj 模型运行一次后的结果如图所示 16 图 5 2 1 5 35 3 求解分配方案的预估求解分配方案的预估 校正算法校正算法 每个租赁点的单车数量可以以预估计算的方式经多次计算得出一个稳定解 即 大部分租赁点的单车数量满足 110 的要求 少部分租赁点单车数目远远超出需 求量 还有少部分单车数目几乎为零 奇点 最后 将计算所得的几个奇点分 块 从自行车数量超出 40 或大量超出需求量的地点运送单车至奇点 用启发算 式法计算运送路线及运送时间 5 45 4 求解调度方案的启发式算法求解调度方案的启发式算法 5 4 15 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 25 6 2 第二问结果第二问结果 如表 5 6 1 所示 网点编 号 7 00 8 30车 辆需求数 11 00 12 3 0车辆需求 数 17 30 19 0 0车辆需求 数 均值最大值 加权均值耗资 5640404040 40 40 0 90000 22 5038373236 38 36 0 86000 7223393432 39 34 0 84000 6033323734 33 34 0 84000 7733362832 36 34 0 84000 7320373631 37 33 0 83000 9023323731 37 33 0 83000 8825333531 35 32 0 82000 4723363230 36 32 0 82000 8713383629 38 32 0 82000 6939212328 39 32 0 82000 468373928 37 31 0 81000 627373827 38 31 0 81000 4933183529 35 31 0 81000 314027825 40 30 0 80000 6324283328 33 30 0 80000 8421293328 33 30 0 80000 8018362225 36 29 0 79000 3615372225 37 29 0 79000 9132222025 32 27 0 77000 7619272925 29 26 0 76000 338273323 33 26 0 76000 4518262322 26 24 0 74000 4132121219 32 23 0 73000 1939000 表 5 6 1 综上所述 我们得出的答案 新增租赁点数目为 23 个 租赁点编号和相对应的放置车辆数目如表所 示 表 5 6 2 网点位置如图 5 6 1 所示 租赁点编号 313336454647495056606263 放置车辆数目 342932263636344144393533 租赁点编号 6972737677808487889091 放置车辆数目 3538373037323336363730 23 图 5 6 1 5 6 35 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 1min 150min 综上 仅有两辆运输车是不够的 所以我们就三辆运输车的情形进行了分 块计算 计算结果如下 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 150min 中午 t 8 5675e 003 s 142 8min 150min 中午 t 8 7849e 003 s 146 4min 150min 平均 t 131 5min 150min 六 模型检验六 模型检验 1 问题一中求解最短路径采用 Floyd Warshall 算法 以动态规划为手段 解决 任意两点间的最短路径 并通过 Matlab 求解 2 问题一求解最短调度时间采用启发式算法 通过 C 程序设计穷举算法 并 搜索最佳调度方案 由于上述结果是通过穷举得到的 必然全局最优 3 问题二引入方便因数 全面综合各方面因素 所以得到的站点分配为最优解 4 问题三的方法与问题一和问题二相似 故所求调度方案为最佳调度方案 七 模型优缺点以及改进七 模型优缺点以及改进 在确定自行车的分配方案和调度方案时 这个问题是在已知节点具体的位 置的条件下求解两个问题 我们对两个问题分开求解 即先确定最分配方案 再根据最优分配方案确定对应的最优调度方案 然而根据数学模型和实际情况 得这两者并不是相互独立的 即问题最优解并非简单地两者最优解的结合 因 此 我们的最优结果可能和实际情况存在偏差 为了方便问题的求解 我们做出了一些假设 比如假设每辆调度车从固定 的某租赁点出发 最后又回到原来的点 而实际情况中会更局具体情况选择车 27 辆停靠点 这些假设方便了求解 但实际上简化了问题的复杂度 7 17 1 分配方案的优点分配方案的优点 租赁点自行车分配中 我们采用了一种创新的分配方案 在分配中不仅考虑 了需求量对分配的影响 而且还按照动态的目光 先给出合理的分配初值 然 后让其按照自行车的骑行规律 即在某个租赁点还车的概率与租车点和还车点 的距离成反比 自动分配若干次 每一次得出一个新的分配方案后和原来的方 案比较 然后做出调整 最终得出最优的分配方案 这个分配方案的优点是突 出的 主要体现在以下几点 1 首先考虑了需求量对分配方案的影响 使之从一开始就是合理的 兼顾重要 因素 2 由于即在某个租赁点还车的概率是一个常数 所以常数因子对分配方案的影 响可以通过一次优化最终补偿 最终的结果是形成的调度方案是满足骑行规 律的最优解 3 这个模型还有一个优点是 在校正后 能够使得需要调度的自行车数目达到 最小 从而在计算调度量时 为最优解提供保证 7 27 2 调度方案的缺优点调度方案的缺优点 调度方案的优点是在租赁点不大的情况下 按照启发式算法一次性可以把 相对来说最优的调度方案解出来 建模简单 求解也相对比较容易 调度方案的缺点重要体现在算法的局限性上 而启发式算法则试图一次提 供全部目标 例如通常能发现很不错的解 但是也没办法证明它不会得到较坏 的解 它通常可在合理时间解出答案 但也没办法知道它是否每次都可以这样 的速度求解 总的来说 启发式算法有一定的不稳定性 可以用性能更好的遗 传算法或者退火算法解决 7 37 3 新增节点模型的优缺点新增节点模型的优缺点 在求解新增节点时 我们巧妙地引入了一个 方便因数 用来衡量新增的 28 租赁点的合理程度 用求解最优解的思路来求解新增的租赁点和分配的自行车 数目 模型简单明了 容易用现成的算法实现 但是方便因数并没有将影响新增租赁点的所有的因素都考虑进去 仅仅考 虑了分配值 节点数 和邻近该租赁点的其他租赁点的数目 其他因素如是否 能达到调配量最小等因素没有考虑 其次定义的一些量如 不尽合理 原 i P i S 因是只考虑了新增加的单个节点所收到的影响 不没有考虑新增的节点间的相 互影响 因此所得的结果有可能和最优解有一定的差距 7 47 4 模型和算法的改进模型和算法的改进 7 4 17 4 1 算法的改进算法的改进 由于启发式算法的局限性 可以采用收敛速度更快的遗传算法 Genetic Algorithm 简称 GA 和退火算法 Stimulated Annealing 简称 SA 与启发 式算法相比较其优点有 计算过程简单 通用 鲁棒性强 适用于并行处理 可用于求解复杂的非线性优化问题 在本题中 由于数据量相对较小 启发式 算法还能够满足要求 为了使结果更加稳定 可以考虑退火算法和遗传算法 7 4 27 4 2 模型的改进模型的改进 我们可以把调度问题看成一个赋有权值的图 G 先要求出图 G 的最小生 成树 使树上各边的总权和达到最小 然后基于最早生成树生成一个可行的 最短行车路径 对上述 30 个租赁点重新编号 依次为 1 30 用集合 R 表示 我们用 0 1 变量来表示公交车是否从租赁点 i 到租赁点 j 即 ij x i 0 i 1 Rj j xij 否则 到租赁点公交车从租赁点 目标函数为寻找一条从起始点开始到各个节点生成的最优树 要求各条 线路的权值和最小 即 ijijRjRi tx min 约束方程为 29 0 1 1 1 1 1 j ijji n i ij n i ij u nxnuu x x ts 求解最小生成树的方法有破圈法 避圈法 Dijkstra 算法等 这里我们 用避圈法求解 避圈法是指将图 G 中的边按照权数大小逐条考察 按不构成 圈的原则加入到 T 树 中 直到为止 即 T 的边数 G 的顶点1 GpTq 数 1 为止 避圈法的算法是 1 把 G 的边按权的大小整理成 21m ewewew 令 0 1 0 jiVT 2 若含圈 则转 3 否则转 4 ij eT 3 令 若则转 2 否则停止 G 不存在最小生成树 1 iimi 4 令 ijj eTT 1 1 jj 5 若 结束 是最小生成树 否则转 3 1 nj j T 根据避圈法的算法 编写 Matlab 程序求得结果 得到最小生成树 结果列表 如下 表 7 4 1 求最小生成树结果 注 图中打 处表示两个租赁点连通 采用最小数算法算出的搜索路径比较原模型结果比较稳定 这是一个突出优点 30 八 参考文献八 参考文献 1 Clarke G and Wright J Scheduling vehicles from a central depot to number of delivery points J Operations research 1964 12 4 12 18 2 刘登涛 方文道 章坚民 等 公共自行车交通系统调度算法 J 计算机系统 应用 2011 20 9 112 116 3 崔宏志 龚加安 带时间窗车辆路径问题的改进节约算法 J 纯粹数学与应 用数学 2011 27 5 688 693 4 柳祖鹏 丁卫东 程逸旻 公共自行车系统站间调度优化研究 J 城市公共 交通 2011 1 39 42 5 肖华勇 实用数学建模与软件应用 西安 西北工业大学出版社 2008 11 附录附录 距离计算 1 distance zeros 53 for i 1 1 53 k 1 for j 1 1 53 if i j distance i k abs x1 i 1 x1 j 1 abs x1 i 2 x1 j 2 end k k 1 end end 概率系数计算 2 31 K for i 1 1 53 s 0 for j 1 1 53 if z i j 0 s s 1 z i j 输出概率的 K end end s 1 s K K s end 分块距离矩阵计算 3 distanceMb zeros 20 for i 1 1 20 k 1 for j 1 1 20 if i j distanceMb i k abs x1 Mb i 1 x1 Mb j 1 abs x1 Mb i 2 x1 Mb j 2 end k k 1 end end 启发式算法代码 4 include include include include define ZD 20 定义站点数 ZD Zhan Dian define DE 3 搜索深度 32 using namespace std int num ZD 各个站点相应的多余 缺少的车辆的数目 int route 10 ZD 车行走的路径 bool IsEnd int num 判断是否所有的车都已经调度完毕 int i for i 0 i ZD i if num i 0 return false else return true int Pathfinding int first int vol int depth 寻路