详情

原文传递 MDLRPPD模型构建及其启发式组合优化算法研究

论文题名：	MDLRPPD模型构建及其启发式组合优化算法研究
关键词：	物流工程;定位路线;集货配送一体化;模拟退火;禁忌搜索
摘要：	对物流系统进行优化设计，从而为相关企业提供物流优化解决方案，对物流研究者来说始终是一个重要研究领域。本文研究的多站点集货配送一体化的定位-路线问题(Multi-depot Location Routing Problem with Pickups and Deliveries,MDLRPPD)是物流系统优化中的一个重要研究方向，是任何一个大型物流配送企业都必然要面临、期待解决的问题。文中分析了物流系统中选址、集货配送一体化运输的互相制约关系，从物流系统总体成本最小的角度，分析了MDLRPPD的数学模型，并探索其组合优化启发式解法。本文在LRP(Location Routing Problem)数学模型的基础上建立了多站点集货配送一体化的定位-路线问题(MDLRPPD)的数学模型，在小规模数据情形下用Lingo软件对所建立数学模型的正确性进行了验证。因其NP-hard属性，本文设计了禁忌-模拟退火组合优化算法对MDLRPPD数学模型进行求解，首先在满足设施集货配送容量约束(即设施服务的客户点的总需求和总供应量都不能超过设施的容量限制)的前提下随机产生多站点定位-配给问题(Multi-depot Location AllocationProblem，MDLAP)的初始解，采用禁忌搜索算法对MDLAP进行优化，将结果作为集货配送一体化车辆路线问题(Vehicle Routing Problem with Pickups andDeliveries，VRPPD)的输入，在VRPPD求解过程中，首先以客户需求量为基数，对选中设施服务的客户进行排序，根据集货配货容量限制依次对客户进行判断，如果客户进入路线以后，在服务车辆卸下其需求物品后，能顺利的将其供应物资装上，那么将该客户纳入本条路线，如此循环直至所有客户都被纳入到相应线路中，从而产生VRPPD初始解；然后采用模拟退火算法通过插入法、路线间交换、路线内部交换、2-opt法对VRPPD进行优化，之后再将VRPPD结果返回到MDLAP阶段通过插入法、站点间客户交换法、站点交换法产生MDLAP优化解的邻域解作为VRPPD的输入，按照特定的终止原则在MDLAP和VRPPD阶段反复循环迭代，保存迭代的最优解，作为MDLRPPD的优化解。借助C++程序语言对该组合优化算法进行编程。然后，对同组小规模数据分别采用Lingo软件和本文设计的组合优化算法C++程序进行实例计算，二者计算结果的费用、设施选取与路线安排方案均一致；最后，利用该组合优化算法程序对中等规模和较大规模测试数据进行了仿真计算。结果表明使用本文设计的禁忌-模拟退火组合优化算法求解MDLRPPD快速有效，在可接受的时间范围内求解较大规模的MDLRPPD是可行有效的。通过对不同规模实例的反复仿真测试发现：随着问题规模的扩大，算法中所涉及的迭代次数、初始温度、降温系数、禁忌长度、邻域解数量等参数逐渐变大，计算机处理时间急剧增加，但算法的稳定性和收敛性不变。并且问题规模与算法计算时间呈指数变化关系，问题规模变化对算法计算时间的影响比参数变化带来的影响要大得多。
作者：	林晖钢
专业：	载运工具运用工程
导师：	胡大伟
授予学位：	硕士
授予学位单位：	长安大学
学位年度：	2009
正文语种：	中文