Academic Publications

The high fuel prices and the important costs associated with windmill downtime during maintenance urge the need to minimize travel time and scheduling of jobs in a short time period. Since landing in windmills at sea is difficult and depends on meteorological parameters, the constraint of maintenance windows is added when searching for the optimal route. To minimize the distance traveled, the Vehicle Routing Problem with Time Windows (VRPTW) is solved, using three different methods. The VRPTW is applied to two separate databases, namely various sets of windmills to be maintained and several numbers of customers to be serviced. Applications with 8 to 175 windmills, divided over 3 farms have shown that the VRPTW solved by using three different methods resulted in a similar relative gain in travel distance, compared to a randomly chosen route. The main difference between the methods studied is the amount of calculation time needed, which varies from 1 second to 6 minutes for the different methods. To demonstrate the general applicability, the same three methods were executed on a set of service tasks performed at 8 to 40 customers of a window decoration company, distributed throughout Belgium, resulting in similar outcomes. In a second part of the paper, the Job Shop Scheduling Problem (JSSP) is solved to minimize the total maintenance span of offshore windmills as an additional objective function. This led to a relative gain of up to 62% in maintenance time, compared to the total maximum maintenance span for an application of 40 windmills. Finally, both objectives, minimal distance and minimal maintenance time span, are combined, resulting in a set of non-dominated maintenance sequences that can be used by the planner.

Keywords: VRPTW, VRPy, OR Tools, ACO, Job Shop Scheduling, Pareto.

[PDF]

Mathematical models can be classified into groups using various criteria: discrete, continuous, linear, non-linear, etc. Different model types also dominate in different research domains. Linear and non-linear optimization models prevail the realm of operations research. Dynamical models such as differential equations, appear more in physics and engineering. Statistical models and models treating uncertainty (p.e. stochastic models, fuzzy models) occur in social sciences. This is not to say that physicists do not use statistics. However, the various research domain use a slightly different vocabulary in building their models.

Coming from the operations research, a lot of attention is given to the classification in this research field. Several model types are formulated in mathematical notation and in the modeling system LPL. They are compared with each other from various point of views. Concrete model application examples are given for most model type.

[PDF]

The Mobile Robot Search Problem (MRSP) is a task of searching for an object in a priory known environment. The location of the object is not known. The goal is to find a trajectory that minimizes the expected time to find the object. The discretized variant of the problem can be viewed as a graph theory problem. This thesis approaches the task by representing the MRSP as a novel combinatorial optimization problem named the Generalized Graph Search Problem (GSP) with orderdependent weights, which combines the Generalized Traveling Salesman Problem (GTSP) and the GSP. The novel problem can be tackled by modifying GLNS, a solver designed for solving the GTSP using metaheuristic concepts Adaptive Large Neighborhood Search and Simulated Annealing. With proposed modifications, the solver is able to efficiently solve the Generalized GSP with orderdependent weights, as we demonstrate in the experimental evaluation.

Keywords: Metaheuristics, Graph Search Problem, Traveling Deliveryman Problem, Generalized Traveling Salesman Problem.

[PDF]

This article investigates a static on-demand transportation problem in which users are picked up and dropped off at existing bus stops. Specifically, the selection of bus stops for each request, along with the bus routes, is simultaneously determined by the booking system using an optimization algorithm. We focus on service quality by lexicographically minimizing passenger travel time (including both walking time and time spent on the bus) and total route length. We introduce a new matheuristic algorithm based on small and large neighborhood search, incorporating state-of-the-art operators and a set covering component. This algorithm outperforms previous approaches by reducing the user ride time by over 24% and shows good performance on related problems benchmarks. The algorithm is tested on a new set of instances, based on real data from New York City, which we propose as a future benchmark. Additionally, we discuss implementation details for decision-makers and practitioners.

Keywords: On-Demand Transportation Problem, Public Bus System, Stop Assignment, Small and Large Neighborhood Search, Set Covering.

[SOURCE] [PDF]

