校车路径优化模型及算法研究

郝 忠 娜

( 南京交通职业技术学院 运输管理系，江苏 南京 211188)

校车路径优化模型及算法研究

郝 忠 娜

( 南京交通职业技术学院 运输管理系，江苏 南京 211188)

以校车站点选择、学生群归属站点的划分以及车辆路径安排为研究对象，重点考虑了学生在车上的最大乘车时间、学生步行到候车站点的最大步行时间等约束条件，以车辆行程时间成本、学生乘车时间成本以及学生步行时间成本最小为目标建立数学规划模型。给出了解决这类问题的改进遗传算法，该算法通过启发式产生初始种群的优良个体，并针对模型特点设计带启发知识的遗传算子，提高寻优效率。实例分析表明，该方法可行，并且有比较显著的效果，能够有效地解决大规模的校车路径优化问题。

交通运输工程；校车路径；优化；数学规划模型；改进遗传算法

0 引 言

校车路径问题(School Bus Routing Problem, SBRP)主要包括站点选择、路径生成、校车时刻表的制定等问题[1]。根据校车派车车辆数，可以分为单校车路径问题和多校车路径问题。笔者针对单校车接学生到校的问题进行研究，其它更多问题可在此基础上进行扩展延伸。

校车路径问题是NP完全问题，对于小规模的应用问题，可以采用精确算法来解决。J. Riera-Ledesma等[2]针对校车路径问题，建立了集划分模型，并设计了BCP(Branch-and-Cut-and-Price)精确算法对模型进行求解。而对于大规模的问题，精确算法难以在合理的时间内得到最优解，因此，人们更多地研究采用各种智能算法来快速获取问题的满意解。A. Bock等[3]考虑学生从家到学校的乘车时间不超过设定值以及车辆容量限制的约束建立模型，并把学生和学校置于固定树的定点用多项式近似算法进行求解。吴耀华等[4]和张丽艳等[5]提出了用改进粒子群算法求解车辆路径问题。P. Díaz等[6]将蚁群算法与大邻域搜索算法(VNS)进行结合，提出了求解校车路径问题的混合算法。P. Schittekat等[7]重点考虑校车路线生成和站点选择问题，并设计一种数学启发式算法进行求解。刘文[8]采用基于满意优化模型和免疫蚁群算法进行模型的建立与求解。B. Kim等[9]考虑到校时间窗建立模型，用精确算法求解特殊情况下的模型，并用启发式算法求解一般情况下的模型。目前，国内外对校车路径问题的研究主要针对站点已经确定的情况来优化行车路线，而同时考虑站点选择、学生群归属站点的划分以及行车路线问题的研究很少。由此，笔者给出选择站点及优化行车路线的数学模型，并用改进的遗传算法进行求解。

1 模型建立

1.1 问题描述

笔者仅针对某区域需要派一辆校车接学生到校的问题，送学生返回的路径问题按照反向路线行驶即可。考虑学生群步行时间、乘车时间以及车辆行驶时间等因素，从所有候选站点中选择若干个需要停靠的站点，制定车辆行驶路线。校车从学校出发，依次到达各个停靠站点接学生，最后返回学校。假设车辆容量足够，所有学生均可在选定的停靠站点上车。

1.2 参数及变量设置

1.3 模型建立

校车路径优化问题要以运营单位的效益和学生的利益最大化为目标，运营单位的效益以校车行程时间最短来体现，学生的利益则以学生步行到站的时间最短以及乘车时间最短来体现。

车辆行程时间最短的目标为：

(1)

设Ωj为车辆到达站点j时未访问的站点的集合(不含j)，则所有学生的乘车时间最短的目标为

(2)

学生步行到候车站点的时间最小的目标为

(3)

为将多目标转换为单目标，各个目标函数值的涵义、范畴要一致。由于目标函数中涉及的时间的数量范畴具有差异性，不能简单相加，故把时间转换成时间成本。设定各个目标的成本系数为：Z表示车辆在行驶过程中的单位时间的行驶成本(含分摊的固定成本和可变成本)；λ表示学生在车上的单位时间成本；μ表示学生步行的单位时间成本。

