□李宏光 陈燕生

[北京化工大学 北京 100029]

考虑站点配置的企业通勤班车综合路径规划方法

□李宏光 陈燕生

[北京化工大学 北京 100029]

针对传统方法中将班车站点选择与路径规划分别进行处理而不能考虑两者间关联的问题，给出了一种考虑站点配置的综合路径规划方法。首先基于信息熵的FCM半监督聚类算法，对企业通勤班车站点配置问题进行求解，确定出基于员工居住信息的合理站点配置方案；在此基础上，基于蚁群算法的对路径优化问题进行求解。实验结果表明，综合路径规划方法可以为优化企业班车站点配置及路径规划策略提供参考。

站点配置；模糊聚类；路径规化；蚁群算法

引言

企业通勤班车站点配置及路径规划属于一类车辆路径问题(Vehicle Routing Problem, VRP)。通勤班车是企业为方便员工上下班而安排的有固定线路并定时行驶的服务车辆。通勤车站点配置策略是影响企业员工乘车便利程度、车辆运营效率和调度计划安排的重要因素。由于通勤班车工作时间处在上下班的高峰期，合理的安排通勤班车的站点及路线，可以降低企业职工路途时间，间接地提高职工的工作效率。

VRP受到研究关注不仅仅是因为它是一类典型较难的组合优化问题，而主要是因为其具有广泛的应用背景和可观的经济效益。国外学者Dantzing和Ramser[1]于1959年最早提出该问题。Balinski等人于1962年提出集分割，考虑可行解集合并在此基础上进行建立了最简单的VRP 优化模型[2]。此后，Eilon等人[3]将动态规划法引入VRP；……