The Pickup and Delivery Problem with Time Windows (PDPTW) involves optimizing routes for vehicles to meet pickup and delivery requests within specific time constraints, a challenge commonly faced in logistics and transportation. Microtransit, a flexible and demand-responsive service using smaller vehicles within defined zones, can be effectively modeled as a PDPTW. Yet, the need for driver breaks—a key human constraint—is frequently overlooked in PDPTW solutions, despite being necessary for regulatory compliance. This study presents a novel mixed-integer linear programming formulation for the Pickup and Delivery Problem with Time Windows and Driver Breaks (PDPTW-DB). To the best of our knowledge this formulation is the first to consider mandatory periodic driver breaks within optimized Microtransit routes. The proposed model incorporates regulatory compliant break scheduling directly within the vehicle routing optimization framework. By considering driver break requirements as an integral component of the optimization process, rather than as a post-processing step, the model enables the generation of routes that respect hours of service regulations while minimizing operational costs. This integrated approach facilitates the generation of schedules that are operationally efficient and prioritize driver welfare through driver breaks.We work with a public transit agency from the southern USA, and highlight the specific nuances of driver break optimization, and present a Pickup and Delivery Problem with Time Windows formulation for optimizing Microtransit operations and scheduling driver breaks. We validate our approach using real-world data from the transit agency. Our results validate our formulation in producing cost-effective, and regulation-compliant solutions.

Keywords: Microtransit, Vehicular Networks, Pickup and Delivery Problem with Time Windows, Driver Breaks, MILP, Optimization.

[SOURCE] [PDF]

Roadside collection of hazardous and textile waste is a time-consuming and recurring task, that must be completed as fast as possible, to minimize the risk of removal or opening by unauthorized persons. The collections are currently planned and carried out manually, and with local knowledge, by the utility company Nyborg Forsyning & Service A/S in Eastern Funen.

In this project it is attempted to accelerate the collections by modelling the waste collection problem as a multi-compartment capacitated vehicle routing problem. The project is focused on delivering a solution to the utility company, that can produce efficient collection routes, by using existing open-source software and solvers, to reduce the time spent on the collections.

It is shown that the solver PyVRP produces better solutions than other comparable open-source and commercial solvers across four synthetically generated datasets based on real-life data. A rough estimate is given showing that the company can save a half to a full day of time on the collection of the largest dataset, if the proposed solution is used. Future research should investigate the possibilities of implementing automatic timetabling for the collections, and explore whether the time it takes to complete the collections can be estimated more accurately.

[PDF]

In constraint-based local search, an assignment to the search variables is improved upon by an iterative procedure that replaces the current assignment with a similar assignment. The latter is selected by a heuristic that assesses the qualities of a subset of all similar assignments, where the quality of such assignments is determined via a process called invariant graph propagation. Since, typically, many similar assignments are considered in every iteration, invariant graph propagation must be as efficient as possible. Since invariant graph propagation is independent of the selection heuristic, any comparison between different invariant graph propagation styles under different selection heuristics can be misleading. In this paper, we describe and compare both theoretically and empirically the throughput of several invariant graph propagation styles, and give criteria when one style or another is to be used.

[SOURCE] [PDF]

This thesis deals with evaluating the effectiveness of the Hexaly Optimizer solver developed by Hexaly. Its performance has been examined on selected multi-goal problems, such as the Traveling deliveryman problem, the Graph search problem, the Generalized traveling salesman problem, and the
Generalized graph search problem. The results were compared with the outputs of advanced existing solvers such as Ms-GVNS, GILS-RVND, and GLNS. The accuracy of the solutions was recorded in tables and graphs to compare the effectiveness of Hexaly Optimizer and other solvers.

Keywords: Hexaly Optimizer, Traveling Deliveryman Problem, Graph Search Problem, Generalized Traveling Salesman Problem, Generalized Graph Search Problem.

[PDF]

We introduce CVQBoost, a novel classification algorithm that leverages early hardware implementing Quantum Computing Inc’s Entropy Quantum Computing (EQC) paradigm, Dirac-3 [Nguyen et. al. arXiv:2407.04512]. We apply CVQBoost to a fraud detection test case and benchmark its performance against XGBoost, a widely utilized ML method. Running on Dirac-3, CVQBoost demonstrates a significant runtime advantage over XGBoost, which we evaluate on highperformance hardware comprising up to 48 CPUs and four NVIDIA L4 GPUs using the RAPIDS AI framework. Our results show that CVQBoost maintains competitive accuracy (measured by AUC) while significantly reducing training time, particularly as dataset size and feature complexity increase. To assess scalability, we extend our study to large synthetic datasets ranging from 1M to 70M samples, demonstrating that CVQBoost on Dirac-3 is well-suited for large-scale classification tasks. These findings position CVQBoost as a promising alternative to gradient boosting methods, offering superior scalability and efficiency for high-dimensional ML applications such as fraud detection.

[PDF]

The resource-constrained project scheduling problem is one of the most investigated problems in the project scheduling literature, and has a rich history. This article provides a perspective on this challenging scheduling problem, without having the ambition to provide a complete overview. Instead, the article does aim to summarize a number of reasons why this problem has been so intensely investigated from different perspectives.

