多车辆合乘问题的两阶段聚类启发式优化算法  

Heuristic Optimization Algorithms of Multi-Carpooling Problem Based on TwoStage Clustering

作　　者：邵增珍[1,2] 王洪国[1] 刘弘[1,2] 宋超超[3] 孟春华[3] 于洪玲[3] 

机构地区：[1]山东师范大学信息科学与工程学院,济南250014 [2]山东省分布式计算机软件新技术重点实验室,济南250014 [3]山东师范大学管理科学与工程学院,济南250014

出　　处：《计算机研究与发展》2013年第11期2325-2335,共11页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60970004);山东省自然科学基金项目(ZR2011FQ029;ZR2011FL026);山东省科技发展计划基金项目(2011YD01099)

摘　　要：车辆合乘问题研究在物流领域和交通领域意义重大.良好的合成策略不仅可以节省物流成本,降低交通拥塞,在减少噪声及提高环境等方面也是很有利的.针对确定性多车辆合乘匹配问题,提出了两阶段聚类的启发式匹配策略:第1阶段聚类过程提出匹配度的概念,用于指导将服务需求分配到某一具体车辆,从而将多车辆问题转化为单车辆问题;第2阶段聚类过程基于"先验聚类"插入思想,可降低单车辆匹配过程的插入试探次数,从而提高算法效率.为提高搭乘成功率并降低运营总成本,通过迁移对第1阶段聚类过程进行调整.实际算例结果表明,算法在可接受时间范围内不仅可提高搭乘成功率,还明显降低车辆的运行成本,表现出较强的实用性.In logistics engineering, transportation system and some other domains, the effect of carpooling is enormously significant. Excellent carpooling strategy may not only economize logistics costs, reduce the traffic jam, but be especially favorable for reducing noise and improving the environment. Thus, a two-stage clustering heuristic strategy is introduced to solve deterministic multi-carpooling problem. In the first stage of the strategy, the conception of matching degree is proposed to guide to assign service requirements to specific vehicle, hence the original problem can be split into several single-vehicle problems. And in the second stage of the strategy, based on priori clustering idea, the number of insertion operations in one single-vehicle matching progress is reduced greatly so as to improve the efficiency of the algorithm. To improve the success rate of matching and reduce total costs, the assignment schema of vehicles is not fixed but adjustable. Heuristic emigration and immigration operators are used in a new distribution when some requirements fail to be assigned or probably lead to long arcs in the last distribution. To verify the validity and practicability of the method, some actual samples are generated based on real map information. Experimental results show the algorithm may not 0nly improve ride success rate greatly, reduce total vehicle costs, but also demonstrate strong practicality.

关 键 词：多车辆合乘匹配问题 两阶段聚类 匹配度 先验聚类 迁出 迁入算子 启发式算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]