检索结果-内蒙古大学图书馆

MEACCP: A membrane evolutionary algorithm for capacitated clustering problem

INFORMATION SCIENCES 2022年 591卷 319-343页

作者： Liu, Yaoyao Guo, Ping Zeng, Yi Chongqing Univ Coll Comp Sci Chongqing 400044 Peoples R China Chongqing Key Lab Software Theory & Technol Chongqing 400044 Peoples R China

The capacitated clustering problem (CCP) is a constrained clustering problem with a wide range of applications in VLSI design, vehicle routing, and mail delivery. In order to improve the performance of solving CCP, this paper proposes a membrane evolutionary algorithm MEACCP based on the Membrane Evolutionary Algorithm Framework (MEAF). First, the membrane structure of MEACCP and its object representation are designed. Second, six evolution operators are designed to evolve objects within the membrane and membrane structures. Third, the MEACCP and the method of membrane population initialization are discussed. Finally, MEACCP experiments were conducted on 100 instances of four different types of benchmark datasets, and the experimental results were compared with the results of the current state-of-the-art CCP algorithms. The experimental results show that the number of instances where MEACCP can find the optimal solution is 4.3 -9.1 times that of the algorithms in comparison, and the stability is better than all comparison algorithms. (c) 2022 Elsevier Inc. All rights reserved.

关键词： capacitated clustering problem Membrane Evolutionary Algorithm Membrane Computing Constrained Combinatorial Optimization problem

来源：评论

学校读者我要写书评

暂无评论

capacitated clustering problems applied to the layout of IT-teams in software factories

引用

ANNALS OF OPERATIONS RESEARCH 2022年第2期316卷 1157-1185页

作者： Negreiros, Marcos J. Maculan, Nelson Batista, Pablor L. Rodrigues, Joao A. Palhano, Augusto W. C. Univ Estadual Ceara Mestrado Profiss Comp Aplicada MPCUMP UECE IFCE Lab Comp Cient LCC Av Silas Munguba 1700Campus Itaperi BR-60714903 Fortaleza CE Brazil Univ Fed Rio de Janeiro Programa Eng Sistemas Comp PESC COPPE Sala H-322B BR-21 94197 Rio De Janeiro RJ Brazil

This work studies Heterogeneous capacitated clustering problems (HCCP) which are variations of the capacitated clustering problem (CCP). They are applied to the layout of IT-Teams in software factory. In the real problem, there are workstations placed along the software factory where they are disposed in a pattern the individuals working in the same project form a group that would be geographically close to each other. The groups are heterogeneous in the number of individuals. The general problem discussed here consider a given number of individuals with attributes (weight and coordinates in Euclidean space), and wishes to determine minimum dissimilarclustersconstrained to a given maximum capacity for eachcluster. The groups are formed to achieve a specific objective of just forming feasible capacitated compact groups and/or also including the position of the group manager. The models here presented and evaluated consider a new generalized version of the heterogeneous capacitated median problem (gHCMP) which extracts the medians from the set of individuals;a new formulation is introduced for the min-max diameter heterogeneous capacitated clustering problem;a new formulation for the minimum group distance heterogeneous capacitated clustering problem;and a new formulation using the HCCCP. We also discuss ways to obtain the best results from the proposed formulations using adequate solvers for each problem;and it is presented a metaheuristic framework for the HCCCP that solves close to optimality all the real instances here tested. We also present the results obtained from the formulations and metaheuristic related to instances that represent real situations about organizing the layout of two Brazilian software factories. The proposed gHCMP model outperform the solutions obtained for the evaluated instances also using the other models.

关键词： capacitated clustering problem Mathematical programming modeling Solvers

来源：评论

学校读者我要写书评

暂无评论

Research on the Application of Weighted Distance K-means clustering Algorithm with Capacity Constraint in Express Service Location 12

Research on the Application of Weighted Distance K-means Clu...

引用

12th International Conference on Information Systems and Computing Technology

