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

exact and Metaheuristic algorithms for Variable Reduction

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2024年第6期28卷 1704-1718页

作者： Song, Aijuan Wu, Guohua Zhou, Ling Wang, Ling Pedrycz, Witold Cent South Univ Sch Traff & Transportat Engn Changsha 410075 Peoples R China Tsinghua Univ Dept Automat Beijing 100084 Peoples R China Univ Alberta Dept Elect & Comp Engn Edmonton AB T6G 2V4 Canada Polish Acad Sci Syst Res Inst PL-01447 Warsaw Poland

A variable reduction strategy (VRS) drives evolutionary algorithms (EAs) to evolve more effectively by simplifying optimization problems. To represent a decision space with the smallest set of variables via VRS, a variable reduction optimization problem (VROP) has been defined, which could be handled by a heuristic rule-based automatic variable reduction algorithm (HR-AVRA). However, HR-AVRA has limitations in identifying an optimal solution and is susceptible of getting trapped in local optimums. To handle these challenges, we propose to solve VROP with exact and metaheuristic algorithms. We construct a linear programming model of VROP for the first time. Then, Gurobi, an exact algorithm optimizer, is employed to seek and identify an optimal solution for it. Subsequently, we design two representative single-point-based and population-based metaheuristic algorithms, simulated annealing-based (SA-AVRA) and ant colony optimization-based (ACO-AVRA) methods, to solve VROP more effectively. These variable reduction algorithms can group variables of a continuous optimization problem into reduced and core variables, with the latter representing both reduced variables and the entire decision space. Extensive experiments verify that Gurobi can provide optimal solutions for small-scale VROPs, while SA/ACO-AVRA enables more reduced variables than other variable reduction methods. We also integrate various variable reduction algorithms with several competitive EAs to tackle equality-constrained optimization problems and nonlinear equations systems. Experiments show that EAs integrated with a variable reduction algorithm outperform both standard EAs and those with several other complexity reduction methods. Furthermore, integrating a variable reduction algorithm that introduces more reduced variables generally can lead to better performance of EAs.

关键词： Mathematical models Search problems Metaheuristics Standards Simulated annealing Linear programming Diversity reception Continuous optimization problem evolutionary algorithm (EA) exact algorithm metaheuristic algorithm variable reduction optimization problem (VROP)

来源：评论

学校读者我要写书评

暂无评论

Optimization of machine schedules and vehicle routes in the mobile additive manufacturing mode

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2024年

作者： Yuan, Biao Cui, Weiwei Shanghai Jiao Tong Univ Sino US Global Logist Inst Data Driven Management Decis Making Lab Shanghai Peoples R China Shanghai Univ Sch Management Shanghai Peoples R China Shanghai Key Lab Intelligent Mfg & Robot Shanghai Peoples R China

Online shopping giant Amazon proposes to use 3D printers mounted on vehicles to print customer purchases on the fly and deliver them immediately. Because of the overlap between production and transportation processes, such a mobile manufacturing mode offers potential savings in lead times and inventory costs. However, the decisions associated with the two processes are intertwined, making it challenging to achieve satisfactory machine schedules and vehicle routes. To address the situation and fully understand the benefits of the mode, we study a related optimisation problem of finding routes for vehicles and production schedules for 3D printers mounted on them with minimum travel costs. First, we construct a mixed-integer programming model to formulate the problem. Then, we develop an exact algorithm to solve it. Specifically, we propose two propositions about the optimal production schedule of machines in the route and develop a labelling algorithm for the pricing problem. And we devise a problem-specific heuristic labelling algorithm to speed up column generation. We use two sizes of instances with five problem parameter settings (including 290 instances) to validate the effectiveness of the algorithm. In addition, we provide some managerial insights for decision-makers by comparing the novel mode with the traditional manufacturing mode.

关键词： Additive manufacturing mobile manufacturing machine scheduling routing exact algorithm SDG 9: Industry, innovation and infrastructure

来源：评论

学校读者我要写书评

暂无评论

Linear models for total coverage problem with connectivity constraints using multiple unmanned aerial vehicles

引用

INTERNATIONAL JOURNAL OF SENSOR NETWORKS 2020年第1期34卷 15-25页

作者： Lamine, Amani Mguis, Fethi Snoussi, Hichem Ghedira, Khaled Manouba Univ SSOIE COSMOS Lab Natl Sch Comp Sci La Manouba 2010 Tunisia Jouf Univ Comp Sci Dept Sakakah 75471 Saudi Arabia Gabes Univ Fac Sci Gabes 6072 Tunisia SSOIE COSMOS Lab La Manouba 2010 Tunisia Univ Technol Troyes Inst Charles Delaunay CNRS LM2SUMR 6279STMR F-10004 Troyes France Honoris United Univ SSOIE COSMOS Lab La Manouba 1002 Tunisia

