Search

The lot-sizing problem aims at determining the products to be produced and their quantities for each time period, which is a difficult problem in production planning. This problem becomes even more complicated when practical aspects such as limited production capacity, bill of materials, and item substitution are considered. In this paper, we study a new variant of the lot-sizing problem, called the multi-level capacitated lot-sizing problem with substitution and backorder. Unlike previous studies, this variant considers substitutions at both the product and component levels, which is based on the real needs of manufacturers to increase planning flexibility. Backorders are allowed, but should be delivered within a certain time limitation. We formulate this problem using a mathematical programming model. A matheuristic approach is proposed to solve the problem. This first generates an initial feasible solution using a relax-and-fix algorithm, and then improves it using a hybrid fix-and-optimise algorithm. The proposed algorithm is calibrated with a full factorial design of experiments, and its efficiency is well validated. Finally, through extensive numerical experiments, we analyse the properties of this new lot-sizing problem, such as the effect of substitution options, and the influence of backorder time limitation, and provide several useful managerial insights for manufacturing companies to save costs in production planning. [ABSTRACT FROM AUTHOR]

This paper considers the multi-vehicle production routeing problem with a maximum-level replenishment policy. This is a well-established problem within vendor managed inventory where production, inventory and routeing decisions are made simultaneously. We present a novel method to solve the problem that outperforms existing methods both in terms of solution gaps and the number of best-known solutions. The proposed matheuristic is tested on three different sets of benchmark instances consisting of 1218 instances and finds or improves the best-known solution for 632 of them. For the remaining instances, the matheuristic is less than 2.5% from the best-known solutions. The method is particularly proficient on large instances and is also efficient for the inventory routeing problem. The success of the method is largely due to its improvement phase where a novel path-flow-inspired mathematical model is introduced. Here, a route set obtained from the current solution is used and retailers can be simultaneously inserted and removed from a route, making the method flexible even when a small route set is used. In addition, we introduce a new production subproblem that approximates the costs of using a vehicle instead of approximating the costs of visiting a retailer, making it very fast to solve. [ABSTRACT FROM AUTHOR]

Multi-variety and small-batch production mode enables manufacturing industries to expeditiously satisfy customers' personalised demands, where a large amount of identical jobs can be split into several sublots, and be processed by reconfigurable machines with multiple machining technics. However, such highly flexible manufacturing environments bring some intractable problems to the production scheduling. Mathematical programming and meta-heuristic methods become less efficient when a scheduling problem contains both discrete and continuous optimisation attributes. Therefore, matheuristic, which combines advantages of the two methodologies, is regarded as a promising solution. This paper investigates a flexible job shop scheduling problem with lot-streaming and machine reconfigurations (FJSP-LSMR) for the total weighted tardiness minimisation. First, a monolithic mixed integer linear programming (MILP) model is established for the FJSP-LSMR. Afterwards, a matheuristic method with a variable neighbourhood search component (MH-VNS) is developed to address the problem. The MH-VNS adopts the classical genetic algorithm (GA) as the framework, and introduces two MILP-based lot-streaming optimisation strategies, LSO1 and LSO2, to improve lot-sizing plans with varying degrees. Four groups of instances are extended from the well-known Fdata benchmark to evaluate the performance of proposed MILP model, LSO1 and LSO2 components, and MH-VNS. Numerical experimental results suggest that LSO1 and LSO2 are efficient in different scenarios, and the proposed MH-VNS can well balance the solution quality and computational costs for reasonably integrating the GA- and MILP-based local search strategies. In addition, a complicated FJSP-LSMR case is abstracted from a real-world shop floor for processing large-sized structural parts to further validate the MH-VNS. [ABSTRACT FROM AUTHOR]

The paper addresses the green sequencing and routing problem, which consists in determining the best sequence of locations to visit within a warehouse for storing and/or retrieval operations, using a fleet composed of both electric vehicles, e.g., equipped with a lithium-ion battery, and conventional vehicles, i.e., with an internal combustion engine. We present a Mixed-Integer Linear Programming formulation to the problem and propose two matheuristics based on suitable decompositions of the mathematical formulation. The two matheuristics have been tested on a pool of small-medium size instances and their performance has been compared to the one of a third matheuristic, previously proposed for the case of conventional vehicles only and here suitable extended to deal with the green aspects of the problem. The performed analysis allowed one to identify the most promising matheuristic in terms of some standard computational indicators, i.e., computing time and percentage optimality gap, as well as in terms of some qualitative aspects of the solutions agreed with a reference company. Such a most promising algorithm has then been further tested to gather some technical insights on what makes the problem hard to solve, as well as to outline some managerial insights. Moreover, its performance has been tested on a pool of real instances comprising ordinary days (with a usual amount of operations to perform) and extremely busy days, showing its efficacy and efficiency also in the considered real application context. [ABSTRACT FROM AUTHOR]

