Procedural content generation has the potential to increase a game’s replayability, reduce development costs and time, and tailor experiences to users. The generation of dialogues and narratives has gained increased interest thanks to the advance of Large Language Models (LLMs) and their potential to generate convincing texts about many subjects. However, many reported implementations have poor reception from users and face limitations. This study presents a systematic mapping of the literature on the use of LLMs for generating dialogues and narratives in digital games, aiming to discover the most used models, datasets, prompt elements, fine-tuning 1 strategies, integration methods in games, how each study was evaluated, and their main issues. Through an extensive search across multiple databases and the application of rigorous inclusion and exclusion criteria, we analyzed 55 articles that apply LLMs in gaming contexts. The most recurrent challenges include narrative incoherence, repetitiveness, memory limitations, and latency, all of which directly impact player immersion. The results reveal the predominance of Generative Pre-trained Transformer (GPT) family models and an increasing use of LLMs in game modifications and interactive environments. This work contributes to the field by providing a comprehensive overview of existing approaches, identifying research gaps, and suggesting future directions, such as the need for standardized evaluation methods, the development of robust solutions to address memory issues, and the importance of comparing LLM-generated content with human-created material.

We propose a system able to orchestrate the procedural generation of three creative facets (levels, narrative, and rules), using quality-diversity algorithms to promote diversity while converging to the desired solutions and able to satisfy different player's profiles. We aim to facilitate the project's reproducibility and extension by presenting the system's architecture and high-level design decisions and showcasing how we decoupled it enough to change algorithms. Our generation starts with a grammar-based quest generator that works as a frame for two quality-diversity algorithms: a level generator, which also creates locked-door puzzles, and an enemy generator, which selects their visuals based on their weapons. A rule-based profile analysis uses a pretest questionnaire to classify the player into four profiles, and the quest generator creates different content for each of them. We use a game prototype to test our system with over 83 players, playing over 204 levels and answering a posttest questionnaire after each. Results show the game and contents were well received, and there was a difference in perception between profiles. Players who played content based on their profile enjoyed it more than those playing content from another profile.

Action-Adventure games have several challenges to overcome, where the most common are enemies. The enemies’ goal is to hinder the players’ progression by taking life points, and the way they hinder this progress is distinct for different kinds of enemies. In this context, this paper introduces an extended version of an evolutionary approach for procedurally generating enemies that target the enemy’s difficulty as the goal. Our approach advances the enemy generation research by incorporating a MAP-Elites population to generate diverse enemies without losing quality. The computational experiment showed the method converged most enemies in the MAP-Elites in less than a second for most cases. Besides, we experimented with players who played an Action-Adventure game prototype with enemies we generated. This experiment showed that the players enjoyed most levels they played, and we successfully created enemies perceived as easy, medium, or hard to face.

Search-based systems have shown to be effective for planning in zero-sum games. However, search-based approaches have important disadvantages. First, the decisions of search algorithms are mostly non-interpretable, which is problematic in domains where predictability and trust are desired such as commercial games. Second, the computational complexity of search-based algorithms might limit their applicability, especially in contexts where resources are shared among other tasks such as graphic rendering. In this work we introduce a system for synthesizing programmatic strategies for a real-time strategy (RTS) game. In contrast with search algorithms, programmatic strategies are more amenable to explanations and tend to be efficient, once the program is synthesized. Our system uses a novel algorithm for simplifying domain-specific languages (DSLs) and a local search algorithm that synthesizes programs with self play. We performed a user study where we enlisted four professional programmers to develop programmatic strategies for mRTS, a minimalist RTS game. Our results show that the programs synthesized by our approach can outperform search algorithms and be competitive with programs written by the programmers.

• Single Evolutionary Algorithm encoding able to create procedural dungeon and mission. • Accurately create feasible dungeons of many sizes, linearity and locked-door puzzles. • A game prototype was developed and used for experiments with players. • Users evaluated the created content as human-made and fun as classic game levels. • Generated content allows a more complete exploration when compared to classic levels. The present research introduces an evolutionary algorithm able to procedurally generate dungeon maps containing locked door missions. The evolutionary algorithm evolves a tree structure, which encodes dungeons, aiming to generate levels close to the input configuration provided by a game designer. The tree structure holds information about the number of rooms, connections between them, and their position within a 2D map. The proposed encoding also allows evolving semantic information about the narrative of the game. This is done by feasibly setting keys and locks throughout the dungeons for locked door missions. The generated dungeons are then evaluated computationally and as a proof of concept using an adventure game prototype. A total of 70 players evaluated the contents and the results show that the procedurally generated levels are perceived as more human-made, fun, and difficult than their human-made counterparts for most cases.

