动态环境下的车辆调度问题研究

动态环境下的车辆调度问题研究作者：郭凤鸣学位授予单位：同济大学相似文献(3条)1.学位论文石磊基于大规模邻域搜索的车辆调度快速算法研究2007现代，企业为了提高竞争力，对供应链管理提出了更高的要求，如何高效率地完成从原材料采购，产品生产到产品配送，已成为各公司研究的重点。现代物流系统作为供应链的重要环节，主要包括运输、存储、包装、装卸和搬运等若干相互依赖、相互制约的子系统，其中物流配送是一个与消费者相连的重要环节。本文主要研究了一类车辆优化调度问题――PDPTW问题（PickupandDeliveryProblemwithTimeWindows，带时间窗口的装卸货问题）及其扩展问题的优化调度算法。有时间窗口的装卸货问题（PDPTW）是一个典型的NP-hard问题，因此成为运筹学与组合优化领域的研究的难点与热点。本文主要在两方面对PDPTW问题开展研究，首先，针对静态的PDPTW问题，相关文献中介绍的一些优化算法在计算时间和解的质量方面缺乏良好的平衡，如文献[15]提到的自适应方法，虽然能得到很好的解，但计算时间过长，难以满足实时性要求。本文通过合理平衡计算时间和解质量，提出了一种快速LNS（LargeNeighborhoodSearch,大规模邻域搜索）算法，这种方法具有求解速度快、求解质量好、对初始解的依赖性小的特点。在保持快速求解的前提下，利用模拟退火在全局寻优中的优势，进一步提出了类模拟的快速LNS算法，改进了单一采用LNS算法的不足。其次，本文结合实际应用时车辆在行驶过程中可能损坏的情况研究了动态PDPTW问题，给出了求解策略。本文的研究工作和成果如下：1．分析了PDPTW问题的标准算例，对已有的相关算法进行了测试，理解其优缺点，为寻求和改进算法打下基础。2．提出了改进的LNS算法，在保持解质量的情况下，缩短了求解过程。求解过程主要以减少车辆为目标，通过优先选出短路径中的客户和与之有较大相关性的客户，来调整邻域搜索方向，使之能快速收敛到一个较优的解上，然后加入随机扰动，充分利用LNS算法本身邻域空间较大的优势，寻找在其它空间内更优的解。3．对比了采用上述改进LNS算法所得到的解与其他相关文献所得到的解的质量，分析了影响解质量的因素，提出了类模拟退火的LNS算法，该算法在保持了改进LNS算法快速性的前提下，利用模拟退火在全局寻优能力上的优点，进一步改进原有解的质量，对不同算例的仿真结果表明，该算法对提高随机分布算例的解的质量，具有极大的优势，并且减小了对于初始解的依赖性。4．参考当前车辆调度领域文献中对动态车辆调度问题的研究，对动态PDPTW问题进行讨论，结合实际执行调度过程中车辆可能损坏的情况，给出解决此类问题的策略，在尽量不新增车辆（即使新增车辆，可能到达事故点取货后，仍然会延期交货）的前提下，依靠剩下的车辆来完成所有客户需求，问题的目标定义为最小化客户不满意度，其中客户不满意度包括延迟客户的总数目和所有客户的延迟时间和。5．通过大量仿真测试，给出了静态PDPTW的问题算法解质量的分析，对比不同算法，不同初始解对问题求解的影响，并通过加入动态PDPTW的概念，分析各个算法的解结构对抗突发事件的鲁棒性。本文的研究工作得到了上海市科技发展基金的支持。2.期刊论文张建勇.李军.郭耀煌模糊需求信息条件下的实时动态车辆调度问题研究-管理工程学报2004,18(4)将传统确定性车辆调度问题扩展为具有模糊特征的模糊车辆调度问题.在对模糊需求信息条件下的车辆调度问题进行简单描述的基础上,阐述了全面、实时地考虑所有可用信息的动态模糊车辆调度问题的求解思路,并通过引入决策者主观偏好和模糊可能性的概念,构建了该问题的数学模型,给出了解决该问题的一种实时启发式算法.最后,在最小化车辆行驶距离的目标下,通过随机模拟方法研究了决策者主观偏好值对最终决策目标的影响作用,并通过与非实时调度的比较验证了实时车辆调度的优越性.3.学位论文杨茹集送货一体化的动态车辆调度问题研究2007随着近年来物流业的快速发展，传统的静态车辆调度模型已不能适用于存在诸多随机因素的实际运输系统。同时，计算机软硬件环境及GPS、GPRS、GIS等技术的日益成熟，使得动态的集送货一体化车辆调度正成为车辆路径问题的研究热点之一。本文从理论研究和实际应用的支撑技术两个方面对动态的集送货一体化车辆调度问题进行全面的分析。首先，本文介绍了动态车辆调度问题的研究背景，概述了其研究现状，并分简单策略、经典插入策略、亚启发式算法三类对目前动态车辆调度问题的算法进行了系统的总结与分析。之后，介绍了相关的信息支撑技术，包括车辆定位、GIS信息系统、GPRS通讯，以及射频识别等技术。本文的主要工作是利用局部调整策略和改进的禁忌搜索算法对有实时顾客需求的集送货一体化车辆优化调度问题进行建模和求解。在静态调度阶段采用启发式插入策略构造初始解，然后通过禁忌搜索算法进行搜索优化，在动态调度阶段禁忌算法采取多初始解并行搜索和全局禁忌表，有效地扩大搜索的范围。在数值计算中得到了高质量的路径结果。随后，本文研究了由于新需求的到来，车辆行驶途中动态改变目的地(改道)这种更具动态性的行为，当新订单到来时，通过构造一个伪结点作为优化计算完成时的车辆所在地，利用适应性存储和插入算法得到初始解。文中还重点探讨了计算时间的选取标准。最后，通过分析集送货一体化动态车辆调度系统的设计目标和设计原则，给出了一个动态车辆优化调度系统的设计方案，包括总体设计、系统组成、系统业务流程、以及主要模块功能说明等。本文链接：授权使用：上海海事大学(wflshyxy)，授权号：55ed7111-67ce-4db1-b8fe-9e090096e933下载时间：2010年10月8日