把多目标函数变为单目标函数，建立模型为

minz=γz1+λz2+μz3

(4)

(5)

(6)

(7)

(8)

Tnjznj≤Tmax, ∀n∈N,j∈M

(9)

(10)

xij={0,1}, ∀i,j∈M

(11)

yj∈{0,1}, ∀j∈M

(12)

znj∈{0,1}, ∀n∈N,j∈M

(13)

模型中：式(4)表示总成本最小的目标；式(5)表示学生群必须到且仅到一个站点候车；式(6)表示当有学生群在站点候车时，必须有校车停靠该站点；式(7)表示车辆只驶入需要停靠的站点；式(8)表示车辆进入站点后必须离开且驶入唯一的下一个站点；式(9)保证学生步行到候车站点的时间不能超过最大步行时间的限制；式(10)保证学生在车上的时间不能超过最大乘车时间的限制；式(11)～式(13)表示决策变量的取值范围。

2 求解模型的改进遗传算法

2.1 算法选择

同时考虑站点选择、学生归属站点及行车路径的校车路径问题属于NP难题。随着规模的增大，解空间呈指数增长，用穷举法或其精确算法显然不能在合理的时间内得到满意解。而遗传算法[10]、粒子群算法[11-12]等智能算法在求解这类问题时通常能获得较满意的结果。遗传算法[10]以生物进化为原型，通过模仿自然界的选择与遗传机理来寻找最优解。与传统的优化方法相比，具有较好的收敛性，计算速度快，同时具有较强的鲁棒性。但一般遗传算法容易陷入“早熟”收敛，因此笔者对一般遗传算法进行改进，结合模型特点，在初始群体的产生以及遗传算子的设计过程中加入启发知识进行改进，以保证算法的多样化及寻优的速度。

2.2 算法设计及实现过程

2.2.1 设 置

设置群体规模R，遗传操作的交叉概率Pc，变异概率Pm，算法最大迭代次数T，以及最大连续相同迭代次数Tsame。

2.2.2 产生初始群体

1)设计染色体编码方式

用十进制编码的方式，用“0”表示学校，用自然数表示候选站点，染色体编码长度为M+2，编码取值范围为[0,M]且为整数。一个染色体中首尾位数分别表示学校，即车辆从学校出发，经过各个站点接收学生上车后，最后回到学校，其中各个学生群到校车停靠的最近站点上车。不被采用的候选站点则用“0”表示，以保持染色体的长度，同时把染色体中非零数字中间包含的“0”元素移到所有非零元素之后。如对于一个有8个候选站点的校车路径问题，染色体长度为10，假设某染色体为[0,2,3,5,4,1,6,8,0,0]，表示的车辆路径为：学校→站点2→站点3→站点5→站点4→站点1→站点6→站点8→学校，候选站点7不被采用。

2)生成初始群体

接学生的校车问题，为考虑学生在车上的乘车时间较短的目标，通常先接收较远站点的学生，再到较近的站点。为得到较优的初始个体，此考虑产生初始群体的方法为：把所有候选站点按站点到学校的距离由远到近进行排序，从学校出发以最远站点为第1个停靠的站点，在按照改进的C-W节约算法经过剩下的站点，最后回到学校，得到第1个染色体个体；依次以次远站点、第3远站点，……，为第1个停靠站点，寻找第2个、第3个染色体，直到产生[M/2]个染色体。若为达到群体规模，则按照随机顺序生成剩下的个体。

针对有些候选站点有可能不被采用的情况，故在初始群体中对部分个体进行删除站点操作：设群体规模为R，在生成的群体中随机选取R/4个染色体进行删除1个站点的操作，再选取R/4个染色体进行删除2个站点的操作。通过删除站点的操作，使初始群体中被选择的站点不限于全部选择，更趋向多样化。

2.2.3 评 价

对染色体进行适应度评价，保存当前最优染色体。

