A Selection Theorem for Strongly Regular Multivalued Mappings

We prove the following generalization of a theorem of Ferry concerning selections of strongly regular multivalued maps onto the class of paracompact spaces: Let : X (Z, ) be a map of a paracompact space X into a metric space (Z, ) whose values (x) are complete subspaces of Z and absolute extensors (AE), for every x X. Suppose that can be represented as = , where : X Y is a continuous singlevalued map of X onto some finite-dimensional paracompact space Y and : Y (Z, ) is a strongly regular map. Then for every closed subset A X and every selection r : A Z of the map |A : A Z, there exists an extension : X Z of r such that is a selection of the map . We also prove a local version of this theorem.     

Bringing order into the neighborhoods: relaxation guided variable neighborhood search

In this article we investigate a new variant of Variable Neighborhood Search (VNS): Relaxation Guided Variable Neighborhood Search. It is based on the general VNS scheme and a new Variable Neighborhood Descent (VND) algorithm. The ordering of the neighborhood structures in this VND is determined dynamically by solving relaxations of them. The objective values of these relaxations are used as indicators for the potential gains of searching the corresponding neighborhoods. We tested this new approach on the well-studied multidimensional knapsack problem. Computational experiments show that our approach is beneficial to the search, improving the obtained results. The concept is, in principle, more generally applicable and seems to be promising for many other combinatorial optimization problems approached by VNS. NICTA is funded by the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.The Institute of Computer Graphics and Algorithms is supported by the European RTN ADONET under grant 504438.     

<Emphasis Type="Italic">F</Emphasis>-Net Convergence with Respect to a Closure Operator

In a category with a closure operator, we introduce the notion of a neighborhood of a point. The neighborhoods are then discussed and used for defining a net convergence structure on the category with respect to the closure operator. The nets considered are obtained as a categorical generalization of the usual nets. We investigate basic properties of the defined convergence. In particular, we study convergence separation and convergence compactness and describe their relationships to the usual closure separation and closure compactness. Mathematics Subject Classifications (2000) 18D35, 54B30, 54A05, 54A20, 54D30.This research was supported by NATO-CNR Outreach Fellowship (No. 219.33) and by Grant Agency of the Czech Republic (No. 201/03/0933).     

Variable Neighborhood Decomposition Search

The recent Variable Neighborhood Search (VNS) metaheuristic combines local search with systematic changes of neighborhood in the descent and escape from local optimum phases. When solving large instances of various problems, its efficiency may be enhanced through decomposition. The resulting two level VNS, called Variable Neighborhood Decomposition Search (VNDS), is presented and illustrated on the p-median problem. Results on 1400, 3038 and 5934 node instances from the TSP library show VNDS improves notably upon VNS in less computing time, and gives much better results than Fast Interchange (FI), in the same time that FI takes for a single descent. Moreover, Reduced VNS (RVNS), which does not use a descent phase, gives results similar to those of FI in much less computing time.     

A Note on Distance Matrices Yielding Elementary Landscapes for the TSP

Symmetric and antisymmetric distance matrices in the single agent traveling salesman problem (TSP) are not the only distance matrices to generate elementary landscapes for swap and 2-opt neighborhoods.     

Reconstruction of the Neighborhood Deck of an Ordered Set

We show that the neighborhood deck of an ordered set can be reconstructed from the deck of one point deleted subsets. As a consequence of the above results we reconstruct some maximal cards and present short new proofs of the reconstructibility of ordered sets of width 2 and of the recognizability of N-free ordered sets. We also reconstruct the maximal cards of N-free ordered sets.     

基于k-means和邻域粗糙集的航空客户价值分类研究

对客户价值进行分类, 识别重要价值客户, 对航空公司获利至关重要。本文提出了基于k-means和邻域粗糙集的航空客户价值分类模型。首先, 从客户的当前价值和潜在价值双视角出发, 建立了航空客户综合价值评价指标体系; 之后, 采用基于Elbow的k-means方法对航空客户进行聚类, 采用邻域粗糙集方法对决策系统进行指标约简, 根据约简后的决策系统完成客户价值初筛。评估前先使用SMOTE方法消除数据的不平衡性, 而后采用网格搜索组合分类器的方法对航空客户价值分类的效果进行评估和检验。最后, 根据评估结果对航空客户价值细分。文末, 对国内某航空公司的62988条真实客户记录进行了实证分析和验证, 其中, 潜在VIP客户群的分类准确率达到了92%, 从而为航空客户价值分类提供了一种新思路。     

面向多个无人机站点的车辆与无人机联合配送路径问题研究

车辆与无人机联合配送模式在产业界受到青睐,该模式有效地降低了配送成本,但却有极大的调度难度,问题的求解也非常复杂。本文对问题进行明确定义并建立模型,根据问题特性设计了一个自适应大规模邻域搜索(Adaptive Large Neighborhood Search, ALNS)算法,进行了大量的实验的对比和分析。研究结果表明,ALNS算法相比Gurobi在运行时间上有明显优势,结果相同甚至更优;车辆与无人机联合配送模式也较仅卡车配送模式节约了成本。     

A three-phase method for identifying functionally related protein groups in weighted PPI networks

Identifying significant protein groups is of great importance for further understanding protein functions. This paper introduces a novel three-phase heuristic method for identifying such groups in weighted PPI networks. In the first phase a variable neighborhood search (VNS) algorithm is applied on a weighted PPI network, in order to support protein complexes by adding a minimum number of new PPIs. In the second phase proteins from different complexes are merged into larger protein groups. In the third phase these groups are expanded by a number of 2-level neighbor proteins, favoring proteins that have higher average gene co-expression with the base group proteins. Experimental results show that: (i) the proposed VNS algorithm outperforms the existing approach described in literature and (ii) the above-mentioned three-phase method identifies protein groups with very high statistical significance.