模拟退火算法在带时间窗的车辆调度问题中应用

合肥工业大学硕士学位论文模拟退火算法在带时间窗的车辆调度问题中应用姓名：屈先锋申请学位级别：硕士专业：管理科学与工程指导教师：储诚斌20081001模拟退火算法在带时间窗的车辆调度问题中应用作者：屈先锋学位授予单位：合肥工业大学相似文献(10条)1.学位论文李杰基于网络的邮政运输车辆调度问题研究2009邮政运输是国家邮政事业的中心环节，关系到国民经济的发展及人民生活的便利程度，它不仅是邮政企业赖以传递邮件实现实物空间转移的物质基础，还是决定邮政企业竞争能力和服务质量的主要因素。然而，邮政运输是否得以顺利快速实现这就要取决车辆调度的合理化程度。因此优化车辆调度成为邮政企业提高运行效益、保持竞争实力的有效途径。本文以省一级邮政汽车运输企业为背景，从邮政运输系统的约束条件、优化目标、车辆、时限、运输成本等因素出发，对邮政运输问题进行了系统分析，提出了解决该问题车辆调度数学模型。由于模拟退火算法局部寻优的能力以及遗传算法固有的缺陷，二者的结合正好实现了优势互补，从而设计了模拟退火混合遗传算法对该问题进行求解。为了评估算法性能，在VisualC++6．0环境下进行编程实验，试验结果表明，利用模拟退火混合遗传算法进行车辆优化调度问题求解，能够方便有效的求得近似最优解，此算法可以应用于邮政车辆调度问题的研究。最后，针对邮政汽车运输企业面临的市场竞争和发展前景以及计算机实现车辆自动调度的趋势，本文提出开发邮政运输车辆调度管理系统的设想，进行系统的可行性分析和对数据的完整性分析，为开发此系统提供了理论依据。该系统的完成将大大提高邮政企业的服务水平，降低运营成本，提高邮政企业的客户满意度。2.期刊论文王海军.杨丽娟.万钰然.WANGHai-jun.YANGLi-juan.WANYu-ran模拟退火算法在应急物流车辆调度中的应用-物流工程与管理2009,31(6)应急物流是处理各类突发事件对物资、人员的需求进行紧急保障的一种特殊物流活动.文中根据应急物流的特点,将模拟退火算法用于应急物流车辆调度研究中,同时通过算例,将模拟退火算法与免疫算法进行比较,证明用模拟退火算法优化车辆行驶路径的可行性和全局最优性.3.学位论文钟石泉物流配送车辆调度智能优化方法研究2004目前，我国物流业正向高度专业化和社会化方向发展。物流配送对物流企业增加利润起着关键作用，而车辆调度问题是物流配送的核心问题。因此，对车辆调度问题(VSP).的研究具有非常重要的意义。VSP是一个典型的NP难题，应用纯粹的数学方法难以求解。随着智能优化技术的发展，越来越多的研究人员用智能方法来解决车辆调度问题，这些智能优化方法主要包括：遗传算法、模拟退火算法、禁忌算法以及人工神经网络等。但是从目前的研究状况来看，基本上都还只是对比较简单的车辆调度问题情况进行研究，而且成果比较分散，无论是研究的深度和广度，都不能满足当今物流业迅速发展的需要。针对上述问题，本文在车辆调度问题现有的理论成果基础上，运用智能方法对各种静态非满载车辆调度问题作了比较系统的研究。首先通过相关文献的总结提炼，较为全面地总结了国内外车辆调度问题的研究现状和研究过程中所存在的不足。然后运用遗传算法、模拟退火算法、禁忌算法以及神经网络中的霍普菲尔德模型对单车场容量约束情况下的车辆调度问题进行优化，并且针对具体情况下不同智能算子的特点进行改进，寻求优化车辆调度问题性能最好的智能算法。最后应用健壮性最好的智能方法对各种静态情况下的车辆调度问题进行研究，这些情况主要包括：单车场容量和时间窗约束VSP，单车场多车型约束VSP，单车场复杂情况VSP，多车场单车型VSP，多车场多车型VSP，单车场非满载集送一体化VSP，多车场非满载集送一体化VSP，多车场开放式VSP等。本文对各种静态情况下的车辆调度问题都进行了试验并且给出了代表性的算例，通过与同类文献的比较，显示了本文所提出的智能方法对优化车辆调度问题的有效性和可行性。4.学位论文周兴田基于模拟退火遗传算法的车辆调度问题研究200721世纪是经济全球化的世纪，随着市场经济的深入发展，作为“第三利润源泉”的物流在我国的生产、分配、流通和消费的各个领域起着越来越重要的作用。物流配送是物流中一个重要的直接与消费者相连的环节，因此配送的地位十分突出，如何实现快速而准确的配送是企业在经营方面必须解决的重要课题。一般意义上的物流配送指配送中心按照不同客户多频度、小批量订货要求组织配送，其中主要内容是根据确定的货物量进行车辆的分配和配送路线的安排，亦即广受研究的车辆路线问题(VehicleSchedulingProblem)。由于从事物流配送的汽车货运工作尤其是从事城市配送的汽车货运工作条件复杂，这就需要建立更加科学，优化的配送调度模型来满足顾客对于服务的高质量需求。本文首先对物流配送车辆调度问题作了简要的概述，通过对问题的简化，给出了相应的数学模型。并对问题的常规求解思路作以介绍。第三章介绍了遗传算法韵基本思想及车辆调度问题中遗传算法的应用。由于遗传算法固有的缺陷以及模拟退火算法局部寻优的能力，在遗传算法中结合模拟退火算法正好实现了优势互补，从而形成了退火遗传算法。接着详细介绍了退火遗传算法的步骤。第四章针对第二章简化后得出的物流配送车辆调度问题，给出一种新的染色体编码方式，使得运用退火遗传算法进行优化寻找运输成本最低解时，该算法能在一定范围内自动搜索所需的最优车辆数。最后用算例说明了在新的编码方式下，运用退火遗传算法解决物流配送问题的有效性和通用性。文章在最后对本文的研究工作做了总结，并指出了进一步的研究方向。5.期刊论文张亚娟.卢新亮基于模拟退火算法的物流配送车辆调度问题研究-现代商业2008,(30)在详细分析遗传算法的局限性的基础上,构造了一种基于遗传算法和模拟退火算法的、用于求解车辆路径问题的退火遗传算法.GA和SA的结合,使得串行搜索成为多点并行搜索,混合算法的搜索行为可通过控制温度参数加以控制,且理论上GA并不影响平稳分布,因此鲁棒性必将提高.6.学位论文石磊基于大规模邻域搜索的车辆调度快速算法研究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的概念，分析各个算法的解结构对抗突发事件的鲁棒性。本文的研究工作得到了上海市科技发展基金的支持。7.期刊论文韩世通.朱晓宁.刘金华.HANShi-tong.ZhuXiao-ning.LIUJin-hua基于混合优化算法的带时间窗的车辆调度问题求解研究-物流科技2005,28(6)论文建立了带时间窗的车辆调度问题的数学模型,并针对遗传算法在局部搜索能力方面的不足,提出将模拟退火算法与遗传算法相结合,从而构造了求解车辆调度问题的混合优化算法,并进行了实验计算.计算结果表明,用这种混合优化算法求解车辆调度问题,可以在一定程度上用模拟退火算法的概率突跳性克服遗传算法在局部搜索能力方面的不足,从而得到质量较高的解.8.学位论文李有兰基于模拟退火算法求解随机需求定位路线问题研究2009随着社会经济的飞速发展，市场竞争已越来越激烈，企业建立竞争优势的关键，已由节约原材料和提高劳动生产率，转向建立高效的物流系统。在经济日益全球化的今天，现代物流作为第三种利润和第三产业的重要组成部分，正受到日益广泛的重视。物流中心的选址作为物流运作中的基础要素，其优化和求解意义重大，对此问题的研究即为定位配给问题(LocationAllocationProblem，LAP)；而车辆路线安排问题(VehicleRoutingProblem，VRP)作为物流系统的重要组成部分，对物流系统成本也有较大影响，综合考虑这两个方面并对其进行优化求解设计就形成了定位路线问题(LocationRoutingProblem，LRP)。LRP以集成的眼光来求解物流系统问题，因此可以从整体上大大降低物流系统总成本。本文研究的随机需求LRP问题(LocationRoutingProblemwithStochasticDemands，LRPSD)是对上述LRP问题的一个扩展，在这一问题中，客户的需求是不能事先确切获知的，只是满足同一种概率分布。由于客户需求的不确定性和车辆容量的限制，必然使得车辆在行驶至某一客户处时发生路由失败，发生失败的车辆返回站点装货(或卸货)之后重新返回服务路线上剩余的客户。针对这一问题，本文对车辆发生失败的次数上限进行了限制，在考虑车辆固定成本、设施建设成本的情况下建立了随机需求LRP问题的数学模型。由于上述问题的NP-Hard属性，本文运用模拟退火算法对求解该问题进行了设计，并用C++和Matlab编程实现了这一算法对问题的求解。求解数据来源于对车辆路线问题solomon25个客户点的国际标准测试数据的改造而获得的，求解过程中先利用空间填充曲线和模拟退火算法求解定位配给问题，再用模拟退火算法求解带随机客户需求的车辆路线安排问题，最后将后者的输出结果返代回定位阶段，对设施的选择进一步优化，从而最终求得本文问题的优化解。本文对各阶段的求解结果进行了统计分析，结果显示：对于一定规模的随机需求LRP问题本文的求解方法速度较快，解的精度较高、稳定性较好，从而证明了本文随机需求LRP模型求解方