论文部分内容阅读
设施布局问题是研究在特定的空间范围内,如何放置一定数量的设施使系统物流成本最低的一类优化问题。合理的布局形式可以有效的减低物流成本,提高生产效率。行设施布局问题是设施布局问题的一类重要的问题,其设施沿行布置,广泛应用于各类生产和服务系统中。行设施布局问题是NP-hard的,很难在多项式时间内得到问题的最优解,因此对行设施布局问题建立高效的数学模型,提出有效的优化算法求解具有重要意义。本文研究了四种行设施布局问题:单行设施布局问题、双行布局问题、过道布置问题和平行行排序问题。提出更符合实际的考虑非对称流量和过道宽度的扩展单行设施布局问题以及考虑非对称流量、过道宽度和设施宽度的扩展过道布置问题。以上问题的求解难度大,无法在合理的时间内得到问题的最优解,对现有模型分析的基础上,提出更加高效的混合整数规划模型,同时根据问题性质和特征,设计启发式算法进行求解。本论文的主要研究内容有:(1)针对考虑非对称流量和过道宽度的单行设施布局问题,以最小化设施间的物流成本为目标,使用不同的建模方式建立四个混合整数规划模型,使用解的质量、求解时间、分支定界节点数和线性规划松弛值大小等指标评价模型性能,结果表明基于多面体理论的模型求解性能最好。同时,对有析取约束的两个模型使用指示约束建模,结果表明其中一个模型性能没有发生显著变化,另一个模型性能变差。使用打破对称约束和替代不重叠约束改进性能最好的模型,结果表明改进模型在Gap值、分支定界节点数和求解时间方面都显著好于原模型。(2)对基于多面体理论的扩展单行设施布局问题模型进行分析,在使用替代不重叠约束模型基础上,使用位置p-q方法和位置q方法产生打破对称约束,结果表明位置p-q方法使原模型的在性能提升更大,相较于原模型,平均求解时间和分支定界节点数分别减少56.77和49.78个百分点。提出两个有效不等式约束一个等式约束的七种组合形式,并研究其对使用位置p-q方法的模型性能的影响。结果表明使用等式约束和三角不等式约束的模型MET及使用等式约束,三角不等式约束及星形不等式约束的模型METS的性能最好,在求解时间,分支定界节点数,对偶单纯形迭代次数等方面得到更好的结果,平均Gap_LP值从62.749%下降到16.987%。(3)由于扩展单行布局问题是NP-hard的,无法在多项式时间得到最优解。在分析最优解的结构特征基础上,提出6种构造启发式算法,结果表明基于设施长度的LBP算法的性能显著优于其它构造启发式算法,将LBP算法与精确方法结合求解扩展单行布局问题的改进模型可缩短求解时间,降低Gap值。提出6种改进启发式算法,结果表明使用插入邻域搜索操作的改进启发式算法Insertion性能最好。将Insertion的邻域搜索结构作为模拟退火算法的邻域搜索结构,提出四种模拟退火算法的形式。结果表明使用性能最好的构造启发式算法产生初始解可提高模拟退火算法的性能,另外迭代次数的增加虽然会使求解时间变长,但可有效提高解的质量。与目前经典算例的最优解进行对比,所提模拟退火算法均能在较短时间得到算例的最优解,验证了模拟退火算法求解扩展单行布局问题的有效性。(4)对基于多面体理论的双行布局问题模型进行分析,证明模型中有一条冗余约束,对去掉该冗余约束和添加一条有效不等式约束的模型进行对比分析,结果表明去掉冗余约束可以减少求解时间,冗余约束和有效不等式约束可提高模型的线性松弛值。减少大M的取值可使模型的性能进一步提高。最后,研究了四种基于位置p-q方法的打破对称约束及隐含within-building约束对模型性能的影响。(5)研究了考虑非对称流量、过道宽度及设施宽度的扩展过道布置问题,建立混合整数规划模型。由于该问题是NP-hard的,提出一种面向学习和基于云理论的模拟退火算法(HLCSA)求解该问题。对随机生成的算例数值实验的结果表明,相较于标准模拟退火算法和基于云理论的模拟退火算法,HLCSA在求解质量和求解时间方面更有优势。同时HLCSA可求得规模数最大为n=15的小规模经典算例的最优解。(6)针对平行行排序问题的混合整数规划模型,对设施不重叠约束进行改进,提出一种改进的混合整数规划模型。数值计算结果表明,针对小规模算例,改进模型在较短的时间内得到最优解;对较大规模算例,改进模型在求解时间和Gap值方面具有更好性能。改进模型给出了文献中没有使用的小规模算例的最优解,同时使用该模型还可以得到部分规模为n=24、n=25和n=30算例的最优解,提高了算例精确解的求解规模。本研究针对四种行设施布局问题及其扩展问题,以最小化设施间物流成本为目标,建立相应的混合整数规划模型,并设计求解方法对问题进行求解。本论文丰富了行设施布局问题的研究内容和方法,对推动设施布局理论的发展具有积极的意义。