考虑行驶时间不确定性的合乘路径鲁棒优化方法

为应对实际合乘过程中时间不确定性带来的负面影响，本文研究不确定行驶时间下的合乘问题。采用预算不确定集合描述时间变量，引入不确定性水平可调节的预算系数，构建以车辆总里程最短和车辆数最少为目标的合乘路径鲁棒优化模型。并设计两阶段算法求解，第1阶段以两乘客间的可行合乘路径为基础，从车辆总里程节省率和乘客时间窗匹配灵活性两方面设计公式量化合乘匹配机会，以匹配机会为权重构建乘客图网络并聚类乘客需求；第2阶段设计以顺序插入启发式方法构造初始解的禁忌搜索算法求解。案例数据实验结果表明：本文聚类方法能保证优化质量并提高85%以上的计算效率，同时能缩减乘客等车时间和绕行距离；增大预算系数时解的鲁棒性逐渐提高，但会增加10%~40%的车辆数并降低1%~10%的里程节省率；大规模乘客案例和窄时间窗案例的合乘路径对不确定时间的敏感性更高，宽时间窗案例无需增加过多额外车辆和总里程就能达到较高水平的路径鲁棒性。

Robust Optimization of Carpooling Routing Problem Under Travel Time Uncertainty

In order to relieve the negative impact of time uncertainty in carpooling process, the study focuses on the carpooling problem with travel time uncertainty. A budget uncertainty set is used to describe the travel time variable, and a budget coefficient with an adjustable uncertainty level is introduced to build a robust optimization model with the shortest total vehicle mileage and the least number of vehicles as the objective function. A two- stage algorithm is designed. In the first stage, based on the feasible carpooling routes between two passengers, we design a formulation to quantify the matching chance in terms of total vehicle mileage saving rate and the passenger time window matching flexibility, and then the matching chance is used as the weight to construct a passenger graph network and cluster the passengers. In the second stage, we design a Tabu search algorithm to solve the problem by constructing an initial solution with the sequential insertion heuristic method. The experimental results show that the clustering method can ensure the solution quality and improve the computational efficiency by more than 85% while reducing the passenger waiting time and detour distance. The robustness of the solution gradually improves when increasing the budget coefficient, but it increases the number of vehicles by 10%~40% and reduces the mileage saving rate by 1%~10%. The carpooling routes of the large-scale cases and the narrow time window cases are more sensitive to the uncertain time, and the wide time window cases can achieve a high level of robustness without adding too many additional vehicles and total mileage.