关键词: 城市交通, 共乘匹配, 时空热度, 启发式算法, 进化算法

Abstract:

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.

Key words: urban traffic, ride-sharing matching, spatiotemporal thermo, heuristic, evolutionary algorithm