车辆调度有及其遗传算法

《车辆调度有及其遗传算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、摘要车辆调度问题就是在满足客户需求的情况下，寻求最优的车辆路径，使得运输成本最小。遗传算法是一种模拟自然界生物进化的搜索算法，由于它具有很强的全局搜索能力和较好的鲁棒性而成为求解车辆调度问题的有效方法。本文介绍了遗传算法的基本概念和基本理论，对遗传算法的选择操作、交叉操作和变异操作做了详细介绍，基于车辆调度问题的特点提出改进的遗传算法。本文将遗传算法和车辆调度问题结合起来，建立了基于最小花费的数学模型，根据问题可行解的结构，提出相应的遗传算法，该算法采用优先权编码通过解码得到可行解，再通过改进的交叉变异方法得到较优的解，从而实现该问题的求解。最

2、后，通过实证分析验证了所建立的基于最小化运输成本车辆调度模型和改进的遗传算法的有效性和可行性。全文共分五章：第一章，介绍车辆调度问题的背景、意义及研究现状。目前对车辆调度问题的研究可分为单配送中心、多配送中心和带时间窗三大类。本章就这三大类情况的求解介绍了几种常见的模型，分别为基于最短路径、基于最短时间和基于最小花费的模型。第二章，介绍遗传算法的理论和算法程序流程图，根据流程图介绍每一操作的特点和原则，对选择操作、交叉操作和变异操作做了详细介绍。第三章，研究多配送中心多车型车辆调度问题，给出基于最小花费模型，该模型的花费包括两个部分，运输费和司

3、机的工资。引进司机的工资更能反应实际情况。给出了改进的遗传算法，对客户采用优先权编码通过解码就能巧妙地处理了由哪个配送中心派哪种车型依次为哪几个客户服务问题，通过实例的计算验证了算法的可行性和有效性。i第四章，研究基于分区的大规模车辆调度问题，给出基于配送中心几何重心的分区聚类方法巧妙地将多配送中心问题化简为多个单配送中心问题，大大降低了问题的复杂度和运算量。再给出基于最小花费模型。对于遗传算法在编码解码的基础上提出了分段交叉，分段变异的思想很好地保留了父代的基因特点。结合实例对比分区和不分区的运算结果验证了基于分区的遗传算法的优越性。第五章，

4、研究带时间窗的车辆调度问题，首先介绍了硬时间窗和软时间窗，分别引入硬时间窗和软时间窗的罚函数，采用罚函数引入适应度函数的方法处理时间窗问题，再基于最小花费模型和改进的遗传算法求解带时间窗的车辆调度问题。实例的结果说明该方法解决此类问题是有效的。第六章，总结。关键词:车辆调度问题;重心分区;遗传算法;时间窗;分段交叉;分段变异;实证分析iiAbstractVehicleschedulingproblemistoseektheoptimalvehiclepathsoastominimizetransportcosts,incaseofmeetcus

5、tomerdemand.Geneticalgorithmisasearchalgorithmbysimulatenaturalbiologicalevolution,becausestrongcapacityofglobalsearchandbetterrobustness,itisaneffectivemethodtosolvethevehicleschedulingproblem.Thispaperintroducesthebasicconceptsofgeneticalgorithmsandthebasictheory,andthesele

6、ctionoperation,crossoveroperationandmutationoperationofgeneticalgorithmareintroducedindetailinthispaper.Theimprovedgeneticalgorithmisproposedbasedonthecharacteristicsofvehicleschedulingproblem.Inthispaper,combinedthegeneticalgorithmandthevehicleschedulingprob-lemstogether,es

7、tablishedamathematicalmodelbasedonminimumcost.Accordingtotheproblemoffeasiblesolutionstructure,putsforwardthecorrespondinggeneticalgorithm,thisalgorithmadoptstheprioritycodingandgetfeasiblesolutionbyde-coding.Crossoverandmutationmethodisimprovedtogetbetterresults,thussolving

8、theproblem.Finally,empiricalanalysisverifythefeasibilityandvalidityofvehicl