The Capacitated Team Orienteering Problem: A Bi-level Filter-and-Fan method

This paper focuses on vehicle routing problems with profits and addresses the so-called Capacitated Team Orienteering Problem. Given a set of customers with a priori known profits and demands, the objective is to find the subset of customers, for which the collected profit is maximized, and to determine the visiting sequence and assignment to vehicle routes assuming capacity and route duration restrictions. The proposed method adopts a hierarchical bi-level search framework that takes advantage of different search landscapes. At the upper level, the solution space is explored on the basis of the collected profit, using a Filter-and-Fan method and a combination of profit oriented neighborhoods, while at the lower level the routing of customers is optimized in terms of traveling distance via a Variable Neighborhood Descent method. Computational experiments on benchmark data sets illustrate the efficiency and effectiveness of the proposed approach. Compared to existing results, new upper bounds are produced with competitive computational times.     

CoMFA,CoMSIA, Topomer CoMFA,HQSAR, molecular docking and molecular dynamics simulations study of triazine morpholino derivatives as mTOR inhibitors for the treatment of breast cancer

mTOR has become a promising target for many types of cancer like breast, lung and renal cell carcinoma. CoMFA, CoMSIA, Topomer CoMFA and HQSAR were performed on the series of 39 triazine morpholino derivatives. CoMFA analysis showed q² value of 0.735, r²_cv value of 0.722 and r²_pred value of 0.769. CoMSIA analysis (SEHD) showed q² value of 0.761, r²_cv value of 0.775 and r²_pred value of 0.651. Topomer CoMFA analysis showed q² value of 0.693, r² (conventional correlation coefficient) value of 0.940 and r²_pred value of 0.720. HQSAR analysis showed q²,r²and r²_pred values of 0.694, 0.920 and 0.750, respectively. HQSAR analysis with the combination of atomic number (A), bond type (B) and atomic connections showed q² and r² values of 0.655 and 0.891, respectively. Contour maps from all studies provided significant insights. Molecular docking studies with molecular dynamics simulations were carried out on the highly potent compound 36. Furthermore, four acridine derivatives were designed and docking results of these designed compounds showed the same interactions as that of the standard PI-103 which proved the efficiency of 3D-QSAR and MD/MS study. In future, this study might be useful prior to synthesis for the designing of novel mTOR inhibitors.     

基于CouchDB和Elastic Search的高性能化学结构搜索引擎与数据库的构建

计算机辅助的化学结构搜索在化学信息学中地位十分重要,本文设计了一套高性能的化学结构和化学数据搜索系统,称为DCAIKU.DCAIKU基于CouchDB无模式数据库和ElasticSearch基础架构构建,通过将结构相似性搜索变换为文字搜索实现了高性能和高灵活性的检索引擎：在满足化学信息存储的高灵活性条件下,仍然可以做到低延迟和高准确性,同时拥有良好的伸缩性,可以大规模并行化和集群化.     

R基团搜索技术用于PTH类Tau蛋白抑制剂的分子设计

对26个PTH类Tau蛋白抑制剂进行了Topomer CoMFA研究, 建立了拟合及预测能力良好的Topomer CoMFA模型, 获得的模型拟合、 交互验证及外部预测的复相关系数分别为0.976, 0.603和0.795, 估计标准偏差和Fisher验证值F分别为0.110和115.778. 使用ZINC化合物数据集作为结构片段源, 通过三维定量构效关系(3D-QSAR)模型搜索具有特定活性贡献的R基团. 以样本中活性最高的1号分子过滤, R₁和R₂贡献值均提高了20%的片段分别有9个与2个. 以此交替取代1号样本的R₁与R₂, 得到18个新颖化合物并预测其活性, 其中的15个预测活性值优于模板分子. 研究结果表明, Topomer search可有效地用于分子设计, 所设计的分子为阿尔茨海默病(AD)药物的研发提供了新的候选物.     

Supporting offshoring and nearshoring decisions for mass customization manufacturing processes

Offshore countries attract companies for a possible relocation of production processes through extremely low worker wages. Particularly, mass production processes seem to be highly appropriate for a relocation. However, while the impact of wage reductions can be directly estimated, an appropriate determination of additional cost consequences proves to be a complex task. For instance, on account of lower education standards and higher fluctuation rates, the average worker skills in offshore countries are often significantly lower than in high-wage countries like the United States. In order to appropriately analyze and evaluate the resulting tradeoff between wages and worker skills for mass customization manufacturing systems, this paper introduces a new approach that comprises a detailed mixed-model assembly line balancing. This approach provides a direct comparison of the estimated variable manufacturing costs by generating a country-dependent line layout for all competing locations. In order to validate the efficiency of the balancing approach and, in particular, derive general implications for management, several test series with various country configurations were executed. First, by attaining improvement rates of up to 40%, the capability of a generated Tabu Search procedure for finding appropriate line layouts was proven. Second, as the main result, the complexity of the variant program was identified as a crucial factor for offshoring decisions since it substantially affects variable manufacturing costs. This was particularly proven for countries with low worker skills, which attract offshoring/nearshoring through exceptionally low labor costs. Hence, companies that consider outsourcing production systems to those countries are strongly hold to examine these decisive effects thoroughly. Regarding this, offshoring becomes very promising for manufacturing processes characterized by a moderate variant complexity level.     

A General Vehicle Routing Problem

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.     

The capture time of a graph

We consider the game of Cops and Robbers played on finite and countably infinite connected graphs. The length of games is considered on cop-win graphs, leading to a new parameter, the capture time of a graph. While the capture time of a cop-win graph on n vertices is bounded above by n−3, half the number of vertices is sufficient for a large class of graphs including chordal graphs. Examples are given of cop-win graphs which have unique corners and have capture time within a small additive constant of the number of vertices. We consider the ratio of the capture time to the number of vertices, and extend this notion of capture time density to infinite graphs. For the infinite random graph, the capture time density can be any real number in [0,1]. We also consider the capture time when more than one cop is required to win. While the capture time can be calculated by a polynomial algorithm if the number k of cops is fixed, it is NP-complete to decide whether k cops can capture the robber in no more than t moves for every fixed t.     

A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints

We present a metaheuristic methodology for the Capacitated Vehicle Routing Problem with two-dimensional loading constraints (2L-CVRP). 2L-CVRP is a generalisation of the Capacitated Vehicle Routing Problem, in which customer demand is formed by a set of two-dimensional, rectangular, weighted items. The purpose of this problem is to produce the minimum cost routes, starting and terminating at a central depot, to satisfy the customer demand. Furthermore, the transported items must be feasibly packed into the loading surfaces of the vehicles. We propose a metaheuristic algorithm which incorporates the rationale of Tabu Search and Guided Local Search. The loading aspects of the problem are tackled using a collection of packing heuristics. To accelerate the search process, we reduce the neighbourhoods explored, and employ a memory structure to record the loading feasibility information. Extensive experiments were conducted to calibrate the algorithmic parameters. The effectiveness of the proposed metaheuristic algorithm was tested on benchmark instances and led to several new best solutions.