多目标定位路线安排问题的算法比较研究

摘要

定位-路线安排问题是集成物流系统中一个重要的问题。在一个完整的物流系统中，需要同时考虑设施点的定位、车辆路线安排和车辆的路线分配等联合决策问题，从而提高配送效率。现有文献中定位决策和车辆路线决策，都是假定一条路线由一辆车提供服务。而通过允许车辆多次使用，可以节省更多的费用。因此，在提出的集成模型中，探究了在路线安排过程中一辆车服务几条路线的概念。 总费用和工作量平衡是影响决策的两个基本标准，本文拓展了对操作员工非常重要的公平原则-工作量平衡(总的行程时间和装载量)，并权衡工作量与总费用之间的平衡。在此基础上，考虑了带路线分配决策的多目标定位-路线安排问题，建立了相应的数学模型，并通过了Lingo程序给予的模型检验。基于求解模型是NP-hard问题，分析了禁忌搜索和模拟退火两种启发式算法对模型的求解，针对每种算法采用了联立和序贯两种不同的车辆路线分配形式，以检验车辆多次使用的效果，并结合一个电信公司的案例，来比较算法性能的差异。最后采用总体比例不同的假设检验来比较两种算法关于多目标解的相对非控。结果表明：区域特征在区分算法性能时具有重要的地位；对于长路线的区域，在充分长的运行时间下，SA形式比TS形式具有更好的结果；而在短路线区域中，SA形式和TS形式生成的结果却没有明显差异；一般来说，路线只受容量约束、不受时间约束的情况下，联立形式优于序贯形式，且联立形式在生成非控解方面比序贯形式具有更高的效率。

目录

文摘

英文文摘

声明

第一章 绪论

1.1研究的背景和意义

1.2定位—路线安排问题的提出

1.2.1 LRP的含义

1.2.2从LAP、VRP到LRP

1.3国内外LRP研究的发展历程与现状

1.4本文的总体思路及主要研究内容

1.4.1总体思路

1.4.2主要研究内容

第二章定位—路线安排问题研究综述

2.1定位一路线安排问题概述

2.1.1定位、配给、路线三者之间的关系

2.1.2定位、路线和定位—路线

2.2 LRP的应用及分类

2.2.1LRP的应用

2.2.2 LRP的分类

2.3 LRP求解算法

2.3.1 LRP求解算法的发展

2.3.2常用的求解LRP的算法

2.4确定型LRP的启发式算法

2.4.1 LRP启发式算法的分类概述

2.4.2聚类法、迭代法和层次法

2.5 LRP的未来研究方向

第三章定位—路线安排问题模型研究

3.1设施选址问题概述

3.1.1设施选址问题的意义及分类

3.1.2基本的选址问题

3.1.3选址问题的优化模型

3.2定位配给问题模型

3.2.1定位配给问题描述

3.2.2定位配给问题模型的建立

3.3车辆路线问题模型

3.3.1车辆路线问题描述

3.3.2车辆路线问题模型的建立

3.4定位—路线安排问题模型

3.4.1多源定位—路线安排问题的数学模型

3.4.2 MDLRP模型的建立

3.5多目标定位—路线安排问题模型

3.5.1多目标LRP描述

3.5.2多目标LRP模型的建立

3.5.3多目标LRP模型的验证

第四章多目标LRP的现代优化算法性能评价

4.1现代优化算法

4.1.1禁忌搜索算法的原理和实现步骤

4.1.2模拟退火算法的原理和实现步骤

4.2案例及数据的收集

4.2.1案例背景介绍

4.2.2数据的收集

4.3多目标LRP优化问题

4.3.1多目标优化问题概述

4.3.2多目标优化问题的求解形式

4.3.3多目标与单目标LRP求解形式的关系

4.4现代优化算法设计

4.4.1序贯方法

4.4.2联立方法

4.4.3算法中一些相关处理

4.4.4禁忌搜索算法

4.4.5模拟退火算法

4.5多目标结果的评价

4.5.1算法中序贯形式和联立形式差异

4.5.2现代优化算法之间的比较

结论

参考文献

附录

攻读硕士学位期间取得的研究成果

致谢