In this paper, we present a heuristic for the non‐unicost set covering problem using local branching. Local branching eliminates the need to define a problem specific search neighbourhood for any particular (zero‐one) optimisation problem. It does this by incorporating a generalised Hamming distance neighbourhood into the problem, and this leads naturally to an appropriate neighbourhood search procedure. We apply our approach to the non‐unicost set covering problem. Computational results are presented for 65 test problems that have been widely considered in the literature. Our results indicate that our heuristic is better than six of the eight other heuristics we examined, slightly worse than that of one heuristic, but that there is a single heuristic that outperforms all others. We believe that the work described here illustrates that the potential for using local branching, operating as a stand‐alone matheuristic, has not been fully exploited in the literature. [ABSTRACT FROM AUTHOR]

The Single Source Capacitated Facility Location Problem (SSCFLP) consists of determining locations for facilities to meet customer demands so that each customer must be served by a single facility. This paper proposes a matheuristic algorithm for solving large-scale SSCFLP instances that combines neighborhood-based heuristic procedures with the solution of two binary linear programming sub-problems through a general-purpose solver. The proposed algorithm starts from the optimal solution of the linear relaxation of the SSCFLP to reduce its size and identify promising potential locations for opening facilities. Computational experiments were performed on two benchmark sets of large instances. For one of them, the developed algorithm obtained optimal solutions for all instances. For the other set, it provided average relative deviations slightly lower than those of three relevant algorithms from the literature. These results allow us to conclude that the proposed algorithm generates good-quality solutions and is competitive in solving large-scale SSCFLP instances. [ABSTRACT FROM AUTHOR]

Warehouses are key elements of supply chain networks, and great attention is paid to increase their efficiency. Highly volatile space requirements are enablers of innovative resource sharing concepts, where warehouse capacities are traded on online platforms. In this context, our paper introduces the on-demand warehousing problem from the perspective of platform providers. The objective prioritises demand-supply matching with maximisation of the number of transactions. If there is a tie, the secondary objective maximises the number of suppliers matched with at least one customer and the number of customers that have matches within a specific threshold with respect to the minimum achievable cost. Besides the mathematical integer programming formulation, a myopic list-based heuristic and an efficient matheuristic approach are presented and benchmarked against the performance of a commercial optimisation solver. The impact of several parameters on the platform's objective is analysed. A particularly relevant finding is that the pricing flexibility on the demand side does not necessarily imply higher payments to the supply side. All data instances are made available publicly to encourage more researchers to work on this timely and challenging topic. [ABSTRACT FROM AUTHOR]

The past few years of the COVID‐19 pandemic outbreak have shown that optimal management of medical specimens is a key aspect of healthcare logistics, both for addressing the delivery of perishable items such as vaccines, and for ensuring the timely analysis of swabs and samples. Accordingly, recent optimization literature described the problem of optimal collection and delivery of medical specimens, modeled as a multitrip vehicle routing problem with time windows and a completion time objective function. Aiming to achieve good‐quality solutions in short computational times, this work describes a hybrid approach, combining a matheuristic construction phase with an adaptive large neighborhood search (ALNS). Our matheuristic relies on a clustering algorithm to yield subsets of the medical specimens that are optimally served by single vehicles of the fleet. The solutions of the matheuristic phase serve as starting points for the ALNS intensification phase. Extensive experimentation on both new and established benchmark problem instances shows that our hybrid method is able to match the optimality of the state of the art on small instances and outperforms the existing exact method by one order of magnitude on larger problems. [ABSTRACT FROM AUTHOR]

