不确定运行时间环境下的车辆调度问题及启发式算法

考虑到物流公司或者配送中心车辆实际运行过程中时间的不确定性,提出了配送服务线路包含时间窗口、车辆容量约束的随机规划模型,以最小化车辆运行成本同时尽可能降低所服务顾客的不满意度.同时,又稍作改进给出了平均-风险模型,由于VRP问题是NP难的,给出了一种基于禁忌搜索的启发式算法,并以北京市13个点的为例,给出求解结果.     

多车型多品种货物配装优化问题的混合启发式算法

为满足客户多样化和个性化的需求,建立能充分、均衡利用装载工具的载重和容积的多品种、多车型货物配装模型,并从全局、整体最优上设计混合启发式算法求解。首先,采用实数序列编码,使问题变得更简洁;基于容重比平衡法构建初始解,提高了解的可行性;用基于排序的选择与最佳保留相结合策略,保证群体的多样性;采用改进的非一致变异,加强染色体的局部搜索能力;其次,对遗传算法求得的精英种群再进行禁忌搜索,提高了搜索效率;最后,通过实例计算证明了上述模型和算法的有效性,并为大规模解决实际问题提供思路。     

Reliability analysis of non‐repairable systems modeled by dynamic fault trees with priority AND gates

Many real‐life systems are typically involved in sequence‐dependent failure behaviors. Such systems can be modeled by dynamic fault trees (DFTs) with priority AND gates, in which the occurrence of the top events depends on not only combinations of basic events but also their failure sequences. To the author's knowledge, the existing methods for reliability assessment of DFTs with priority AND gates are mainly Markov‐state‐space‐based, inclusion–exclusion‐based, Monte Carlo simulation‐based, or sequential binary decision diagram‐based approaches. Unfortunately, all these methods have their shortcomings. They either suffer the problem of state space explosion or are restricted to exponential components time‐to‐failure distributions or need a long computation time to obtain a solution with a high accuracy. In this article, a novel method based on dynamic binary decision tree (DBDT) is first proposed. To build the DBDT model of a given DFT, we present an adapted format of the traditional Shannon's decomposition theorem. Considering that the chosen variable index has a great effect on the final scale of disjoint calculable cut sequences generated from a built DBDT, which to some extent determines the computational efficiency of the proposed method, some heuristic branching rules are presented. To validate our proposed method, a case study is analyzed. The results indicate that the proposed method is reasonable and efficient. Copyright © 2015 John Wiley & Sons, Ltd.     

混合启发式算法求解多配送人员车辆路径问题

为解决带时间窗和多配送人员的车辆路径问题,本文采用混合启发式算法对其进行求解。该算法主要由整数规划重组、局部搜索算法和模拟退火算法三部分组成。在算法中,整数规划重组有效提高了解的质量,局部搜索算法和模拟退火算法保证了算法搜索的深入性和广泛性。通过与CPLEX和禁忌搜索算法进行对比,证实了混合启发式算法实用价值更高,求解效果更好。     

范数下无容量限制设施选址逆问题的求解方法

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。