作者： Cheng, Xu Zheng, Fengfeng Chengdu Univ Technol Coll Comp Sci & Cyber Secur Chengdu Peoples R China

ISBN: (纸本)9798350379860;9798350379877

clustering is an unsupervised machine learning method, which aims to group data points according to the similarity of data. As a mature clustering algorithm, K-means has been widely used in the location problem. This paper discusses its application in an express service location problem, especially through the improved K-means algorithm to optimize the location decision. The advantage of the algorithm in this paper is that it considers the different influence of the receiving volume and the delivering volume on the cost of the express logistics field, the self-defined weighted distance is introduced to combine the express transportation distance with the express delivery and receipt index, which more accurately reflects the economic cost and benefit of the express delivery enterprise. On this basis of the weighted distance, the algorithm is customized and improved through a capacity constraint in order to satisfy the location demand of the express delivery enterprise. Finally, a numeric experiment shows the effectiveness and practicality of our algorithm on the express service location problem.

关键词： K-means clustering capacitated clustering problem weighted distance express service location

来源：评论

学校读者我要写书评

暂无评论

capacitated clustering problem in computational biology: Combinatorial and statistical approach for sibling reconstruction

引用

COMPUTERS & OPERATIONS RESEARCH 2012年第3期39卷 609-619页

作者： Chou, Chun-An Chaovalitwongse, Wanpracha Art Berger-Wolf, Tanya Y. DasGupta, Bhaskar Ashley, Mary V. Univ Washington Dept Ind & Syst Engn Washington DC USA Univ Washington Dept Radiol Washington DC USA Rutgers State Univ Dept Ind & Syst Engn Piscataway NJ 08855 USA Princeton Univ Dept Operat Res & Financial Engn Princeton NJ 08544 USA Univ Illinois Dept Comp Sci Chicago IL USA Univ Illinois Dept Biol Chicago IL USA

The capacitated clustering problem (CCP) has been studied in a wide range of applications. In this study, we investigate a challenging CCP in computational biology, namely, sibling reconstruction problem (SRP). The goal of SRP is to establish the sibling relationship (i.e., groups of siblings) of a population from genetic data. The SRP has gained more and more interests from computational biologists over the past decade as it is an important and necessary keystone for studies in genetic and population biology. We propose a large-scale mixed-integer formulation of the CCP for SRP that is based on both combinatorial and statistical genetic concepts. The objective is not only to find the minimum number of sibling groups, but also to maximize the degree of similarity of individuals in the same sibling groups while each sibling group is subject to genetic constraints derived from Mendel's laws. We develop a new randomized greedy optimization algorithm to effectively and efficiently solve this SRP. The algorithm consists of two key phases: construction and enhancement. In the construction phase, a greedy approach with randomized perturbation is applied to construct multiple sibling groups iteratively. In the enhancement phase, a two-stage local search with a memory function is used to improve the solution quality with respect to the similarity measure. We demonstrate the effectiveness of the proposed algorithm using real biological data sets and compare it with state-of-the-art approaches in the literature. We also test it on larger simulated data sets. The experimental results show that the proposed algorithm provide the best reconstruction solutions. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： clustering analysis capacitated clustering problem Combinatorial optimization Sibling reconstruction Computational biology

来源：评论

学校读者我要写书评

暂无评论

Integrated student to school assignment and school bus routing problem for special needs students

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2021年 152卷 102416-102416页

作者： Ansari, Azadeh Farrokhvar, Leily Kamali, Behrooz West Virginia Univ Dept Ind & Management Syst Engn 1306 Evansdale Dr Morgantown WV 26506 USA Calif State Univ Northridge Dept Syst & Operat Management 18111 Nordhoff St Northridge CA 91330 USA

