Epidemic outbreaks, such as the one generated by the coronavirus disease, have raised the need for more efficient healthcare logistics. One of the challenges that many governments have to face in ...such scenarios is the deployment of temporary medical facilities across a region with the purpose of providing medical services to their citizens. This work tackles this temporary-facility location and queuing problem with the goals of minimising costs, the expected completion time, population travel time, and waiting time. The completion time for a facility depends on the numbers assigned to those facilities as well as stochastic arrival times. This work proposes a learnheuristic algorithm to solve the facility location and population assignment problem. Firstly a machine learning algorithm is trained using data from a queuing model (simulation module). The learnheuristic then constructs solutions using the machine learning algorithm to rapidly evaluate decisions in terms of facility completion and population waiting times. The efficiency and quality of the algorithm is demonstrated by comparison with exact and simulation-only (simheuristic) methodologies. A series of experiments are performed which explore the trade-offs between solution cost, completion time, population travel time, and waiting time.
This work proposes a learnheuristic approach (combination of heuristics with machine learning) to solve an aerial-drone team orienteering problem. The goal is to maximise the total reward collected ...from information gathering or surveillance observations of a set of known targets within a fixed amount of time. The aerial drone team orienteering problem has the complicating feature that the travel times between targets depend on a drone’s flight path between previous targets. This path-dependence is caused by the aerial surveillance drones flying under the influence of air-resistance, gravity, and the laws of motion. Sharp turns slow drones down and the angle of ascent and air-resistance influence the acceleration a drone is capable of. The route dependence of inter-target travel times motivates the consideration of a learnheuristic approach, in which the prediction of travel times is outsourced to a machine learning algorithm. This work proposes an instance-based learning algorithm with interpolated predictions as the learning module. We show that a learnheuristic approach can lead to higher quality solutions in a shorter amount of time than those generated from an equivalent metaheuristic algorithm, an effect attributed to the search-diversity enhancing consequence of the online learning process.
•Introduction to the team orienteering problem for aerial drones with path dependent travel times.•Learnheuristic solution approach integrates metaheuristics and machine learning.•Learnheuristic approach is compared to metaheuristic and a priori learning methods.•Learnheuristic solution reduces solution time by two orders of magnitude.•Learnheuristic simultaneous learning and optimisation gives rise to emergent beneficial search diversity.
This paper considers an agri-food supply chain with a single fresh food supplier, who owns a central warehouse that serves several retail centers. Retail centers carry a certain amount of inventory ...of the fresh product, which is prone to deterioration. The supplier makes both inventory and routing decisions to minimize the inventory, transportation, food-waste, and stock-out costs in the face of stochastic customer demand and perishable products that need to be delivered to each retail center. This inventory routing problem is known as perishable inventory routing problem (PIRP) with stochastic demands in the literature. We model it using a mixed integer program and propose a simheuristic algorithm, which integrates Monte Carlo simulation within an iterated local search, to solve it. Our experiments show that the proposed algorithm can improve the initial solution with reasonable computational times. The resulting procedure is easy to implement and is applicable to other domains where a multi-period PIRP with stochastic demands may appear.
•The description of a multi-vehicle routing problem in interconnected networks.•The design, implementation, and testing of heuristic-based solving approaches.•A novel optimization heuristic based on ...concepts from discrete-event simulation.•A set of sustainability-based (socially and environmentally) considerations.•A set of benchmarks useful for testing other approaches for solving this problem.
Modern transport systems are not only large-scale but also highly dynamic, which makes it difficult to optimize by just employing classical methods. This paper analyzes a realistic and novel problem within the Physical Internet initiative which consists of container transportation throughout a spoke-hub network. Containers need to be transported from their origin locations to their final destinations on or before a given deadline, and they can be temporarily stored in network hubs. Each truck can move one container at a time from one hub to another, containers can be transported by different trucks during their path from their origin to their destination, and drivers need to be back at their starting points in due time. A deterministic heuristic, based on discrete-event simulation, is proposed as a first step to address the intrinsic dynamism of this time-evolving system. Then, in a second step, a biased-randomized version of this heuristic is incorporated into a multi-start framework (BR-MS) to generate better solutions. Next, our methodology is extended to a iterated local search (ILS) framework. Finally, a two-stage algorithm, combining both the BR-MS and the ILS frameworks is proposed. Several computational experiments have been carried out on a set of new benchmark instances, adapted from real road networks, to illustrate the problem and compare the performance of the different solving approaches.
The goal of the portfolio optimization problem is to minimize risk for an expected portfolio return by allocating weights to included assets. As the pool of investable assets grows, and additional ...constraints are imposed, the problem becomes NP-hard. Thus, metaheuristics are commonly employed for solving large instances of rich versions. However, metaheuristics do not fully account for random returns and noisy covariances, which renders them unrealistic in the presence of heightened uncertainty in financial markets. This paper aims to close this gap by proposing a simulation–optimization approach – specifically, a simheuristic algorithm that integrates a variable neighborhood search metaheuristic with Monte Carlo simulation – to deal with stochastic returns and noisy covariances modeled as random variables. Computational experiments performed on a well-established benchmark instance illustrate the advantages of our methodology and analyze how the solutions change in response to a varying degree of randomness, minimum required return, and probability of obtaining a return exceeding an investor-defined threshold.
Display omitted
•We employ a simheuristic algorithm to solve the stochastic portfolio optimization problem (SPOP).•The algorithm integrates a variable neighborhood search with Monte Carlo simulation.•Expected asset returns and return covariances are modeled as random variables.•The best stochastic solution to the SPOP has a lower risk than the best deterministic solution (BDS).•The BDS deteriorates when return covariances become more uncertain.
In the context of simulation-based optimisation, this paper reviews recent work related to the role of metaheuristics, matheuristics (combinations of exact optimisation methods with metaheuristics), ...simheuristics (hybridisation of simulation with metaheuristics), biased-randomised heuristics for ‘agile’ optimisation via parallel computing, and learnheuristics (combination of statistical/machine learning with metaheuristics) to deal with
NP-hard
and large-scale optimisation problems in areas such as transport and logistics, manufacturing and production, smart cities, telecommunication networks, finance and insurance, sustainable energy consumption, health care, military and defence, e-marketing, or bioinformatics. The manuscript provides the main related concepts and updated references that illustrate the applications of these hybrid optimisation–simulation–learning approaches in solving rich and real-life challenges under dynamic and uncertainty scenarios. A numerical analysis is also included to illustrate the benefits that these approaches can offer across different application fields. Finally, this work concludes by highlighting open research lines on the combination of these methodologies to extend the concept of simulation-based optimisation.
•This paper addresses Location Routing Problem with a Constrained Distance (LRPCD).•It is an extension of Location Routing Problem (LRP) in interest of greener transportation using Electric Vehicle ...(EV’s).•A mathematical programming model is suggested to formulate LRPCD.•A multi-start heuristic is developed utilizing biased-randomization and well-known Tillman’s heuristic which can generate good-quality solutions in almost real-time.•A more complete metaheuristic based on VNS and biased-randomization is employed which can produce better solutions in higher computational time.
The introduction of Electric Vehicles (EVs) in modern fleets facilitates a shift towards greener road transportation practices. However, the driving ranges of EVs are limited by the duration of their batteries, which raises some operational challenges. This paper discusses the Location Routing Problem with a Constrained Distance (LRPCD), which is a natural extension of the Location Routing Problem when EVs are utilized. A fast multi-start heuristic and a metaheuristic are proposed to solve the LRPCD. The former combines biased-randomization techniques with the well-known Tillman’s heuristic for the Multi-Depot Vehicle Routing Problem. The latter incorporates the biased-randomized approach into the Variable Neighborhood Search (VNS) framework. A series of computational experiments show that the multi-start heuristic is able to generate good-quality solutions in just a few seconds, while the biased-rendomized VNS metaheuristic provides higher-quality solutions by employing more computational time.
The two-dimensional vehicle routing problem (2L-VRP) is a realistic extension of the classical vehicle routing problem in which customers’ demands are composed by sets of non-stackable items. ...Examples can be found in real-life applications such as the transportation of furniture or industrial machinery. Often, it is necessary to consider stochastic travel times due to traffic conditions or customers availability. However, there is a lack of works discussing stochastic versions of the 2L-VRP. This paper offers a model of the 2L-VRP with stochastic travel times that also includes penalty costs generated by overtime. To solve this stochastic and non-smooth version of the 2L-VRP, a hybrid simheuristic algorithm is proposed. Our approach combines Monte Carlo simulation, an iterated local search framework, and biased-randomised routing and packing heuristics. Our algorithm is tested on an extensive benchmark, which extends the deterministic one for the 2L-VRP with unrestricted and non-oriented loading.
The Time Capacitated Arc Routing Problem (TCARP) extends the classical Capacitated Arc Routing Problem by considering time-based capacities instead of traditional loading capacities. In the TCARP, ...the costs associated with traversing and servicing arcs, as well as the vehicle’s capacity, are measured in time units. The increasing use of electric vehicles and unmanned aerial vehicles, which use batteries of limited duration, illustrates the importance of time-capacitated routing problems. In this paper, we consider the TCARP with stochastic demands, i.e.: the actual demands on each edge are random variables which specific values are only revealed once the vehicle traverses the arc. This variability affects the service times, which also become random variables. The main goal then is to find a routing plan that minimizes the expected total time required to service all customers. Since a maximum time capacity applies on each route, a penalty time-based cost arises whenever a route cannot be completed within that limit. In this paper, a strategic oscillation simheuristic algorithm is proposed to solve this stochastic problem. The performance of our algorithm is tested in a series of numerical experiments that extend the classical deterministic instances into stochastic ones.
•Time Capacitated Arc Routing Problem (TCARP) with Stochastic Demands.•A Simheuristic algorithm to solve the TCARP with Stochastic Demands.•Strategic Oscillation Simheuristic algorithm.
•A simulation-optimization approach for the single-period inventory routing problem with stock-outs.•Consideration of stochastic demands.•Description of a variable neighbourhood search metaheuristic ...for the inventory routing problem.•Establishment of personalized replenishment-strategies at all customers.•Risk-analysis of obtained results.
Vendor managed inventory aims at reducing supply chain costs by centralizing inventory management and vehicle routing decisions. This integrated supply chain approach results in a complex combinatorial optimization problem known as the inventory routing problem (IRP). This paper presents a variable neighborhood search metaheuristic hybridized with simulation to solve the IRP under demand uncertainty. Our simheuristic approach is able to solve large sized instances for the single period IRP with stochastic demands and stock-outs in very short computing times. A range of experiments underline the algorithm’s competitiveness compared to previously used heuristic approaches. The results are analyzed in order to provide closer managerial insights.
PDF