The multi-mode resource constrained project scheduling problem (MRCPSP) is an NP-hard optimisation problem involving scheduling tasks under resource and precedence constraints, while there are several modes for executing each task. In this paper, we propose a novel matheuristic based on relax-and-solve (R &S) algorithm to solve MRCPSP. In addition, a mathematical programming model, which is the generalisation of the multi-dimensional knapsack problem is developed. That model conducts the mode selection process for the purpose of generating an initial feasible solution. We evaluate the performance of the proposed algorithm by solving benchmark instances that are widely used in the literature. The results demonstrate that the proposed R &S algorithm outperforms the state-of-the-art methods for solving the MRCPSP. [ABSTRACT FROM AUTHOR]

Production and inventory routing problems consider a single-product supply chain operating under a vendor-managed inventory system. A plant creates a production plan and vehicle routes over a planning horizon to replenish its customers at minimum cost. In this paper, we present two- and three-index formulations, implement a branch-and-cut algorithm based on each formulation, and introduce a local search matheuristic-based algorithm to solve the problem. In order to combine all benefits of each algorithm, we design a parallel framework to integrate all three fronts, called the three-front parallel branch-and-cut algorithm (3FP-B&C). We assess the performance of our method on well-known benchmark instances of the inventory routing problem (IRP) and the production routing problem (PRP). The results show that our 3FP-B&C outperforms by far other approaches from the literature. For the 956 feasible small-size IRP instances, our method proves optimality for 746, being the first exact algorithm to solve all instances with up to two vehicles. 3FP-B&C finds 949 best known solutions (BKS) with 153 new BKS (NBKS). For the large-size set, our method provides two new optimal solutions (OPT), and finds 82% of BKS, being 70% of NBKS for instances with up to five vehicles. This result is more than twice the number of BKS considering all heuristic methods from the literature combined. Finally, our 3FP-B&C finds the best lower bounds (BLB) for 1,169/1,316 instances, outperforming all previous exact algorithms. On the PRP, our method obtained 278 OPT out of the 336 instances of benchmark set of small- and medium-size instances being 19 new ones in addition to 335 BKS (74 NBKS) and 313 BLB (52 new ones). On another set of PRP with medium- and large-size instances, our algorithm finds 1,105 BKS out of 1,440 instances with 584 NBKS. Besides that, our 3FP-B&C is the first exact algorithm to solve the instances with an unlimited fleet, providing the first lower bounds for this subset with an average optimality gap of 0.61%. We also address a very large-size instance set, the second exact algorithm to address this set, outperforming the previous approach by far. Finally, a comparative analysis of each front shows the gains of the integrated approach. History: This paper has been accepted for the Transportation Science Special Issue: DIMACS Implementation Challenge: Vehicle Routing. Funding: C. M. Schenekemberg was supported by the São Paulo Research Foundation (FAPESP) [Grant 2020/07145-8]. A. A. Chaves was supported by FAPESP [Grants 2018/15417-8 and 2016/01860-1] and Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 312747/2021-7 and 405702/2021-3]. L. C. Coelho was supported by the Canadian Natural Sciences and Engineering Research Council [Grant 2019-00094]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0261. [ABSTRACT FROM AUTHOR]

The execution of a project is often distributed among multiple sites. The planning of such a project includes selecting a specific site for the execution of each of the project's activities and allocating the available resource units to the execution of these activities over time. While some resource units are available at a certain site only, others can be moved across sites. Given the spatial distance between sites, transportation times arise if a resource unit must be transported from one site to another or if the output of an activity must be transported to another site. This planning problem has been introduced in recent literature as the multi-site resource-constrained project scheduling problem. We present a continuous-time model and devise a matheuristic for this planning problem. The continuous-time model uses, among others, binary variables to impose a sequence between activities assigned to the same resource units. In the matheuristic, the binary restrictions on these variables are initially relaxed and iteratively restored for the subset of activities scheduled in the current iteration. We compare the performance of the continuous-time model and the matheuristic to the performance of a discrete-time model and several metaheuristics from the literature using two sets of test instances from the literature. Both the continuous-time model and the matheuristic derive on average superior solutions in shorter average running times than the reference approaches. [ABSTRACT FROM AUTHOR]

