Abstract: This paper addresses a dynamic matching and vehicle routing problem for online ride-sharing services at airport terminals. In the current operations, passengers have to wait for a long time at airport for partner passengers and drivers have a high vehicle-traveling cost. To deal with the two issues above, this study proposes a prospective matching policy that consolidates the already arrived and coming passengers together during each decision period, and a two-stage stochastic programming model is then established. To efficiently solve the problem in a real-time setting, a large number of scenarios of passenger random arrivals is compressed using Bayesian estimation and then a deterministic approximated model is established. To obtain a high-quality solution within a reasonable computational time, an improved differential evolution (DE) algorithm is then developed, in which the space-time similarity of passengers is calculated and used to encode the individuals of DE population. The effectiveness and efficiency of the proposed matching policy and the DE algorithm are verified by a simulation experiment based on the industrial data set.

Key words: online ride-sharing, matching policy, vehicle routing problem, differential evolution algorithm

摘要： 网约车拼车服务作为共享经济领域重要应用,已成为国内外研究热点。针对机场在线拼车平台运营中乘客等待时间过长和车辆行驶成本较高的突出问题,本文提出前瞻式动态拼车匹配策略。该策略将未来随机到达乘客信息纳入当前已到达乘客的拼车匹配决策中,建立了乘客匹配与车辆路径联合优化两阶段随机规划模型。为了在动态环境中实时产生高质量的匹配与路径规划方案,首先基于贝叶斯估计压缩乘客随机到达情景空间,建立了问题的确定性近似最优模型。为了快速求解模型,提出基于订单目的地和乘客期望到达时间相似度的匹配规则,并以此开发改进的差分进化算法。最后,基于某拼车平台真实订单数据,通过对比测试验证了前瞻式匹配策略和改进差分进化算法的有效性与计算效率。

关键词: 在线拼车, 匹配策略, 车辆路径规划, 差分进化