一种用于公共自行车调度的改进GA-SA算法

赵红梦，姜志侠，曾 坤

(长春理工大学 理学院，吉林 长春 130022)

0 引 言

随着中国经济的快速发展以及居民生活水平的不断提高，交通拥堵问题日益严重，为了更好地响应党中央绿色出行的号召，缓解城市交通压力，城市公共自行车应运而生。随着公共自行车的高效发展，一系列问题也逐渐显现，如由于调度不平衡导致租还车难的问题大大降低了用户对于公共自行车使用的满意度，对公共自行车进行调度优化的研究迫在眉睫；考虑到车辆的容量要求，如何设计节约成本的调度方案，最大程度地提高市民对公共自行车使用的满意度是亟待解决的问题。

目前学者对公共自行车单调度问题的研究主要分为调度模型和调度方法两大类。2005年任传祥等[1]提出混合遗传模拟退火算法解决公交车辆行车计划模型；2011年Mike Benchimo等[2]重点研究以调度运输费用最小为目标函数的车辆静态调度优化模型；2013年Daniel Chemla[3]用禁忌搜索算法解决静态公共自行车问题；2017年Fábio Cruz等[4]提出一种基于局部迭代的启发式算法解决单调度静态无时间窗优化模型；同年Aritra Pal[5]等提出了一种求解静态完全再平衡问题的混合整数线性规划模型，利用混合嵌套的大邻域搜索与可变邻域下降算法解决公共自行车调度问题；2017年栾英杰[6]提出一种GA-SA算法解决公共自行车调度问题。基于此，文中主要研究静态公共自行车调度问题，以成本最小化为目标建立调度模型，并利用改进的遗传模拟退火算法进行求解。……