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

作     者：潘立军 符卓 刘喜梅 PAN Li-jun;FU Zhuo;LIU Xi-mei

作者机构：湖南工程学院管理学院湖南湘潭411104 中南大学交通运输工程学院湖南长沙410075 

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

出 版 物：《运筹与管理》 (Operations Research and Management Science)

年 卷 期：2019年第28卷第10期

页      码：26-32页

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

主 题 词：车辆路径问题(VRP) 单车再平衡问题(BRP) 插入启发式算法 容差 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 081104[081104] 08[工学] 070105[070105] 0835[0835] 0701[理学-数学类] 0811[工学-水利类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.12005/orms.2019.0220

馆 藏 号：203822314...