原文传递
车辆共享系统优化调度研究——以公共自行车为例
| 论文题名： | 车辆共享系统优化调度研究——以公共自行车为例 |
| 关键词： | 公共自行车;调配策略;分支定价算法;初等最短路问题;双向动态规划 |
| 摘要： | 近年来，车辆共享系统得到快速发展，作为经济节能、环保低碳以及方便灵活的绿色出行方式而受到政府和社会大力推广。共用共享的车辆（自行车、汽车、电动车等）成为城市交通新的选项和重要补充，其中起源于欧洲的第三代城市公共自行车系统，经过不断的改进和发展，越来越受到民众的欢迎。一个良好的公共自行车系统不仅有赖于租赁点的合理规划与布局、租赁点停车桩合理数量的设置，更与公共自行车的人工调配密切相关。合理的人工调配可以实现整个租赁系统的库存均衡，提高客户满意度，吸引更多的潜在客户使整个系统实现均衡良性的发展。因此对公共自行车调配策略的探索与优化具有很高的研究价值和实际意义。 本文基于公共自行车静态车辆调度自身的特点，以同时取送货的车辆路径问题为原型，首先探讨了公共自行车夜间优化调度问题。以实现系统均衡为最终目标，建立了以运输总成本最小为目标的优化调度模型。其次，针对公共自行车特有的高峰时期借还量时空分布严重不平衡导致的无车可借无位可还的问题，提出一种应急预调度策略。在高峰来临前一定时间内对各个租赁点进行预调度，调度车优先访问关键节点。并针对这一策略建立了以面向收益的车辆路径问题为原型的优化模型。 针对上述问题，本文使用分支定价这一精确算法进行求解。分支定价算法是一种将列生成技术嵌入分支定界的每个节点上的广义的分支定界算法。列生成算法可以将一个具有大规模变量的线性规划问题进行分解，形成一个与原问题等价的主问题和一系列的定价子问题，定价子问题通常具有有效的求解算法。通过对定价子问题的快速求解，进行主问题与子问题之间的循环迭代并最终实现对原问题求解。 本文在使用分支定价算法对上文提到的两个模型求解的过程中，首先将建立的原问题的混合整数规划模型转化为集划分模型，将集划分模型作为列生成算法的主问题。在本文研究的调度优化问题中，主问题对应的定价子问题表现为一种带资源约束的初等最短路问题(RCESPP)，在对该问题进行求解的过程中，本文采用一种双向动态规划算法进行求解。在求解静态调度模型时，由于公共自行车调度自身单一品种、取送货结合的特点，使用取货量和送货量作为关键资源约束，在求解应急调度（高峰预调度）模型时，由于这一模型特有的时效性要求，将行使时间加入关键资源，通过将上述关键资源在统治规则和状态扩张限制技术中加以应用，有效控制未被统治状态的规模，提高算法效率。 本文通过大量实验，验证了在中小规模的算例中，这一算法的有效性。 |
| 作者： | 戴盛隆 |
| 专业： | 物流工程 |
| 导师： | 彭扬 |
| 授予学位： | 硕士 |
| 授予学位单位： | 浙江工商大学 |
| 学位年度： | 2014 |
| 正文语种： | 中文 |
检索历史
应用推荐
