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

An ant colony optimization technique for solving min-max Multi-Depot Vehicle Routing Problem

SWARM AND EVOLUTIONARY COMPUTATION 2013年第0期13卷 63-73页

作者： Narasimha, Koushik Venkata Kivelevitch, Elad Sharma, Balaji Kumar, Manish Univ Cincinnati Sch Dynam Syst Cincinnati OH 45221 USA Univ Cincinnati Sch Aerosp Syst Cincinnati OH 45221 USA Univ Toledo Dept Mech Ind & Mfg Engn Toledo OH 43606 USA

The Multi-Depot Vehicle Routing Problem (MDVRP) involves minimizing the total distance traveled by vehicles originating from multiple depots so that the vehicles together visit the specified customer locations (or cities) exactly once. This problem belongs to a class of Nondeterministic Polynomial Hard (NP Hard) problems and has been used in literature as a benchmark for development of optimization schemes. This article deals with a variant of MDVRP, called min-max MDVRP, where the objective is to minimize the tour-length of the vehicle traveling the longest distance in MDVRP. Markedly different from the traditional MDVRP, min-max MDVRP is of specific significance for time-critical applications such as emergency response, where one wants to minimize the time taken to attend any customer. This article presents an extension of an existing ant-colony technique for solving the Single Depot Vehicle Routing Problem (SDVRP) to solve the multiple depots and min-max variants of the problem. First, the article presents the algorithm that solves the min-max version of SDVRP. Then, the article extends the algorithm for min-max MDVRP using an equitable region partitioning approach aimed at assigning customer locations to depots so that MDVRP is reduced to multiple SDVRPs. The proposed method has been implemented in MATLAB for obtaining the solution for the min-max MDVRP with any number of vehicles and customer locations. A comparative study is carried out to evaluate the proposed algorithm's performance with respect to a currently available Linear Programming (LP) based algorithm in literature in terms of the optimality of solution. Based on simulation studies and statistical evaluations, it has been demonstrated that the ant colony optimization technique proposed in this article leads to more optimal results as compared to the existing LP based method. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Multi-Depot Vehicle Routing Problem Ant colony optimization combinatorial optimization problems Min-max objective

来源：评论

学校读者我要写书评

暂无评论

Solving large scale traveling salesman problems by chaotic neurodynamics

引用

NEURAL NETWORKS 2002年第2期15卷 271-283页

作者： Hasegawa, M Ikeguchi, T Aihara, K Independent Adm Inst Commun Res Lab Wireless Commun Div Wireless Networks Integrat Grp Yokosuka Kanagawa 2390847 Japan Saitama Univ Grad Sch Sci & Engn Dept Informat & Numer Sci Saitama 3388570 Japan Saitama Univ Fac Engn Dept Informat & Comp Sci Saitama 3388570 Japan Univ Tokyo Grad Sch Frontier Sci Dept Complex Sci & Engn Bunkyo Ku Tokyo 1138656 Japan JST CREST Kawaguchi Saitama 3320012 Japan

We propose a novel approach for solving large scale traveling salesman problems (TSPs) by chaotic dynamics. First, we realize the tabu search on a neural network, by utilizing the refractory effects as the tabu effects. Then, we extend it to a chaotic neural network version. We propose two types of chaotic searching methods, which are based on two different tabu searches. While the first one requires neurons of the order of n(2) for an n-city TSP, the second one requires only n neurons. Moreover, an automatic parameter tuning method of our chaotic neural network is presented for easy application to various problems. Last, we show that our method with n neurons is applicable to large TSPs such as an 85,900-city problem and exhibits better performance than the conventional stochastic searches and the tabu searches. (C) 2002 Elsevier Science Ltd. All rights reserved.

关键词： chaotic neural networks combinatorial optimization problems traveling salesman problems tabu search

来源：评论

学校读者我要写书评

暂无评论

A rapid learning automata-based approach for generalized minimum spanning tree problem

引用

JOURNAL OF combinatorial optimization 2020年第3期40卷 636-659页

作者： Zojaji, Masoumeh Meybodi, Mohammad Reza Mollakhalili Mirzaie, Kamal Islamic Azad Univ Dept Comp Engn Maybod Branch Maybod Iran

Generalized minimum spanning tree problem, which has several real-world applications like telecommunication network designing, is related to combinatorial optimization problems. This problem belongs to the NP-hard class and is a minimum tree on a clustered graph spanning one node from each cluster. Although exact and metaheuristic algorithms have been applied to solve the problems successfully, obtaining an optimal solution using these approaches and other optimization tools has been a challenge. In this paper, an attempt is made to achieve a sub-optimal solution using a network of learning automata (LA). This algorithm assigns an LA to every cluster so that the number of actions is the same as that of nodes in the corresponding cluster. At each iteration, LAs select one node from their clusters. Then, the weight of the constructed generalized spanning tree is considered as a criterion for rewarding or penalizing the selected actions. The experimental results on a set of 20 benchmarks of TSPLIB demonstrate that the proposed approach is significantly faster than the other mentioned algorithms. The results indicate that the new algorithm is competitive in terms of solution quality.