The use of unmanned aerial vehicles (UAVs) has recently increased both in civilian and military operations, and the planning of their routes is critical. This research investigates a routing problem in which a UAV network, equipped with sensors, covers a given area and maintains connectivity with its neighbouring UAVs and the base station, while respecting to the UAVs lifetime. To cover the area, two integer linear programming models are formulated to solve two problems optimally. In the first one, covering means that all positions should be visited. However, in the second one, covering means that every position should be covered at least by one UAV. Due to the limited communication radius of the UAVs, connectivity then has to find inter-UAVs routing paths to satisfy the communication between UAVs and the base. We verify by experiments that the models, using Cplex, can provide an optimal solution of different area dimensions.

关键词： UAV unmanned aerial vehicle communication area coverage UAV route planning integer linear model exact algorithm

来源：评论

学校读者我要写书评

暂无评论

A Satisfiability algorithm for Some Class of Dense Depth Two Threshold Circuits

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2015年第1期E98D卷 108-118页

作者： Amano, Kazuyuki Saito, Atsushi Gunma Univ Dept Comp Sci Kiryu Gunma 3768515 Japan

Recently, Impagliazzo et al. constructed a nontrivial algorithm for the satisfiability problem for sparse threshold circuits of depth two which is a class of circuits with cn wires. We construct a nontrivial algorithm for a larger class of circuits. Two gates in the bottom level of depth two threshold circuits are dependent, if the output of the one is always greater than or equal to the output of the other one. We give a nontrivial circuit satisfiability algorithm for a class of circuits which may not be sparse in gates with dependency. One of our motivations is to consider the relationship between the various circuit classes and the complexity of the corresponding circuit satisfiability problem of these classes. Another background is proving strong lower bounds for TC0 circuits, exploiting the connection which is initiated by Ryan Williams between circuit satisfiability algorithms and lower bounds.

关键词： satisfiability exact algorithm threshold circuit

来源：评论

学校读者我要写书评

暂无评论

Clustered coverage orienteering problem of unmanned surface vehicles for water sampling

引用

NAVAL RESEARCH LOGISTICS 2020年第5期67卷 353-367页

作者： Zhang, Wei Wang, Kai Wang, Shuaian Laporte, Gilbert Hong Kong Polytech Univ Dept Logist & Maritime Studies Hong Kong Peoples R China MIT Sloan Sch Management 77 Massachusetts Ave Cambridge MA 02139 USA HEC Montreal Dept Decis Sci Montreal PQ Canada

This study investigates a clustered coverage orienteering problem (CCOP), which is a generalization of the classical orienteering problem. The problem is widely motivated by the emerging unmanned techniques (eg, unmanned surface vehicles and drones) applied to environmental monitoring. Specifically, the unmanned surface vehicles (USVs) are used to monitor reservoir water quality by collecting samples. In the CCOP, the water sampling sites (ie, the nodes) are grouped into clusters, and a minimum number of nodes must be visited in each cluster. With each node representing a certain coverage area of the water, the objective of the CCOP is to monitor as much as possible the total coverage area in one tour of the USV, considering that overlapping areas provide no additional information. An integer programming model is first formulated through a linearization procedure that captures the overlapping feature. A two-stage exact algorithm is proposed to obtain an optimal solution to the problem. The efficiency and effectiveness of the two-stage exact algorithm are demonstrated through experiments on randomly generated instances. The algorithm can effectively solve instances with up to 60 sampling sites.

关键词： clustered coverage orienteering problem exact algorithm unmanned surface vehicle water sampling

来源：评论

学校读者我要写书评

暂无评论

Heterogeneous vehicle pickup and delivery problems: Formulation and exact solution

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2019年第May期125卷 181-202页

作者： Sun, Wei Yu, Yang Wang, Junwei Liaoning Univ Sch Business Shenyang 110316 Liaoning Peoples R China Northeastern Univ State Key Lab Synthet Automat Proc Ind Dept Intelligent Syst Engn Shenyang 110819 Liaoning Peoples R China Univ Hong Kong Dept Ind & Mfg Syst Engn Pokfulam Rd Hong Kong Peoples R China

The heterogeneous green pickup and delivery problem (GPDP) aims to minimize carbon emissions of pickups and deliveries by a fleet of heterogeneous vehicles. We propose the first exact algorithm for solving the heterogeneous GPDP. This exact algorithm is based on a set partitioning model and the key characteristics of its optimal solution. We prove that the optimal solution is composed of the optimal trips of heterogeneous vehicles;thus, the solution space is significantly reduced by cutting the non-optimal trips. The proposed exact algorithm can rapidly find the optimal solution of the largest-scale instance from Li & Lim benchmarks and three types of vehicles. The exact algorithm is also validated by solving a practical case of heterogeneous GPDP in China. Based on the extensive experiments, we conclude an interesting managerial insight that heterogeneous vehicles can always effectively reduce carbon emissions except for two situations.

关键词： Carbon emissions Green pickup and delivery problem Heterogeneous vehicles exact algorithm

