Search

Encouraged by the success of applying metaheuristics algorithms to other ranking-based problems (Kemeny ranking problem and parameter estimation for Mallows distributions), in this paper we deal with the rank aggregation problem (RAP), which can be viewed as a generalization of the Kemeny problem to arbitrary rankings. While in the Kemeny problem the input is a set of permutations, the RAP consists in obtaining the consensus permutation for a sample of arbitrary rankings. This is an NP-hard problem which can be approached by using greedy heuristic algorithms (e.g. Borda). Such algorithms are fast but the solutions so obtained are far to be optimal. In this paper, we propose the use of more complex search processes to deal with the RAP. In particular, we perform a comparative study among some local-based search metaheuristics: hill climbing (HC), iterated local search (ILS), variable neighborhood search (VNS) and greedy randomized adaptive search procedure (GRASP). We provide a complete analysis of the experimental study regarding accuracy and number of iterations required to reach the best solution. From the results we can conclude that the selection of a suitable neighborhood plays a key role, and that depending on the available resources (cpu time) a different algorithm (VNS, ILS or GRASP) could be the proper choice.

The single-row facility layout problem (SRFLP) is an NP-hard problem, which consists of arranging facilities along a straight line in order to minimize the weighted sum of distances between all pairs of facilities. In this paper, an implementation of the Greedy Randomized Adaptive Search Procedure (GRASP) meta-heuristic is presented to solve large-scale instances of the problem. The novelty of the proposed implementation is that it is endowed with a diversification phase based on frequency memory. The algorithm was tested on 93 instances with sizes up to one thousand facilities. To date, in the literature, there is only one work, which has considered instances of such magnitude. Computational experiments demonstrate the efficiency of the proposed algorithm, which improved the best-known values for 29 out of 93 instances.

Cloud computing has emerged as a new paradigm for hosting and supplying services over the Internet. This technology has brought many benefits, such as eliminating the need for maintaining expensive computing hardware. With an increasing demand for cloud computing, providing performance guarantees for applications that run over cloud become important. Applications can be abstracted into a set of virtual machines with certain guarantees depicting the quality of service of the application. In this paper, we consider the placement of these virtual machines across multiple data centers (VMPlacement), meeting the quality of service requirements while minimizing the bandwidth cost of the data centers. This problem is a generalization of the NP-hard generalized quadratic assignment problem (GQAP). In this paper, we present a greedy randomized adaptive search procedure and a biased random-key genetic algorithm, both hybridized with a path-relinking strategy and a local search based on variable neighborhood descent for solving this problem. The hybrid heuristics are also tested on instances of the GQAP. We show that both algorithms are effective in quickly solving small and large instances of VMPlacement problem, especially when the path-relinking is used. For GQAP, the results outperform the previous state-of-the-art algorithms.

We consider a hub-and-spoke network design problem with inter-hub economies-of-scale and hub congestion. We explicitly model the economies-of-scale as a concave piece-wise linear function and congestion as a convex function. The problem is modeled as a nonlinear mixed integer program that is difficult to solve directly since the objective function has both convex and concave nonlinear terms and hence finding an optimal solution may not be easy. A Lagrangian approach is proposed to obtain tight upper and lower bounds. The Lagrangian decomposition exploits the structure of the problem and decomposes it to convex and concave subproblems. Furthermore, we add some valid inequalities to accelerate the convergence rate of the Lagrangian heuristic. To tackle large instances, a Greedy Randomized Adaptive Search Procedure (GRASP) is developed. Both the Lagrangian heuristic and GRASP provide high-quality solutions within reasonable computational time. The optimal designs of hub-and-spoke networks with nonlinear inter-hub economies-of-scale and congestion at hub locations are analyzed in comparison with other models in the literature to demonstrate the significant impact of modeling nonlinearity in economies-of-scale and congestion simultaneously rather than independently.

This paper presents two metaheuristic algorithms for the solution of the p-next center problem: a Greedy Randomized Adaptive Search Procedure and a Variable Neighborhood Search algorithm, that will be subsequently hybridized. The p-next center problem is a variation of the p-center problem, which consists of locating p out of n centers and assigning them to users in order to minimize the maximum, over all users, of the distance of each user to its corresponding center plus the distance between this center to its closest alternative center. This problem emerges from the need to reach a secondary help center in the case of a natural disaster, when the closest center may become unavailable.

Due to the constantly increasing mission demands for the space network (SN), the technical issue of high-efficient scheduling has attracted continuous attention in recent years. Most of the previous scheduling algorithms have generally ignored two critical factors, i.e., the dynamic property of single access (SA) antenna's setup times and the time-space distribution characteristics of users’ requested missions. In this paper, we build a mathematical model for the heterogeneous intersatellite link antenna (ILA) pointing route problem with the consideration of constraints on visibility windows and dynamic setup times. Specifically, the ILA's pointing mechanics cost and the missions’ time-space distribution are first taken into account into the scheduling model. Meanwhile, a new two-stage heuristic algorithm with hierarchical scheduling strategies is proposed to solve this optimization model. Finally, we employ the SN dataset to verify our proposed model by comparing three algorithms, the existing greedy randomized adaptive search procedure (GRASP) algorithm with static setup times, our improved GRASP algorithm with dynamic setup times, and our proposed two-stage heuristic algorithm. Experimental results show that our improved GRASP can schedule 3.72%, 10.36%, 12.51% more missions and can consume 53.18%, 49.95%, and 49.32% less setup times of SA antennas than the original Rojanasoonthon's GRASP for the mission scale of 200, 400, and 600, respectively. Moreover, compared with the improved GRASP algorithm, our proposed two-stage heuristic algorithm is more effective, which can further enhance the total number of scheduled missions by 2.41%, 4.43%, and 6.02% and reduce the setup times of SA antennas by 11.84%, 10.38%, and 9.54%.