The paper introduces a evolutionary algorithm, based on Multi Population Genetic Algorithm (MPGA), to support decisions about allocation and power sizing of generation units within power systems. The effectiveness of the MPGA is tested over two different radial distribution systems taking into account five different scenario. The evaluated power systems are the 33 and 69-bus radial distribution systems, which are benchmark systems from literature. The promising results achieved are compared against recent literature results for the same problem.

The present paper introduces a hybrid genetic algorithm for path planning problem with obstacle avoidance. The genetic algorithm is combined with Ray Casting (RC) algorithm, where RC is responsible to avoid obstacles and to find safe regions for emergency landing. Thus, the path planning system must deal with a non-convex environment when planning and re-planning trajectories. The system must also work embedded on the UAV running under a Raspberry Pi board. The hybrid method is evaluated over 50 benchmark maps from literature with satisfactory results reported.

In the path planning task for autonomous mobile robots, robots should be able to plan their trajectory to leave the start position and reach the goal, safely. There are several path planning approaches for mobile robots in the literature. Ant Colony Optimization algorithms have been investigated for this problem, giving promising results. In this paper, we propose the Max-Min Ant System for Dynamic Path Planning algorithm for the exploratory path planning task for autonomous mobile robots based on topological maps. A topological map is an environment representation whose focus is the main reference points of the environment and their connections. Based on this representation, the path can be composed by a sequence of state/actions pairs, which facilitates the navigability of the path, with no need to have the information of the complete map. The proposed algorithm was evaluated in static and dynamic environments, showing promising results in both of them. Experiments in dynamic environments show the adaptability of our proposal.

A key challenge for planning systems in real-time multiagent domains is to search in large action spaces to decide an agent’s next action. Previous works showed that handcrafted action abstractions allow planning systems to focus their search on a subset of promising actions. In this paper we show that the problem of generating action abstractions can be cast as a problem of selecting a subset of pure strategies from a pool of options. We model the selection of a subset of pure strategies as a two-player game in which the strategy set of the players is the powerset of the pool of options— we call this game the subset selection game. We then present an evolutionary algorithm for solving such a game. Empirical results on small matches of µRTS show that our evolutionary approach is able to converge to a Nash equilibrium for the subset selection game. Also, results on larger matches show that search algorithms using action abstractions derived by our evolutionary approach are able to substantially outperform all state-of-the-art planning systems tested.

The path planning methods based on nonconvex constrained optimization, such as mixed-integer linear programming (MILP), have found various important applications, ranging from unmanned aerial vehicles (UAVs) and autonomous underwater vehicles (AUVs) to space vehicles. Moreover, their stochastic extensions have enabled risk-aware path planning, which explicitly limits the probability of failure to a user-specified bound. However, a major challenge of those path planning methods is constraint violation between discrete time steps. In the existing approach, a path is represented by a sequence of waypoints and the safety constraints (e.g., obstacle avoidance) are imposed on waypoints. Therefore, the trajectory between waypoints could violate the safety constraints. A naive continuous-time extension results in unrealistic computation cost. In this paper, we propose a novel approach to ensure constraint satisfaction between waypoints without employing a continuous-time formulation. The key idea is to enforce that the same inequality constraint is satisfied on any two adjacent time steps, under assumptions of polygonal obstacles and straight line trajectory between waypoints. The resulting problem encoding is MILP, which can be solved efficiently by commercial solvers. Thus, we also introduce novel extensions to risk-allocation path planners with improved scalability for real-world scenarios and run-time performance. While the proposed encoding approach is general, the particular emphasis of this paper is placed on the chance-constrained, nonconvex path-planning problem (CNPP). We provide extensive simulation results on CNPP to demonstrate the path safety and scalability of our encoding and related path planners.