来源：评论

学校读者我要写书评

暂无评论

exact Monte Carlo simulation of killed diffusions

引用

ADVANCES IN APPLIED PROBABILITY 2008年第1期40卷 273-291页

作者： Casella, Bruno Roberts, Gareth O. Univ Warwick Dept Stat Coventry CV4 7AL W Midlands England

We describe and implement a novel methodology for Monte Carlo simulation of one-dimensional killed diffusions. The proposed estimators represent an unbiased and efficient alternative to current Monte Carlo estimators based on discretization methods for the cases when the finite-dimensional distributions of the process are unknown. For barrier option pricing in finance, we design a suitable Monte Carlo algorithm both for the single barrier case and the double barrier case. Results from numerical investigations are in excellent agreement with the theoretical predictions.

关键词： Monte Carlo diffusions exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms for the Steiner problem in networks

引用

DISCRETE APPLIED MATHEMATICS 2001年第1-3期112卷 263-300页

作者： Polzin, T Daneshmand, SV Univ Mannheim D-68131 Mannheim Germany

We present several new techniques for dealing with the Steiner problem in (undirected) networks. We consider them as building blocks of an exact algorithm, but each of them could also be of interest in its own right. First, we consider some relaxations of integer programming formulations of this problem and investigate different methods for dealing with these relaxations, not only to obtain lower bounds, but also to get additional information which is used in the computation of upper bounds and in reduction techniques. Then, we modify some known reduction tests and introduce some new ones. We integrate some of these tests into a package with a small worst-case time which achieves impressive reductions on a wide range of instances. On the side of upper bounds, we introduce the new concept of heuristic reductions. On the basis of this concept, we develop heuristics that achieve sharper upper bounds than the strongest known heuristics for this problem despite running times which are smaller by orders of magnitude. Finally, we integrate these blocks into an exact algorithm. We present computational results on a variety of benchmark instances, The results are clearly superior to those of all other exact algorithms known to the authors. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： Steiner problem reduction tests lower bounds heuristics exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An Inventory-Routing Problem with Pickups and Deliveries Arising in the Replenishment of Automated Teller Machines

引用

TRANSPORTATION SCIENCE 2016年第3期50卷 1077-1091页

作者： van Anholt, Roel G. Coelho, Leandro C. Laporte, Gilbert Vis, Iris F. A. Vrije Univ Amsterdam Fac Econ & Business Adm NL-1081 HV Amsterdam Netherlands Univ Laval CIRRELT Quebec City PQ G1V 0A6 Canada Univ Laval Fac Sci Adm Quebec City PQ G1V 0A6 Canada HEC Montreal CIRRELT Montreal PQ H3T 2A7 Canada HEC Montreal Canada Res Chair Distribut Management Montreal PQ H3T 2A7 Canada Univ Groningen Fac Econ & Business NL-9747 AE Groningen Netherlands

The purpose of this paper is to introduce, model, and solve a rich multiperiod inventory-routing problem with pickups and deliveries motivated by the replenishment of automated teller machines in the Netherlands. Commodities can be brought to and from the depot, as well as being exchanged among customers to efficiently manage their inventory shortages and surpluses. A single customer can both provide and receive commodities at different periods, since its demand changes dynamically throughout the planning horizon and can be either positive or negative. In the case study, new technology provides these machines with the additional functionality of receiving deposits and reissuing banknotes to subsequent customers. We first formulate the problem as a very large-scale mixed-integer linear programming model. Given the size and complexity of the problem, we first decompose it into several more manageable subproblems by means of a clustering procedure, and we further simplify the subproblems by fixing some variables. The resulting subproblems are strengthened through the generation of valid inequalities and solved by branch and cut. We assess the performance of the proposed solution methodology through extensive computational experiments using real data. The results show that we are able to obtain good lower and upper bounds for this new and challenging practical problem.

关键词： inventory-routing vehicle routing inventory management pickup and delivery branch and cut clustering exact algorithm recirculation automated teller machines

来源：评论

学校读者我要写书评

暂无评论

An efficient parameterized algorithm for m-set packing

引用

JOURNAL OF algorithmS-COGNITION INFORMATICS AND LOGIC 2004年第1期50卷 106-117页

作者： Jia, WJ Zhang, CL Chen, J City Univ Hong Kong Dept Comp Engn & IT Hong Kong Hong Kong Peoples R China Jinan Univ Dept Math Guangzhou 510632 Peoples R China Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

We present an efficient parameterized algorithm solving the Set Packing problem, in which we assume that the size of the sets is bounded by m. In particular, if the size m of the sets is bounded by a constant, then our algorithm is fixed-parameter tractable. For example, if the size of the sets is bounded by 3, then our algorithm runs in time O((5.7k)(k)n). (C) 2003 Elsevier Inc. All rights reserved.

关键词： parameterized computation set packing exact algorithm NP-hard problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：