The largest citrus-producing region in Brazil, concentrated in the states of Sao Paulo and Minas Gerais, is also the largest citrus-producing region in the world. Data from 2016 indicate that for every five glasses of orange juice consumed in the world, three are produced in Brazil. Thus, citriculture stands out in Brazilian agribusiness. Along with the growth of this agricultural sector is the emergence of diseases that affect citrus trees. In this paper, two mathematical models are presented to describe the dynamics and chemical control of citrus diseases. These models involve the theory of optimal control, considering the spatial spread of disease vectors. The first model consists of a system of ordinary differential equations with transport rates. The second model involves the Greedy Randomized Adaptive Search Procedure in control theory, considering the spread of the vectors from a partial differential equation model involving diffusion. The models are approached in a scenario for Huanglongbing disease, also called greening, which is considered to be the most devastating citrus disease in the world because of its characteristics and the damage it causes, and because there is still no cure.

This paper addresses the transportation of valuable goods in which security carriers are interested to optimize the operating costs and the vehicle routes’ security. In real operations, route planning and scheduling are normally performed manually based on individual experience. Hereupon, an optimizing approach should be developed to target the robbery risk reduction and the distribution network’ operational costs. Facing the dangerous nature of operations, some considerations play an important role, including demand fluctuations and traffic congestion of the urban environment. To handle these issues, we respectively benefit from the robust optimization theory and considering time-dependent travel speeds with satisfying the “first-in-first-out” property. This paper proposes a rich vehicle routing problem denoted by the secure time-dependent vehicle routing problem with time windows including pickup and delivery with uncertain demands (S-TD-VRPTWPD-UD). A mathematical formulation and an efficient solution approach combining the greedy randomized adaptive search procedure (GRASP) and the iterated local search (ILS) are developed to minimize the predictability of route plans using an integrated risk index, besides the travel costs. Extensive computational experiments on this problem are performed to analyze the impact of the demand uncertainty and the speed time-dependency and to show the efficiency of the GRASP × ILS implementation. The results show the significant improvements due to the time-dependency as well as the extra cost of protecting the model against the worst-case scenario of demand requests by deriving the robust counterpart of the S-TD-VRPTWPD-UD.

The Multi-Depot Electric Vehicle Location Routing Problem with Time Windows and Battery Swapping (MDEVLRPTW-BS) aims to mitigate the environmental impacts caused by the use of vehicles with an internal combustion engine and uses economically viable electric vehicles in transportation services with time window restrictions. This problem is complex as one must define (i) the location of the battery swapping stations, (ii) the depots to be used from a list of candidates, and (iii) the assignment and routing of a fleet of electric vehicles. We propose here two constructive methods to solve MDEVLRPTW-BS, namely, Cheapest Insertion and Disruption of Routes. These constructive approaches are used with the Greedy Randomized Adaptive Search Procedure (GRASP) and the Random Variable Neighborhood Descent (RVND) method with six movement operators. Two of these operators, namely Isolate and ChangeBSS, are also proposed here for solving MDEVLRPTW-BS. The proposals are compared with a technique from the literature using instances with 5, 10, and 15 customers, and the proposed approaches presented good results, mainly regarding the processing time. Also, we propose new sets of instances larger than those from the literature. Thus, the search techniques can be analyzed when subjected to greater and more realistic situations. These new instances are composed of 100, 144, 288, 360, 420, and 600 customers. For these cases, the approaches also obtained good and promising results, mainly when the Disruption of Routes approach (GRASP-DR-RVND) is used.

Problems encountered in fields like scheduling, assignment, vehicle routing are mostly NPhard. These problems need efficient solution procedures. If confronted with an NP-hard problem, one may have three ways to go: one chooses to apply an enumerative method that yields an optimum solution, or apply an approximation algorithm that runs in polynomial time, or one resorts to some type of heuristic technique without any a priori guarantee for quality of solution and time of computing (Aarts & Lenstra, 2003). Heuristics fall under the general heading of local search approaches. Hence, local search techniques are widely used to find “close-to-optimum” solutions to these problems in a “reasonable” amount of time. Tabu search (TS) is one of the most efficient heuristic techniques in the sense that it finds quality solutions in relatively short running time. This chapter will provide a basic description of TS giving insights for novice readers as well as introduce application areas and provide comparisons of TS to other meta-heuristic procedures for the readers with more experience on local search procedures. The chapter will be organized as follows: The second section is going to introduce the basic terminology. For example, definitions for global optimization, local search, heuristics, and meta-heuristics will be provided. The section will also provide brief descriptions of TS as well as the following meta-heuristics to which TS will be compared: simulated annealing (SA), genetic algorithms (GA), ant colony optimization (ACO), greedy randomized adaptive search procedure (GRASP), and particle swarm optimization (PSO). Second section is intended to give the readers a good overall view of the “local search” area and let them know that TS will be compared to several other meta-heuristic procedures. In the third section, basic steps of TS, SA, GA, ACO, GRASP and PSO will be described. As the mechanisms of these procedures are explained, differences and similarities between TS and each of the other procedures will be pointed out. Section three will familiarize the readers with the various meta-heuristic procedures that will be discussed throughout the chapter. The fourth section will be dedicated to identifying the different problems for which TS was used to generate solutions. For example; TS has been used to solve scheduling problems, routing problems, and assignment problems. We will try to generate a comprehensive list of the problems to which TS has been applied. This section will provide the reader with an understanding of how TS has been used. In the fifth section, efficiency and effectiveness of TS will be compared to other metaheuristic procedures. Reasons why TS is more efficient and/or effective than some of the O pe n A cc es s D at ab as e w w w .ite ch on lin e. co m

In this article, we have investigated monotone linkage functions defined on convex geometries, antimatroids, and semilattices in general. It has been shown that the class of functions defined as minimum values of monotone linkage functions has close relationship with the class of quasi-concave set functions. Quasi-concave functions defined on semilattices, antimatroids and convex geometries determine special substructures of these set families. This structures allow building efficient algorithms that find minimal sets on which values of quasi-concave functions are maximum. The mutual critical step of these algorithms is how to describe the set closure operator. If an efficient algorithm of the closure construction exists it causes the optimization algorithm to be efficient as well. On the other hand, we think that the closure construction problem is interesting enough to be investigated separately. Thus, we suppose that for an arbitrary semilattice the problem of closure construction has exponential complexity. An interesting direction for future work is to develop our methods for relational databases, where a polynomial algorithm for closure construction is known [3]. We have considered some applications of quasi-concave functions to clustering a structured data set, where together with pair-wise similarities between objects, we are also given additional information about objects organization. We focused on a simple structure - a partition model of data where the objects are a priori partitioned into groups. While clustering such data, we also considered an additional requirement of being able to differentiate between pairwise similarities across different partite sets. Existing clustering methods do not solve this problem, since they are limited to finding clusters in a collection of isolated objects. The requirement of differentially treating pair-wise relationships across different groups was modeled by a multipartite graph along with a hierarchical relationship between these groups. The problem was reduced to finding the cluster (subgraph) of the highest density in the multipartite graph.