Planning petrol station replenishment is an important logistics activity for all the major oil companies. The studied Multi-Depot Periodic Petrol Station Replenishment problem derives from a real case in which the company must replenish a set of petrol stations from a set of depots, during a weekly planning horizon. The company must ensure refuelling according to available visiting patterns, which can be different from customer to customer. A visiting pattern predefines how many times (days) the replenishment occurs during a week and in which visiting days a certain amount of fuel must be delivered. To fulfill the weekly demand of each petrol station, one of the available replenishment plans must be selected among a given set of visiting patterns. The aim is to minimize the total distance travelled by the fleet of tank trucks during the entire planning horizon. A matheuristic approach is proposed, based on the cluster-first route-second paradigm, to solve it. The proposed approach is thoroughly tested on a set of realistic random instances. Finally, a weekly large real instance is considered with 194 petrol stations and two depots. [ABSTRACT FROM AUTHOR]

Steelmaking-Continuous Casting (SCC) is a bottleneck in the steel production process and its scheduling has become more challenging over time. In this paper, we provide an extensive literature review that highlights challenges in the SCC scheduling and compares existing solution methods. From the literature review, we collect the essential features of an SCC process, such as unrelated parallel machine environments, stage skipping, and maximum waiting time limits in between successive stages. We consider an SCC scheduling problem with as objective the minimisation of the weighted sum of cast break penalties, total waiting time, total earliness, and total tardiness. We formulate the problem as a mixed-integer linear programming model and develop an iterated greedy matheuristic that solves its subproblems to find a near-optimal solution. Through numerical experiments, we show that our algorithm outperforms two types of genetic algorithms when applied to test instances. [ABSTRACT FROM AUTHOR]

In this paper, the economic optimisation of cold storage is studied. A modern cold room is mainly composed of compressors, a tank to store heat-transfer fluid and cold rooms. The main cost is incurred by energy consumption and maintenance. The price of electricity, which is known in advance, varies during the day. Production schedules that entail higher risks of compressor wear, and thus high maintenance costs, have to be avoided. The temperature inside the cold rooms must be maintained within the allowed range, and complex thermodynamic processes make it difficult to predict temperature. The tank has a limited capacity. This paper presents the first model optimising the management cost of a cold store with a tank. Maintenance costs are considered for compressors, and Artificial Neural Networks are used to forecast the temperatures in the cold rooms. An optimal Dynamic Programme is designed for the case with one cold room and a matheuristic algorithm is presented for the general case with several cold rooms. A comparison with a classical hysteresis controller shows significant savings. The impact of storage capacity on operating costs is evaluated, after which the influence of the maintenance cost value is discussed. [ABSTRACT FROM AUTHOR]

The simple assembly line balancing problem (SALBP) considers work division among different workstations of a serially arranged assembly process to maximise its efficiency under workload (cumulative) and technological (precedence) constraints. In this work, we consider a variant of the SALBP which allows parallel workstations. To study the effect of parallel stations, we propose a new problem (the parallel station assembly line balancing problem or PSALBP) in which the objective is to minimise the number of parallel stations required to obtain the maximum theoretical efficiency of the assembly process. We study the complexity of the problem and identify a polynomially solvable case. This result is then used as a building block for the development of a heuristic solution procedure. Finally, we carry out a computational experiment to identify the characteristics of assembly lines that may benefit from station paralleling and to evaluate the performance of the proposed heuristic. [ABSTRACT FROM AUTHOR]

Capacitated lot sizing is a frequently encountered production-planning problem in manufacturing companies. However, many real life factors are usually not taken into account during the model development phase for these problems. In this study, an integrated lot-sizing and scheduling problem of a paper bag production firm is considered. A mixed integer mathematical programming model is proposed for modeling and solving the problem. Setup cost/time between product and period changes are considered in the proposed model. It is aimed to minimize the total cost of production, holding inventory, backorder, procurement and setup for product type change and product period change. It is observed that productive utilization of manufacturing resources and the generation of more effective production plans are possible by the application of the proposed model. [ABSTRACT FROM AUTHOR]

The Minimum Broadcast Time (MBT) is a well‐known data dissemination problem whose goal is to find a broadcast scheme that minimizes the number of steps needed to execute the broadcast operation. The problem has many applications in distributed systems and, in particular, the Industry 4.0 domain. Because Industry 4.0 applications rely primarily on the use of large‐scale machine to machine communications, they need data dissemination techniques that combine high reliability with low communication latency. This work proposes a Biased Random‐Key Genetic Algorithm and a matheuristic for the MBT. We carry out experiments with our algorithms on instances commonly used in the literature (hypercube, shuffle exchange, cube‐connected cycles, de Bruijn, Harary graphs), and also on massive synthetic instances (up to 1000 vertices), allowing to cover many possibilities of real industry topologies. Our proposal is also compared with state‐of‐the‐art exact methods and heuristics. Experimental results show that our algorithm is able to outperform the best‐known heuristics for the MBT, and also that it is a very good alternative for large instances that cannot be solved by current exact methods. [ABSTRACT FROM AUTHOR]

