Two exact algorithms for the vehicle routing problem on trees

This article describes a heuristic and two exact algorithms for several classes of vehicle routing problems defined on tree networks. These include capacitated and time‐constrained vehicle routing problems. One of the exact algorithms is based on the computation of bin packing lower bounds. The other uses column generation. The first algorithm performs better on problems containing small customer demands and in which all vehicles are identical. Otherwise, the second algorithm is more powerful and more versatile. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 75–89, 1999     

多捐赠者肾脏调换问题

用于器官移植的肾脏处于严重的短缺状态。为缓解这一问题,越来越多的国家开始实施各种形式的肾脏调换计划。肾脏调换问题一般被建模为一个合作博弈(KE)。其中的局中人为病人及与其配型失败的捐赠者所构成的二元组。现实中不乏拥有多个配型失败捐赠者的病人。定义了多捐赠者肾脏调换博弈(MDKE),分析了其可行解及稳定解的结构,证明了捐赠多颗肾脏无益于参与稳定调换,将TTC算法、KE稳定解的NP难解性以及最大覆盖稳定解的不可近似性拓展到MDKE。实验表明引入MDKE效果显著。     

Improved bounds for batch scheduling with nonidentical job sizes

Here, we revisit the bounded batch scheduling problem with nonidentical job sizes on single and parallel identical machines, with the objective of minimizing the makespan. For the single machine case, we present an algorithm which calls an online algorithm (chosen arbitrarily) for the one‐dimensional bin‐packing problem as a sub‐procedure, and prove that its worst‐case ratio is the same as the absolute performance ratio of . Hence, there exists an algorithm with worst‐case ratio , which is better than any known upper bound on this problem. For the parallel machines case, we prove that there does not exist any polynomial‐time algorithm with worst‐case ratio smaller than 2 unless P = NP, even if all jobs have unit processing time. Then we present an algorithm with worst‐case ratio arbitrarily close to 2. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 351–358, 2014     

弹药塑料包装透湿机理与应用研究

对弹药塑料包装材料的透湿机理、测试方法、透湿原因、影响因素等进行了分析,并针对塑料包装材料在弹药中的应用现状,提出了提高弹药塑料包装防潮性能的建议。     

包装对弹药保障时效的影响

从包装的角度分析了在时间、运力不受限和受限的情况下对保障时间的影响,同时结合我军弹药保障的特点,对弹药保障模式与弹药包装模式的优化组合进行了分析。     

Bin‐packing problem with concave costs of bin utilization

We consider a generalized one‐dimensional bin‐packing model where the cost of a bin is a nondecreasing concave function of the utilization of the bin. Four popular heuristics from the literature of the classical bin‐packing problem are studied: First Fit (FF), Best Fit (BF), First Fit Decreasing (FFD), and Best Fit Decreasing (BFD). We analyze their worst‐case performances when they are applied to our model. The absolute worst‐case performance ratio of FF and BF is shown to be exactly 2, and that of FFD and BFD is shown to be exactly 1.5. Computational experiments are also conducted to test the performance of these heuristics. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

On online bin packing with LIB constraints

In many applications of packing, the location of small items below large items, inside the packed boxes, is forbidden. We consider a variant of the classic online one‐dimensional bin packing, in which items allocated to each bin are packed there in the order of arrival, satisfying the condition above. This variant is called online bin packing problem with LIB (larger item in the bottom) constraints. We give an improved analysis of First Fit showing that its competitive ratio is at most , and design a lower bound of 2 on the competitive ratio of any online algorithm. In addition, we study the competitive ratio of First Fit as a function of an upper bound (where d is a positive integer) on the item sizes. Our upper bound on the competitive ratio of First Fit tends to 2 as d grows, whereas the lower bound of two holds for any value of d. Finally, we consider several natural and well known algorithms, namely, Best Fit, Worst Fit, Almost Worst Fit, and Harmonic, and show that none of them has a finite competitive ratio for the problem. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

基于遗传算法优化网络权值的装箱问题研究

通过对Hopfield网络模型的研究,把一种类型的装箱问题转化成Hopfield网络模型,再利用遗传算法优化Hopfield网络中的连接权值,形成混合优化算法求解装箱问题,最后通过实例验证了该算法的有效性。     

不同填料旋转床功耗与气体压降特性对比研究

采用同心环波纹碟片填料和不锈钢波纹丝网两种填料,在气液逆流CO2吸收操作时,对旋转床的功耗及气体压降进行了对比实验分析。功耗特性对比结果表明,当液流量不变,旋转床转速低于38 rad/s时,丝网填料旋转床吸收器消耗的功率大于碟片填料旋转床吸收器消耗的功率;转速高于38 rad/s时则相反。气体压降特性对比结果表明,在液流量和旋转床转速不变的操作条件下,碟片填料旋转床的气体压降要大于丝网填料旋转床的气体压降约50 Pa;在气流量和转速不变的操作条件下,当液流量较小时,丝网填料旋转床的气体压降大于碟片填料旋转床的气体压降;当液流量较大时则相反。在相同气流量和液流量下,碟片旋转床气体压降要大于丝网填料旋转床气体压降。研究结果为AIP系统旋转床吸收器的填料优选及全系统的优化设计提供了重要的依据。     

A model to design recreational boat mooring fields

This article develops a mathematical model and heuristic algorithm to design recreational boating mooring fields. The boating industry is important to the Florida economy, and boat storage is becoming a concern among those in the industry. The mooring field design problem is formulated to maximize the total number of boat feet moored in the mooring field. In the model, we allow two adjacent moorings to overlap, which introduces a risk that under certain conditions the boats on these moorings could contact each other. We identify the conditions when contact is possible and quantify the probability of contact. The mooring field design problem is formulated as a nonlinear mixed‐integer programming problem. To solve the problem, we decompose it into two separate models, a mooring radii assignment model and a mooring layout model, which are solved sequentially. The first is solved via exhaustive enumeration and the second via a depth‐first search algorithm. Two actual mooring fields are evaluated, and in both cases our model leads to better layouts than ones experts developed manually. The mooring field design model rationalizes the mooring field design and shows that in one case by increasing the risk from 0 to 1%, the mooring efficiency increases from 74.8% to 96.2%. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009