Since the creation of operations research as a discipline, a continued interest has been in the development of heuristics or approximation algorithms to solve complex combinatorial optimization problems. As many problems have been proven computationally intractable, the heuristic approaches become increasingly important in solving various large practical problems. The most popular heuristics that have been widely studied in literature include Simulated Annealing (SA) (Kirkpatrick 1983), Tabu Search (TS) (Glover 1986), and Genetic Algorithm (GA) (Holland 1975). Simulated annealing is a stochastic search method that explores the solution space using a hill climbing process. Tabu search, on the other hand, is a deterministic search algorithm that attempts exhaustive exploration of the neighbourhood of a solution. In contrast to the local search algorithms such as SA and TS that work with one feasible solution in each iteration, GA employs a population of solutions and is capable of both local and global search in the solution space. Despite their successes in solving many combinatorial problems, these algorithms have some limitations. For instance, SA can be easily trapped in a local optimum or may require excessive computing time to find a reasonable solution. To successfully implement a tabu search algorithm, one requires a good knowledge about the problem and its solution space to define an efficient neighbourhood structure. Genetic algorithms often converge to a local optimum prematurely and their success often relies on the efficiency of the adopted operators. Due to the deficiencies of the conventional heuristics and ever increasing demand for more efficient search algorithms, researchers are exploring two main options, developing new methods such as nature inspired metaheuristics and investigating hybrid algorithms. In recent years, a number of metaheuristics have been developed. Examples include the Greedy Randomized Adaptive Search Procedure (GRASP) (Feo & Resende, 1995; Aiex et al., 2003), Adaptive Multi Start (Boese et al., 1994), Adaptive Memory Programming (AMP) 9

Low-carbon economy advances the sustainable development of the transportation of hazardous chemicals. This paper focuses on the multi-trip heterogeneous vehicle routing problem that includes the prioritization of customers and transportation of incompatible cargoes (MTHVRP-PCIC) in which some customers are prioritized for delivery by heterogeneous vehicles and more than one type of cargo is transported. This is an issue because some cargoes are incompatible with each other and therefore cannot be loaded into the same vehicle. MFHVRP-PCIC aims to find a set of routes resulting in minimal costs including fixed cost, travel cost and carbon emission cost. This problem occurs in real-life applications in the hazardous chemicals road transportation industry. This paper contributes to addressing the MTHVRP-PCIC from a problem definition, model, and methodological point of view. We establish a mathematical formulation for this problem. A two-stage hybrid metaheuristic approach (TSHM) is also devised to solve this problem. First, an improved greedy randomized adaptive search procedure is designed to generate initial feasible solutions. Then, a hybrid genetic algorithm including local search strategies, split-feasibility procedure, and simulated annealing is designed to solve this problem. Finally, the proposed approach is applied to solve a real case of hazardous chemical delivery and a benchmark dataset, and the resulting solutions indicate the advantage of our algorithm compared with those solutions obtained from managerial experience and classical algorithms.

This work presents a novel greedy randomized adaptive search procedure approach for dealing with the maximum diversity problem from a multi-objective perspective. In particular, five of the most extended diversity metrics were considered, with the aim of maximizing all of them simultaneously. The metrics considered have been proven to be in conflict, i.e., it is not possible to optimize one metric without deteriorating another one. Therefore, this results in a multi-objective optimization problem where a set of efficient solutions that are diverse with respect to all the metrics at the same time must be obtained. A novel adaptation of the well-known greedy randomized adaptive search procedure, which has been traditionally used for single-objective optimization, was proposed. Two new constructive procedures are presented to generate a set of efficient solutions. Then, the improvement phase of the proposed algorithm consists of a new efficient local search procedure based on an exchange neighborhood structure that follows a first improvement approach. An effective exploration of the exchange neighborhood structure is also presented, to firstly explore the most promising ones. This feature allowed the local search proposed to limit the size of the neighborhood explored, resulting in an efficient exploration of the solution space. The computational experiments showed the merit of the proposed algorithm, when comparing the obtained results with the best previous method in the literature. Additionally, new multi-objective evolutionary algorithms derived from the state-of-the-art were also included in the comparison, to prove the quality of the proposal. Furthermore, the differences found were supported by non-parametric statistical tests.

We study a hub location problem with multiple functions based on a real-world regional logistics network. A hub-and-spoke network is designed to serve the demand between origins and destinations. The decision maker is to determine the functions of the candidate hubs, and a function is represented by its connections with different types of nodes, such as warehouse, station and external hub. We present an MIP model that can be solved by mathematical programming solvers for small-scale instances. A construction heuristic and two customized metaheuristics methods are proposed to solve large-scale instances, namely a construction heuristic, a variable neighborhood search and a greedy randomized adaptive search procedure. The computation results show the effectiveness of our methods to solve practical instances.

Multiple Traveling Repairmen Problem (mTRP) is a class of NP-hard combinatorial optimization problems which has many practical applications. In this paper, a general variant of mTRP, also known as Bounded Single-Depot Multiple Traveling Repairmen Problem (Bounded-mTRP) is introduced. In Bounded-mTRP problem, fleet of identical vehicles is dispatched to serve a set of customers. Each vehicle that starts from the depot is only allowed to visit the number of customers within a predetermined interval and each customer must be visited exactly once. Such restrictions appear in real-life applications where the purpose is to have a good balance of workloads for the repairmen. The goal is to find the order of customer visits that minimizes the sum of waiting times. In our work, we propose a metaheuristic algorithm which is mainly based on the principles of Greedy Randomized Adaptive Search Procedure (GRASP) and Variable Neighborhood Search (VNS) to solve the problem. GRASP is used to build an initial solution in a construction phase. In a cooperative way, VNS is employed to generate various neighborhoods in an improvement phase, therefore, it can prevent the search to escape from local optimal. In addition, we also introduce a new novel neighborhoods' structure in VNS for the problem. Extensive numerical experiments on benchmark instances show that our algorithm can reach the optimal solutions for the problems with 50 vertices in a reasonable amount of time. Moreover, the new best known solutions can be found in comparison with the state-of-the-art metaheuristic algorithms.