The present paper proposes two hybrid genetic algorithms as decision-making techniques for operational level decisions in the Glass Container Industry (GCI). The proposed methods address a production scenario where one new furnace and the related machines must be added to the current industrial plant. The configurations for each machine connected in a furnace is a decision to be taken, which depends on demand forecasts for glass containers within a time horizon. It is a tactical and operational level decisions that must be efficiently made. A mathematical formulation is first presented to describe precisely the objective and constraints for such problem. The formulation will also allow solving the problem instances by applying an exact method. Next, a hybrid approach combining genetic algorithms with mathematical programming techniques, and a greedy filter heuristic is proposed to solve the same problem instances. The set of instances is generated with data provided by a GCI located in Portugal and Brazil. The results reported indicate that the hybrid genetic algorithms return solutions able to support the operational and tactical decisions.

This paper addresses the vehicle routing problem with time windows (VRPTW), aiming to minimize the total travel time. A simple memetic algorithm (MA) is proposed for solving this problem. At the beginning of the search, a clustering procedure is applied to customers' spatial information. The search procedure consists of relocating customers between close routes, seeking to minimize detour costs associated with the relocations. The information gathered by the clustering procedure is used to identify which routes lie close to each other. Computational experiments on the Solomon's benchmark set show the effectiveness of the proposed approach, which produces competitive solutions and outperforms four out of six solution approaches considered for comparison regarding the travel cost attained over all the instances of the benchmark set.

The present paper proposes an evolutionary algorithm for procedural content generation of dungeon maps together with locked door missions. The algorithm evolves a tree structure which contains information of a dungeon. The aim is to converge the generated dungeons as close as possible to the input configuration set by a game designer. The dungeon holds information about rooms such as their number, connections between them and position in a 2D map (also knows as grid). It also contains relevant semantic information for generating narrative properties in the dungeon. Those are the placement of keys and locks in it, in a feasible way. Results show the algorithm is able to create dungeons within the desired configurations for a large set of different inputs. Also, they show the generated maps are perceived as human-designed, and evoke similar opinions of fun and difficulty when compared to human-designed maps.

Cloud computing provides infrastructure for executing workflows that require high processing and storage capacity. Although there are several algorithms for scheduling workflows, few consider security criterion. Algorithms that cover security usually optimize either cost or makespan. However, there are cases where the user would like to choose or evaluate among different solutions that present a trade-off between monetary cost and execution time (makespan) of the workflow. The selection of the tasks, which involve confidential/sensitive data, has to prioritize the safe execution of the workflow. In this paper, we propose a multi-objective optimization for scheduling of workflow tasks in cloud environments by considering cost and makespan under different task selection policies. Extensive experiments in real-world workflows with different policies show that our approach returns several solutions in the Pareto frontier for both cost and makespan. The results revealed a reasonable ability to find Pareto frontiers during the optimization process.

Nowadays, the access to a cloud computing environment is provided on-demand, offering transparent services to clients. Although the cloud allows an abstraction of the behavior of the infrastructure in the service providers (involving logical and physical resources), the Service Level Agreements (SLAs) fulfilment remain a challenge, because depending on the service demand and the system configuration, the providers may not be able to meet the clients requirements. In this way, mechanisms that take account of load balancing and resource provisioning algorithms to provide an efficient load distribution in the available resources are necessary. However, the studies in the literature do not effectively address the problem of the resource provisioning to meet clients requirements using optimization techniques, restricting the analysis to a limited set of objectives. This paper proposes algorithms to address the computational resource provisioning problem using optimization techniques on-the-fly. The techniques optimize the use of the resources available in the cloud infrastructure, aiming to fulfill the clients requirements defined in the SLAs, and ensuring the efficient use of resources.

Generating feasible levels for physics-based puzzle games is a complex and time-consuming task. This is because the mechanics of these games are based on realistic physics, so simulations are required to evaluate the playability of the generated levels. Recently, a few generators have been able to produce considerably complex levels in the context of the Angry Birds game, a very famous title of this genre. However, none of these generators are able to guarantee the playability of their produced levels. This paper presents Tanager, a level generator based on a genetic algorithm that is capable of producing feasible levels for the Angry Birds game. Evaluating playability in this game requires checking both the stability of the stacked blocks and the possibility of killing all the pigs with the given amount of birds. These two components are handled by the algorithm through a simulation. The first one is calculated by measuring the overall velocity of the blocks and the second is defined by an intelligent agent, which plays the levels. Three sets of experiments are conducted to evaluate Tanager. The first one measures the performance of the genetic algorithm underneath Tanager. The second one explores the expressivity of the generated levels considering their structural characteristics. The third one measures design quality of levels via an online user study. Results show that Tanager is capable of generating a considerable variety of feasible levels that are as engaging and enjoyable as those manually designed. However, the generated levels are less challenging than the hand-authored ones.

