The Capacitated Vehicle Routing Problem (CVRP) has been subject to intense research efforts for more than sixty years. Yet, significant algorithmic improvements are still being made. The most competitive heuristic solution algorithms of today utilize, and often combine, strategies and elements from evolutionary algorithms, local search, and ruin-and-recreate based large neighborhood search. In this paper we propose a new hybrid metaheuristic for the CVRP, where the education phase of the hybrid genetic search (HGS) algorithm proposed by (Vidal Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood 2020) is extended by applying large neighborhood search (LNS). By performing a series of computational experiments, we attempt to answer the following research questions: 1) Is it possible to gain performance by adding LNS as a component in the education phase of HGS? 2) How does the addition of LNS change the relative importance of the local search neighborhoods of HGS? 3) What is the effect of devoting computational efforts to the creation of an elite solution in the initial population of HGS? Through a set of computational experiments we answer these research questions, while at the same time obtaining a good configuration of global parameter settings for the proposed heuristic. Testing the heuristic on benchmark instances from the literature with limited computing time, it outperforms existing algorithms, both in terms of the final gap and the primal integral.
20 March 2019 in International Transactions in Operational Research
This paper studies operational planning and disruption management in offshore oil and gas logistics. A significant amount of time is currently spent on operational planning, and major costs are caused by disruptions to the planned routes and schedules for the vessels supplying the offshore installations. The disruptions are mainly due to uncertain and harsh weather conditions. To be able to solve realistic instances of the planning problem, a variable neighbourhood search heuristic is proposed, and tested on instances based on data provided by the case company. The computational results show that the heuristic finds optimal solutions for all the problem instances where the optimal solution is known, and finds high-quality solution for larger instances.
Background: Dual-level stochastic programming is a technique that allows modelling uncertainty at two different levels, even when the time granularity differs vastly between the levels. In this paper we study the problem of determining the optimal fleet size and mix of vessels performing maintenance operations at offshore wind farms. In this problem the strategic planning spans decades, while operational planning is performed on a day-to-day basis. Since the operational planning level must somehow be taken into account when making strategic plans, and since uncertainty is present at both levels, dual-level stochastic programming is suitable. Methods: We present a heuristic solution method for the problem based on the greedy randomized adaptive search procedure (GRASP). To evaluate the operational costs of a given fleet, a novel fleet deployment heuristic (FDH) is embedded into the GRASP. Results: Computational experiments show that the FDH produces near optimal solutions to the operational day-to-day fleet deployment problem. Comparing the GRASP to exact methods, it produces near optimal solutions for small instances, while significantly improving the primal solutions for larger instances, where the exact methods do not converge. Conclusions: The proposed heuristic is suitable for solving realistic instances, and produces near optimal solution in less than 2 h.
1 October 2018 in Journal of Physics: Conference Series
The offshore wind sector has achieved significant cost reductions in recent years. However, there is still work to be done to maintain and surpass these savings across current and future farms. There is increased competition to reduce costs within the industry itself. Additional challenges are foreseen at future sites located further from shore, in harsher conditions and deeper waters. Larger turbines and projects also mean new equipment, logistics and maintenance requirements. Moreover, farms are approaching the decommissioning phase where there is little experience. Modelling is a safe and cost-effective way to evaluate and optimise operations. However, there is a lack of comprehensive decision-support tools, detailed enough to provide insight into the effects of technological innovations and novel strategies. To address the gap, the EU FP7 LEANWIND project developed a suite of state-of-the-art logistics optimisation and financial simulation models. They can assess a farm scenario in detail at every stage of the project lifecycle and supply-chain, identifying potential cost reductions and more efficient strategies. This paper introduces the models including: an overview of their scope and capabilities; how they can be applied; and the potential end users.
21 December 2020 in INFOR: Information Systems and Operational Research
This paper studies the strategic problem of finding a cost optimal fleet of vessels to support maintenance operations at offshore wind farms. A dual-level stochastic model is formulated, taking into account both long-term strategic uncertainty and short-term operational uncertainty in a single optimization model. The model supports wind farm owners in making strategic decisions regarding the number, placement, charter length, and types of vessels to charter, to meet maintenance demands throughout the lifetime of a wind farm. To evaluate the quality of strategic fleet size and mix decisions, the model also considers the operational decisions of how to utilize the fleet to support maintenance operations. The model accounts for strategic uncertainties that have not been considered in previously developed optimization models for offshore wind, such as uncertainty related to long-term trends in electricity prices and subsidy levels, the stepwise development of wind farms, and technology development in the vessel industry. To solve the proposed stochastic programming model we have developed an ad hoc integer L-shaped method, with customized optimality cuts. The computational experiments show that the proposed method outperforms solving the deterministic equivalent using a commercial MIP solver.