An innovative trajectory strategy was proposed and accessed for wire arc additive manufacturing (WAAM), applicable to different and more complex geometries, rather than being a single solution. This strategy, named Pixel, can be defined as a complex multitask procedure to carry out optimized path planning, whose operation is made through computational algorithms (heuristics), with accessible computational resources and tolerable computational time. The model layers are fractioned in squared grids, and a set of dots is systematically generated and distributed inside the sliced outlines, resembling pixels on a screen, over which the trajectory is planned. The Pixel strategy was based on creating trajectories from the technique travelling salesman problem (TSP). Unlike existing algorithms, the Pixel strategy uses an adapted greedy randomized adaptive search procedure (GRASP) metaheuristic, aided by four concurrent trajectory planning heuristics, developed by the authors. Interactions provide successive trajectories from randomized initial solutions (global search) and subsequent iterative improvements (local search). After all recurrent loops, a trajectory is defined and written in machine code. Computational evaluation was implemented to demonstrate the effectof each of the heuristics on the final trajectory. An experimental evaluation was eventually carried out using two different not easily printable shapes to demonstrate the practical feasibility of the proposed strategy. Funding information:Conselho Nacional de Desenvolvimento Científico e TecnológicoGrant number 302863/2016-8

In recent years, statistics show that the percentage of household consumption in GDP is getting higher and higher. One of the subsequent influences is that the transport demand for packages has increased sharply. Hence it is very necessary to propose diverse transport organization modes in accordance with the different situation in different countries. A kind of new transportation mode, multi-package multi-train pickup and delivery problem with time window (MPMT-PDPTW) is proposed in this paper. It aims to achieve express package transportation with minimum cost and maximize utilization of luggage car of a passenger train at the same time. Considering the multiple constraints, such as limited carrying capacity, fixed departing and accepting time, we define the quality of service (QoS) as the evaluation criteria for package express transportation by the passenger train. A kind of meta-heuristic algorithm, greedy randomized adaptive search procedure (GRASP), is designed to make full use of the redundant capacity of railway luggage car. An example is designed according to the railway passenger train timetable released by China Railway Corporation (CRC), the assignment schemes of packages at different railway stations reveal that the new transportation mode proposed in this paper is feasible and practical in package express transportation, and also has advantages in speed comparing with the highway and in transport cost over the airline.

Wildfires are a natural phenomenon that occurs regularly in many terrestrial ecosystems. Due to global warming, the rate and the span of wildfires have remarkably increased during the last years, causing important economic losses as well as human casualties. In the last years, several initiatives have been undertaken in order to apply operations research tools to help firefighting teams schedule and optimize their protection activities when fighting wildfires. In this context, a recent variant of the Team Orienteering Problem (TOP) called the Asset Protection Problem (APP) has been proposed in [21]. In this problem, firefighting teams should provide a protective service to a set of assets endangered by wildfires. These activities can be performed by a heterogeneous fleet of vehicles and should occur within specific time intervals estimated based on the firefronts progression. This variant of the TOP incorporates three additional constraints, namely, time windows, synchronized visits and compatibility constraints between vehicles and assets. In this paper, we propose a hybrid approach that combines a Greedy Randomized Adaptive Search Procedure coupled with an Iterated Local Search (GRASP×ILS) and a post-optimization phase that consists of a Set Covering Problem formulation to efficiently solve the problem. Interestingly, the GRSAP×ILS incorporates an adaptive candidate-list based insertion heuristic as well as a Variable Neighborhood Descent (VND) procedure. The post optimization phase is used at the end of the resolution to improve the best solution found by the GRSAP×ILS. Detailed computational tests have been carried out to prove the effectiveness of our method. The results show that our method, called Hybrid-Heuristic, out-performs the methods of the literature, since it achieves an overall improvement of the best known solutions by 8.52% and 7.8% on medium and large-size instances respectively, while maintaining much lesser computational times.

The Electric Vehicle Routing Problem (EVRP) is a recently formulated combination of the Capacitated Vehicle Routing Problem (CVRP) and the Green Vehicle Routing Problem (GVRP). The goal is to satisfy all customers’ demands while considering the vehicles’ load capacity and limited driving range. All vehicles start from one central depot and can recharge during operation at multiple charging stations. The EVRP reflects the recent introduction of electric vehicles into fleets of delivery companies and represents a general formulation of numerous more specific VRP variants. This paper presents a newly proposed approach based on Greedy Randomized Adaptive Search Procedure (GRASP) scheme addressing the EVRP and documents its performance on a recently created dataset.GRASP is a neighborhood-oriented metaheuristic performing repeated randomized construction of a valid solution, which is subsequently further improved in a local search phase. The implemented metaheuristic improves multiple best-known solutions and sets a benchmark on some previously unsolved instances.