In the family traveling salesman problem (FTSP), there is a set of cities which are divided into a number of clusters called families. The salesman has to find a shortest possible tour visiting a specific number of cities from each of the families without any restriction of visiting one family before starting the visit of another one. In this work, the general concept of the Partial OPtimization Metaheuristic Under Special Intensification Conditions is linked with the exact optimization by a classical solver using a mathematical programming formulation for the FTSP to develop a matheuristic. Moreover, a genetic and a simulated annealing algorithm are used as metaheuristics embedded in the approach. The method is examined on a set of benchmark instances and its performance is favorably compared with a state-of-the-art approach from literature. Moreover, a careful analysis of the specific components of the approach is undertaken to provide insights into the impact of their interplay. [ABSTRACT FROM AUTHOR]

Every year, wildfires accentuated by global warming, cause economic and ecological losses, and often, human casualties. Increasing operational capacity of firefighter crews is of utmost importance to better face the forest fire period that yearly occurs. In this study, we investigate the real-world firefighters timetabling problem of the INFOCA institution, Andalusia (Spain). The main issue is to achieve maximum operational capability while taking into account work regulation constraints. This paper proposes an Integer Linear Programming (ILP) formulation that makes it feasible to solve small/medium instances to optimality. We put forward a matheuristic (ILPH) based on the ILP formulation, and we obtain solutions for larger instances. We propose an Adaptive Large Neighbourhood Search metaheuristic (ALNS) to obtain better results for larger instances and we use a version of the ILPH as one of the constructive methods. The ALNS obtains all the optimal solutions found by the ILP on small instances. It yields better solutions than the ILPH matheuristic on larger instances within shorter processing times. We report on experiments performed on datasets generated using real-world data of the INFOCA institution. The work was initiated as part of the GEO-SAFE project. [ABSTRACT FROM AUTHOR]

In this article, we present and solve the multi‐purpose K$$ K $$‐drones general routing problem (MP K$$ K $$‐DGRP). In this optimization problem, a fleet of multi‐purpose drones, aerial vehicles that can both make deliveries and conduct sensing activities (e.g., imaging), have to jointly visit a set of nodes to make deliveries and map one or more continuous areas. This problem is motivated by global healthcare applications that deploy multipurpose drones that combine delivery trips with collection of aerial imaging data for use in emergency preparedness and resilience planning. The continuous areas that have to be mapped may correspond to terrain surfaces (e.g., flooded areas or regions with a disease outbreak) or to infrastructure networks to be inspected. The continuous areas can be modeled as a set of lines so that each area is completely serviced if all the lines covering it are traversed. Thus, given a set of nodes and a set of lines, the problem is to design drone routes of shortest total duration traversing the lines and visiting the nodes, while not exceeding the range limit (flight time) and capacity (loading) of the drones. Unlike ground vehicles in classical routing problems, drones can enter a line through any of its points, service only a part of that line and then exit through another of its points. The possibility of flying directly between any two points of the network offered by drones can lead to reduced costs, but it increases the difficulty of the problem. To deal with this problem, the lines are discretized, allowing drones to enter and exit each line only at a finite set of points, thus obtaining an instance of the K$$ K $$‐vehicles general routing problem (K$$ K $$‐GRP). We present in this article an integer programming formulation for the K$$ K $$‐GRP and propose a matheuristic algorithm and a branch‐and‐cut procedure for its solution. Results are provided for problems with up to 20 deliveries and up to 28 continuous areas. [ABSTRACT FROM AUTHOR]

