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

□李宏光 陈燕生

[北京化工大学 北京 100029]

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

□李宏光 陈燕生

[北京化工大学 北京 100029]

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

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

引言

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

VRP受到研究关注不仅仅是因为它是一类典型较难的组合优化问题，而主要是因为其具有广泛的应用背景和可观的经济效益。国外学者Dantzing和Ramser[1]于1959年最早提出该问题。Balinski等人于1962年提出集分割，考虑可行解集合并在此基础上进行建立了最简单的VRP 优化模型[2]。此后，Eilon等人[3]将动态规划法引入VRP；Jerby Shai等人优化设计了列车循环路线[4]；Gendreau等人应用禁忌搜索算法解决VRP问题[5]。韩艳等人构建了最大出行需求及线路总体通行时间最短的双重寻优目标，并运用启发式算法进行求解[6]。张丽萍等人运用改进遗传算法解决VRP问题[7]。然而，目前大多数处理VRP方法中将站点配置问题与路径规划问题分别进行处理，实际上两者之间存在紧密联系。

本文综合考虑了企业员工居住地信息和班次安排对通勤车站点配置方案的影响以及站点配置方案对路径优化选择的影响，建立站点配置及路径优化的综合模型并基于蚁群算法与旅行商算法进行求解。实例研究表明本文研究可为改善企业班车站点选择及路径规划策略提供参考。

一、综合路径规划研究

（一）综合路径规划模型

针对单车场、单车型、非满载、纯载客的通勤车路径优化问题，路径规划的目标是在安排企业通勤车数量的基础上使得总运行路程最小。这里，对问题做如下说明：（1）设定企业所在地为通勤车起始点；（2） 通勤车将员工从企业送到各个站点，完成任务后所有车辆返回企业以便于统一管理。所使用通勤车型号一致，即所有通勤车行驶速度相等，通勤车搭载员工数不能超过最大载客量；（3） 站点固定，且每个站点的员工乘车数已知，但所设站点数目应使得员工出行成本最小。

基于聚类方法选择出使员工出行成本最小的站点配置方案，并在此基础上进行路径规划。通勤车路径优化模型需要满足如下约束：（1） 每条通勤车路径上各站点总人数不超过通勤车的最大承载能力；（2） 每个站点都得到车辆接送服务；（3） 每条通勤车路径上的站点数不超过总站点数；（4） 员工只能选择一辆通勤车进行搭乘。

S-总站点数目；

U-所需通勤车数目；

Wi-每个站点员工数目；

Iki-在i站点乘车员工k与i站点之间的距离；

mu-每辆通勤车载客量；

dij-站点i与j之间距离；

nu-第u辆通勤车经过的站点数目(nu表示未用第u量车)；

Ru-表示第u条路径的通勤车站点集合；

这样，企业通勤车综合路径优化问题描述如下：u

其中：式(1)、(2)为优化目标，即通勤车行驶总路程最短和员工出行成本最小；式(3)、(4)、(5)为约束条件，分别表示每条路线上各站点总人数不超过通勤车最大承载能力、每个站点都得到车辆接送服务、以及每条路径上的站点数不超过总站点数；式(6)表示每条路线的站点组成；式(7)表示每个员工仅能乘坐一辆通勤车；式(8)表示站点i到j间由车辆u经过时，

（二）基于FCM聚类的站点配置

企业通勤车站点配置是后勤保障系统的重要基础设施和不可缺少的重要环节。站点配置首先需要满足员工从居住位置到乘车站点的成本最小。另外，考虑到不同的通勤车站点配置方案会直接影响路径规划的结果，而站点配置需要考虑其合理性。为此，本文将站点配置作为综合路径规划问题的约束和前提，提出基于FCM的聚类算法对员工居住位置坐标值进行聚类，从而求解站点配置问题。

模糊C-均值聚类算法(Fuzzy C-Means,即FCM)[8～9]是一种聚类效率较好且广泛应用的聚类算法。传统FCM是基于模糊隶属度函数确定聚类程度的一种聚类算法，把n个d维样本分为c类，聚类中心可表示为，其中vi表示类i的类中心。标准FCM聚类算法的数学模型可简单表述为：

其中，uij表示样本xj属于类i的程度；U表示uij构成的c×N隶属度矩阵；V为vi构成的c×n类中心矩阵；表示一个加权模糊指数，反映控制隶属度在各类间重合归属的程度；表示样本点xj到类中心vi的欧氏距离。

考虑到经典FCM聚类算法的局限性，即在每次聚类过程中数据均匀收缩，在标准FCM数学模型的约束条件中增加信息熵约束，弥补模糊聚类存在数据收缩问题的不足，从而提高聚类性能[10]。约束条件中引入信息熵的FCM聚类算法数学模型可表示为：

上述优化模型等价于

（三）综合路径规划算法

蚁群算法(Ant Colony Optimization，即ACO)是由意大利学者Maniezzo等人[11]在1996 年率先提出的一种以自然界蚁群觅食行为启发产生的仿生优化算法，属于随机搜索算法的一种。本文针对需要解决的企业通勤班车综合路径规划问题，对蚁群算法的参数设置、转移概率计算以及信息素更新等方面做了相应的变化，并用于求解通勤班车路线优化问题。

实际中的VRP问题相对于TSP问题有更多的约束条件。因此，在计算转移概率时考虑约束条件的信息，使其更具实际意义。通过考虑通勤车路径优化模型的约束条件，概率转移公式为:

这样，改进后的概率转移计算公式考虑了实际约束条件，并结合随机性选择策略，从而提高了算法的全局搜索能力，避免产生局部最优解。