Περίληψη: Τα τελευταία χρόνια παρατηρείται έντονα η τάση των επιχειρήσεων να επενδύσουν στη Διαχείριση της Εφοδιαστικής Αλυσίδας. Πράγματι, η Διαχείριση της Εφοδιαστικής Αλυσίδας, ή εν συντομία τα Logistics, αποτελούν πλέον βασικό πυλώνα στον στρατηγικό σχεδιασμό των επιχειρήσεων κι όχι άδικα. Η βελτιστοποίηση των μεταφορών και των αποθεμάτων έχει πάψει να θεωρείται απλώς ένα ανταγωνιστικό πλεονέκτημα, αφού πλέον αποτελεί επιτακτική ανάγκη για τη βιωσιμότητα των επιχειρήσεων. Η παρούσα διπλωματική εργασία πραγματεύεται ένα από τα σημαντικότερα προβλήματα της Εφοδιαστικής Αλυσίδας, αυτό της δρομολόγησης οχημάτων. Πιο συγκεκριμένα, πρόκειται για τοΧρονικώς Εξαρτώμενο Πρόβλημα Δρομολόγησης Οχημάτων (Time Dependent Vehicle Routing Problem), το οποίο προσπαθεί να προσεγγίσει ρεαλιστικά μία πραγματική κατάσταση με στόχο τη βελτιστοποίηση του κόστους. Με την έννοια πραγματική κατάσταση νοούνται όλες εκείνες οι παράμετροι που ενδέχεται να επηρεάσουν τον τρόπο και τους χρόνους των μεταφορών, όπως για παράδειγμα η κυκλοφοριακή συμφόρηση ή η κατάσταση του οδικού δικτύου. Γι' αυτό, οι χρόνοι μετάβασης εξαρτώνται από τη χρονική στιγμή της ημέρας κατά την οποία πραγματοποιείται μία μεταφορά, καθώς η μέρα χωρίζεται στα κατάλληλα χρονικά διαστήματα. Έπειτα, ο αλγόριθμος, που χρησιμοποιείται για την επίλυση του προβλήματος, είναι ο GRASP (Greedy Randomized Adaptive Search Procedure). Ο GRASP πρόκειται για μία επαναληπτική διαδικασία, η οποία αποτελείται από δύο φάσεις. Στην πρώτη φάση κατασκευάζεται μία πιθανή λύση μέσω μίας τυχαιοποιημένης συνάρτησης απληστίας. Η συνάρτηση, αυτή, σε κάθε επανάληψη επιλέγει τυχαία τον επόμενο πελάτη προς εξυπηρέτηση μέσα από μία λίστα περιορισμένων υποψηφίων (Restricted Candidate List). Στη δεύτερη φάση, η λύση που κατασκευάστηκε, ακολουθεί μία διαδικασία τοπικής αναζήτησης, προκειμένου να βελτιωθεί το συνολικό της κόστος. Εν τέλει, συγκρίνοντας όλες τις πιθανές λύσεις που κατασκευάστηκαν, προκύπτει το τελικό αποτέλεσμα. Δηλαδή, η βέλτιστη λύση μαζί με το αντίστοιχο κόστος.

During the period 2012–2016, 99.0% of the municipalities of the State of Veracruz in Mexico have been subject to emergency declarations by the National Fund for Disaster Relief derived from the impact of hydro-meteorological phenomena. The present work develops a hybrid capacitated multi-facility location model based on (1) the p-median algorithm, (2) the Nearest Neighbor (NN) algorithm, (3) the Greedy Randomized Adaptive Search Procedure (GRASP) algorithm, and (4) the continuous review (q, R) inventory model with uncertain demand. To support the organization of humanitarian relief efforts and maintain the quality of life of specific affected people in this region. The hybrid model identifies multiple feasible locations for the establishment of pre-positioned warehouses and their inventories. In contrast to other works, the proposed model extends on the characteristics of the required inventories to be stored. These are classified into food, clothing, personal hygiene, water, and personal health, and each one is classified depending on the life stages of the person: (a) early childhood; (b) childhood; (c) adolescence; (d) adult, and (e) third age. This classification is performed to provide products according to the specific needs of the affected people according to their age. As a result, 20 feasible locations throughout the State of Veracruz were identified, and for each pre-positioned warehouse, economic order quantities, reorder points, and safety stocks were defined.

The quadratic assignment problem (QAP) is classified as an NP-hard problem, so metaheuristic procedures are often used to solve it. QAP is a classic combinatorial optimization problem with real applications, for example in supply chain, logistics, manufacturing, finance, among others. In this article, to search for QAP solutions, the design of a program code for the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic was implemented with three different neighborhood structures contained in k-exchange mode in order to perform the local search. The experimental procedure was applied for large-scale test instances available from QAPLIB. Finally, the results of the approximations to the optimal solutions are reported.

We propose a method to reduce the complexity of Generalized Linear Models in the presence of categorical predictors. The traditional one-hot encoding, where each category is represented by a dummy variable, can be wasteful, difficult to interpret, and prone to overfitting, especially when dealing with high-cardinality categorical predictors. This paper addresses these challenges by finding a reduced representation of the categorical predictors by clustering their categories. This is done through a numerical method which aims to preserve (or even, improve) accuracy, while reducing the number of coefficients to be estimated for the categorical predictors. Thanks to its design, we are able to derive a proximity measure between categories of a categorical predictor that can be easily visualized. We illustrate the performance of our approach in real-world classification and count-data datasets where we see that clustering the categorical predictors reduces complexity substantially without harming accuracy.

This paper presents route planning for a tourist as tourist trip design problem (TTDP) using discrete cuckoo search algorithm (DCS). The DCS algorithm is based on brood parasitic nature of cuckoo bird which is characterized by levy flight. The experiment of proposed DCS is conducted on orienteering problem (OP) benchmark instances and their performance compared with existence data of iterative local search (ILS) and greedy randomized adaptive search procedure (GRASP). Result showed that proposed DCS is required less computational time as compared to ILS and GRASP. It concluded that DCS is efficient method for exploring and exploiting search space in reasonable amount of time.