In this paper, we present the first Assignment-Dial-A-Ride problem motivated by a real-life problem faced by medico-social institutions in France. Every day, disabled people use ride-sharing services to go to an appropriate institution where they receive personal care. These institutions have to manage their staff to meet the demands of the people they receive. They have to solve three interconnected problems: the routing for the ride-sharing services; the assignment of disabled people to institutions; and the staff size in the institutions. We formulate a general Assignment-Dial-A-Ride problem to solve all three at the same time. We first present a matheuristic that iteratively generates routes using a large neighborhood search in which these routes are selected with a mixed integer linear program. After being validated on two special cases in the literature, the matheuristic is applied to real instances in three different areas in France. Several managerial results are derived. In particular, it is found that the amount of cost reduction induced by the people assignment is equivalent to the amount of cost reduction induced by the sharing of vehicles between institutions. [ABSTRACT FROM AUTHOR]

The paper deals with a sequencing and routing problem originated by a real-world application context. The problem consists in defining the best sequence of locations to visit within a warehouse for the storage and/or retrieval of a given set of items during a specified time horizon, where the storage/retrieval location of an item is given. Picking and put-away of items are simultaneously addressed, by also considering some specific requirements given by the layout design and operating policies which are typical in the kind of warehouses under study. Specifically, the considered sequencing policy prescribes that storage locations must be replenished or emptied one at a time by following a specified order of precedence. Moreover, two fleet of vehicles are used to perform retrieving and storing operations, whose routing is restricted to disjoint areas of the warehouse. We model the problem as a constrained multicommodity flow problem on a space-time network, and we propose two Mixed-Integer Linear Programming formulations, whose primary goal is to minimize the time traveled by the vehicles during the time horizon. Since large-size realistic instances are hardly solvable within the time limit commonly imposed in the considered application context, a matheuristic approach based on a time horizon decomposition is proposed. Finally, we provide an extensive experimental analysis aiming at identifying suitable parameter settings for the proposed approach, and testing the matheuristic on particularly hard realistic scenarios. The computational experiments show the efficacy and the efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]

Resource scheduling has been one of the most prominent problems due to its technical challenges and prevalence in real-life. In this paper, we focus on an extension of the parallel machine scheduling problem with additional resources, which can be classified as a static resource-constrained parallel machine scheduling problem with unspecified job-machine assignment. The novelty of the problem we tackle stems from the additional resource that consists of components with discrete levels. The allocation of this resource to machines induces general covering constraints. This distinct characteristic of the additional resource also arises in a real-life audit scheduling problem, in which local branches of a financial firm are to be audited by a set of auditors with different experience levels. The quantification of the auditor experience and the branch experience requirement enable us to model this problem as an extension of the aforementioned scheduling problem with extra constraints related to the auditing process. We propose mathematical models for these problems and two constructive heuristic algorithms. The upper bounds attained by these algorithms are improved by a tabu-search algorithm, and an efficient lower bounding technique is developed for comparative purposes. We conduct extensive computational experiments to assess the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

The classic version of the Inventory Routing Problem considers a system with one supplier that manages the inventory level of a set of customers. The supplier defines when and how much products to supply and how to combine customers in routes while minimising storage and transportation costs. We present a new version of this problem that considers a twoechelon system with indirect deliveries and routing decisions at both levels. In this variant, the products are delivered to customers through distribution centres to meet demands with a minimum total cost. We propose a mathematical formulation and a branch-and-cut algorithm combined with a two-step matheuristic to solve the proposed problem for different inventory policies and routing configurations. Intrinsic new valid inequalities to the two-echelon system are introduced. We analyse the efficiency of the new valid inequalities as well as the already known valid inequalities from the literature. Computational experiments are presented for a new set of benchmark instances. The results show that, for the simplest inventory policy, the proposed method is able to solve small and some medium-scale instances to the proven optimality and find feasible solutions for all instances. [ABSTRACT FROM AUTHOR]

This article proposes a framework for the integration of tactical and operational optimisation models for maintenance scheduling and routing at offshore windfarms. A tactical model is formulated to find the optimal schedule for preventive maintenance over a medium-term planning horizon (one month). The schedule is produced assuming a weather forecast for the entire planning horizon, which in practice will be uncertain. However, for each day, an operational maintenance routing model is solved to obtain optimal vessel routes with a one-day planning horizon, assuming an updated weather forecast for that day. In the operational routing model, the turbines scheduled for preventive maintenance are provided by the tactical scheduling model, whereas the turbines requiring corrective maintenance are provided by information about failures and alarms updated on a daily basis. In the case that the solution generated by the routing model contains turbines that cannot be maintained, the monthly maintenance activities are rescheduled by solving the tactical scheduling model considering the delayed activities. As the routing problem is too time consuming to solve exactly, we propose efficient matheuristic solution methods incorporating Variable Neighbourhood Search and an exact method. Computational experiments have been carried out to assess the performance of the tactical-operational framework. [ABSTRACT FROM AUTHOR]

