求解车辆路径问题的启发式算法及其在注塑排程问题中的应用

发布时间：2019-09-26 15:00

【摘要】：车辆路径问题是目前研究最为广泛,应用价值较高的一类组合优化问题。制造业中的注塑排程可建模为带时间窗的车辆路径问题,并由车辆路径问题的算法进行求解,该类问题的求解最常采用的是启发式算法。启发式算法目前已广泛应用于各类优化问题的求解。对于较大规模优化问题,现有启发式算法常面临运算时间长、求解精度不高等困难。通过归约的方法将大规模优化问题转化为规模较小的优化实例是求解该类问题的有效途径之一。本论文围绕车辆路径问题、生产排程中的注塑排程及如何利用归约的方法设计求解大规模优化问题的高效启发式算法这三个方面进行研究,主要工作和成果如下:1)提出求解车辆路径问题的快速多邻域迭代局部搜索算法。局部搜索算法中需要反复对邻域解进行评估,该评估占用了算法大部分运行时间。为此,提出应用于车辆路径问题多种邻域解的合法性快速评估策略,该策略将时间、容量、最大行驶距离等各种约束嵌入客户节点信息,将邻域解的评估计算复杂度降低为O(1),提高了算法的计算效率。构造车辆路径问题偏移实例,采用可变长编码,实现车辆数和运输成本的同步优化。算法仿真结果表明,该算法能在短时间内获得车辆路径问题的满意解。2)提出基于归约的迭代局部搜索算法。优化问题的可行解可看作是由一组基元构成的,可行解的进化过程可看作是基元不断改善的过程。所谓“归约”是指将解个体中的优质基元固化,将原问题转化为规模更小的归约实例。基于此,提出一种新颖的归约实例构造方法,该方法依据近似骨架概率选择优质基元,优质基元在新的归约实例中以封装成虚拟客户节点的方式被固化。基于归约的迭代局部搜索算法是一种基于种群的优化方法。在算法进化过程中,利用近似骨架概率信息可不断获得规模数更小的归约实例,缩小邻域搜索范围,进而提高算法的搜索效率。实验结果表明该算法能够获得比快速多邻域迭代局部搜索算法更为精确的结果。3)提出一种新型的求同优化算法。该算法的基础是对可行解中基元的合理评估,为此,提出结合解个体的优劣程度和基元在种群中那个的获接受程度的基元认同度计算方法,并依据基元认同度选择优质基元。优质基元构成优质个体,定义个体认同度,并利用个体认同度指导算法的优化过程。在求同优化算法的迭代过程中,解个体的共同基元获保留,其他基元在后续迭代中不断优化。随着共同基元的增加,种群中所有解个体进化为同一个解,此即为所求。求同优化算法的收敛速度快,求解精度高,能有效求解大规模容量约束车辆路问题。4)提出应用于注塑排程的快速多邻域迭代局部搜索算法。注塑排程本质上可建模为带时间窗的车辆路径问题。提出机器码和时间窗交叠检测方法,得到应用于注塑机约束和模具约束的快速评估策略。该算法能够在短时间内获得注塑排程的满意解,具有很强的实用性。
【图文】：

趋势图,社会物流,总费用,趋势

会必不可少的工具。目前，计算机能够高效地实现的计算、统计、检索等工作中解放出来。现实生活计算模型，并设计相应的算法由计算机进行求解。例、交通领域的航线规划问题、制造业中的生产排程问合计算机求解的模型。其中制造业和物流业是我国的高制造业和物流业的管理水平，对节约企业生产成本务的迅速普及，中国的物流行业得到快速发展。然而商务的运营成本，制约了电子商务的快速扩张。数用为 10.2 万亿元，，占 GDP 的比率为 18%。图 1.1 给用与 GDP 的比率变化趋势。从该趋势图可见，近年率维持在 17~18%之间。而美国、日本和德国的这一约为 11.5%，这反映出中国物流成本明显偏高。

示意图,生产过程

tion molding scheduling，IMS）的数学模型。同时，针对注塑排程，窗交叠检测方法，进而得到应用于注塑机约束和模具约束的快速评估解 VRPTW 的快速多邻域迭代局部搜索 (fast multi-neighborhood iteraNILS) 算法的基础上，提出应用于注塑排程的改进 FMNILS(iMNILS)算法。仿真实验结果表明，iFMNILS 算法能够在较短的时间解，具有很强的实用性。程及其数学模型产过程型（Injection molding）工艺是目前应用最为广泛的塑料材料加工方法、自动化程度高、生产效率高、原料浪费少、能生产复杂形状的产品于电气和电子、电信工程、航空航天、日用品等领域[131]。通过注塑品称为注塑产品，即通过注塑机加热塑料至塑化熔融，再注射至模具经冷却固化后脱模所获的制品，其生产过程示意图如下所示：
【学位授予单位】：深圳大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP301.6

【参考文献】