大规模车辆路径问题的优化方法研究

《大规模车辆路径问题的优化方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、天津大学博士学位论文大规模车辆路径问题的优化方法研究StudyonOptimizationMethodsofLargeScaleVehicleRoutingProblems一级学科：管理科学与工程学科专业：管理科学与工程研究生：朱琳指导教师：李波教授天津大学管理与经济学部二零一四年六月万方数据独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得天津大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本

2、研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：签字日期：年月日学位论文版权使用授权书本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。特授权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：导师签名：签字日期：年月日签字日期：年月日万方数据中文摘要配送环节在大规模的物流网络系统中有着重要的地位，根据国外权威数据显示，超过一

3、半的物流成本来自于配送环节，尤其是在大规模物流配送网络中。而随着交通线路的日趋复杂以及更高的客户响应需求，对科学规划路径也提出了很高的要求。因此，大规模车辆路径问题的优化研究成为合理降低物流成本的关键。本文针对大规模的车辆路径问题，考虑客户的静态和动态需求来研究车辆路径问题。主要包括两个方面：一是在考虑客户静态需求基础上，根据客户需求是否可以分割配送来研究车辆路径问题的优化方法，并基于启发式方法求解了需求允许分割下的车辆路径问题；二是考虑客户随机需求的基础上，应用马尔科夫过程和启发式算法来给出一对车辆实时动态路径规划的策略。本文的主要工作

4、内容和创新点如下：首先，针对大规模配送系统中的客户需求进行客户聚类子问题的研究，以便在每个聚类集上的车辆配送问题研究。提出了一种新的基于人工免疫系统的聚类算法。为了得到较好地初始解，引入自组织映射方法来生成初始抗体群；在迭代聚类算法过程中，设计了一系列优化和控制进化的策略，如聚类满意度、种群规模的阈值、学习率、聚类监测点和聚类评价指标等。这些策略可以使得聚类参数阈值实现自适应量化来减少用户的主观因素影响；并通过策略的综合作用，来同时得到一种取得局部聚类和全局聚类的方法。最后，仿真实验和分析比较说明了本文方法的有效性。其次，考虑了静态客户需

5、求下的大规模车辆路径问题。在前一部分的研究基础上，提出了一个基于人工免疫系统(AIS)的启发式算法来求解车辆路径问题。通过引入一种新的路径覆盖方法，设计了一种新的编码和算法结构。配送路径通过先聚类后路径的方法产生，并通过网络更新机制来产生初始抗体，以机会均等下的双向学习来扩增抗体。进一步，发展了同心圆建造策略来识别不同客户类，以便形成更多的配送路径以供选择；而提出的两种精英策略(AB)和(R)来去掉较差的抗体以保持配送路径库中路径的多样性。然后，再通过求解更新后路径库中的集合覆盖模型，使得VRP解随着不断增加的路径选择而逐步实现优化过程。

6、最后，还设计了路径合并策略来进一步增加更优的路径。这样，最终的VRP最优解通过在最终路径库中选择成本最优的路径来得到。仿真实验分析说明了所提算法的有效性。万方数据第三，在考虑客户静态需求下，针对一类客户需求允许分割的集成装载问题进行研究。分析该问题的特点，建立了一个双层规划模型来进行描述。为求解该问题，提出了一种双层的聚类算法，即把客户需求进行子聚类的算法和针对每个聚类的客户需求，再进行车辆配载聚类的算法。算法综合应用了人工免疫系统、启发式规则和伪系统聚类算法等，逐步迭代得出整个系统的最优解。最后，设计了仿真数值实验，并进一步与现有文献的

7、研究成果进行了比较分析，得出了所提算法性能的优异性。最后，对于随机客户需求下的车辆路径问题，提出了一个成对合作重新规划路径的策略问题。该策略可以实现配送的一对车辆相互配合，通过两者之间触发有效的通讯，基于实时的客户需求更新车辆指派，来实现配送中路径重优化的动态规划效果。本章提出了一个双层马尔科夫过程来描述此策略，同时设计了启发式算法来根据实时信息动态改变车辆的访问顺序以及车辆的指派方案。仿真数值实验同样证明：本章方法与最新的文献研究成果相比较，所提算法显示出了较好的效果，有着20%-30%的成本节约。关键词：车辆路径问题；随机需求；分割配

8、送；人工免疫算法；启发式算法万方数据ABSTRACTDistributionoperationhasanessentialpositioninthelogisticsnetworks.Acco