Background: Network Functions Virtualization (NFV) is a paradigm shift in the way network operators deploy and manage their services. The basic idea behind this new technology is the separation of network functions from the traditional dedicated hardware by implementing them as a software that is able to run on top of general-purpose hardware. Thus, the resulting pieces of software are called Virtual Network Functions (VNFs). NFV is expected, on one hand, to lead to increased deployment flexibility and agility of network services and, on the other hand, to reduce operating and capital expenditures. One of the major challenges in NFV adoption is the NFV Infrastructure's Resource Allocation (NFVI-RA) for the requested VNF-Forwarding Graph (VNF-FG). This problem is named VNF-forwarding graph mapping problem and is known to be an NP-hard problem. Objective: To address the VNF-FG mapping problem, the objective is to design a solution that uses a meta-heuristic method to minimize the mapping cost. Methods: To cope with this NP-Hard problem, this paper proposes an algorithm based on Greedy Randomized Adaptive Search Procedure (GRASP), a cost-efficient meta-heuristic algorithm, in which the main objective is to minimize the mapping cost. Another method named MARA (Most Available Resource Algorithm) was devised with the objective of reducing the Substrate Network’s resources use at the bottleneck clusters. Results: The Performance evaluation is conducted using real and random network topologies to confront the proposed version of GRASP with another heuristic, existing in the literature, based on the Viterbi algorithm. The results of these evaluations reveal the efficiency of the proposed GRASP ‘s version in terms of reducing the cost mapping and performs consistently well across all the evaluations and metrics. Conclusion: The problem of VNF-FG mapping is formalized, and a solution based on GRASP meta- heuristic is proposed. Performance analysis based on simulations are given to show the behavior and efficiency of this solution.

Cyber-Physical Systems (CPS) will form the basis for the world's critical infrastructure and, thus, have the potential to significantly impact human lives in the near future. In recent years, there has been an increasing demand for connectivity in CPS, which has brought to attention the issue of cyber security. Aside from traditional information systems threats, CPS faces new challenges due to the heterogeneity of devices and protocols. In this paper, we investigate how Feature Selection may improve intrusion detection accuracy. In particular, we propose an adapted Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic to improve the classification performance in CPS perception layer. Our numerical results reveal that GRASP metaheuristic overcomes traditional filter-based feature selection methods for detecting four attack classes in CPSs.

Several metaheuristics can be considered for solving a given optimization problem. Unfortunately none of them is better on all instances. Selecting a priori the best metaheuristic for a given instance is a difficult task which can be addressed using meta-learning. In this work, we propose a method to recommend, for a MaxSAT instance, the best metaheuristic among three: Genetic Algorithm (GA), Bee Swarm Optimization (BSO) and Greedy Randomized Adaptive Search Procedure (GRASP). Basically, a learning model is trained to induce associations between MaxSAT instances’ characteristics and metaheuristics’ performances. The built model is able to select the best metaheuristic for a new MaxSAT instance. We experiment different learning algorithms on different instances from several benchmarks. Experimental results show that the best metaheuristic is selected with a prediction rate exceeding 80% regardless the learning algorithm. They also prove the effect of instances used in training on the model performance.

International audience; Dealing with the ever-increasing video traffic is certainly one of the major challenges facing Internet Service Providers (ISPs). In this context, the strategic placement of caches is seen as one of the most important remedies, especially with recent advances in the field of virtualization. Unlike the existing works, which only focus on the placement issue, we also consider the problem of determining the optimal amount of cache to place at each possible location. We formalize, in this paper, the problem of caches placement as a multi-objective optimization problem, in which we minimize both the average distance from which contents are retrieved and the peering links utilization. As the proposed problem is NP-hard, we propose to solve it using the Greedy Randomized Adaptive Search Procedure (GRASP) meta-heuristic. Simulations results reveal the quality of the obtained solutions compared to an exhaustive search method. At the same time, they reveal that the solution is not to put all resources at the edge or at the core, as some studies claim, but to partition them judiciously, which mainly depends on the objectives of the ISPs.

Este artículo aborda el problema de selección de portafolio de proyectos para la adjudicación de interventorías de obra pública a través de concursos de méritos abiertos (CMA) supervi-sados por el Instituto Nacional de Vías (INVIAS) en Colombia. En esta modalidad, cada con-cursante presenta un portafolio único de proyectos históricos para cuantificar su experiencia como interventor. Como alternativa al uso de hojas de cálculo en Excel con procedimientos limitados de enumeración exhaustiva, se evaluó un algoritmo genético meta-optimizado (GA) y un procedimiento de búsqueda voraz adaptativo probabilista meta-optimizado (GRASP) para el caso de estudio de una Compañía con 207 contratos de trayectoria en el sector. Ambas metaheurísticas consiguieron encontrar puntajes de valoración óptimos para distintas instancias de prueba, sin embargo, el algoritmo GA presentó un mejor desempeño consistentemente en todas las instancias de evaluación, encontrando en algunos casos hasta 10 portafolios óptimos en menos de 9 minutos., This article addresses the problem of project portfolio selection for the adjudication of public works audits through open merit competitions (CMA) supervised by the National Institute of Roads (INVIAS) in Colombia. In this modality, each contestant presents a unique portfolio of historical projects to quantify their experience as a controller. As an alternative to using Excel spreadsheets with limited exhaustive enumeration procedures, a meta-optimized genetic algorithm (GA) and a meta-optimized probabilistic adaptive greedy search procedure (GRASP) were evaluated for a Company case study. with 207 experience contracts in the sector. Both metaheuristics were able to find optimal evaluation scores for different test instances, however, the GA algorithm presented a consistently better performance in all evaluation instances, finding in some cases up to 10 optimal portfolios in less than 9 minutes., Recibido: 03-01-2020Aceptado: 18-06-2020 Disponible online: 15-11-2020, Publicación científica semestral Universidad EIA, Envigado, Colombia

A state estimation process is highly influenced by the level of the measurement redundancies. However, due to financial and operational constraints, redundancy is in practice limited, making the power systems metering design a challenging problem. Therefore, for the first time, a methodology to design a metering system for state estimation in power systems is proposed, in which the metering placement is modeled as a combinatorial constrained optimization problem, where the final goal is to maximize the system redundancy – expressed by observability indicators – subjected to investment constraints. A Genetic Algorithm and a Greedy Randomized Adaptive Search Procedure, combined with a constructive heuristic are investigated for the metering design problem. Tests with IEEE-14, IEEE-30, IEEE-118 bus systems and part of a real Brazilian system are carried out to evaluate the performance of the proposed methodology. The results also show that, for the IEEE-118 bus system, 30% of the total cost of the measurements and RTUs is required to ensure observability, whereas 32% and 60% are necessary to eliminate the network critical measurements and to obtain a system without critical sets, respectively.