由于模型的目标函数值恒为正，适应度函数采用目标函数值的倒数表示。假设第i个个体的目标函数值为z(i)，则该染色体对应的适应度值为f(i)=1/z(i)。对于不满足约束条件的个体，则令其适应度值为0。由个体的编码方式决定了染色体约束条件式(6)～(8)以及式(11)～(13)恒成立，对于式(5)，在每一个染色体实时进行学生群归属站点的划分，保持该约束条件的成立。对于式(9)～(10)则需要进行逐一判断，当有其中一个条件不满足时，即可令适应度值为0。

2.2.4 进行遗传操作

1)选择操作

在进行选择操作时，采用以下方法选择染色体进入下一步操作：

(a)将当前的染色体按照适应度值从高到低排序，取前R/4个染色体直接进入下一代，保证群体中适应度值较高的个体优先被选择；

(b)从当前群体中随机选择3R/4个染色体进入下一代操作，保持群体的多样化。

2)交叉操作

将群体中的染色体进行随机配对，对每一对染色体以Pc概率进行交叉操作：逐一考虑每一对染色体，产生随机数ε∈[0,1]，若ε≤Pc，则对该对染色体中表示候选站点的基因座上的基因值进行交叉；若ε>Pc，则该对染色体不进行交叉操作，直接保留到下一代。在交叉操作过程中，若表示站点的基因座的值为0，则把零元素移到所有非零元素的后面。

3)变异操作

由于规划问题中候选站点存在被采用与不被采用的情况，因此，在变异算子的设计中除改变染色体中的站点顺序的操作，还要增加给染色体增加站点与删除站点的变异操作。依次考虑群体中的个体，产生随机数ξ∈[0,1]，把变异概率Pm分成3部分考虑变异操作：

(a)若ξ≤Pm/3，对染色体的基因值进行改变顺序的操作，产生[2,M+1]范围内的两个不相等随机整数P1，P2，交换染色体中基因座P1，P2位置上的基因值；

(b)若Pm/3<ξ≤2Pm/3，则判断染色体中是否有缺失的候选站点，若有，则以[2,M+1]范围内的一个随机整数作为插入位置，从缺失的候选站点中随机选择一个插入该位置，再把除了染色体首末位之外的一个“0”元素删除，保持染色体的长度不变；

(c)若2Pm/3<ξ≤Pm，则进一步判断染色体中非零元素的个数是否大于2，若是，则随机选择染色体中的非零元素进行删除，再在末位补“0”；

若不满足以上条件，则保留原来的染色体，不进行变异操作。

2.2.5 重新评价及判断

1)重新评价当前染色体适应值，更新当前最优染色体。

2)判断是否满足终止条件:(a)算法迭代到最大迭代次数T；(b)有连续Tsame代的最佳染色体相同。若满足终止条件，输出历史最优值的首次出现的代数，最优适应度值以及最佳个体，算法终止；否则，返回步骤2.2.4节。

3 算 例

3.1 基本数据

某学校在一个区域内需要派一辆校车接学生上学，共有79个学生，根据住所的集聚性，所有学生可分为33个学生群体，根据学生住所及道路状况，有7个候选站点可供选择。以学校为坐标原点(0,0)，各个候选站点的坐标位置如表1，各学生群的坐标位置及人数如表2。

表1 候选站点的坐标位置Table 1 Coordinates of the candidate station location /km

表2 学生群的位置坐标及人数Table 2 Coordinates and the number of student of each student group

注：表中学生群的序号续候选站点的编号

设两点之间的距离系数α=1，校车行驶速度v1=30 km/h，学生步行速度v2=5 km/h，车辆停靠站点消耗的最短时间t1=2 min，每个学生上车消耗的时间t2=3 s，学生最大步行时间Tmax=15 min，学生在车上的最长乘车时间tmax=50 min，车辆单位时间的行驶成本γ=200 元/h，学生在车上的单位时间成本λ=2.5 元/h，学生步行的单位时间成本μ=3.0 元/h，求出校车的路径优化方案。

