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.
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 uncapacitated facility location problem (UFLP) is a popular NP‐hard optimization problem that has been traditionally applied to logistics and supply networks, where decisions are difficult to ...reverse. However, over the years, many new application domains have emerged, in which real‐time optimization is needed, such as Internet of Vehicles (IoV), virtual network functions placement, and network controller placement. IoV scenarios take into account the presence of multiple roadside units (RSUs) that should be frequently assigned to operating vehicles. To ensure the desired quality of service level, the allocation process needs to be carried out frequently and efficiently, as vehicles' demands change. In this dynamic environment, the mapping of vehicles to RSUs needs to be reoptimized periodically over time. Thus, this article proposes an agile optimization algorithm, which is tested using existing benchmark instances. The experiments show that it can efficiently generate high‐quality and real‐time results in dynamic IoV scenarios.
The multiperiod vehicle routing problem (MPVRP) is an extension of the vehicle routing problem in which customer demands have to be delivered in one of several consecutive time periods, for example, ...the days of a week. We introduce and explore a variant of the MPVRP in which the carrier offers a price discount in exchange for delivery flexibility. The carrier's goal is to minimize total costs, which consist of the distribution costs and the discounts paid. A biased‐randomized iterated local search algorithm is proposed for its solution. The two‐stage algorithm first quickly generates a number of promising customer‐to‐period assignments, and then intensively explores a subset of these assignments. An extensive computational study demonstrates the efficacy of the proposed algorithm and highlights the benefit of pricing for delivery flexibility in different settings.
•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.
This paper describes a ‘simheuristic’ algorithm – one which combines simulation with heuristics – for solving a stochastic variant of the well-known Inventory-Routing Problem. The variant discussed ...here is integrated by a vehicle routing problem and several inventory problems characterized by stochastic demands. Initial stock levels and potential stock-outs are also considered, as well as a set of alternative refill policies for each retail center. The goal is to find the personalized refill policies and associated routing plan that minimize, at each single period, the expected total costs of the system, i.e., the sum of inventory and routing costs. After motivating it, a detailed description of the problem is provided. Then, a review of the related literature is performed and our simulation–optimization approach is introduced. The paper presents a set of numerical experiments comparing the proposed method against different refill strategies and discusses how total costs evolve as the level of system uncertainty and the inventory-holding costs per unit are varied.
This paper discusses the two-dimensional loading capacitated vehicle routing problem (2L-CVRP) with heterogeneous fleet (2L-HFVRP). The 2L-CVRP can be found in many real-life situations related to ...the transportation of voluminous items where two-dimensional packing restrictions have to be considered, e.g.: transportation of heavy machinery, forklifts, professional cleaning equipment, etc. Here, we also consider a heterogeneous fleet of vehicles, comprising units of different capacities, sizes and fixed/variable costs. Despite the fact that heterogeneous fleets are quite ubiquitous in real-life scenarios, there is a lack of publications in the literature discussing the 2L-HFVRP. In particular, to the best of our knowledge no previous work discusses the non-oriented 2L-HFVRP, in which items are allowed to be rotated during the truck-loading process. After describing and motivating the problem, a literature review on related work is performed. Then, a multi-start algorithm based on biased randomization of routing and packing heuristics is proposed. A set of computational experiments contribute to illustrate the scope of our approach, as well as to show its efficiency.
The interplay between mutation and selection plays a fundamental role in the behavior of evolutionary algorithms (EAs). However, this interplay is still not completely understood. This paper presents ...a rigorous runtime analysis of a non-elitist population-based EA that uses the linear ranking selection mechanism. The analysis focuses on how the balance between parameter η, controlling the selection pressure in linear ranking, and parameter χ controlling the bit-wise mutation rate, impacts the runtime of the algorithm. The results point out situations where a correct balance between selection pressure and mutation rate is essential for finding the optimal solution in polynomial time. In particular, it is shown that there exist fitness functions which can only be solved in polynomial time if the ratio between parameters η and χ is within a narrow critical interval, and where a small change in this ratio can increase the runtime exponentially. Furthermore, it is shown quantitatively how the appropriate parameter choice depends on the characteristics of the fitness function. In addition to the original results on the runtime of EAs, this paper also introduces a very useful analytical tool, i.e., multi-type branching processes, to the runtime analysis of non-elitist population-based EAs.
Transportation, logistics, and supply chain systems and networks constitute one of the pillars of modern economies and societies. From sustainable traffic management in smart cities or air ...transportation to green and socially responsible logistics practices, many enterprises and governments around the world have to make decisions that affect the efficiency of these complex systems. Typically, optimization algorithms are employed to deal with these challenges, and simulation approaches are utilized when considering scenarios under uncertainty. However, better results might be achieved by hybridizing both optimization algorithms with simulation techniques to deal with real-life transportation, logistics, and SCM challenges, which often are large-scale and NP-hard problems under uncertainty conditions. Hence, simheuristic algorithms (combining metaheuristics with simulation) as well as other simulation optimization approaches constitute an effective way to support decision makers in such complex scenarios. This reprint presents a collection of selected articles on simulation optimization in transportation, logistics, and supply chain management. The reprint is strongly connected to the topics covered in the Winter Simulation Conference (WSC) track on logistics, transportation, and SCM, which includes a stream in simheuristic algorithms as well.
Green transportation is becoming relevant in the context of smart cities, where the use of electric vehicles represents a promising strategy to support sustainability policies. However the use of ...electric vehicles shows some drawbacks as well, such as their limited driving-range capacity. This paper analyses a realistic vehicle routing problem in which both driving-range constraints and stochastic travel times are considered. Thus, the main goal is to minimize the expected timebased cost required to complete the freight distribution plan. In order to design reliable routing plans, a simheuristic algorithm is proposed. It combines Monte Carlo simulation with a multi-start metaheuristic, which also employs biased-randomization techniques. By including simulation, simheuristics extend the capabilities of metaheuristics to deal with stochastic problems. A series of computational experiments are performed to test our solving approach as well as to analyse the effect of uncertainty on the routing plans.
PDF
