Search results for "Algorithm"

showing 10 items of 4887 documents

A branch-and-cut algorithm for the Orienteering Arc Routing Problem

2016

[EN] In arc routing problems, customers are located on arcs, and routes of minimum cost have to be identified. In the Orienteering Arc Routing Problem (OARP),in addition to a set of regular customers that have to be serviced, a set of potential customers is available. From this latter set, customers have to be chosen on the basis of an associated profit. The objective is to find a route servicing the customers which maximize the total profit collected while satisfying a given time limit on the route.In this paper, we describe large families of facet-inducing inequalities for the OARP and present a branch-and-cut algorithm for its solution. The exact algorithm embeds a procedure which builds…

Mathematical optimization021103 operations researchGeneral Computer Science0211 other engineering and technologiesOrienteering02 engineering and technologyManagement Science and Operations ResearchTime limitRouting problems with profitsPolyhedronExact algorithmOrienteering Arc Routing ProblemBranch-and-cutModeling and Simulation0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingDestination-Sequenced Distance Vector routingMATEMATICA APLICADAInteger programmingArc routingAlgorithmBranch and cutMathematicsComputers & Operations Research
researchProduct

Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems

2018

Abstract For the exact solution of many types of vehicle-routing problems, column-generation based algorithms have become predominant. The column-generation subproblems are then variants of the shortest-path problem with resource constraints which can be solved well with dynamic-programming labeling algorithms. For vehicle-routing problems with a pickup-and-delivery structure, the strongest known dominance between two labels requires the delivery triangle inequality (DTI) for reduced costs to hold. When the direction of labeling is altered from forward labeling to backward labeling, the DTI requirement becomes the pickup triangle inequality (PTI). DTI and PTI cannot be guaranteed at the sam…

Mathematical optimization021103 operations researchInformation Systems and ManagementGeneral Computer ScienceTriangle inequalityComputation0211 other engineering and technologiesStructure (category theory)02 engineering and technologyManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringAccelerationModeling and Simulation0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingPickupPoint (geometry)Column generationRouting (electronic design automation)AlgorithmMathematicsEuropean Journal of Operational Research
researchProduct

Advanced Greedy Randomized Adaptive Search Procedure for the Obnoxious p-Median problem

2016

Abstract The Obnoxious p-Median problem consists in selecting a subset of p facilities from a given set of possible locations, in such a way that the sum of the distances between each customer and its nearest facility is maximized. The problem is NP -hard and can be formulated as an integer linear program. It was introduced in the 1990s, and a branch and cut method coupled with a tabu search has been recently proposed. In this paper, we propose a heuristic method – based on the Greedy Randomized Adaptive Search Procedure, GRASP, methodology – for finding approximate solutions to this optimization problem. In particular, we consider an advanced GRASP design in which a filtering mechanism avo…

Mathematical optimization021103 operations researchInformation Systems and ManagementOptimization problemGeneral Computer ScienceHeuristic (computer science)business.industryGRASP0211 other engineering and technologies02 engineering and technologyManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringTabu searchModeling and Simulation0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingLocal search (optimization)businessBranch and cutAlgorithmMetaheuristicGreedy randomized adaptive search procedureMathematicsEuropean Journal of Operational Research
researchProduct

Multi-objective memetic optimization for the bi-objective obnoxious p -median problem

2018

Abstract Location problems have been studied extensively in the optimization literature, the p-median being probably one of the most tackled models. The obnoxious p-median is an interesting variant that appears in the context of hazardous location. The aim of this paper is to formally introduce a bi-objective optimization model for this problem, in which a solution consists of a set of p locations, and two conflicting objectives arise. On the one hand, the sum of the minimum distance between each client and their nearest open facility and, on the other hand, the dispersion among facilities. Both objective values should be kept as large as possible for a convenient location of dangerous faci…

Mathematical optimization021103 operations researchInformation Systems and Managementbusiness.industryComputer scienceCrossoverFeasible region0211 other engineering and technologiesContext (language use)02 engineering and technologySpace (commercial competition)Management Information SystemsSet (abstract data type)Artificial IntelligenceMutation (genetic algorithm)0202 electrical engineering electronic engineering information engineeringMemetic algorithm020201 artificial intelligence & image processingLocal search (optimization)businessSoftwareKnowledge-Based Systems
researchProduct

A biased random-key genetic algorithm for the time-invariant berth allocation and quay crane assignment problem

2017

We address Berth Allocation and Quay Crane Assignment Problems in a heuristic wayWe propose a Biased Random-Key Genetic Algorithm for BACAP and its extension BACASPSolutions of the Genetic Algorithm are improved by a Local SearchThe complete procedure obtains high-quality solutions for large instances Maritime transportation plays a crucial role in the international economy. Port container terminals around the world compete to attract more traffic and are forced to offer better quality of service. This entails reducing operating costs and vessel service times. In doing so, one of the most important problems they face is the Berth Allocation and quay Crane Assignment Problem (BACAP). This pr…

Mathematical optimization021103 operations researchOperations researchHeuristic (computer science)Computer scienceHeuristicbusiness.industry0211 other engineering and technologiesGeneral Engineering02 engineering and technologyComputer Science ApplicationsArtificial IntelligenceContainer (abstract data type)Genetic algorithm0202 electrical engineering electronic engineering information engineeringKey (cryptography)020201 artificial intelligence & image processingLocal search (optimization)businessAssignment problemMetaheuristicLocal search (constraint satisfaction)Expert Systems with Applications
researchProduct