The present paper describes an embedded system architecture, based on genetic algorithms, aiming safety mission execution by Unmanned Aerial Vehicles (UAVs). A two-dimensional non-convex environment is considered since obstacle avoidance happens. The embedded system integrates the Mission Oriented Sensor Array (MOSA) and In-Flight Awareness (IFA) systems, where MOSA is responsible for mission accomplishment and IFA stands for flight safety. The features of MOSA and IFA are combined under a platform that applies promising genetic algorithm approaches from literature to reach their goals. First, the genetic algorithms performance running from the embedded system is compared against their performance on a personal computer architecture. Next, the proposed system is evaluated in a real-world scenario using Software-In-The-Loop (SITL) technique. The computational results showed that the embedded system provides reliable results.

The present paper evaluates some strategies to apply path re-planning algorithms for emergency landing of Unmanned Aerial Vehicles (UAVs). The strategies proposed are based on executing only one path re-planning algorithm or a combination of them using an ensemble approach. The proposed methods are integrated to the security supervision system of the UAV, namely In-Fly Awareness (IFA), where decision-making algorithms are applying after a critical situation happens. The critical situations considered are battery overheating and engine failure. The performance of the proposed strategies for emergency landing is evaluated in a real world scenario using the Software-In-The-Loop (SITL) technique. Computational results reported show that these strategies are promising based on the success rate to land the UAV safely.

This paper addresses the Vehicle Routing Problem with Time Windows (VRPTW). A crossover operator which uses the information gathered by a clustering procedure is described. In the proposed approach, a hierarchical clustering procedure is applied to the customers' spatial data. The crossover procedure creates a new solution by removing and reinserting customers and uses the clusters to identify the most promising reinsertion locations. Thus, the proposed operator avoids exhaustive search. Computational experiments show the effectiveness of the proposed operator, that produces competitive solutions and improves the overall performance of the evolutionary algorithm when compared against an approach based on exhaustive search.

In the path planning problem for autonomous mobile robots, robots have to plan their path from the start position to the goal. In this paper, we investigate the application of the MMAS algorithm to the exploratory path planning problem, in which the robots should explore the environment at the same time they plan the path. Max-min ant system is an ant colony optimization algorithm that exploits the best solutions found. In addition, to analyze the quality of solutions obtained, we also analyze the traveled distance spent by robots in the first iteration of the algorithm. The environment is previously unknown to the robots, although it is represented by a topological map, that does not require precise information from the environment and provides a simple way to execute the navigation of the path. Thus, the paths are represented by a sequence of actions that the robots should execute to reach the goal. The navigation of the best solution found was implemented in a realistic robotic simulator. The proposed algorithm provides a very good performance in relation to a genetic algorithm and the well-known A∗ algorithm that deal with this problem.

This paper proposes a hybrid method to define a path planning for unmanned aerial vehicles in a non-convex environment with uncertainties. The environment becomes non-convex by the presence of no-fly zones such as mountains, cities and airports. Due to the uncertainties related to the path planning in real situations, risk of collision can not be avoided. Therefore, the planner must take into account a lower level of risk than one tolerated by the user. The proposed hybrid method combines a multi-population genetic algorithm with visibility graph. This is done by encoding all possible paths as individuals and solving a linear programming model to define the full path to be executed by the aircraft. The hybrid method is evaluated from a set of 50 maps and compared against an exact and heuristic approaches with promising results reported.

Procedural content generation (PCG) systems are designed to automatically generate content for video games. PCG for physics-based puzzles requires one to simulate the game to ensure feasibility and stability of the objects composing the puzzle. The major drawback of this simulation-based approach is the overall running time of the PCG process, as the simulations can be computationally expensive. This paper introduces a method that uses machine learning to reduce the number of simulations performed by an evolutionary approach while generating levels of Angry Birds, a physics-based puzzle game. Our method uses classifiers to verify the stability and feasibility of the levels considered during search. The fitness function is computed only for levels that are classified as stable and feasible. An approximation of the fitness that does not require simulations is used for levels that are deemed as unstable or unfeasible by the classifiers. Our experiments show that naively approximating the fitness values can lead to poor solutions. We then introduce an approach in which the fitness values are approximated with the average fitness value of the levels' parents added to a penalty value. This approximation scheme allows the search procedure to find good-quality solutions much more quickly than a competing approach-we reduce from 43 to 25 minutes the running time required to generate one level of Angry Birds.