关键词： Generalized minimum spanning tree Induced subgraph Learning automata combinatorial optimization problems Random search

来源：评论

学校读者我要写书评

暂无评论

Box puzzling problem solver by hysteresis neural networks

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2001年第9期E84A卷 2173-2181页

作者： Nakaguchi, T Isome, S Jin'no, K Tanaka, M Sophia Univ Dept Elect & Elect Engn Tokyo 1028554 Japan

We propose hysteresis neural network solving combinatorial optimization problems, Box Puzzling Problem. Hysteresis neural network searches solutions of the problem with nonlinear dynamics. The output vector becomes stable only when it corresponds with a solution. This system does never become stable without satisfying constraints of the problem. After estimating hardware calculating time, we obtain that numerical calculating time increases extremely comparing with hardware tune as problem's scale increases. However the system has possibility of limit cycle. Though it is very hard to remove limit cycle completely, we propose some methods to remove this phenomenon.

关键词： nonlinear dynamics hysteresis neural networks combinatorial optimization problems constraint satisfaction problems box puzzling problem

来源：评论

学校读者我要写书评

暂无评论

Energy Efficient Memristive Transiently Chaotic Neural Network for combinatorial optimization

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS 2024年第8期71卷 3708-3716页

作者： Bao, Han Ren, Pengyu Xu, Kehong Yang, Ling Zhou, Houji Li, Jiancong Li, Yi Miao, Xiangshui Huazhong Univ Sci & Technol Sch Integrated Circuits Wuhan 430074 Peoples R China Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA Hubei Yangtze Memory Labs Wuhan 430205 Peoples R China

The utilization of memristive analog-digital mixed in-memory computing has significantly tackled the issues of massive computing resources and time delays in solving combinatorial optimization problems. However, further improvements in computing energy efficiency are still desirable for resource-constrained conditions and practical applications. Therefore, in this work, a memristive analog transiently chaotic neural network (TCNN) system is proposed to solve the traveling salesman problems (TSPs), which is consisted of 1) a memristor array to perform matrix-vector multiplication for the network iteration;2) neuronal modules and nonlinear activation function modules to emulate the basic functions of the network;3) chaotic simulated annealing (CSA) modules to improve the solution performance at extremely low hardware overhead. Based on these, after mapping the TSPs onto the memristor array, the proposed TCNN can self-iterate to convergence states to solve the problems with high performance. Compared to prior analog-digital mixed ones, the analog system can eliminate the extra control and data conversions during the network solving process, and achieve an 8 x reduction in the total energy consumption in consecutive solving tasks.

关键词： Memristors Analog-digital conversion Hardware Neurons Circuits Urban areas Simulated annealing Computing in-memory memristor analog computing combinatorial optimization problems transiently chaotic neural network

来源：评论

学校读者我要写书评

暂无评论

An improved ant colony optimization and its application to vehicle routing problem with time windows

引用

NEUROCOMPUTING 2012年 98卷 101-107页

作者： Ding, Qiulei Hu, Xiangpei Sun, Lijun Wang, Yunzeng Dongbei Univ Finance & Econ Sch Business Adm Dalian 116025 Peoples R China Dalian Univ Technol Inst Syst Engn Dalian 116023 Peoples R China Univ Calif Riverside A Gary Anderson Grad Sch Management Riverside CA 92521 USA

The ant colony optimization (ACO), inspired from the foraging behavior of ant species, is a swarm intelligence algorithm for solving hard combinatorial optimization problems. The algorithm, however, has the weaknesses of premature convergence and low search speed, which greatly hinder its application. To improve the performance of the algorithm, a hybrid ant colony optimization (HACO) is presented in this paper. By adjusting pheromone approach and introducing a disaster operator, the HACO prevents the search process from getting trapped in the local optimal solution. Then, by taking the candidate list into consideration and combining the ACO with the saving algorithm and A-interchange mechanism, the HACO improves the convergence speed. Furthermore, this paper gives a guideline on how to adjust the parameters to achieve the good performance of the algorithm. Finally, the HACO is applied to solve the vehicle routing problem with time windows. The effectiveness of the HACO on solving combinatorial optimization problems is validated by comparing the computational results with those previously presented in the literature. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Ant colony optimization Vehicle routing problem with time windows combinatorial optimization problems

来源：评论

学校读者我要写书评

暂无评论

A new efficient encoding mode of genetic algorithms for the generalized plant allocation problem

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2004年第5期20卷 1019-1034页

作者： Hou, YC Chang, YH Natl Cent Univ Dept Informat Management Chungli 320 Taiwan