Heuristics for the Bi-Objective Diversity Problem

2018

Abstract The Max-Sum diversity and the Max-Min diversity are two well-known optimization models to capture the notion of selecting a subset of diverse points from a given set. The resolution of their associated optimization problems provides solutions of different structures, in both cases with desirable characteristics. They have been extensively studied and we can find many metaheuristic methodologies, such as Greedy Randomized Adaptive Search Procedure, Tabu Search, Iterated Greedy, Variable Neighborhood Search, and Genetic algorithms applied to them to obtain high quality solutions. In this paper we solve the bi-objective problem in which both models are simultaneously optimized. No pre…

Mathematical optimization021103 operations researchOptimization problemComputer science0211 other engineering and technologiesGeneral Engineering02 engineering and technologyResolution (logic)Tabu searchComputer Science ApplicationsSet (abstract data type)Artificial IntelligenceGenetic algorithm0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingHeuristicsMetaheuristicVariable neighborhood searchGreedy randomized adaptive search procedureExpert Systems with Applications
researchProduct

Evolutionary multi-objective optimization algorithms for fuzzy portfolio selection

2016

Graphical abstractDisplay Omitted HighlightsWe consider a constrained three-objective optimization portfolio selection problem.We solve the problem by means of evolutionary multi-objective optimization.New mutation, crossover and reparation operators are designed for this problem.They are tested in several algorithms for a data set from the Spanish stock market.Results for two performance metrics reveal the effectiveness of the new operators. In this paper, we consider a recently proposed model for portfolio selection, called Mean-Downside Risk-Skewness (MDRS) model. This modelling approach takes into account both the multidimensional nature of the portfolio selection problem and the requir…

Mathematical optimization021103 operations researchOptimization problemCrossover0211 other engineering and technologiesEvolutionary algorithm02 engineering and technologyFuzzy logicMulti-objective optimization0202 electrical engineering electronic engineering information engineeringExpected returnPortfolio020201 artificial intelligence & image processingAlgorithmSoftwarePossibility theoryMathematicsApplied Soft Computing
researchProduct

A Simple Indicator Based Evolutionary Algorithm for Set-Based Minmax Robustness

2018

For multiobjective optimization problems with uncertain parameters in the objective functions, different variants of minmax robustness concepts have been defined in the literature. The idea of minmax robustness is to optimize in the worst case such that the solutions have the best objective function values even when the worst case happens. However, the computation of the minmax robust Pareto optimal solutions remains challenging. This paper proposes a simple indicator based evolutionary algorithm for robustness (SIBEA-R) to address this challenge by computing a set of non-dominated set-based minmax robust solutions. In SIBEA-R, we consider the set of objective function values in the worst c…

Mathematical optimization021103 operations researchSIBEA uncertaintyComputer sciencepareto-tehokkuusComputation0211 other engineering and technologiesEvolutionary algorithm02 engineering and technologyMinimaxmonitavoiteoptimointihypervolumeminmax robustRobustness (computer science)set-based dominancealgoritmit0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingPareto optimal solutions
researchProduct

District metered area design through multicriteria and multiobjective optimization

2022

[EN] The design of district metered areas (DMA) in potable water supply systems is of paramount importance for water utilities to properly manage their systems. Concomitant to their main objective, namely, to deliver quality water to consumers, the benefits include leakage reduction and prompt reaction in cases of natural or malicious contamination events. Given the structure of a water distribution network (WDN), graph theory is the basis for DMA design, and clustering algorithms can be applied to perform the partitioning. However, such sectorization entails a number of network modifications (installing cut-off valves and metering and control devices) involving costs and operation changes,…

Mathematical optimization06.- Garantizar la disponibilidad y la gestión sostenible del agua y el saneamiento para todosGeneral Mathematicsgraph theoryGeneral Engineeringk-means clusteringk-means algorithmTOPSISGraph theorymetaheuristicfuzzy AHPdistrict metered areasMulti-objective optimizationwater distribution systemsmultiobjective optimizationMATEMATICA APLICADATOPSISMetaheuristicDecision makingFuzzy ahpMathematics
researchProduct

A fast heuristic for solving the D1EC coloring problem

2010

In this paper we propose an efficient heuristic for solving the Distance-1 Edge Coloring problem (D1EC) for the on-the-fly assignment of orthogonal wireless channels in wireless as soon as a topology change occurs. The coloring algorithm exploits the simulated annealing paradigm, i.e., a generalization of Monte Carlo methods for solving combinatorial problems. We show that the simulated annealing-based coloring converges fast to a sub optimal coloring scheme even for the case of dynamic channel allocation. However, a stateful implementation of the D1EC scheme is needed in order to speed-up the network coloring upon topology changes. In fact, a stateful D1EC reduces the algorithm’s convergen…

Mathematical optimization:QA Mathematics::QA75 Electronic computers. Computer science [Q Science]TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESChannel allocation schemesHeuristic (computer science)Computer scienceSettore ING-INF/03 - Telecomunicazioni:T Technology (General) [T Technology]Topology (electrical circuits)Greedy coloringEdge coloringTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESStateful firewall:Q Science (General) [Q Science]TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYConvergence (routing)Simulated annealing:TK Electrical engineering. Electronics Nuclear engineering [T Technology]Channel assignment Edge coloring Simulated annealing.MathematicsofComputing_DISCRETEMATHEMATICS
researchProduct