An Improved Branch & Bound Method for the Uncapacitated Competitive Location Problem

In this paper, the problem of locating new facilities in a competitive environment is considered. The problem is formulated as the firm expected profit maximization and a set of nodes is selected in a graph representing the geographical zone. Profit depends on fixed and deterministic location costs and, since customers are independent decision-makers, on the expected market share. The problem is an instance of nonlinear integer programming, because the objective function is concave and submodular. Due to this complexity a branch & bound method is developed for solving small size problems (that is, when the number of nodes is less than 50), while a heuristic is necessary for larger problems. The branch & bound is called data-correcting method, while the approximate solutions are obtained using the heuristic-concentration method.     

A heuristic approximation of the worst case of Shellsort

A heuristic algorithm is presented to construct permutations which require as many moves in sorting by Shellsort as possible. The approximations obtained are compared with those found by other known methods. Experiments were performed with up ton=2047 elements to be sorted, and the results show the distinct superiority of the heuristic approximations. The actual times needed by Shellsort to sort the worst permutations achieved were determined and compared with the corresponding times of Shellsort in the average case, as well as with the times of quicksort and heapsort in their worst cases.     

Worst-case analysis of the subset sum algorithm for bin packing

We analyze the worst-case ratio of a natural heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. We show a nontrivial upper bound on this ratio of , almost matching a known lower bound.     

基于电子地图的路径最优算法研究

针对车载导航系统和交通监控系统中的最优路径这一关键技术,研究了矢量奄际图数据结构及春用它表示的真实道路网络的特点,探讨了基于电子地图最优路径求解的启发式代价树搜索算法,并提出了不同情形下的求解策略。     

A Robust Genetic Algorithm for Resource Allocation in Project Scheduling

Genetic algorithms have been applied to many different optimization problems and they are one of the most promising metaheuristics. However, there are few published studies concerning the design of efficient genetic algorithms for resource allocation in project scheduling. In this work we present a robust genetic algorithm for the single-mode resource constrained project scheduling problem. We propose a new representation for the solutions, based on the standard activity list representation and develop new crossover techniques with good performance in a wide sample of projects. Through an extensive computational experiment, using standard sets of project instances, we evaluate our genetic algorithm and demonstrate that our approach outperforms the best algorithms appearing in the literature.     

有限注意力下一类满意启发式决策的建模与理性分析

在决策者有限注意力下,现实生活中决策人的选择行为往往表现出一类“满意启发式”特征。基于个体决策者偏好的不完备性,借助方案集系列、考虑集等相关概念探讨了满意启发式决策规则的建模;论证了方案集系列可观与部分可观条件下一类满意决策函数的存在性,以及基于相关理性条件的理性特征,并结合顾客购买行为案例的仿真实验对所建立的满意决策模型进行了验证。仿真结果表明决策者在时间紧逼和信息不完整的情形下可以通过排除部分方案的方式保证以最大概率选到满意方案。研究结果可为现实生活中决策人在时间紧迫、信息缺失等情形下的选择提供一定的理论参考与指导,也可作为一类满意决策研究的理论基础。     

考虑不确定因素的结构损伤定位方法

将应变模态作为实测资料应用概率方法进行结构损伤定位.采用的模态误差考虑了建模误差和测量误差等不确定因素,避免了测量自由度与模型自由度不匹配的问题.研究了损伤状态搜索策略,并对应变模态和位移模态分别作为实测资料的定位结果进行了比较,表明采用应变模态具有更高的定位精度.     

Adaptive linear combination of heuristic orderings in constructing examination timetables

In this paper, we investigate adaptive linear combinations of graph coloring heuristics with a heuristic modifier to address the examination timetabling problem. We invoke a normalisation strategy for each parameter in order to generalise the specific problem data. Two graph coloring heuristics were used in this study (largest degree and saturation degree). A score for the difficulty of assigning each examination was obtained from an adaptive linear combination of these two heuristics and examinations in the list were ordered based on this value. The examinations with the score value representing the higher difficulty were chosen for scheduling based on two strategies. We tested for single and multiple heuristics with and without a heuristic modifier with different combinations of weight values for each parameter on the Toronto and ITC2007 benchmark data sets. We observed that the combination of multiple heuristics with a heuristic modifier offers an effective way to obtain good solution quality. Experimental results demonstrate that our approach delivers promising results. We conclude that this adaptive linear combination of heuristics is a highly effective method and simple to implement.     

A block-based layer building approach for the 2D guillotine strip packing problem

We examine the 2D strip packing problems with guillotine-cut constraint, where the objective is to pack all rectangles into a strip with fixed width and minimize the total height of the strip. We combine three most successful ideas for the orthogonal rectangular packing problems into a single coherent algorithm: (1) packing a block of rectangles instead of a single rectangle in each step; (2) dividing the strip into layers and pack layer by layer; and (3) unrolling and repacking the top portion of the solutions where usually wasted space occurs. Computational experiments on benchmark test sets suggest that our approach rivals existing approaches.     

单回路物流配送问题的新算法——吞圈法

提出解决单回路物流配送问题的一个新启发式算法——吞圈法,通过实验证明,该方法的求解性能稳定,运算次数少,且求解质量较高,优于经典的最近邻点法和最近插入法,也优于大部分智能化算法,是求解单回路物流配送问题的有效方法.