In this paper, we address the combined problem of assigning students to schools and generating school bus routes for special needs students. Special needs students typically require additional accommodations, both in terms of the services available at school and during pick-ups and drop-offs. This introduces additional complexities to the problems of assignment and routing for students. We develop a mathematical model that jointly addresses these problems, and incorporate multi-loads and heterogeneous bus fleet features. The model simultaneously assigns special needs students to schools based on their level of need and the availability of resources, and generates efficient routes to transport them to their designated schools. We propose a two-phase heuristic approach using the capacitated clustering problem, which is capable of generating high-quality solutions. We evaluate our proposed methodology using several randomly generated instances, and a real-world case study in Fort Smith, Arkansas. The results from the case study demonstrate that the proposed methodology can reduce the total miles traveled by buses by over 35% on average, when compared to previously developed heuristics in the literature for the same case study.

关键词： Transportation Heuristics School bus routing capacitated clustering problem Special needs students

来源：评论

学校读者我要写书评

暂无评论

Bus Pooling: A Large-Scale Bus Ridesharing Service

引用

IEEE ACCESS 2019年 7卷 74248-74262页

作者： Liu, Kaijun Zhang, Jingwei Yang, Qing Guilin Univ Elect Technol Guangxi Key Lab Trusted Software Guilin 541004 Peoples R China Guilin Univ Elect Technol Guangxi Key Lab Automat Detect Technol & Instrume Guilin 541004 Peoples R China

Ridesharing, a shared service that uses the information and knowledge matching, can efficiently utilize scattered social resources to reduce the demand for vehicles in urban road networks. However, car ridesharing has the problems of low capacity and high cost, and it cannot satisfy demands for recurring, long-distance, and low-cost trips. In this paper, we formally define the bus ridesharing problem and propose a large-scale bus ridesharing service to resolve this problem. In our proposed model, the rider can use an online bus-hailing service to upload his or her trip demand and wait to be picked up when it gathers enough people. The provider assigns drivers to riders after integrating the matched ride requests. To maximize ridesharing's success rate, we developed both exact algorithms and approximate algorithms to optimize the ride-matching service. A real-life dataset that contains 65,065-trip instances extracted from 10,585 Shanghai taxis from one day (Apr 1, 2018) is used to demonstrate that our proposed service can provide higher cost performance and on-demand bus services for every ride request. Meanwhile, it reduces the number of vehicles used by 92% and 96% and the amount of oil used by 87% and 92% compared with car ridesharing and no ridesharing, respectively.

关键词： Ridesharing bus pooling capacitated clustering problem location-allocation problem

来源：评论

学校读者我要写书评

暂无评论

A general framework for nested variable neighborhood search

引用

Electronic Notes in Discrete Mathematics 2017年 58卷 159-166页

作者： Brimberg, Jack Mladenović, Nenad Todosijević, Raca Urošević, Dragan Royal Military College of Canada Kingston Ontario Canada Mathematical Institute SANU Belgrade Serbia

In this paper we review a recently proposed variant of variable neighborhood search (VNS) referred to as nested variable neighborhood search (NVNS) and propose a generalization of this approach. In addition, we develop a heuristic stemming from this general framework and apply it on the capacitated clustering problem (CCP). Based on obtained results the proposed heuristic outperforms the current state-of-the-art for the CCP. © 2017 Elsevier B.V.

关键词： capacitated clustering problem Nested variable neighborhood search variable neighborhood descent

来源：评论

学校读者我要写书评

暂无评论

A reactive GRASP with path relinking for capacitated clustering

引用

JOURNAL OF HEURISTICS 2011年第2期17卷 119-152页

作者： Deng, Yumin Bard, Jonathan F. Univ Texas Austin Grad Program Operat Res & Ind Engn Austin TX 78712 USA