This paper presents a novel Hybrid Genetic Algorithm (HGA) for image denoising, whose main purpose is to restore images while preserving relevant information, for instance, texture and edges. The proposed method combines operators available in existing evolutionary methods, such as crossover, mutation and population reinitialization with some state-of-the-art image denoising methods. Experiments are conducted on a set of noise contaminated images commonly used by the scientific community as benchmark, where different levels of noise are applied to the images. The results achieved by the proposed method are compared against image denoising methods. The HGA performance demonstrated to be very effective and competitive, outperforming other approaches in several levels of noise.

The path planning task for mobile robots consists of define a trajectory to the robot leaves its start position and reach its goal without to collide with obstacles. In general, the robot needs to know previous information about the environment (e.g. maps, predefined routes) to plan its trajectory. In an exploration task, the robot does not know the environment and discovers it when moving to reach the goal coordinates. In this paper, an exploratory path planning aiming to reach a goal position is studied and a new method based on genetic algorithm, topological environment representation and realistic robot actions is proposed. In this method, the robots execute a sequence of reliable local actions (simple reactive behaviors) to move through the unknown environment, adopting a topological environment representation. They plan the path at the same time the environment is explored, in which the genetic algorithm evolves the sequence of actions to be executed. The results show that the squad of robots (GA population) reach the goal faster than an individual search. The proposed approach deal with environment traps better than the classical search A* algorithm and a variation of the A*, named C*, here also introduced.

This paper studies the path planning for Unmanned Aerial Vehicles (UAVs) under critical situations, where the aircraft has to execute a hard landing. Such critical situations can be provoked by equipment failures or extreme environmental situations that demand the UAV to abort the mission running and to land the aircraft without risk for people, properties and itself. First, a mathematical formulation is introduced to describe this problem. A planner system is proposed based on a multi-population genetic algorithm and a greedy heuristic. Computational results are conducted over a large set of scenarios with different levels of difficulty. Also, some simulations are executed using FlightGear simulator to illustrate the UAV's behaviour when landing under different wind velocities. The results achieved indicate the greedy heuristic is able to define faster feasible landing paths, whose quality can be improved by the evolutionary approach always within a short computation time.

This paper presents an estimation of distribution algorithm (EDA) to generate levels for physics-based puzzle games with the Angry Birds mechanics. The proposed EDA keeps three probability tables during its evolutionary process to sample new individuals that encode informations about the amount and placement of game objects inside the level. Sampled individuals are evaluated by a simulation-based fitness function, which considers the stability and the amount of the game objects inserted in a level. The best individual sampled from the probability tables is used to update them. Experiments indicated that the proposed EDA was capable of creating stable structures related to the Angry Bird gameplay.

The development of Wireless Sensor Networks (WSNs) applications is an arduous task, since the application needs to be customized for each sensor. Thus, the automatic generation of WSN's applications is desirable to reduce costs, since it drastically reduces the human effort. This paper presents the use of Genetic Programming to automatically generate WSNs applications. A scripting language based on events and actions is proposed to represent the WSN behavior. Events represent the state of a given sensor node and actions modify these states. Some events are internal states and others are external states captured by the sensors. The genetic programming is used to automatically generate WSNs applications described using this scripting language. These scripts are executed by all network's sensors. This approach enables the application designer to define only the overall objective of the WSN. This objective is defined by means of a fitness function. An event-detection problem is presented in order to evaluate the proposed method. The results shown the capability of the developed approach to successfully solve WSNs problems through the automatic generation of applications.

The present paper solves the multi-level capacitated lot sizing problem with backlogging (MLCLSPB) combining a genetic algorithm with the solution of mixed-integer programming models and the improvement heuristic fix and optimize. This approach is evaluated over sets of benchmark instances and compared to methods from literature. Computational results indicate competitive results applying the proposed method when compared with other literature approaches.