另外，蚁群算法中当每一只蚂蚁结束循环后，为防止路径上信息素累积量过多导致启发信息被残留信息淹没，需要及时更新对路径上的残留信息素，更新公式为：

其中：p表示信息素挥发系数，相应的1-p表示信息素残留系数，且表示第k只蚂蚁在路径i-j上分泌的信息素量；表示所有蚂蚁在路径i-j上分泌的信息素总量；Q表示各路径上信息素大小； LK表示第k只蚂蚁在当次循环中的走过的总路程。

值得注意的是，蚁群算法中的各个参数值的合理设置可使优化结果更有效。α值过大，算法收敛过快，容易陷入局部优化；β值越大，位置近的站点被选概率大，也不利于全局优化；越小表示路径上的信息素越不易挥发，残留信息过多，使结果陷入局部最优；p越大，残留信息的作用被淹没。本文对参数设置进行动态调整，初始设置值较小，扩大算法搜索范围，随着算法迭代到一定次数后增大参数值，逐步优化出最优路径。本文将站点配置问题作为综合路径规划问题的约束，整个综合路径规划问题包括以下步骤：

1.初始化聚类及蚁群算法的各参数值；

5.初始化员工位置矩阵C；

7.将按式(13)更新为

10.根据聚类结果确定站点位置；

11.根据式(15)(16)选择下一站点j；

14.根据式(17),(18),(19)更新每条路径上的信息素；

16.输出综合路径优化结果。

二、实例研究

在已知所有员工居住地点坐标的情况下，采用Matlab实现基于信息熵的FCM半监督聚类算法，确定出所有员工出行成本和（距离）最小的站点布局方案，如图1所示，最优站点配置数目为17，各站点坐标如表1所示。

表1　17个站点的坐标值

另外，考虑到通勤班车路线的规划对员工上下班时间以及企业班车调度成本有着至关重要的影响，因此本文在考虑站点配置的约束情况下，对通勤班车路径优化模型进行求解。设企业所在地为始发站，记为站点0；通勤车最大载客量为60人；企业共有30辆通勤车；各站点员工数目分别为9、11、6、14、12、9、12、7、15、13、7、12、4、11、8、14、13；站点i与j之间距离可通过公式（20）进行计算：

图2　通勤班车最优运行路线图

算法的收敛过程如图3所示，可以看出具有很好的收敛性。

图3　改进蚁群算法收敛过程

三、结论

论文从不同的通勤车站点配置方案会直接影响路径规划结果的角度，将通勤班车站点配置作为其路径规划问题的约束和前提，提出一种综合站点配置的企业通勤班车路径规划方法，并基于FCM聚类及蚁群算法对综合路径规划问题进行求解。实验结果表明本文提出的整合优化模型可为改善企业通勤班车站点选择及路径规划策略提供参考。

[1] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1):80-91.

[2] BALINSKI M L, QUANDT R E. On an integer program for a delivery problem [J]. Operations Research, 1962, 12(2): 300-304.

[3] EILON S, WATSON-GANDY C D T, CHRISTOFIDES N. Distribution management[M]. London: Griffin, 1971.

[4] JERBY S, CEDER A. Optimal routing design for shuttle bus service[J]. Transportation Research Record: Journal of the Transportation Research Board, 2006, 1971(1): 14-22.

[5] GENDREAU M, HERTZ A, LAPORTE G. A tabu search heuristic for the vehicle routing problem[J]. Management Science, 1994, 40(10): 1276-1290.

[6] 韩艳, 关宏志, 赵红征. 通勤班车出行线路优化研究[J]. 武汉理工大学学报: 交通科学与工程版, 2011, 35(2): 379-382.

[7] 张丽萍, 柴跃廷. 车辆路径问题的改进遗传算法[J].系统工程理论与实践, 2002, 22(8): 79-84.

[8] CHEN M S, WANG S W. Fuzzy clustering analysis for optimizing fuzzy membership functions[J]. Fuzzy Sets and Systems, 1999, 103(2): 239-254.

[9] BEZDEK J C, HATHAWAY R J, SABIN M J, et al. Convergence theory for fuzzyC-means: Counterexamples and repairs[J]. Systems, Man and Cybernetics, IEEE Transactions on, 1987, 17(5):873-877.

[10] 郭新辰, 樊秀玲, 郗仙田, 韩啸. 改进的FCM半监督聚类算法[J]. 吉林大学学报: 理学版, 2014, 52(06): 1293-1296.

[11] MANIEZZO V, DORIGO M, COLORNI A. The ant system: Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems Man and Cybernetics, 1996 (Part B): 29-41.

编辑 何 婧

Study on Enterprise Shuttle Bus Location and Route Optimization： An Integrated Approach

LI Hong-guang CHEN Yan-sheng
(Beijing University of Chemical Technology Beijing 100029 China)

Enterprise’s shuttle bus location and route optimization problems play an important role in increasing the logistics management efficiency and operation expenditure control. Traditional researches optimize location and route separately, thus causing danger to ignore the close connection between them. In this paper, we propose an information entropy-based improved fuzzy c-means semi-supervised clustering algorithm for bus location optimization and experiments are conducted to evaluate the reliability and effectiveness of it. Thereafter, a shuttle bus route selection model is introduced and an enhanced ant colony optimization (ACO) algorithm is designed to obtain the optimal results.

location selection; fuzzy c-means; vehicle routing problem; ant colony optimization

U491.2

A [DOI]10.14071/j.1008-8105(2016)04-0068-06

2015 - 04 - 12

李宏光（1963- ）男，北京化工大学信息科学与技术学院教授、博士生导师；陈燕生（1983- ）男，北京化工大学信息科学与技术学院硕士研究生.