任务点选择概率
任务点按选择概率的轮盘分布
26
蚁群算法求解带时间窗车辆调度问题
求解过程：
27
蚁群算法求解带时间窗车辆调度问题
任务点分组时间合理性检查条件：

(ELi ELi

El j El j
)

t
ji

ELx

ELi或者ELx

EL j
或者
i, j Vk i, j Vk i, j Vk , x Vk
基于蚁群算法的车辆 调度问题研究
报告人:滕玮 导 师:刘玉华教授
2006年6月
1
主要内容
绪 论 车辆调度问题的分析 蚁群算法的原理与一个应用模型的建立 蚁群算法求解车辆调度问题 优化调度算法在车辆调度系统中的应用 总结与展望
2
绪论
课题来源 本课题来自武汉市科技局设立的“无线分组数据传输
启发因子 选择概率
8
蚁群算法主要流程
9
仿真试验
算法具有很好的收敛性
10
仿真试验
11
仿真试验
12
蚁群算法的优缺点
主要优点： 蚁群算法是一种分布式的本质并行算法 蚁群算法是一种正反馈算法 蚁群算法具有较强的鲁棒性 易于与其它方法结合
主要不足之处： 收敛速度慢、计算时间长 易于过早的陷入局部最优 在不利于解决连续问题
31
系统组成结构
车辆调度系统结构图
32
车辆优化调度子系统
车辆优化调度子系统功能结构
33
车辆优化调度系统流程分析
34
算法的选择策略
在算法的选择策略上参照了如下规则
35
算法的选择策略
调度任务解决过程
(1) 获取货源信息： (2) 货源数据与运力资源数据的搜索与调用 (3) 智能调度 (4) 货运任务的全程实时管理与行为记录
1. TSP数学模型 2. 一般车辆调度问题 3. 带时间窗的车辆调度问题
硬时间窗车辆调度问题 软时间窗车辆调度问题
4
蚁群算法的原理与一个应用模型的建立
蚁群算法的原理
5
基于蚁群算法的连接增强问题求解
连接增强问题数学模型 蚁群算法求解连接增强问题思想
6
蚁群算法信息素更新
7
蚁群算法启发因子和选择概率
36
全文总结
本文主要创新点如下： 1．本论文针对一般蚁群算法的在寻优过程中容易出现停滞现象或收
敛过早，或者搜索效率不高等缺点进行了分析，提出从信息素更 新规则、更新系数和更新策略方面进行改进的方案，并就蚂蚁前 进选择策略和如何确定选择集合做改进，通过实例验证，该方案 有效的提高了算法收敛速度，扩大了算法搜索空间。 2．本文为求解一般车辆调度问题和带时间窗的车辆调度问题，设计 了基于Sweep算法和蚁群算法的二阶求解方法，实现对车辆数和 路径长度的优化，并对算法的仿真实验结果进行分析，指出了该 方法求解过程中出现随机性的一些原因。试验结果证明，该算法 能有效地实现对路径和车辆数的优化。 3．车辆调度问题是一个很典型的组合优化问题，蚁群算法是现代智 能优化算法，本文将蚁群算法和车辆调度问题结合起来，实现了 对车辆调度的优化，证明了蚁群算法适合于解决车辆调度优化问 题，并尝试将蚁群算法应用到实际车辆调度系统中，为建立完善 合理的车辆调度系统提供了技术参考。
18
蚁群算法求解一般车辆调度问题
求解过程：
19
实例分析
任务点和车场分布如图所示：
图4.4 任务点和车场的分布图 注：图中方形代表车场，圆形代表任务点
20
实例分析
初始扫描线与X轴夹角设定为0，算法第一步由Sweep算法的两个分组 (1,3,5,6,8,11,12)，(2,4,7,9,10)。分组结果如下图所示：
4S一体化智能交通系统”项目。 课题背景及研究意义
1. “第三大利润源” 2. 适应新经济发展的需要 国内外研究现状 1. 国外对车辆调度问题已经作了大量而深入的研究 2. 国内研究车辆调度问题比国外相对落后
3
车辆调度问题的分析
车辆调度问题的描述
车辆调度问题的分类 车辆调度问题数学模型分析
30
优化调度算法在车辆调度系统中的应用
无线分组数据传输4S一体化智能交通系统是由武 汉市科技局下达的科研项目，该项目2005年6月通过 鉴定(鉴定证书编号：武科高鉴字[2005]第131号)。该 系统将无线分组数据传输（GPRS）、遥感遥测 （RS）、全球卫星定位系统（GPS）、地理信息系 统（GIS）和遥控技术一体化。在GPRS网所覆盖的 全国范围内同时对多个车辆实现远程控制及包含图像 传输在内的多项实用功能。系统将所有移动目标的实 时活动数据传回监控中心，以供监控中心对移动目标 进行实时监控管理、调度等。为长途客运、出租车运 营、私家车提供无线监控，协助警察打击犯罪活动； 为物流企业提供获得实时车辆行驶位置、速度等车辆 信息的手段，以实现对车辆的智能化调度。

(EL EL j
j Eli Eli
)

tij

ELx

EL j或者ELx

ELi
i, j Vk i, j Vk i, j Vk , x Vk
28
实例分析
采用标准数据 R102
29
实例分析
给出一个解得出车安排：车辆数17，总行驶路程1503.7313，总等待 时间是747.9307。出车安排如下表所示。
图4.5 任务点的分组情况 注：图中方形代表车场，圆形和三角形代表任务点，相同形状的任务点属于一组
21
实例分析
选择
，得到最短路径长度分别为78.78 (1,3,5,6,8,11,12)，
55.52(2,4,7,9,10)。调度方案如下图所示：
图4.6 调度方案 注：图中方形代表车场，圆形和三角形代表任务点，相同形状的任务点属于一组
13
蚁群算法求解车辆调度问题
Sweep算法
开始扫描前
扫描分组后
注：图中圆点代表任务点，方块代表车场；不同线型连接的任务点代表不同分组。
14
蚁群算法求解车辆调度问题
Sweep算法步骤：
15
蚁群算法求解车辆调度问题
蚁群算法求解TSP问题的实现步骤：
16
蚁群算法求解车辆调度问题
17
蚁群算法求解TSP问题的流程图
22
蚁群算法求解带时间窗的车辆调度问题
带时间窗车辆调度问题的多目标函数
23
蚁群算法的改进
信息素浓度更新规则改进
24
蚁群算法的改进
系数更新策略的改进
25
蚁群算法的改进
轮盘赌选择策略
轮盘赌选择策略类似于博彩游戏中的轮盘赌。如表4.4所示，任务 点各自的选择概率将轮盘分成4个扇区，要进行1次选择，随机生成1 个随机数，相对于转动轮盘1次，获得1次指针停止位置，指针停止在 某一扇区，该扇区代表该任务点被选中。