共享单车再平衡问题及其容差插入启发式算法

论文摘要

共享单车再平衡问题是一类NP-难问题,已有启发式求解算法随着问题规模扩大求解速度显著变慢。本文先讨论了该问题的线路可行变换性质,推导证明了插入构造可行解时,被插入位置允许插入客户点的容量区间。在此基础上,提出容差概念,设计了容差插入启发式算法,对该算法应用标准算例测试表明,算法速度快,参数设置简单;算法找到11个测试算例的当前最好解,其中1个为新的当前最好解;算法求解大容量问题的质量优于中、小容量问题。

论文目录

• 0 引言
• 1 BRP数学模型
• 2 BRP模型性质
• 3 求解BRP的容差插入启发式算法
• 4 算法测试
•   4.1 测试环境与测试方法
•   4.2 测试结果
• 5 结论及研究展望

文章来源

类型: 期刊论文

作者: 潘立军,符卓,刘喜梅

关键词: 车辆路径问题,单车再平衡问题,插入启发式算法,容差

来源: 运筹与管理 2019年10期

年度: 2019

分类: 基础科学,工程科技Ⅱ辑,信息科技

专业: 公路与水路运输,计算机软件及计算机应用

单位: 湖南工程学院管理学院,中南大学交通运输工程学院

基金: 国家自然科学基金面上项目(71271220),湖南省自然科学基金项目(2019JJ60038),湖南省双一流应用特色学科工商管理资助(湘教通[2018]469号)

分类号: TP301.6;U491.225

页码: 26-32

总页数: 7

文件大小: 348K

下载量: 141