This study proposes a novel, efficient means of encoding genetic algorithms to solve the generalized plant allocation problem. The problem relates to allocating products across plants to minimize a total cost function. The proposed encoding method can reduce the search space of solutions more efficiently than the penalty encoding method does. The new encoding method thus exhibits higher performance. It need involve only a few more generations to yield sufficiently good solutions when the number of plants is increased. The penalty encoding method, however, requires many more generations to yield the same solutions. Additionally, a new simultaneous crossover and mutation operation is proposed to enable the new method of encoding chromosomes to run correctly following standard genetic algorithm procedures. In addition to the mathematical certification, the performance of this approach is evaluated using some test problems of various sizes. Solutions obtained by this approach are always efficient.

关键词： genetic algorithms efficient encoding scheme plant allocation combinatorial optimization problems penalty encoding

来源：评论

学校读者我要写书评

暂无评论

SELF-EVOLVING ANT COLONY optimization AND ITS APPLICATION TO TRAVELING SALESMAN PROBLEM

引用

INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL 2012年第12期8卷 8311-8321页

作者： Zhou, Xiao-Fan Wang, Rong-Long Univ Fukui Grad Sch Engn Fukui 9108507 Japan

Ant colony optimization (ACO) algorithms are a recently developed, population-based approach which has been successfully applied to combinatorial optimization problems. However, in the ACO algorithms, it is difficult to adjust the balance between intensification and diversification and thus the performance is not always very well. In this paper we proposed an improved ACO algorithm in which a self-evolving strategy is adopted so as to acquire a trade-off between intensification and diversification. With this strategy we make each ant evolve by means of multiple pheromone deposition, the total concentration of which includes two parts, that is, one part is deposited by several best ants of the last iteration and the ant that has searched the global-best solution by the current iteration, and the other part is deposited temporarily by each ant itself of the last iteration as well. The proposed algorithm is tested by simulating Traveling Salesman Problem (TSP) and experimental results show that Self-evolving Ant Colony optimization has superior performance when compared with other existing ACO algorithms.

关键词： Ant colony optimization combinatorial optimization problems Traveling salesman problem Self-evolving strategy

来源：评论

学校读者我要写书评

暂无评论

Deep Reinforcement Learning for UAV Routing in the Presence of Multiple Charging Stations

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2023年第5期72卷 5732-5746页

作者： Fan, Mingfeng Wu, Yaoxin Liao, Tianjun Cao, Zhiguang Guo, Hongliang Sartoretti, Guillaume Wu, Guohua Cent South Univ Sch Traff & Transportat Engn Changsha 410017 Hunan Peoples R China Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore Acad Mil Sci Beijing Beijing 100091 Peoples R China ASTAR Inst Infocomm Res I2R Singapore Singapore Natl Univ Singapore Dept Mech Engn Singapore 119077 Singapore

Deploying Unmanned Aerial Vehicles (UAVs) for traffic monitoring has been a hotspot given their flexibility and broader view. However, a UAV is usually constrained by battery capacity due to limited payload. On the other hand, the development of wireless charging technology has allowed UAVs to replenish energy from charging *** this paper, we study a UAV routing problem in the presence of multiple charging stations (URPMCS) with the objective of minimizing the total distance traveled by the UAV during traffic monitoring. We present a deep reinforcement learning based method, where a multi-head heterogeneous attention mechanism is designed to facilitate learning a policy that automatically and sequentially constructs the route, while taking the energy consumption into account. In our method, two types of attentions are leveraged to learn the relations between monitoring targets and charging station nodes, adopting an encoder-decoder-like policy network. Moreover, we also employ a curriculum learning strategy to enhance generalization to different numbers of charging stations. Computational results show that our method outperforms conventional algorithms with higher solution quality (except for exact methods such as Gurobi) and shorter runtime in general, and also exhibits strong generalized performance on problem instances with different distributions and sizes.

关键词： Routing Monitoring Charging stations Autonomous aerial vehicles Reinforcement learning Vehicle routing Mathematical programming combinatorial optimization problems deep reinforcement learning heuristics UAV routing

来源：评论

学校读者我要写书评

暂无评论

A multi-start iterated greedy algorithm for the minimum weight vertex cover P3 problem

引用

APPLIED MATHEMATICS AND COMPUTATION 2019年 349卷 359-366页

作者： Zhang, Wenjie Tu, Jianhua Wu, Lidong Beijing Univ Chem Technol Dept Math Beijing 100029 Peoples R China Univ Texas Tyler Dept Comp Sci Tyler TX 75799 USA

Given a vertex-weighted graph G = (V, E) and a positive integer k >= 2, the minimum weight vertex cover P-k (MWVCPk) problem is to find a vertex subset F subset of V with minimum total weight such that every path of order k in G contains at least one vertex in F. For any integer k >= 2, the MWVCPk problem for general graphs is NP-hard. In this paper, we restrict our attention to the MWVCP3 problem and present a multi-start iterated greedy algorithm to solve the MWVCP3 problem. The experiments are carried out on randomly generated instances with up to 1000 vertices and 250000 edges. Our work is the first one to adopt heuristic algorithms to solve the MWVCP3 problem, and the experimental results show that our algorithm performs reasonably well in practice. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Iterated greedy algorithm Minimum weight vertex cover P-3 problem Heuristic algorithms combinatorial optimization problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：