Digital images play an essential role in analysis tasks with applications in various knowledge domains, such as medicine, meteorology, geology, biology, among others. Such images can be degraded by noise during the process of acquisition, transmission, storage or compression. Although several image denoising methods have been proposed in the literature, noise suppression in images still remains a challenging problem for researchers since the process can cause the removal of relevant image features, such as edges and corners. This papers describes a novel image denoising method based on a genetic algorithm. A population of noisy images is evolved for several epochs applying tailor-made crossover and mutation operators. The population is reinitialized every time a convergence occurs, when only the best individual (image) is kept for the next epoch. Experimental results demonstrate that the proposed method is competitive in comparison with state-of-the-art approaches.

The development of Wireless Sensor Networks (WSNs) applications is an arduous task, since the developer has to design the behavior of the nodes and their interactions. The automatic generation of WSN's applications is desirable to reduce costs, since it drastically reduces the human effort. This paper presents the use of Genetic Programming to automatically generate WSNs applications. A scripting language based on events and actions is proposed to represent the WSN behavior. Events represent the state of a given sensor node and actions modify these states. Some events are internal states and others are external states captured by the sensors. A parallel genetic algorithm is used to automatically generate WSNs applications in this scripting language. These scripts are executed by a middleware installed on all sensors nodes. This approach enables the application designer to define only the overall objective of the WSN. This objective is defined by means of a fitness function. An event-detection problem is presented in order to evaluate the proposed method. The results showed the capability of the developed approach to successfully solve WSNs problems through the automatic generation of applications.

The present paper applies a multi-population genetic algorithm (MPGA) to the Proportional, Integral and Derivative (PID) controller tuning problem. Two control criteria were optimized, the integral of the time multiplied by the absolute error (ITAE), and the integral of the time multiplied by the absolute output (ITAY). The MPGA is compared with a standard genetic algorithms (SGA) already applied to the same control model. The control criteria are supplied by neural networks (NN) previously trained for this purpose. The control tuning and the corresponding responses were obtained using the MATLAB/SIMULNK environment. The computational results show a superior performance of the MPGA even when compared with the exact values found by dynamic simulation using gradient techniques.

This paper presents preliminary results found by a hybrid heuristic applied to solve the Multi-Level Capacitated Lot Sizing Problem (MLCLSP). The proposed method combines a multi-population genetic algorithm and flx-and-optimize heuristic. These methods are also integrated to a mathematical programming approach. For this, a mathematical reformulation of MLCLSP model is proposed to embed the exact solution of the model in the heuristic approaches. The hybrid heuristic is evaluated in two sets of benchmark instances. The solutions found are compared with those reached by other methods from literature. The preliminary results obtained indicate that the hybrid heuristic outperforms other approaches in the majority of problems solved.

This paper proposes a tabu search approach to solve the Synchronized and Integrated Two-Level Lot Sizing and Scheduling Problem (SITLSP). It is a real-world problem, often found in soft drink companies, where the production process has two integrated levels with decisions concerning raw material storage and soft drink bottling. Lot sizing and scheduling of raw materials in tanks and products in bottling lines must be simultaneously determined. Real data provided by a soft drink company is used to make comparisons with a previous genetic algorithm. Computational results have demonstrated that tabu search outperformed genetic algorithm in all instances. Copyright 2011 ACM.

The present paper evaluates meta-heuristic approaches to solve a soft drink industry problem. This problem is motivated by a real situation found in soft drink companies, where the lot sizing and scheduling of raw materials in tanks and products in lines must be simultaneously determined. Tabu search, threshold accepting and genetic algorithms are used as procedures to solve the problem at hand. The methods are evaluated with a set of instance already available for this problem. This paper also proposes a new set of complex instances. The computational results comparing these approaches are reported.

This paper proposes two evolutionary approaches as procedures to solve the Synchronized and Integrated Two-Level Lot-Sizing and Scheduling Problem (SITLSP). This problem can be found in some industrial settings, mainly soft drink companies, where the production process involves two interdependent levels with decisions concerning raw material storage and soft drink bottling. The first approach to solve the SITLSP is a Multi-Population Genetic Algorithm (GA) with a hierarchical ternary tree structure for populations. The second approach is a Memetic Algorithm (MA) that extends the GA approach through the inclusion of a local search procedure. The computational study reported reveals that those methods are an effective alternative to solve real-world instances of the SITLSP.