This paper presents a greedy randomized adaptive search procedure (GRASP) coupled with path relinking (PR) to solve the problem of clustering n nodes in a graph into p clusters. The objective is to maximize the sum of the edge weights within each cluster such that the sum of the corresponding node weights does not exceed a fixed capacity. In phase I, both a heaviest weight edge (HWE) algorithm and a constrained minimum cut algorithm are used to select seeds for initializing the p clusters. Feasible solutions are obtained with the help of a self-adjusting restricted candidate list that sequentially guides the assignment of the remaining nodes. At each major GRASP iteration, the list length is randomly set based on a probability density function that is updated dynamically to reflect the solution quality realized in past iterations. In phase II, three neighborhoods, each defined by common edge and node swaps, are explored to attain local optimality. The following exploration strategies are investigated: cyclic neighborhood search, variable neighborhood descent, and randomized variable neighborhood descent (RVND). The best solutions found are stored in an elite pool. In a post-processing step, PR is applied to the pool members to cyclically generate paths between each pair. As new solutions are uncovered, a systematic attempt is made to improve a subset of them with local search. Should a better solution be found, it is saved temporally and placed in the pool after all the pairs are investigated and the bottom member is removed. The procedure ends when no further improvement is possible. Extensive computational testing was done to evaluate the various combinations of construction and local search strategies. For instances with up to 40 nodes and 5 clusters, the reactive GRASP with PR found optimal solutions within a negligible amount of time compared to CPLEX. In general, the HWE algorithm in the construction phase, RVND in the local search phase, and the use of PR pro

关键词： GRASP capacitated clustering problem Path relinking Variable neighborhood search

来源：评论

学校读者我要写书评

暂无评论

The capacitated centred clustering problem

引用

COMPUTERS & OPERATIONS RESEARCH 2006年第6期33卷 1639-1663页

作者： Negreiros, M Palhano, A Univ Estadual Ceara UECE CEFET Mestrado Profiss Computacao BR-60740000 Fortaleza Ceara Brazil COM & REP LTDA GRAPHVS CONS COM BR-60150161 Fortaleza Ceara Brazil

The capacitated centred clustering problem (CCCP) consists of defining a set of clusters with limited capacity and maximum proper similarity per cluster. Each cluster is composed of individuals from whom we can compute a centre value and hence, determine a similarity measure. The clusters must cover the demands of their individuals. This problem can be applied to the design of garbage collection zones, defining salesmen areas, etc. In this work, we present two variations (p-CCCP and Generic CCCP) of this problem and their mathematical programming formulations. We first focus our attention on the Generic CCCP, and then we create a new procedure for p-CCCP. These problems being NP-HARD, we propose a two-phase polynomial heuristic algorithm. The first phase is a constructive phase for which we will propose two variants: the first technique uses known cluster procedures oriented by a log-polynomial geometric tree search, the other one uses unconstrained to constrained clustering. The second phase is a refinement of the variable neighbourhood search (VNS). We also show the results we have obtained for tests from the CCP literature, the design of garbage collection zones, and salesmen areas distribution using the approach implemented for the SISROT (R) system. (c) 2004 Elsevier Ltd. All rights reserved.

关键词： clustering capacitated clustering problem VNS metaheuristic

来源：评论

学校读者我要写书评

暂无评论

An effective VNS for the capacitated p-median problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第3期191卷 612-622页

作者： Fleszar, K. Hindi, K. S. Amer Univ Beirut Fac Engn & Architecture Beirut 11072020 Lebanon Amer Univ Beirut Sch Business Beirut 11072020 Lebanon

In the capacitated p-median problem (CPMP), a set of n customers is to be partitioned into p disjoint clusters, such that the total dissimilarity within each cluster is minimized subject to constraints on maximum cluster capacity. Dissimilarity of a cluster is the sum of the dissimilarities between each customer who belongs to the cluster and the median associated with the cluster. An effective variable neighbourhood search heuristic for this problem is proposed. The heuristic is characterized by the use of easily computed lower bounds to assess whether undertaking computationally expensive calculation of the worth of moves, within the neighbourhood search, is necessary. The small proportion of moves that need to be assessed fully are then evaluated by an exact solution of a relatively small subproblem. Computational results on five standard sets of benchmark problem instances show that the heuristic finds all the best-known solutions. For one instance, the previously best-known solution is improved, if only marginally. (C) 2007 Elsevier B.V. All rights reserved.

关键词： variable neighbourhood search capacitated p-median problem capacitated clustering problem hybrid heuristics

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：