网络物流中的两个最优算法.pdfVIP

摘 要 摘 要 随着经济的飞速发展，网络物流越来越成为人们关注的焦点，成为生产生活中不可 缺失的重要部分。在最小风险和最优网络问题的研究中，图论中有一些经典算法。但是， 随着网络物流的发展和科技的进步，最小风险和最优网络问题的一些算法已经不能适应 当前的要求，迫切需要人们不断地探索新的最小风险和最优网络的算法。 对于网络物流中的最小风险问题，危险品的运输因其运送物资的特殊性，不仅要求 人们站在网络优化的角度考虑输送费用的优化线路问题，而且要求人们对其整个输送过 程中的风险性给以足够的重视，甚至对后者的要求远远大于前者。 对于网络物流中的最优网络问题，根据实际生产生活的需要，当限定条件加上必过 某些线路时，网络优化变的相对复杂，因此如何运用最长路思想解决网络物流中的最优 网络问题亟待探索与研究。 本文基于最小风险、最优网络与图的关系，分别给出危险品配送的最小风险最低费 用算法和经过给定边集的最优网络算法，其主要内容如下： (1) 针对危险品配送路径优化问题，将可能影响风险的所有因素转变为一个风险函 数考虑，同时综合考虑其他约束条件，给出一种基于深度优先的最小生成树改进算法， 从而实现危险品运输中风险小而路径优之目的。同时，通过对算法复杂度的分析，得知 该算法实用性强、占用空间较少，最后通过实例验证该算法的有效性与正确性。 (2) 针对有向网络中经过指定边集的最优网络问题，基于顶点层次的思想，将有向 网络转化为新的层次网络，然后运用最长路的相关知识以广度优先的原则遍历层次网络 的每层顶点，进而给出基于层次网络的经过给定边集的最优网络算法。最后用实例验证 了算法的有效性与正确性。 关键词 图论 最小费用 最小风险 最长路 最优网络 I Abstract Abstract With the rapid development of economy, the logistics network becomes a focus and an important part in production and life. There are many classic algorithms for the study on the minimum risk and optimal network in graph theory. However, with the development of the logistics network and the progress of science and technology, people need to explore new algorithms for minimum risk and optimal network constantly because one can not adapt to the current requirements now. In light of the particularity of dangerous goods transportation, people need to not only consider the optimization of transmission lines in the perspective of network optimization, but also pay enough attention to the risk in the process of conveying. Sometimes, the latter is more important than the former. The problem of network optimization in logistics network becomes complicated relatively if the qualification has some lines which are given accordi