Course timetables are the organizational foundation of a university's educational program. While students and lecturers perceive timetable quality individually according to their preferences, there are also collective criteria derived normatively such as balanced workloads or idle time avoidance. A recent challenge and opportunity in curriculum-based timetabling consists of customizing timetables with respect to individual student preferences and with respect to integrating online courses as part of modern course programs or in reaction to flexibility requirements as posed in pandemic situations. Curricula consisting of (large) lectures and (small) tutorials further open the possibility for optimizing not only the lecture and tutorial plan for all students but also the assignments of individual students to tutorial slots. In this paper, we develop a multi-level planning process for university timetabling: On the tactical level, a lecture and tutorial plan is determined for a set of study programs; on the operational level, individual timetables are generated for each student interlacing the lecture plan through a selection of tutorials from the tutorial plan favoring individual preferences. We utilize this mathematical-programming-based planning process as part of a matheuristic which implements a genetic algorithm in order to improve lecture plans, tutorial plans, and individual timetables so as to find an overall university program with well-balanced timetable performance criteria. Since the evaluation of the fitness function amounts to invoking the entire planning process, we additionally provide a proxy in the form of an artificial neural network metamodel. Computational results exhibit the procedure's capability of generating high quality schedules. [ABSTRACT FROM AUTHOR]

Large-neighbourhood search (LNS) heuristics are important mathematical programming techniques that search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. Extending such powerful generic LNS heuristics to the branch-and-price context is inherently challenging. The most prominent challenges arise from the fact that in branch-and-price algorithms, columns are generated with the sole aim to solve linear programming relaxations. Hence, the ability to form integer feasible solutions is not considered during the generation of columns. Without any changes to the standard pricing schemes, the potential of deploying generic LNS heuristics within a branch-and-price procedure is severely limited. This paper proposes a matheuristic, based on an LNS heuristic framework, where the novelty is a customised pricing scheme for generating columns to solve an auxiliary problem. The theoretical foundation for this pricing scheme is a set of optimality conditions for integer programs. From this foundation, a column generation strategy is developed for finding columns that are likely to be of use in high-quality primal feasible solutions for the original problem. The proposed matheuristic is implemented in the generic branch-price-and-cut solver GCG. On a broad test set comprising classical block diagonal structured instances and general instances from the MIPLIB 2017 Collection, the computational results show a significant improvement to the solving performance of GCG. [ABSTRACT FROM AUTHOR]

The Capacitated Facility Location Problem (CFLP) is a well-known optimisation problem with applications in a number of fields, such as distribution system planning, telecommunication network design, and supply chain design. The goal of this paper is to present a matheuristic algorithm based on the corridor method, to develop a general algorithm for a number of variants of the CFLP. The algorithm exploits solutions obtained via Lagrangean relaxation and builds corridors around such solutions via the introduction of constraints around the incumbent solution, used to limit the size of the solution space explored at each iteration. A thorough exploration of the neighbourhoods induced by the corridors is carried out using a mixed integer programming (MIP) solver. More precisely, we solve to (near) optimality over 500 benchmark instances, using the single-source as well as the multi-source formulations, both in the nominal variant, i.e. the deterministic version of the problem, and the robust variant, i.e. the version obtained when using robust optimisation to model the uncertainty of the problem parameters. The performance of the algorithm is highly competitive when compared with the best approaches proposed in the literature for each variant of the CFLP, especially considering that the algorithm has not been designed with a specific CFLP formulation in mind. [ABSTRACT FROM AUTHOR]

This survey paper provides an overview of current developments for the Portfolio Optimisation Problem (POP) based on articles published from 2018 to 2022. It reviews the latest solution methodologies utilised in addressing POPs in terms of mechanisms and performance. The methodologies are categorised as Metaheuristic, Mathematical Optimisation, Hybrid Approaches, Matheuristic and Machine Learning. The datasets (benchmark, real-world, and hypothetical) utilised in portfolio optimisation research are provided. The state-of-the-art methodologies for benchmark datasets are presented accordingly. Population-based metaheuristics are the most preferred techniques among researchers in addressing the POP. Hybrid approaches is an emerging trend (2018 onwards). The OR-Library is the most widely used benchmark dataset for researchers to compare their methodologies in addressing POP. The research challenges and opportunities are discussed. The summarisation of the published papers in this survey provides an insight to researchers in identifying emerging trends and gaps in this research area.