We consider the multicontainer loading problem of a company that has to serve its customers by first putting the products on pallets and then loading pallets onto trucks. When a large number of units of a product have to be shipped, the company requires that homogeneous pallets, with only one product, are built first, then weakly heterogeneous pallets, in which each layer corresponds to a single product, and finally strongly heterogeneous pallets with the remaining units of the products. To be useful in practice, the solutions have to satisfy five types of constraints: geometric constraints, so that pallets are completely inside the trucks and do not overlap; weight constraints, limiting the total weight a truck can bear and the maximum weight supported by each axle; constraints limiting the position of the centre of gravity of the cargo; dynamic stability constraints, to avoid cargo displacement when the truck is moving; and constraints ensuring that the delivery dates of products are respected. We have developed a Greedy Randomized Adaptive Search Procedure, including some improvement methods tailored to the problem, among them an adaptation of ejection chains. The approach has been tested on a benchmark of real problems and it has been shown to be capable of finding high-quality, realistic solutions in short computing times. We also provide a comparison with an integer programming formulation that justifies the use of a metaheuristic algorithm.

The work presented focuses on the resolution of the multi compartment vehicle routing problem (MCVRP), a variant of the general vehicle routing problem (VRP). An adapted Discrete Bat Algorithm (DBA) is applied and numerical results are compared to results obtained by a Greedy Randomized Adaptive Search Procedure (GRASP). The algorithm proved to be efficient and further studies can be done to enhance its performance.

In this paper, we address the Close Enough Orienteering Problem (CEOP) that is motivated to find the most rewarding route visiting disk-shaped regions under the given travel budget. The CEOP differs from the regular OP in the continuous optimization of finding the most suitable waypoint locations to collect the reward associated with each region of interest in addition to the selection of the subset of the regions and sequence of their visits as in the OP. We propose to employ the Greedy Randomized Adaptive Search Procedure (GRASP) combinatorial metaheuristic to solve the addressed CEOP, in particular, the GRASP with Segment Remove. The continuous optimization is addressed by the newly introduced heuristic search that is applied in the construction phase and also in the local search phase of the GRASP. The proposed approach has been empirically evaluated using existing benchmarks, and based on the reported comparison with existing algorithms, the proposed GRASP-based approach provides solutions with the competitive quality while its computational requirements are low.

This paper considers the uncapacitated r -allocation p -hub maximal covering problem (UrApHMCP), which represents a generalization of the well-known p -hub maximal covering problem, as it allows each non-hub node to send and receive flow via at most r hubs, r ≤ p . Two coverage criteria are considered in UrApHMCP — binary and, for the first time in the literature, partial coverage. Novel mathematical formulations of UrApHMCP for both coverage criteria are proposed. As the considered UrApHMCP is an NP-hard optimization problem, two efficient heuristic methods are proposed as solution approaches. The first one is a variant of General Variable Neighborhood Search (GVNS), and the second one is based on combining a Greedy Randomized Adaptive Search Procedure (GRASP) with Variable Neighborhood Descent (VND), resulting in a hybrid GRASP-VND method. Computational study is performed over the set of CAB and AP benchmark instances with up to 25 and 200 nodes, respectively, on TR instances including 81 nodes, as well as on the challenging USA423 and URAND hub instances with up 423 and 1000 nodes, respectively. Optimal or feasible solutions are obtained by CPLEX solver for instances with up to 50 nodes, while instances of larger dimensions are out of reach for CPLEX solver. On the other hand, both GVNS and GRASP-VND reach optimal solutions or improve lower bounds provided by CPLEX in short CPU times. In addition, both heuristics quickly return solutions on problem instances of large dimensions, thus indicating their potential to solve effectively large, realistic sized problem instances. The conducted non-parametric statistical tests confirm robustness of the proposed GVNS and GRASP-VND and demonstrate that the these two metaheuristics outperform other tested algorithms for UrApHMCP.

The volume of data traffic in backbone networks is increasing at a speed that exceeds the growth rates of capacities offered in currently used wavelength division multiplexing (WDM) networks. As a short term solution to the potential capacity crunch, the concept of flexible-grid elastic optical networks is nowadays implemented in many backbone networks. However, in a longer term the space division multiplexing (SDM) technology is the most promising solution for satisfying the capacity requirements in future optical networks. The combination of both technologies allows for realization of spectrally-spatially flexible optical networks (SS-FONs). In this paper, we focus on a network scenario in which two different types of traffic flows are carried over an SS-FON, namely, unicast and anycast flows. Unicast flows are used for basic one-to-one communication, while anycast flows — defined as one-to-one-of-many communication — are related to the network traffic generated in data centers and the fact that data centers placed in different network locations can provide the same service or content to network users. For provisioning of lightpaths for both types of traffic, we address the basic optimization problem in SS-FONs, which is routing, space and spectrum allocation (RSSA). The aim of this study is threefold. First, we propose an effective metaheuristic method based on the greedy randomized adaptive search procedure (GRASP) to solve the RSSA problem. Second, we compare performance of the proposed GRASP method against reference optimization approaches. Finally, we present and discuss a wide range of experiments focused on analysis of SS-FONs with joint unicast and anycast traffic. The main conclusions are: (i) the proposed GRASP algorithm provides results very close to optimal (only 0.5% optimality gap) for smaller problem instances and significantly outperforms other heuristics for larger problem instances (in average around 6.8% better than the reference simulated annealing algorithm); (ii) the use of anycast connections in SS-FONs allows to improve the network performance in terms of spectrum usage.

This paper considers a special case of famous vehicle routing problem with additional risk constraints, called the Risk-constrained Cash-in-Transit Vehicle Routing Problem (RCTVRP). We propose a fuzzy GRASP (Greedy Randomized Adaptive Search Procedure) hybridized with path relinking (PR) methodology for solving the RCTVRP. Introduced PR structure, which can be used for other vehicle routing problems, is implemented. To make the algorithm's time complexity smaller, new data structure for the RCTVRP is incorporated. Proposed fuzzy GRASP with PR hybrid shows better computational performance compared to its non-fuzzy version. Furthermore, computational results on publicly available data sets indicate that proposed algorithm outperforms all existing methods from the literature for solving the RCTVRP.

Cluster analysis is an unsupervised machine learning task that aims at finding the most similar groups of objects, given a prespecified similarity measure. When modeled as an optimization problem, clustering problems generally are NP -hard. Therefore, the use of metaheuristic approaches appears to be a promising alternative. In this paper, a continuous greedy randomized adaptive search procedure (C-GRASP) approach is proposed to solve a partitional clustering problem that aims at minimizing the intra-cluster distances. Computational experiments carried out on existing databases showed that the results obtained by the proposed algorithm was, on average, superior to those found by other well-known metaheuristics, as well as to those achieved by state-of-the-art algorithms from the literature.

Offshore production has a high level of complexity inherent to its development and exploration. This context leads to the need for the Multi-objective and Multi-level Capacitated Oil Platform Location Problem (MMCOPLP), which is used for the definition of places for platforms and drilling of wells, given a set of possible candidate points. The conflict between objectives is commonly present in the multi-objective problems and, consequently, there is a set of optimal solutions called the Pareto Optimal. The Pareto Optimal is hard to be determined by exact methods, and heuristics and/or metaheuristics are implemented as alternative methods. Considering the above, the main objective of this study is to propose a Non-dominated Sorting Genetic Algorithm (NSGA-II) to solve the MMCOPLP. Instances are also proposed and the e-Constraint exact method is used to find the Pareto Optimal. Based on the error ratio, on generational distance and on hypervolume metrics, computational experiments show that the NSGA-II provides good solutions, close to Pareto Optimal and better than a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic proposed in the literature.

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 previous effort has been devoted to study the “combined problem” from a multi-objective perspective. In particular, we adapt the mono-objective methodologies applied to this problem to the resolution of the bi-objective problem, obtaining approximations to its efficient front. An empirical comparison discloses the best alternative to tackle this NP -hard problem.

The Capacitated Team Orienteering Problem (CTOP) is a variant of the well-known Team Orienteering Problem where additional capacity limitation constraints are considered for each vehicle. Solving CTOP consists of organizing a set of routes that maximize the total profit collected from the served customers while taking into consideration the capacity and travel time limitation for each vehicle. In this paper, we propose a variable space search heuristic to solve CTOP. Our algorithm alternates between two search spaces: the giant tour and routes search spaces. We develop a hybrid heuristic as a framework for our algorithm composed of a combination between Greedy Randomized Adaptive Search Procedure and Evolutionary Local Search. Several local search techniques were developed in each search space to improve the quality of the solutions and the giant tours. A dedicated optimal split procedure and a concatenation technique are performed to ensure the link between the search spaces. This approach shows its high performance on the benchmark of CTOP, and proves its competitiveness in comparison to the other heuristic methods available in the literature as it yields to strict improvements with small computational time.

The connected vertex cover (CVC) problem, which has many important applications, is a variant of the vertex cover problem, such as wireless network design, routing, and wavelength assignment problem. A good algorithm for the problem can help us improve engineering efficiency, cost savings, and resources consumption in industrial applications. In this work, we present an efficient algorithm GRASP-CVC (Greedy Randomized Adaptive Search Procedure for Connected Vertex Cover) for CVC in general graphs. The algorithm has two main phases, i.e., construction phase and local search phase. In the construction phase, to construct a high quality feasible initial solution, we design a greedy function and a restricted candidate list. In the local search phase, the configuration checking strategy is adopted to decrease the cycling problem. The experimental results demonstrate that GRASP-CVC is better than other comparison algorithms in terms of effectivity and efficiency.

In this paper, we develop a greedy algorithm for solving the problem of sparse learning over a right stochastic network in a distributed manner. The nodes iteratively estimate the sparse signal by exchanging a weighted version of their individual intermediate estimates over the network. We provide a restricted-isometry-property (RIP)-based theoretical performance guarantee in the presence of additive noise. In the absence of noise, we show that under certain conditions on the RIP-constant of measurement matrix at each node of the network, the individual node estimates collectively converge to the true sparse signal. Furthermore, we provide an upper bound on the number of iterations required by the greedy algorithm to converge. Through simulations, we also show that the practical performance of the proposed algorithm is better than other state-of-the-art distributed greedy algorithms found in the literature.

An unexpected difference between online and offline algorithms is observed. The natural greedy algorithms are shown to be worst case online optimal for Online Independent Set and Online Vertex Cover on graphs with “enough” isolated vertices, Freckle Graphs. For Online Dominating Set , the greedy algorithm is shown to be worst case online optimal on graphs with at least one isolated vertex. These algorithms are not online optimal in general. The online optimality results for these greedy algorithms imply optimality according to various worst case performance measures, such as the competitive ratio. It is also shown that, despite this worst case optimality, there are Freckle graphs where the greedy independent set algorithm is objectively less good than another algorithm. It is shown that it is NP -hard to determine any of the following for a given graph: the online independence number, the online vertex cover number, and the online domination number.

Natural gas distribution systems are inherently vulnerable to accidental or intentional intrusion. Such events lead to financial losses and endanger the environmental and public safety. Therefore, it is crucial to adequately monitor the gas distribution systems. An important step toward this goal is to optimize the placement of sensors in the network. In this paper, we propose three design objectives including time-to-detection (TTD), sensitivity, and impact propagation (IP) and implement five multi-objective optimization algorithms (greedy, greedy randomized adaptive search procedure, non-dominated sorting genetic algorithm II, FrameSense, and particle swarm optimization (PSO)) to strategically place the sensors. From the results on an artificial network with 37 nodes and 50 branches and a real network in Singapore with 148 nodes and 150 branches, we find that Greedy and PSO algorithms are almost 10 times faster than the other algorithms in computational time. We also investigate the tradeoff between the design objectives and the number of sensors. Since TTD, sensitivity, and IP have different measurement units, we normalize their values within 0 to 1 (0%-100%) and consider the average of those three normalized values as the design cost. For 10% design cost, the number of required sensors is 5 and 8 for the artificial network and the real network, respectively. The results indicate that PSO yields the sensor configuration with the lowest design cost and the computational time. NRF (Natl Research Foundation, S’pore)