It will be shown that this scheduling problem has many faces, and therefore deserves a lot of research time from a computational and theoretical point of view as well as from a practical point of view. An overview of possible extensions to other problems and a detailed overview of the used (both heuristic and exact) solution methods will be given. In addition, the data used will be discussed and interesting avenues for further research will be mentioned throughout the different sections.

Keywords: Project Scheduling, Resource Constraints, Literature Review, Project Data, Methodological Advances, Variants and Extensions.

[SOURCE] [PDF]

This work presents a case study where four well-known derivative-free solvers are benchmarked on several instances based on the solar suite of problems: an easy to use, freely available and open-source Concentrated Solar Power (CSP) plant simulator. The solar simulator provides a collection
of ten test problems designed to reflect real-world blackbox optimization challenges. The design of CSP plants involves solving complex and often computationally expensive optimization problems. These problems rely on highly diverse models which may be difficult to interface with optimization
solvers. As a result, standardized benchmark problems for optimization solvers in the CSP design field are scarce. Such benchmarks are essential for selecting the most appropriate solver for a given optimization problem. The solar problems model numerous components of the power plant, ranging
from the design of the heliostat field to the choice of turbine.

Keywords: Blackbox Optimization (BBO); Derivative-Free Optimization (DFO); Benchmarking; Concentrated Solar Power (CSP); Solar Thermal Power.

[SOURCE] [PDF]

This study addresses the rural postman problem with load-dependent costs, a variant of the arc routing problem where the traversal cost of an edge depends on its length and the vehicle’s load. The objective is to find a minimum-cost tour that services all required edges, a problem of particular importance when the demand weight is significant compared to the vehicle’s curb weight. We present an integer linear programming model for the problem and propose a heuristic algorithm based on bio-inspired methodologies to efficiently obtain near-optimal solutions within short computing times. The effectiveness of the approach is demonstrated through computational experiments on benchmark instances, and the results highlight the practicality of the proposed methods.

Keywords: CPP-LC, Genetic Algorithm, Rural Postman Problem, Transportation, Logistics.

[SOURCE] [PDF]

Traffic crashes and congestion generate high social and economic costs, yet traditional traffic monitoring methods, such as police patrols, fixed cameras, and helicopters, are costly, labor-intensive, and limited in spatial coverage. This paper presents a novel Drone Routing and Scheduling with Flexible Multiple Visits (DRSFMV) framework, an optimization model for planning drone-based highway monitoring under realistic operational constraints, including battery limits, variable monitoring durations, recharging at a depot, and target-specific inter-visit time limits. A mixed-integer nonlinear programming (MINLP) model and a linearized version (MILP) are presented to solve the problem. Due to the NP-hard nature of the underlying problem structure, a heuristic solver, Hexaly, is also used. A case study using real traffic census data from three Southern California counties tests the models across various network sizes and configurations. The MILP solves small and medium instances efficiently, and Hexaly produces high-quality solutions for large-scale networks. Results show clear trade-offs between drone availability and time-slot flexibility, and demonstrate that stricter revisit constraints raise operational cost.

Keywords: Drone Routing and Scheduling, Unmanned Aerial Vehicles (UAVs), Traffic Monitoring, Mixed-Integer Nonlinear Programming (MINLP).

[SOURCE] [PDF]

This case study tackles a real-world problem of a transportation company that is modeled as a scheduling optimization problem. The main goal of the considered problem is to schedule the maximum number of jobs that must be performed by vehicles over a specific planning horizon in order to minimize the total operational costs. Here, each customer request corresponds to a job composed of multiple operations, such as loading, unloading, and mandatory jobs, each associated with a specific location and time window. Once a job is allocated to a vehicle, all its operations must be executed by that same vehicle within their designated time constraints. Due to the imposed limitations, not every job can feasibly be scheduled. To address this challenge, two distinct methodologies are proposed. The first, a Holistic approach, solves the entire problem formulation using a black-box optimizer, serving as a comprehensive benchmark. The second, a Divide-and-Conquer approach, combines a heuristic greedy algorithm with a binary linear programming, decomposing the problem into sequential subproblems. Both approaches are implemented using the solver Hexaly. A comparative analysis is conducted under different scenarios and problem settings to highlight the advantages and drawbacks of each approach. The results show that the Divide-and-Conquer approach significantly improves computational efficiency, reducing time by up to 99% and vehicle usage by around 15–20% compared to the Holistic method. On the other hand, the Holistic method better ensures that mandatory jobs are completed, although at the cost of more resources.

