车辆调度问题优化算法研究

《车辆调度问题优化算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、上海交通大学博士学位论文车辆调度问题优化算法研究姓名：贾永基申请学位级别：博士专业：控制理论与控制工程指导教师：席裕庚20041201上海交通大学博士学位论文车辆调度问题优化算法研究摘要车辆调度问题是现代物流系统优化中关键的一环也是开展电子商务不可缺少的内容对车辆调度优化理论与算法进行系统研究是构建综合物流系统建立现代调度指挥系统发展智能交通运输系统和开展电子商务的基础车辆调度问题最早是由Dantzig和Ramser于1959年提出的由于这一问题的理论涉及多学科很多实际问题都可以归于这一类问题应用

2、前景广阔所以一直成为运筹学与组合优化领域的研究热点最近几十年来对车辆调度问题的研究取得了很多有意义的成果已经广泛用于生产生活的各个方面如报纸或货物投递出租车调度和包裹快递等在已有研究工作的基础上本文主要研究了车辆调度问题中的PDPTW问题PickupandDeliveryProblemwithTimeWindows带时间窗口的装卸货问题及其扩展问题PDPTW问题是为一个车队寻找最优的运输路径来满足所有客户的运输需求本文分析了该问题及其扩展问题的性质并分别提出了其静态和动态问题的启发式调度算法本文最

3、后对多目标车辆调度问题进行了研究本文的主要研究成果如下1.针对PDPTW问题计算复杂度高的特点把禁忌搜索算法应用到该问题的求解中提出了解决实际规模和复杂度的PDPTW问题的两阶段禁忌搜索算法第一阶段构造一个初始可行解第二阶段使用禁忌搜索算法改进解对该算法进行了复杂度分析和仿真测试在保证解的性能的基础上在较短的计算时间内得到了PDPTW实例的满意解2.在上文算法的基础上进行了算法改进和扩展研究使其性能更好能够处理更复杂的PDPTW问题(1)对于构造初始解的插入算法进行了改进使得构造的初始解更有效更稳

4、定(2)通过引入快速局部搜索来加快禁忌搜索算法的邻域搜索速度提出了求解PDPTW问题的混合禁忌搜索算法该算法在保持解的质量不变的前提下可以极大的减少算法的计算时间(3)分析了在求解一类特殊PDPTW问题中出现的搜索停滞现象首次提出了有相似客户PDPTW问题并改进了禁忌搜索算法使其能够有效的求解此类问题(4)针对多车库PDPTW问题提出了处理多车库的方法在对两阶段禁忌搜索算法做很小改变的情况下使其可以适应多车库i上海交通大学博士学位论文PDPTW问题的求解要求3.针对现实中存在的大多数车辆调度问题都

5、是动态问题分析了动态车辆调度问题不同于静态车辆调度问题的主要特点提出了求解动态PDPTW问题的滚动时域调度算法并分析了该算法的三个要素当前客户窗口当前客户窗口的调度和滚动策略最后测试分析了算法性能和影响算法性能的因素4.提出了在车辆运输系统中广泛应用的一类特殊PDPTW问题——独占性PDPTW问题该问题与一般PDPTW问题的主要区别在于一旦车辆开始服务某客户一直到把货物运到该客户的目的地为止中间不允许服务别的客户给出了该问题的数学描述分析了其性质并把问题简化为不对称TSPTW问题然后分别提出了单车

6、多车独占性PDPTW问题的求解算法实现了计算时间和最终解性能之间的统一5.针对目前大多数车辆调度问题的研究都是基于优化运输成本的单目标问题本文提出了客户满意度的概念提出了一类既考虑运输成本又考虑客户满意度的多目标车辆调度问题然后提出了求解该问题的多目标混合遗传算法可以得到问题的有效解本章最后还提出了基于满意优化的多目标车辆调度问题的求解算法可以充分利用调度者的经验快速的得到多目标车辆调度问题的满意解关键词车辆调度问题带时间窗口的装卸货问题独占性动态多目标启发式算法禁忌搜索算法滚动时域调度算法遗传算

7、法ii上海交通大学博士学位论文OptimalAlgorithmResearchofVehicleSchedulingProblemAbstractVehicleschedulingproblemisthekeypartofmodernlogisticsystem,andalsotheindispensableportionofthee-businessactivities.Tostudytheoptimaltheoryandalgorithmofvehicleschedulingproblemis

8、thebasisofconstructingtheintegratedlogisticsystem,establishingmodernschedulingsystem,developingtheintelligenttransportationsystemanddevelopingthee-business.VehicleschedulingproblemwasfirstlyproposedbyDantzigandRamserin1959.Forthetheoryofthispr