对本例采用改进的遗传算法求解，设定算法的参数如下：种群规模R=50，交叉概率Pc=0.6，变异概率Pm=0.1，最大迭代终止代数T=200，最大相同最佳迭代次数Tsame=50。

3.2 结果分析

3.2.1 最优解

应用改进的遗传算法，用matlab编程运算。经50次运算，有49次得到相同的最优解。其中最快得到最优解的是第3次运算第29次迭代得到最优解的适应度值为f=3.466×10-3，总成本函数值为z=288.501(元)，表3为所求得的最优解。

表3 改进遗传算法得到的最优解Table 3 The optimal solution by improved genetic algorithm

最优解路径网络如图1，图中带箭头的实线表示校车行车路径，虚线表示学生群所归属的候车站点。

图1 校车行驶的最优路径网络Fig.1 The optimal routing network of school bus

3.2.2 不同算法结果比较分析

吴耀华等[4]，张丽艳等[5]和张海刚等[13]提到了改进用粒子群算法求解车辆路径问题具有快速收敛的特点。为了更进一步地验证本文改进遗传算法的有效性，将改进遗传算法与基本遗传算法(GA)、基本粒子群算法(PSO)以及改进的粒子群算法各随机运算50次，进行对比分析。集中算法的最大迭代次数均为200，最大相同迭代次数均为50，对比结果如表4。分别选取4种算法中收敛最快的最优运行结果进行对比，如图2。

表4 4种算法运行结果对比Table 4 The comparison of running results by four kinds of algorithms

由表4可见，改进的GA算法的搜索成功率比改进PSO高出8个百分点，同时迭代次数和运行时间均较少；比基本PSO算法和基本GA算法的搜索成功率高出超过20个百分点，同时迭代次数和运行时间明显小于PSO算法和基本GA算法。

图2 4种算法最优解收敛对比Fig.2 The comparison of convergence of the optimal solutions by the four kinds of algorithms

从图2可以看出，改进GA算法的收敛速度略高于改进的PSO算法，而明显高于基本GA算法和基本PSO算法。可见，改进的GA算法明显优于其它3种方法，是解决这类问题的有效方法。

3.2.3 最优解敏感性分析

根据所得的最优路径，把未被选中的站点按照最近原则插入最优路径中进行敏感性分析如表5。

表5 最优方案的敏感性分析Table 5 Sensitivity analysis of the optimal solutions

从表4可见，几个方案均满足约束条件，而方案4与最优方案1相比，最长步行时间缩短了2.093 min，付出的代价是学生在车上的最长乘车时间增加了5.975 min，同时目标函数的总成本值增加22.23元。同样，方案2和方案3与最优方案1相比也显然处于劣势。由此，可以看出方案1明显优于其它方案。

4 结 语

笔者综合考虑校车路径问题中站点选择、学生群归属站点划分以及车辆行程线路问题，考虑车辆行驶成本、学生在车上的乘车成本以及学生的步行成本问题建立了数学规划模型。根据模型特点设计了改进的遗传算法进行求解，有效降低问题的复杂度，提高搜索效率。通过实例进行分析，表明该算法具有较强的寻优能力，为校车路径问题提供有效的解决方法。

[1] KINABLE J,SPIEKSMA F C R,VANDEN B G.School bus routing—a column generation approach [J].InternationalTransactionsinOperationalResearch,2014,21(3):453-478.

[2] RIERA-LEDESMA J,SALAZAR-GONZALEZ J J.A column generation approach for a school bus routing problem with resource con-straints[J].Computers&OperationsResearch,2013,40(2):566-583.

[3] BOCK A,GRANT E,KOENEMANN J.The school bus problem on trees[J].Algorithmica,2013,67(1):518-528.

[4] 吴耀华，张念志.带时间窗车辆路径问题的改进粒子群算法研究[J].计算机工程与应用,2010,46(15):230-234. WU Yaohua,ZHANG Nianzhi.Modified particle swarm optimization algorithm for vehicle routing problem with time windows[J].ComputerEngineeringandApplications,2010,46(15):230-234.

[5] 张丽艳,庞小红,夏蔚军,等.带时间窗车辆路径问题的混合粒子群算法[J].上海交通大学学报,2006,40(11):1890-1894. ZHANG Liyan,PANG Xiaohong,XIA Weijun,et al.A hybrid particle swarm optimization algorithm for vehicle routing problem with time windows[J].JournalofShanghaiJiaotongUniversity,2006,40(11):1890-1894.

[7] SCHITTEKAT P,KINABLE J,SORENSEN K.A metaheuristic forthe school bus routing problem with bus stop selection[J].EuropenJournalofOperationalResearch,2013(2):518-528.

[8] 刘文.校车优化调度算法及模型研究[J].清华大学学报(自然科学版),2013,53(2):247-251. LIU Wen.An optimization model and algorithms for school bus dispatching[J].JournalofTsinghuaUniversity(ScienceandTechnology),2013,53(2):247-251.

[9] KIM B,KIM S,PARK J.A school bus scheduling problem[J].EuropeanJournalofOperationalResearch,2012,218(2):577-585.

[10] 吴天羿,许继恒,刘建永,等.求解有硬时间窗车辆路径问题的改进遗传算法[J].系统工程与电子技术，2014，36(4):708-713. WU Tianyi,XU Jiheng,LIU Jianyong,et al.Improved genetic algorithm for vehicle routing problem with hard time windows[J].SystemsEngineeringandElectronics,2014,36(4):708-713.

[11] 李毅,陆百川,刘春旭.车辆路径问题的混沌粒子群算法研究 [J].重庆交通大学学报(自然科学版),2012,31(4):842-845. LI Yi,LU Baichuan,LIU Chunxu.Research on chaos particle swarm optimization algorithm for vehicle routing problem[J].JournalofChongqingJiaotongUniversity(NaturalScience),2012,31(4):842- 845.

[12] 彭勇,谢禄江,刘松.时变单车路径问题建模及算法设计[J].重庆交通大学学报(自然科学版),2013,32(2):263-266. PENG Yong,XIE Lujiang,LIU Song.Route modeling and algorithm designing of time-dependent single vehicle[J].JournalofChongqingJiaotongUniversity(NaturalScience),2013,32(2):263-266.

[13] 张海刚，顾幸生，吴燕翔.改进的粒子群算法及其在带软时间窗车辆调度问题中的应用[J].华东理工大学学报(自然科学版),2009,35( 5):774-778 . ZHANG Haigang,GU Xingsheng,WU Yanxiang.Vehicle scheduling problem with soft time windows based on improved particle swarm optimization[J].JournalofEastChinaUniversityofScienceandTechnology(NaturalScienceEdition),2009 ,35(5):774-778.

An Optimization Model and Algorithm for School Bus Routing

HAO Zhongna

(College of Transportation Management, Nanjing Communications Institute of Technology, Nanjing 211188, Jiangsu, P. R. China)

To facilitate selection of school bus stations, allocating student groups to stations and developing vehicle routings, the mathematical programming model was established to minimize the cost of the vehicle travel time, the students journey time, and the students walking time to the station by considering the key constraint conditions such as the longest riding time in the school bus and the longest walking time of students to the station. Then the improved genetic algorithm was put forward to for above purpose and by this algorithm, the excellent individual of initial population was produced by heuristic method, and the operators with heuristic knowledge were designed to improve the excellent searching efficiency. The example analysis results show that the proposed method is feasible with significant results, which can effectively provide optimal route for school bus of large number.

traffic and transportation engineering; school bus routing; optimization; mathematical programming model; improved genetic algorithm

10.3969/j.issn.1674-0696.2016.02.26

2014-11-06；

2015-12-13

江苏省教育厅高校哲学社会科学研究项目(2013SJB6300048)；南京交通职业技术学院校级课题(JR1210)

郝忠娜(1978—)，女，山东烟台人，副教授，硕士，主要从事交通运输规划与管理方面的研究。E-mail：haozn1978@163.com。

U121

A

1674-0696(2016)02-126-05