Keywords: Scheduling Problem, Commercial Constraints, Time Windows, Divide-and-Conquer Algorithm, Hexaly.

[SOURCE] [PDF]

EasyLocal++ is a white-box C++ framework for designing local search algorithms. Over the years, it has been successfully used across various domains, such as timetabling, rostering, scheduling, and logistics, and has produced state-of-the-art results in benchmark datasets and competitions. Beyond research, EasyLocal++ has found practical use in real-world and industrial settings, demonstrating the flexibility and adaptability of the framework for different applications. In this paper, we position EasyLocal++ within the existing literature by comparing its capabilities with those of
available alternative/similar tools. We then trace its history from its initial design 25 years ago to the current version. Furthermore, we describe its architecture, highlighting its design principles and functionalities. We also discuss the features developed to simplify the design of local search methods and enhance their performance. Lastly, we explore potential future perspectives and developments.

Keywords: Software Tools, Algorithm Engineering, Local Search, Metaheuristics.

[SOURCE] [PDF]

We tackle a capacitated lot-sizing and scheduling problem (CLSP) with the main objective of minimizing changeover time in the production of metal parts for car seats. Changeovers occur when a machine (or production line) is reconfigured to produce a different product or part, leading to production downtime and loss of efficiency. In this study, we first provide a mixed-integer programming (MIP) formulation of the problem. We test the limits of solving the problem with commercial mathematical programming software. We also propose two approaches to tackle instances found in practice for which the mathematical programming model is not a viable solution method. Both approaches are based on partitioning the entire production of a part into production runs (or work slots). In the first approach, the work slots are assigned to machines and sequenced by a metaheuristic that follows the search principles of the GRASP (greedy randomized adaptive procedure) and VNS (variable neighborhood search) methodologies. In the second approach, we develop a Hexaly Optimizer (formerly known as LocalSolver) model to assign and sequence work slots. The study provides insights into how to minimize changeovers and improve production efficiency in metal parts manufacturing for car seats. The findings of this study have practical implications for the auto-part manufacturing industry, where efficient and cost-effective production is critical to meet the demands of the market.

Keywords: Lot Sizing, Multi-Period Production Scheduling, Nonidentical Parallel Machines, Metaheuristic Optimization.

[SOURCE] [PDF]

Local search is a common method for solving combinatorial optimisation problems. We focus on general-purpose local search solvers that accept as input a constraint model — a declarative description of a problem consisting of a set of decision variables under a set of constraints. Existing approaches typically take as input models written in solver-independent constraint modelling languages like MiniZinc. The ATHANOR solver we describe herein differs in that it begins from a specification of a problem in the abstract constraint specification language ESSENCE, which allows problems to be described without commitment to low-level modelling decisions through its support for a rich set of abstract types. The advantage of proceeding from ESSENCE is that the structure apparent in a concise, abstract specification of a problem can be exploited to generate high quality neighbourhoods automatically, avoiding the difficult task of identifying that structure in an equivalent constraint model. Based on the twin benefits of neighbourhoods derived from high level types and the scalability derived by searching directly over those types, our empirical results demonstrate strong performance in practice relative to existing solution methods.

[PDF]

The Quadratic Knapsack Problem (QKP) involves selecting a subset of elements that maximizes the sum of pairwise and singleton utilities without exceeding a given budget. The pairwise utilities are nonnegative, the singleton utilities may be positive, negative, or zero, and the node costs are nonnegative. We introduce a Breakpoints Algorithm for QKP, named QKBP, which is based on a technique proposed in Hochbaum (2009) for efficiently generating the concave envelope of the solutions to the relaxation of the problem for all values of the budget. Our approach utilizes the fact that breakpoints in the concave envelopes are optimal solutions for their respective budgets. For budgets between breakpoints, a fast greedy heuristic derives high-quality solutions from the optimal solutions of adjacent breakpoints. The QKBP algorithm is a heuristic which is highly scalable due to an efficient parametric cut procedure used to generate the concave envelope. This efficiency is further improved by a newly developed compact problem formulation. Our extensive computational study on both existing and new benchmark instances, with up to 10,000 elements, shows that while some leading algorithms perform well on a few instances, QKBP consistently delivers highquality solutions regardless of instance size, density, or budget. Moreover, QKBP achieves these results in significantly faster running times than all leading algorithms. The source code of the QKBP algorithm, the benchmark instances, and the detailed results are publicly available on GitHub.

[SOURCE] [PDF]