改进H-GASA算法求解网约车拼车服务问题

摘要

目前网约车拼车服务存在响应不及时、乘客舒适度低等现象，亟需对拼车路线及求解算法进行优化。本文首先考虑路网条件及时间窗阈值影响，以网约车运行成本与乘客出行成本最小化为目标，构建基于双向线路的网约车拼车优化模型（"one-to-many"online car-hailing carpooling model under multiple constraints）。其次以遗传算法为基础，结合模拟退火温度调控机制，改进适应度评价和接受准则，提出混合遗传-模拟退火算法（hybrid genetic-simulated annealing algorithm,H-GASA）。最后以呼和浩特东站及其周围交通网络为例进行实例验证。实验结果表明，与其他算法相比，H-GASA算法在多种时间窗下均能有效降低乘客出行时间和车辆运营成本。此外，H-GASA算法得到的网约车拼车服务问题求解方案更优，收敛曲线更平缓，效率更高，验证了H-GASA在克服遗传算法过快收敛问题上的有效性。

关键词

线路规划 / 网约车拼车 / H-GASA算法 / 时间窗阈值