考虑时空热度的共乘匹配问题建模及求解

Modelization and Resolution of Ride-sharing Problem with Spatiotemporal Thermo

在共乘匹配问题中,考虑时空热度对共乘车主收益的影响,构建了以共乘收益和共享路线百分比为优化目标的数学模型,提出了一种启发式多进程进化算法用于求解.算法根据历史数据采用三次样条插值法和复合辛普森求积法得到预计订单的时空热度,从而预估车主共乘收益.在进化算法中,根据差异度自适应选择不同的交叉策略,以达到搜索深度和广度的自动平衡.实验结果表明,该算法与最优化算法(匈牙利算法)比较,在以相同效用矩阵作为输入条件时,本文方法可在较短时间内得到高质量的解,且在处理大规模实例上效果明显,能够高效求解共乘匹配问题.

Taking the influence of spatiotemporal thermo on driver's profit into consideration in ride-sharing problem,a mathematical model is constructed to optimize the profit of drivers and the percentage of shared routes,and a multi-process evolutionary heuristic is proposed to solve the problem.Based on historical data,the approach first uses cubic spline interpolation method and compound Simpson quadrature method to predict the spatiotemporal thermo,so as to estimate driver's profit in ride-sharing.In the evolutionary algorithm,different crossover strategies are adaptively and dynamically selected according to individual differences to balance automatically the intensity and the diversity of the search process.The experimental results show that,compared with the Hungarian optimization algorithm,this algorithm can obtain high quality solutions with short computing time when the same utility matrix is used as input,and has good performance in dealing with large-scale instances,therefore can efficiently solve ride-sharing problem.