Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (2): 602-607.DOI: 10.11772/j.issn.1001-9081.2017.02.0602

Previous Articles     Next Articles

Genetic algorithm with preference matrix for solving long-term carpooling problem

GUO Yuhan, ZHANG Meiqi, ZHOU Nan   

  1. School of Software, Liaoning Technical University, Huludao Liaoning 125105, China
  • Received:2016-08-24 Revised:2016-09-17 Online:2017-02-10 Published:2017-02-11
  • Supported by:
    This work is supported by the Natural Science Foundation of Liaoning Province (2015020095).

基于偏好矩阵遗传算法求解长期车辆合乘问题

郭羽含, 张美琪, 周楠   

  1. 辽宁工程技术大学 软件学院, 辽宁 葫芦岛 125105
  • 通讯作者: 郭羽含,1515120191@qq.com
  • 作者简介:郭羽含(1983-),男,黑龙江哈尔滨人,副教授,博士,主要研究方向:智能搜索算法、车辆调度问题、供应链优化问题;张美琪(1991-),女,辽宁阜新人,硕士研究生,主要研究方向:供应链优化问题;周楠(1992-),女,辽宁朝阳人,主要研究方向:车辆调度问题。
  • 基金资助:
    辽宁省自然科学基金资助项目(2015020095)。

Abstract: A Preference Matrix based Genetic Algorithm (PMGA) was introduced for solving the Long-Term Car Pooling Problem (LTCPP), and a group of users with both vehicle and the same destination was assigned to the co-generation group to minimize the total travel cost. First, the objective function of calculating the cost of all users was set up, and a long-term car pooling model with constraints of user time window and car capacity was designed. Then based on the characteristics of the model and classic Genetic Algorithm (GA), a preference matrix mechanism was adapted into the crossover and mutation operators to memorize and update the preference information among different users, thus improving the quantity and the quality of feasible solutions. The experimental results show that in the same computing environment, the optimal solution value of 20 solutions obtained by PMGA is the same as that of the exact algorithm when the number of users is less than 200. Moreover, PMGA is remarkable in solution quality when dealing with large size of instances. The proposed algorithm can significantly improve the solution quality of the long-term car pooling problem, and play an important role in reducing vehicle emission and traffic congestion.

Key words: combinational optimization, vehicle scheduling problem, heuristics algorithm, Genetic Algorithm (GA), Long-Term Car Pooling Problem (LTCPP)

摘要: 针对长期车辆合乘问题(LTCPP),提出带有偏好矩阵的遗传算法(PMGA),将拥有私家车且目的地相同的用户群体分配到产生总花费最少的合乘小组。首先,建立计算基于全体用户费用成本的目标函数,构建以用户时间窗和车容量为约束的长期车辆合乘模型;然后,结合模型特点,在传统遗传算法(GA)的基础上,通过在交叉算子与变异算子中添加偏好矩阵记录并更新用户间的偏好信息来提高可行解的数量和质量。实验结果表明,在相同计算环境下,当用户数量小于200时,通过PMGA所获得的20个解中的最优解的值与最优化算法相同;而处理大规模的实例时,PMGA可以获得更高质量的解。所提算法可以明显提高长期车辆合乘问题的求解质量,在降低汽车尾气污染和减少交通拥挤等方面具有重要作用。

关键词: 组合优化, 车辆调度问题, 启发式算法, 遗传算法, 长期车辆合乘问题

CLC Number: