Enhancing and extending the classical GRASP framework with biased randomisation and simulation

Abstract Greedy Randomised Adaptive Search Procedure (GRASP) is one of the best-known metaheuristics to solve complex combinatorial optimisation problems (COPs). This paper proposes two extensions of the typical GRASP framework. On the one hand, applying biased randomisation techniques during the solution construction phase enhances the efficiency of the GRASP solving approach compared to the traditional use of a restricted candidate list. On the other hand, the inclusion of simulation at certain points of the GRASP framework constitutes an efficient simulation–optimisation approach that allows to solve stochastic versions of COPs. To show the effectiveness of these GRASP improvements and extensions, tests are run with both deterministic and stochastic problem settings related to flow shop scheduling, vehicle routing, and facility location.

• Publication year

  2018

• Venue

  Journal of the Operational Research Society

• Publication date

  2018-10-17

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1080/01605682.2018.1494527
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A simheuristic algorithm for solving the arc-routing problem with stochastic demands

  2018cited by this paper
• Waste collection under uncertainty: a simheuristic based on variable neighbourhood search

  2017cited by this paper
• A biased-randomized metaheuristic for the capacitated location routing problem

  2017cited by this paper
• Supporting multi-depot and stochastic waste collection management in clustered urban areas via simulation–optimization

  2017cited by this paper
• Biased randomization of heuristics using skewed probability distributions: A survey and some applications

  2017cited by this paper
• Parallel multi‐core hyper‐heuristic GRASP to solve permutation flow‐shop problem

  2017cited by this paper
• Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic

  2017cited by this paper
• A multi-start randomized heuristic for real-life crew rostering problems in airlines with work-balancing goals

  2017cited by this paper
• hybrid GRASP-VNS for Ship Routing and Scheduling Problem with Discretized Time Windows. Engineering Applications of Artificial Intelligence

  2017cited by this paper
• Advanced Greedy Randomized Adaptive Search Procedure for the Obnoxious p-Median problem

  2016cited by this paper
• A discrete-event driven metaheuristic for dynamic home service routing with synchronised trip sharing

  2016cited by this paper
• Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet

  2016cited by this paper
• GRASP with path-relinking

  2016cited by this paper
• A BRILS metaheuristic for non-smooth flow-shop problems with failure-risk costs

  2016cited by this paper
• A Glowworm Swarm Optimization algorithm for the Vehicle Routing Problem with Stochastic Demands

  2016cited by this paper
• Optimization by GRASP: Greedy Randomized Adaptive Search Procedures

  2016cited by this paper
• SimILS: a simulation-based extension of the iterated local search metaheuristic for stochastic combinatorial optimization

  2016cited by this paper
• An ILS-biased randomization algorithm for the two-dimensional loading HFVRP with sequential loading and items rotation

  2016cited by this paper
• A Biased-Randomised Large Neighbourhood Search for the two-dimensional Vehicle Routing Problem with Backhauls

  2016cited by this paper
• Multiobjective GRASP with Path Relinking

  2015cited by this paper
• Combining biased randomization with iterated local search for solving the multidepot vehicle routing problem

  2015influential reference
• Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization

  2015cited by this paper
• Horizontal cooperation in road transportation: a case illustrating savings in distances and greenhouse gas emissions

  2015cited by this paper
• A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems

  2015influential reference
• GRASP for the uncapacitated r-allocation p-hub median problem

  2014cited by this paper
• A simheuristic algorithm for solving the permutation flow shop problem with stochastic processing times

  2014influential reference
• A simheuristic algorithm for the Single-Period Stochastic Inventory-Routing Problem with stock-outs

  2014cited by this paper
• GRASP for the Vehicle Routing Problem with Time Windows, synchronization and precedence constraints

  2014cited by this paper
• A simulation-optimization approach to deploy Internet services in large-scale systems with user-provided resources

  2014influential reference
• Vehicle Routing

  2014cited by this paper
• Improved heuristics for the regenerator location problem

  2014cited by this paper
• A biased-randomized algorithm for the two-dimensional vehicle routing problem with and without item rotations

  2014cited by this paper
• Multi-start methods for combinatorial optimization

  2013cited by this paper
• Multiple Phase Neighborhood Search-GRASP for the Capacitated Vehicle Routing Problem

  2012cited by this paper
• Metaheuristics in Logistics and Supply Chain Management

  2012influential reference
• Production , Manufacturing and Logistics Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking

  2011cited by this paper
• A GRASP algorithm for flexible job-shop scheduling problem with limited resource constraints

  2011cited by this paper
• A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times

  2011cited by this paper
• MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems

  2011influential reference
• Facility location: concepts, models, algorithms and case studies. Series: Contributions to Management Science

  2011cited by this paper
• Using parallel & distributed computing for real-time solving of vehicle routing problems with stochastic demands

  2011cited by this paper
• Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands

  2011cited by this paper
• Handbook of Metaheuristics

  2010cited by this paper
• An annotated bibliography of GRASP-Part II: Applications

  2009influential reference
• Greedy Randomized Adaptive Search Procedures

  2009cited by this paper
• Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm

  2009influential reference
• An annotated bibliography of GRASP - Part I: Algorithms

  2009influential reference
• Logic classification and feature selection for biomedical data

  2008cited by this paper
• Facility Location

  2007cited by this paper
• Implementation of grasp in flow shop scheduling

  2006cited by this paper
• A hybrid multistart heuristic for the uncapacitated facility location problem

  2006cited by this paper
• Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking

  2006cited by this paper
• Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem

  2004cited by this paper
• GRASP: Greedy Randomized Adaptive Search Procedures

  2003cited by this paper
• Parallel GRASP with path-relinking for job shop scheduling

  2003cited by this paper
• Scatter Search: Diseño Básico y Estrategias avanzadas

  2002cited by this paper
• Computational results with a branch and cut code for the capacitated vehicle routing problem

  1998cited by this paper
• Scheduling: Theory, Algorithms, and Systems

  1994cited by this paper
• Benchmarks for basic scheduling problems

  1993cited by this paper
• Probabilistic Analysis of a Relaxation for the k-Median Problem

  1986cited by this paper
• Book Selection

  1984cited by this paper
• A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem

  1983cited by this paper
• The Complexity of Flowshop and Jobshop Scheduling

  1976cited by this paper

• Heuristics for the weighted total domination problem

  2025cites this paper
• Application of Optimization Algorithms in Voter Service Module Allocation

  2025cites this paper
• GRASP: an application to efficiently plan the low carbon emission distributed additive manufacturing

  2025cites this paper
• A biased randomised GRASP for the electric vehicle routing problem with heterogeneous supplemental infrastructures

  2025cites this paper
• A multistart biased-randomized algorithm for solving a three-dimensional case picking problem with real-life constraints

  2023cites this paper
• Deep Reinforcement Learning Based Pushing and Grasping Model with Frequency Domain Mapping and Supervised Learning

  2023cites this paper
• Efficient GRASP solution approach for the Prisoner Transportation Problem

  2023cites this paper
• Constraint-based robust planning and scheduling of airport apron operations through simheuristics

  2022cites this paper
• A Biased-Randomized Discrete-Event Algorithm for the Hybrid Flow Shop Problem with Time Dependencies and Priority Constraints

  2022cites this paper
• A biased-randomized discrete-event heuristic for coordinated multi-vehicle container transport across interconnected networks

  2022cites this paper
• Applying Simheuristics to Minimize Overall Costs of an MRP Planned Production System

  2022cites this paper
• Internet of Vehicles and Real-Time Optimization Algorithms: Concepts for Vehicle Networking in Smart Cities

  2022cites this paper
• On the role of metaheuristic optimization in bioinformatics

  2022cites this paper
• Multicriteria Route Planning for In-Operation Mass Transit under Urban Data

  2022cites this paper
• A GRASP with penalty objective function for the Green Vehicle Routing Problem with Private Capacitated Stations

  2022cites this paper
• A GA-simheuristic for the stochastic and multi-period portfolio optimisation problem with liabilities

  2022cites this paper
• Solution approaches for the vehicle routing problem with occasional drivers and time windows

  2022cites this paper
• Agile optimization for a real‐time facility location problem in Internet of Vehicles networks

  2021cites this paper
• Optimizing ride-sharing operations in smart sustainable cities: Challenges and the need for agile algorithms

  2021cites this paper
• Combining Heuristics with Simulation and Fuzzy Logic to Solve a Flexible-Size Location Routing Problem under Uncertainty

  2021cites this paper
• A simheuristic algorithm for video streaming flows optimisation with QoS threshold modelled as a stochastic single-allocation p-hub median problem

  2021influential citation
• A review of the role of heuristics in stochastic optimisation: from metaheuristics to learnheuristics

  2021cites this paper
• Agile Computational Intelligence for Supporting Hospital Logistics During the COVID-19 Crisis

  2021cites this paper
• Maximizing customers' lifetime value using limited marketing resources

  2021cites this paper
• Fuzzy Simheuristics for Optimizing Transportation Systems: Dealing with Stochastic and Fuzzy Uncertainty

  2021cites this paper
• Edge Computing and IoT Analytics for Agile Optimization in Intelligent Transportation Systems

  2021cites this paper
• A Real-time Energy-Saving Mechanism in Internet of Vehicles Systems

  2021cites this paper
• Combining Parallel Computing and Biased Randomization for Solving the Team Orienteering Problem in Real-Time

  2021cites this paper
• Supporting Hospital Logistics During the First Months of The COVID-19 Crisis: A Simheuristic for the Stochastic Team Orienteering Problem

  2021influential citation
• Last-Mile Delivery of Pharmaceutical Items to Heterogeneous Healthcare Centers with Random Travel Times and Unpunctuality Fees

  2021cites this paper
• APPLYING SIMHEURISTICS FOR SAFETY STOCK AND PLANNED LEAD TIME OPTIMIZATION IN A ROLLING HORIZON MRP SYSTEM UNDER UNCERTAINTY

  2021cites this paper
• Waste Collection of Medical Items Under Uncertainty Using Internet of Things and City Open Data Repositories: A Simheuristic Approach

  2021cites this paper
• A BIASED-RANDOMIZED DISCRETE-EVENT HEURISTIC FOR THE HYBRID FLOW SHOP PROBLEM WITH BATCHING AND MULTIPLE PATHS

  2021cites this paper
• Solving an Urban Ridesharing Problem with Stochastic Travel Times: A Simheuristic Approach

  2021cites this paper
• LAST-MILE DELIVERY OF PHARMACEUTICAL ITEMS TO HETEROGENEOUS HEALTHCARE CENTERS WITH RANDOM TRAVEL TIMES AND UNPUNCTUALITY FEES

  2021cites this paper
• Supporting Efficient Assignment of Medical Resources in Cancer Treatments with Simulation-Optimization

  2021cites this paper
• UPCommons Portal del coneixement obert de la UPC

  2021cites this paper
• Shortest path tour problem with time windows

  2020cites this paper
• Green hybrid fleets using electric vehicles: solving the heterogeneous vehicle routing problem with multiple driving ranges and loading capacities

  2020cites this paper
• A dynamic programming algorithm for solving the k-Color Shortest Path Problem

  2020cites this paper
• Combining simheuristics with Petri nets for solving the stochastic vehicle routing problem with correlated demands

  2020cites this paper
• A Simheuristic Algorithm for the Location Routing Problem with Facility Sizing Decisions and Stochastic Demands

  2020cites this paper
• A Simheuristic Algorithm for Reliable Asset and Liability Management Under Uncertainty Scenarios

  2020cites this paper
• ON THE USE OF SIMHEURISTICS TO OPTIMIZE SAFETY-STOCK LEVELS IN MATERIAL REQUIREMENTS PLANNING WITH RANDOM DEMANDS

  2020cites this paper
• Fuzzy Simheuristics: Solving Optimization Problems under Stochastic and Uncertainty Scenarios

  2020cites this paper
• Using Biased-Randomized Algorithms for the Multi-Period Product Display Problem with Dynamic Attractiveness

  2020cites this paper
• A Discrete-Event Heuristic for Makespan Optimization in Multi-Server Flow-Shop Problems with Machine re-entering

  2020cites this paper
• On the use of Simheuristics to Optimize Safety-Stock Levels in Material Requirements Planning with Random Demands

  2020cites this paper
• A simheuristic algorithm for time-dependent waste collection management with stochastic travel times

  2020cites this paper
• A biased-randomized algorithm for optimizing efficiency in parametric earthquake (Re) insurance solutions

  2020cites this paper
• A biased-randomized iterated local search for the vehicle routing problem with optional backhauls

  2020cites this paper
• A learnheuristic approach for the team orienteering problem with aerial drone motion constraints

  2020cites this paper
• Speeding up computational times in simheuristics combining genetic algorithms with discrete-Event simulation

  2020cites this paper
• A reactive simheuristic using online data for a real-life inventory routing problem with stochastic demands

  2020cites this paper
• Modern Optimization and Simulation Methods in Managerial and Business Economics: A Review

  2020cites this paper
• Modelling human network behaviour using simulation and optimization tools: the need for hybridization

  2019cites this paper
• A Simheuristic for the Unmanned Aerial Vehicle Surveillance-Routing Problem with Stochastic Travel Times and Reliability Considerations

  2019cites this paper
• Simulation-Based Optimization in Transportation and Logistics: Comparing Sample Average Approximation with Simheuristics

  2019cites this paper
• A simheuristic for routing electric vehicles with limited driving ranges and stochastic travel times

  2019cites this paper
• On the Use of Biased-Randomized Algorithms for Solving Non-Smooth Optimization Problems

  2019influential citation
• A biased‐randomized iterated local search for the distributed assembly permutation flow‐shop problem

  2019cites this paper
• Simheuristic algorithms for the sustainable freight transport problem

  2019cites this paper
• An Inventory-Routing Problem with Stochastic Demand and Stock-Out: A Solution and Risk Analysis Using Simheuristics

  2019cites this paper
• Combining the Internet of Things with Simulation-Based Optimization to Enhance Logistics in an Agri-Food Supply Chain

  2019cites this paper
• Why Simheuristics? Benefits, Limitations, and Best Practices When Combining Metaheuristics with Simulation

  2017cites this paper
• The Shortest Path Tour Problem and its variants

  2017cites this paper