摘要
在共乘匹配问题中,考虑时空热度对共乘车主收益的影响,构建了以共乘收益和共享路线百分比为优化目标的数学模型,提出了一种启发式多进程进化算法用于求解.算法根据历史数据采用三次样条插值法和复合辛普森求积法得到预计订单的时空热度,从而预估车主共乘收益.在进化算法中,根据差异度自适应选择不同的交叉策略,以达到搜索深度和广度的自动平衡.实验结果表明,该算法与最优化算法(匈牙利算法)比较,在以相同效用矩阵作为输入条件时,本文方法可在较短时间内得到高质量的解,且在处理大规模实例上效果明显,能够高效求解共乘匹配问题.
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.
作者
郭羽含
于俊宇
GUO Yu-han;YU Jun-yu(School of Software,Liaoning Technical University,Huludao 125105,Liaoning,China)
出处
《交通运输系统工程与信息》
EI
CSCD
北大核心
2019年第6期112-122,共11页
Journal of Transportation Systems Engineering and Information Technology
基金
辽宁省自然科学基金(2019-ZD-0048)
辽宁省教育厅基础研究项目(LJ2019JL012)~~
关键词
城市交通
共乘匹配
时空热度
启发式算法
进化算法
urban traffic
ride-sharing matching
spatiotemporal thermo
heuristic
evolutionary algorithm