A number of research studies has addressed supply chain planning from various perspectives (strategical, tactical, operational) and demonstrated the advantages of integrating both production and distribution planning (PDP). The globalisation of supply chains and the fourth industrial revolution (Industry 4.0) mean that companies must be more agile and resilient to adapt to volatile demand, and to improve their relation with customers and suppliers. Hence the growing interest in coordinating production-distribution processes in supply chains. To deal with the new market's requirements and to adapt business processes to industry's regulations and changing conditions, more efforts should be made towards new methods that optimise PDP processes. This paper proposes a matheuristic approach for solving the PDP problem. Given the complexity of this problem, combining a genetic algorithm and a mixed integer linear programming model is proposed. The matheuristic algorithm was tested using the Coin-OR Branch & Cut open-source solver. The computational outcomes revealed that the presented matheuristic algorithm may be used to solve real sized problems. [ABSTRACT FROM AUTHOR]

Planning petrol station replenishment is an important logistics activity for all the major oil companies. The studied Multi-Depot Periodic Petrol Station Replenishment problem derives from a real case in which the company must replenish a set of petrol stations from a set of depots, during a weekly planning horizon. The company must ensure refuelling according to available visiting patterns, which can be different from customer to customer. A visiting pattern predefines how many times (days) the replenishment occurs during a week and in which visiting days a certain amount of fuel must be delivered. To fulfill the weekly demand of each petrol station, one of the available replenishment plans must be selected among a given set of visiting patterns. The aim is to minimize the total distance travelled by the fleet of tank trucks during the entire planning horizon. A matheuristic approach is proposed, based on the cluster-first route-second paradigm, to solve it. The proposed approach is thoroughly tested on a set of realistic random instances. Finally, a weekly large real instance is considered with 194 petrol stations and two depots.

Designing a public transport timetable that maximizes passenger service, measured in weighted travel time, is an intricate problem. The weighted travel time depends on the free route choice of passengers. Passenger route choice depends on the timetable. In turn, the timetable that minimizes weighted travel time depends on the route choice of passengers—and therefore requires passenger route choice information. Consequently, a sequential approach where timetables are designed provided pre-fixed passenger assignment to routes may not find the optimal timetable. This paper aims to integrate passenger route choice and timetabling. It addresses the problem of designing maximal passenger service public transport timetables in systems with free route choice within a budget for operating costs. Operating costs are defined by the minimal cost vehicle schedule required to operate the timetable. The proposed methodology integrates a matheuristic for timetabling and vehicle scheduling with a passenger assignment model in an iterative framework, where different forms of integration are evaluated. Focus is on long- to medium-term timetabling, provided an initial timetable. The results for a realistic case study in the Greater Copenhagen area indicate that our approach consistently leads, at no additional cost, to timetables that represent a reduction in passenger weighted travel time in comparison with both an initial timetable and a non-integrated timetabling method that receives a single-passenger assignment as input. [ABSTRACT FROM AUTHOR]

One of the most valuable and promising applications for Unmanned aerial vehicles (UAVs) is in natural disaster management, where these aircraft can operate autonomously without any need for human intervention during their flights. In this paper, we foster the interface of Operational Research with computer science in general and sensor networking in particular by focusing on managing a post-disaster emergency scenario where the use of a fleet of UAVs helps rescue teams identify people needing help inside an affected area. We model this situation as an original graph theoretical problem called Multi-Depot Multi-Trip Vehicle Routing Problem with Total Completion Time minimization (MDMT-VRP-TCT). The main novelty of the MDMT-VRP-TCT is the combination of the following three features: multi-depot, multi-trip, and completion time minimization. We propose a mixed-integer linear programming (MILP) formulation, develop a matheuristic framework to address large instances, and present an extended set of experiments to test the performance of the proposed matheuristic: first, we compare the matheuristic with the MILP formulation on a set of small instances (up to 30 nodes); then, we compare our matheuristic with two heuristics from networking literature, showing that it outperforms the existing algorithms. [ABSTRACT FROM AUTHOR]