交通运输系统工程与信息 ›› 2018, Vol. 18 ›› Issue (1): 121-126.

• 系统工程理论与方法 • 上一篇    下一篇

基于改进差分进化算法的出租车合乘问题研究

郑建国*,李园园   

  1. 东华大学 旭日工商管理学院,上海 200051
  • 收稿日期:2017-06-30 修回日期:2017-11-18 出版日期:2018-02-25 发布日期:2018-02-26
  • 作者简介:郑建国(1962-),男,福建龙岩人,教授.
  • 基金资助:

    上海市自然科学基金/Shanghai Natural Science Foundation (15ZR1401600).

Shared Taxi Problem Based on the Improved Differential Evolution Algorithm

ZHENG Jian-guo,LI Yuan-yuan   

  1. The Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, China
  • Received:2017-06-30 Revised:2017-11-18 Online:2018-02-25 Published:2018-02-26

摘要:

在现有出租车合乘问题研究基础上,考虑乘客模糊时间窗、合乘意愿等因素,建立 更符合实际的多对多合乘模型,并使用改进的差分进化算法进行求解.该算法设计了一种分段 实数编码方案、基于个体排序的缩放因子F 与交叉概率CR及混合轮盘赌的半贪婪选择策略. 仿真结果表明:所提算法的求解效果优于传统差分进化算法与遗传算法,是解决该类问题的 有效方法;与非合乘模式相比,所建模型成本减少、服务乘客数增加,模型合理有效;同时分析 了模糊时间窗、合乘意愿2个因素对模型求解结果的影响.

关键词: 城市交通, 出租车合乘, 差分进化算法, 模糊时间窗, 合乘意愿

Abstract:

A more realistic many-to-many dynamic shared taxi model is established, with considering the factors such as fuzzy time window and willingness to carpool, and the improved differential evolution algorithm is supposed. A segmented real number coding scheme is designed in this algorithm, as well as the scaling factor F and the crossover probability CR based on the individual ranking and a semi- greedy selection strategy mixed roulette. The simulation results indicate that the proposed algorithm could find higher quality solutions than the traditional differential evolution algorithm and the genetic algorithm; compared with the non- carpool mode, the total cost of the developed model is reduced, and the number of served passengers is increased; besides, the influence of the fuzzy time window and willingness to carpool on the solution of the model is also analyzed.

Key words: urban traffic, taxi sharing, differential evolution algorithm, fuzzy time window, willingness to carpool

中图分类号: