计算机系统应用  2018, Vol. 27 Issue (10): 268-272 PDF

1. 中国科学院大学, 北京 100049;
2. 中国科学院 沈阳计算技术研究所, 沈阳 110168

Optimization and Application of Vehicle Scheduling Algorithm Based on Hadoop
CHEN Yan1, YU Fang2, TIAN Yue2, LIU Lu2
1. University of Chinese Academy of Sciences, Beijing 100049, China;
2. Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China
Abstract: With the rapid development of Internet technology, the information data generated by all industries and professions is growing at an exponential rate. The traditional vehicle scheduling algorithm in dealing with dynamic vehicle scheduling problem, already cannot satisfy real-time and large-scale scenario, while big data in Hadoop technology can be a good solution. Therefore, this study constructs a dynamic vehicle scheduling parallel intelligent optimization algorithm based on Hadoop. Based on traditional genetic algorithm, the Hadoop platform parallel computing mechanism is used to improve the weak global optimization ability and converging to local optimal solution of the algorithm. The improved algorithm can effectively cope with massive and rapid response of the vehicle scheduling. The result of numerical calculation shows that the algorithm of vehicle scheduling based on Hadoop can effectively improve the optimization performance of traditional scheduling algorithm and has a good acceleration ratio when dealing with large-scale vehicle scheduling problems.
Key words: intelligent scheduling     Hadoop     vehicle scheduling algorithm     algorithm to optimize     heuristic algorithm

1 传统启发式算法 1.1 遗传算法基本原理

1.2 粒子群算法基本原理

1.3 并行启发式算法原理

Combine函数的输入是Map的输出<key2, value2>, 而此函数的输出依然是键值对可以表示为<key3, value3>, key3依然还是簇类向量标识符, value3为相同key3的所有向量组合和这些向量的数目.

Reduce函数处理属于同一簇的所有数据对象向量, 并重新生成新的簇类中心向量, 其输入输出均是键值对形式. 此时调用传统启发式算法, 实现输入数据对象的随机快速搜索.

2.2 遗传算法的MapReduce并行过程

(1) Map函数

Map(key, value):

Individual ← INDIVIDUAL REPRESENTA TION(key)

fitness ← CALCULATEFITNESS(individual)

EMIT (individual, fitness)

{Keep track of the current best}

if fitness > max then

max ← fitness

maxInd ← individual

end if

if all individuals have been processed then

Write best individual to global file in DFS

end if

(2) C. Partitioner

int GETPARTITION(key, value, numReducers):

return RANDOMINT(0, numReducers - 1)

(3) Reduce过程

Initialize processed ←0, tournArray [2· tSize],

crossArray [cSize]

REDUCE(key, values):

while values.hasNext() do

individual ← INDIVIDUALREPRESENTA TION(key)

fitness ← values.getValue()

if processed < tSize then

{Wait for individuals to join in the tournament and put them for the last rounds}

tournArray [tSize + processed%tSize] ← individual

else

{Conduct tournament over past window}

SELECTIONANDCROSSOVER()

end if

processed ← processed + 1

if all individuals have been processed then

{Clean up for the last tournament windows}

for k=1 to tSize do

SELECTIONANDCROSSOVER()

processed ← processed + 1

end for

end if

end while

SELECTIONANDCROSSOVER:

crossArray[processed%cSize] ← TOURN (tournArray)

if (processed - tSize) % cSize = cSize - 1 then

newIndividuals ← CROSSOVER(crossArray)

for individual in newIndividuals do

EMIT (individual, dummyFitness)

end for

end if

3.2 计算实例及分析

 图 2 算法收敛性能

4 结论

 [1] 冯亮, 梁工谦. 基于GPS/GIS协同的动态车辆调度和路径规划问题研究. 计算机科学, 2017, 44(9): 272-276, 285. [2] 冯亮, 梁工谦. 联网中物流配送车辆调度目标定位设计与仿真. 计算机仿真, 2017, 34(4): 377-381, 405. DOI:10.3969/j.issn.1006-9348.2017.04.080 [3] 唐德权, 黄金贵, 史伟奇. 基于大数据平台的动态车辆路径调度算法. 计算机工程, 2018, 44(1): 74-78. DOI:10.3969/j.issn.1000-3428.2018.01.012 [4] 张丽平. 基于GPS数据的公交车辆动态调度研究[硕士学位论文]. 杭州: 浙江工业大学, 2016. [5] 段晓红. 城市快速路网应急车辆动态调度与再配置研究[硕士学位论文]. 北京: 北京交通大学, 2016. [6] 姚莉. 移动配送模式下快速响应需求的车辆动态调度研究[硕士学位论文]. 北京: 北京交通大学, 2017.