[优秀论文]车辆调度问题优化算法研究.pdf

上海交通大学
博士学位论文
车辆调度问题优化算法研究
姓名:贾永基
申请学位级别:博士
专业:控制理论与控制工程
指导教师:席裕庚
20041201
上海交通大学博士学位论文
车辆调度问题优化算法研究
摘要
车辆调度问题是现代物流系统优化中关键的一环也是开展电子商务不可缺少的内容
对车辆调度优化理论与算法进行系统研究是构建综合物流系统建立现代调度指挥系统发
展智能交通运输系统和开展电子商务的基础
车辆调度问题最早是由 Dantzig 和 Ramser 于 1959 年提出的由于这一问题的理论涉及
多学科很多实际问题都可以归于这一类问题应用前景广阔所以一直成为运筹学与组合
优化领域的研究热点最近几十年来对车辆调度问题的研究取得了很多有意义的成果已
经广泛用于生产生活的各个方面如报纸或货物投递出租车调度和包裹快递等
在已有研究工作的基础上本文主要研究了车辆调度问题中的 PDPTW 问题 Pickup and
Delivery Problem with Time Windows 带时间窗口的装卸货问题及其扩展问题 PDPTW
问题是为一个车队寻找最优的运输路径来满足所有客户的运输需求本文分析了该问题及其
扩展问题的性质并分别提出了其静态和动态问题的启发式调度算法本文最后对多目标车辆
调度问题进行了研究本文的主要研究成果如下
1. 针对 PDPTW 问题计算复杂度高的特点把禁忌搜索算法应用到该问题的求解中
提出了解决实际规模和复杂度的 PDPTW 问题的两阶段禁忌搜索算法第一阶段构
造一个初始可行解第二阶段使用禁忌搜索算法改进解对该算法进行了复杂度分
析和仿真测试在保证解的性能的基础上在较短的计算时间内得到了 PDPTW 实
例的满意解
2. 在上文算法的基础上进行了算法改进和扩展研究使其性能更好能够处理更复杂
的 PDPTW 问题(1) 对于构造初始解的插入算法进行了改进使得构造的初始解
更有效更稳定(2) 通过引入快速局部搜索来加快禁忌搜索算法的邻域搜索速度
提出了求解 PDPTW 问题的混合禁忌搜索算法该算法在保持解的质量不变的前提
下可以极大的减少算法的计算时间(3) 分析了在求解一类特殊 PDPTW 问题中出
现的搜索停滞现象首次提出了有相似客户 PDPTW 问题并改进了禁忌搜索算法
使其能够有效的求解此类问题(4) 针对多车库 PDPTW 问题提出了处理多车库
的方法在对两阶段禁忌搜索算法做很小改变的情况下使其可以适应多车库
i
上海交通大学博士学位论文
PDPTW 问题的求解要求
3. 针对现实中存在的大多数车辆调度问题都是动态问题分析了动态车辆调度问题不
同于静态车辆调度问题的主要特点提出了求解动态 PDPTW 问题的滚动时域调度
算法并分析了该算法的三个要素当前客户窗口当前客户窗口的调度和滚动策
略最后测试分析了算法性能和影响算法性能的因素
4. 提出了在车辆运输系统中广泛应用的一类特殊 PDPTW 问题——独占性 PDPTW 问
题该问题与一般 PDPTW 问题的主要区别在于一旦车辆开始服务某客户一直
到把货物运到该客户的目的地为止中间不允许服务别的客户给出了该问题的数
学描述分析了其性质并把问题简化为不对称 TSPTW 问题然后分别提出了单车
多车独占性 PDPTW 问题的求解算法实现了计算时间和最终解性能之间的统一
5. 针对目前大多数车辆调度问题的研究都是基于优化运输成本的单目标问题本文提
出了客户满意度的概念提出了一类既考虑运输成本又考虑客户满意度的多目标车
辆调度问题然后提出了求解该问题的多目标混合遗传算法可以得到问题的有效
解本章最后还提出了基于满意优化的多目标车辆调度问题的求解算法可以充分
利用调度者的经验快速的得到多目标车辆调度问题的满意解







关键词车辆调度问题带时间窗口的装卸货问题独占性动态多目标启发式算法
禁忌搜索算法滚动时域调度算法遗传算法






ii
上海交通大学博士学位论文
Optimal Algorithm Research of Vehicle Scheduling Problem
Abstract
Vehicle scheduling problem is the key part of modern logistic system, and also the
indispensable portion of the e-business activities. To study the optimal