原文传递
基于动态规划与遗传模拟退火算法解定位路线安排问题
| 论文题名： | 基于动态规划与遗传模拟退火算法解定位路线安排问题 |
| 关键词： | 运输路线;空间填充曲线;模拟退火算法 |
| 摘要： | 定位—运输路线安排问题(LocationRoutingProblem，LRP)是物流系统中一个重要问题，因其NP-hard属性，当节点数较多时精确解不宜得到。本文分别提出了单设施定位—路线安排问题(Single-DepotLocationRoutingProblem，SDLRP)和多设施定位—路线安排问题(Mutil-DepotLocationRoutingProblem，MDLRP)的数学模型，并通过Lingo程序给予了检验。基于求解该模型的复杂性，进而提出了相应的两种启发式解法。对于SDLRP，本文提出了基于空间填充曲线和动态规划的启发式算法；即利用空间填充曲线(Space-FillingCurves，SFC)构造初始解，同时实现设施定位，以保证初始解的质量，之后运用动态规划的方法确定最优车辆配置，并通过2-opt对路线进行改进。对于MDLRP，提出了一种两阶段启发式求解算法。该方法分两步实现：首先，采用基于模拟退火算法的启发式方法确定被选择的潜在设施及由每一个选中的设施所要提供服务的客户群；其次，运用混合遗传模拟退火算法求解每一确定客户群中的优化运输路线。此方法集成了设施定位和路线问题，在较短时间内得到问题的优化解，而且避免了遗传算法中存在的早熟收敛问题，增强了算法的全局收敛性，同时通过引入加速适应度函数，在某种程度上提高了算法的收敛速度。最后，通过实例验证了两种方法的快速有效性。 |
| 作者： | 朱志强 |
| 专业： | 载运工具运用工程 |
| 导师： | 胡大伟 |
| 授予学位： | 硕士 |
| 授予学位单位： | 长安大学 |
| 学位年度： | 2006 |
| 正文语种： | 中文 |
检索历史
应用推荐
