previous day
next day
all days

View: session overviewtalk overview

08:45-09:45 Session 12: Julia tutorial: multi-objective metaheuristics
Antonio J. Nebro (University of Málaga, Spain)
Xavier Gandibleux (Université de Nantes, France)
Location: Auditorium
09:45-10:15Coffee Break

Meet in the "Compagnie des Indes" room on the ground floor.

10:15-12:15 Session 13A: Advances in combinatorial optimization 2
Stefan Voss (University of Hamburg, Germany)
Fred Glover (Entanglement Inc., United States)
Gary Kochenberger (Entanglement Inc., United States)
Rick Hennig (Entanglement Inc., United States)
Modeling and Solving Polynomial Binary Programs: Going beyond QUBO

ABSTRACT. Polynomial Unconstrained Binary Optimization (PUBO) models, which include QUBOs as a special case, are proving to be an important modeling and solution approach for many important combinatorial optimization problems. The dominant practice today for polynomial orders greater than two is to employ quadratization techniques to convert the current model into an equivalent QUBO model to be solved by standard QUBO means. In this paper, we report on a generalization of our QUBO solver that enables us to directly solve the PUBO model at hand without having to resort to recasting into a larger but equivalent QUBO model. Computational experience is presented on a variety of well-known problems such as max 3SAT and Steiner Triple Covering illustrating the attractiveness of our approach compared to other results reported in the literature.

Raka Jovanovic (Qatar Environment and Energy Research Institute , Hamad Bin Khalifa University, Qatar, Qatar)
Stefan Voss (Institute of Information Systems, University of Hamburg, Germany, Germany)
A metaheuristic approach for solving the maximum disjoint dominating sets problem

ABSTRACT. In this paper the fixed set search (FSS), a population-based metaheuristic, is applied to the Maximum Disjoint Dominating Sets Problem (MDDSP). Initially, a greedy randomized adaptive search procedure (GRASP) is developed to solve the MDDSP. Subsequently, the FSS enhances GRASP by incorporating a learning mechanism that identifies common elements in high-quality solutions. Computational experiments show that the proposed method significantly outperforms current state-of-the-art methods.

Nozomi Kotake (Nippon Institute of Technology, Japan)
Rikuto Shibutani (Nippon Institute of Technology, Japan)
Kazuma Nakajima (Nippon Institute of Technology, Japan)
Takafumi Matsuura (Nippon Institute of Technology, Japan)
Takayuki Kimura (Nippon Institute of Technology, Japan)
Adaptive Ant Colony Optimization Using Node Clustering with Simulated Annealing

ABSTRACT. Multiple fields, including transport, and engineering, require finding the shortest route. This problem is known as the traveling salesman problems (TSP), an NP-hard combinatorial optimization problems. As the number of cities increases, finding the shortest path in TSP, considering all combinations, becomes challenging. The ant colony optimization (ACO) has been proposed as a solution to TSP. However, the performance of an ACO heavily depends on its parameters. In addition, finding appropriate settings of parameters for each problem is time-consuming. To address this, an adaptive ant colony optimization with node clustering (AACO-NC) has been proposed. AACO-NC uses both node clustering and effective pheromone evaporation to find the shorter route. Despite its strength, our preliminary experiments suggest that the pheromone updates restricts the solution search range. Consequently, finding a good solution becomes increasingly difficult as the search progresses. Therefore, we implement the simulated annealing (SA) method to expand the solution search space and to escape from the local optimum solution. Numerical experiments demonstrate that the proposed method outperforms the conventional method on a variety of benchmark problems, yielding a smaller error rate between the optimal solution and the mean value.

Marc Benito-Marimón (Universitat de Valencia, Spain)
Rafa Martí (Universitat de Valencia, Spain)
Anna Martínez-Gavara (Universitat de Valencia, Spain)
The Multiple Linear Ordering Problem

ABSTRACT. The linear ordering problem (LOP) is a very well-known NP-hard problem in combinatorial optimization. Given a set of elements, and its dominance matrix, the objective is to find a simultaneous ordering of rows and columns of the matrix, to maximize the sum of entries above the upper diagonal. This linear ordering provides a rank of the elements maximizing the dominance that results in many practical applications, from economy to social networks. However, the LOP may have many alternate optima with significantly different orderings, which makes difficult to provide an optimal representative ranking. In spite of its practical significance, little effort has been dedicated to explore the structure of alternate LOP optimal solutions. In this talk, we first review previous papers on this topic(Anderson et al.,2022; Cameron et al.,2021 ) , and then we present both a mathematical model and a heuristic algorithm, based on the VNS methodology, to obtain the k most distant optimal solutions. Our computational testing shows that the VNS succesfully identifies the most diverse LOP optimal solutions, to first disclose the rankability of the input data, and their applicability to a practical problem. In this way, we avoid drawing unfair conclusions from non-representative optimal rankings.

10:15-12:15 Session 13B: Algorithm configuration and visualization 2
Christian Blum (Spanish National Research Council (CSIC), Spain)
Location: Salle Colbert 2
Elmar Steiner (Department of Operations and Information Systems, University of Graz, Austria)
Ulrich Pferschy (Department of Operations and Information Systems, University of Graz, Austria)
A Dynamic Algorithm Configuration Framework Using Combinatorial Problem Features and Reinforcement Learning

ABSTRACT. This study explores the dynamic configuration of a populationbased metaheuristic with reinforcement learning. Beyond achieving high performance, our dual focus involves utilizing hyperparameters as indicators for transitions between exploration and exploitation phases. We investigate how this information can be effectively harnessed for responsive balance tailored to each problem instance. Specifically, we analyze the potential of integrating the Local Optima Network (LON), an abstraction of the fitness landscape, to inform parameter generation. To study the relationship between indicators and responsive control, we embed the algorithm within a reinforcement learning framework.

Yunshuang Xiao (Université libre de Bruxelles (ULB), Belgium)
Leslie Pérez Cáceres (Pontificia Universidad Católica de Valparaíso, Chile)
Manuel López-Ibáñez (University of Manchester, UK)
Thomas Stützle (Université libre de Bruxelles (ULB), Belgium)
Automatic Configuration with crace

ABSTRACT. Automatic algorithm configuration does support the configuration and the design of optimization algorithms by helping in the design of these algorithm by providing spezialised tools for adjusting their parameters including categorical, ordinal and numerical ones. In particular, the parallel execution of the target algorithm is crucial for the implementation of such algorithms. In irace this was done by the R tools. Yet, with growing size of the parallel cores this was not enough due to the results of how the parallelisation is done in the R tools. We propose an alternative to irace, which is based on a python tool, called crace, and that performs a single race but this in parallel. It generates new configurations asynchronously and admits a highly flexible configuration process. In this talk, we generally describe crace and we show some results on difficult benchmark problems. In fact, we detail some solution-quality benchmarks and also some time-varying benchmarks which show its wide range of application. The results when compared to irace show that it has some encouraging performance.

Mario A. Navarro (Universidad de Guadalajara, Mexico)
Angel Casas Ordaz (Universidad de Guadalajara, Mexico)
Beatriz A. Rivera-Aguilar (Universidad de Guadalajara, Mexico)
Bernardo Morales-Castañeda (Universidad de Guadalajara, Mexico)
Diego Oliva (Universidad de Guadalajara, Mexico)
Populations of hyperparametric solutions for the design of metaheuristic algorithms: An empirical analysis of performance in Particle Swarm Optimization

ABSTRACT. Particle Swarm Optimization (PSO) is one of the most famous swarm-based algorithms used for solving optimization problems. PSO has received growing attention within many fields of the research community. Since its inception, a number of prominent improvements have been created. Within the broad spectrum of proposals that have emerged in the last few decades, improvements have been made to swarm initialization, new parameters have been introduced, such as the constraint on the inertia weight coefficient, and even mutation operators have been introduced to the PSO. However, the PSO has drawbacks and shortcomings, such as no convergence or loss of diversity, or stagnation at local minima. This study proposes a hyperparametric population of solutions approach; the central premise is that each of the swarm particles has different parameters so that each has unique characteristics to promote exploitation-exploration and guide a heuristic with healthy diversity; empirical analysis and statistical tests performed on the proposed algorithm show the feasibility of the approach compared to improved versions of PSO found in the literature.

Francesca Da Ros (Università degli Studi di Udine, Italy)
Eugenia Zanazzo (Università degli Studi di Udine, Italy)
Luca Di Gaspero (DPIA - University of Udine, Italy)
Applying Learning to Rank for Algorithm Selection

ABSTRACT. We explore the use of Learning to Rank (LtR) methods in selecting the algorithmic configurations of simulated annealing metaheuristics. Our approach involves using a racing method to filter down the list of algorithm configurations and identify a subset of high-performance ones. We then train a LtR model to predict the ranking of these configurations, with the goal of finding the most suitable algorithm for specific problem instances. In this methodology, each algorithm configuration is treated as a document, and the problem instance is treated as a query, using terminology from Information Retrieval, where the LtR method comes from. We break down each instance into features, which allows the LtR model to predict how each algorithm will perform for a given instance. Initial tests conducted on a medical student scheduling problem have shown this method to be effective, although further research is needed for more detailed results. The work is carried within the project "Models and algorithms for the optimization of integrated healthcare management" (PRIN-2020 program, project no. 2020LNEZYC, funded by the Italian Ministry of University and Research (MUR)).

10:15-12:15 Session 13C: Operations research for healthcare 1
Salma Makboul (UTT, France)
Eugenia Zanazzo (University of Udine, Italy)
Sara Ceschia (University of Udine, Italy)
Andrea Schaerf (University of Udine, Italy)
Solving the Integrated Patient-to-Room and Nurse-to-Patient Assignment by Simulated Annealing

ABSTRACT. We consider a recently-proposed integrated healthcare problem that deals with the assignment of patients to suitable rooms in wards (Patient-to-Room) and the assignment of nurses to patients to balance their workload (Nurse-to-Patient), in one single stage. For this problem, we designed a local search approach that uses the union of two distinct neighborhoods and is guided by a Simulated Annealing metaheuristic. We tuned our search method, ran it on the available dataset, and validated it using the available solution checker. Finally, we report our results for different running times, in order to show how the scores evolve based on the granted time.

Sara Ceschia (Polytechnic Department of Engineering and Architecture, University of Udine, Italy)
Luca Di Gaspero (Polytechnic Department of Engineering and Architecture, University of Udine, Italy)
Simona Mancini (Department of Engineering, University of Palermo, Italy)
Vittorio Maniezzo (Department of Computer Science, University of Bologna, Italy)
Roberto Montemanni (Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, Italy)
Roberto Maria Rosati (Polytechnic Department of Engineering and Architecture, University of Udine, Italy)
Andrea Schaerf (Polytechnic Department of Engineering and Architecture, University of Udine, Italy)
Enhancing Real-World Applicability in Home Healthcare: A Metaheuristic Approach for Advanced Routing and Scheduling

ABSTRACT. We consider the home healthcare scheduling and routing problem, and we extend the classic formulation introduced by Mankowska et al (2014), by adding several real-world features. For this novel problem, we created a new realistic dataset, and we developed a metaheuristic approach based on a combination of neighborhoods guided by a Simulated Annealing procedure. Our solver, properly engineered and tuned, is able to solve all instances in a short time. Our experimental results highlight the relative importance of the various (original and new) cost components.

Diana Aires (University of Lisbon, Portugal)
Brígida Ferreira (University of Lisbon, Portugal)
Humberto Rocha (University of Coimbra, Portugal)
Joana Dias (FEUC and INESCC, Portugal)
Inverse biological radiotherapy treatment planning optimization using simulated annealing

ABSTRACT. Approximately 50% of cancer patients undergo radiotherapy, making it a pivotal aspect of cancer treatment. The optimization of radiotherapy treatment plans can be enhanced through radiobiological models, capitalizing on their direct correlation between delivered radiation dose and clinical outcomes. These models contribute to personalized treatments by accounting for the distinct radiosensitivity of various tissues. However, their implementation adds complexity to the radiotherapy treatment planning process, introducing non-linear and non-convex objective functions. This study employs simulated annealing for inverse treatment planning optimization in Intensity-Modulated Radiation Therapy while incorporating radiobiological models. To assess the advantages of the new biological treatment optimization algorithm proposed, four different tumour cases were selected: breast, head and neck, pancreas, and prostate cancer. The results demonstrated a notable decrease in normal tissue complication probability and an increased overall dose in the target volume for all tested cases. This indicates a significant sparing of surrounding organs at risk while increasing the mean dose in the tumor volume. In conclusion, radiobiological models emerge as valuable tools with the potential to yield markedly improved treatment outcomes. The integration of metaheuristics, such as simulated annealing, proves to be a valuable option for optimizing treatment plans and maximizing the benefits of radiobiological models.

Ruan Myller Magalhães Oliveira (Universidade Federal de Catalão - UFCAT, Brazil)
Manuel Iori (University of Modena and Reggio Emilia - UNIMORE, Italy)
Arthur Kramer (Mines Saint-Etienne, University Clermont Auvergne, France)
Thiago Alves de Queiroz (Universidade Federal de Catalão - UFCAT, Brazil)
A Re-optimization Heuristic for a Dial-a-Ride Problem in the Transportation of Patients

ABSTRACT. In this paper, we handle the problem of picking and delivering patients among the distinct units of a hospital. This problem is found in hospitals with several (specialized) units covering a large area, and it emerges from a real situation faced by a hospital in northern Italy. Patient transportation requests arrive dynamically during the day, and the hospital transportation department must service them all using capacitated and homogeneous vehicles. Each request is associated with a patient urgency level (weight) and a time window. The objective is to design vehicle routes to serve all requests and minimize the total weighted tardiness. To solve the problem, we propose a re-optimization heuristic based on two policies that mimic the patients' and hospital's decision-making processes. We then improve the solutions obtained with the policies using a tabu search. Computational results show that we can obtain high-quality solutions using the tabu search compared with the policies and a simulated annealing-based heuristic from the literature.

10:15-12:15 Session 13D: Data-driven approaches
Francesco Zito (University of Catania, Italy)
Isaac Lozano-Osorio (Universidad Rey Juan Carlos, Spain)
Jesús Sánchez-Oro (Universidad Rey Juan Carlos, Spain)
Abraham Duarte (Universidad Rey Juan Carlos, Spain)
Kenneth Sörensen (University of Antwerp, Belgium)
What characteristics define a Good Solution in Social Influence Minimization Problems?

ABSTRACT. The evolution of Social Networks has introduced significant challenges related to information overload. These challenges are covered in diverse areas, such as viral marketing or misinformation control. As social networks grow in complexity, the essential need to leverage data-driven insights becomes evident. The aim of the Social Influence Minimization Problem (IMP) is to identify and strategically block users to curtail information dissemination. Structural insights can be extracted through data-mining techniques to guide the design of efficient heuristics and the identification of influential users to be blocked. Considering good and bad quality solutions, a supervised learning approach is used to classify the extracted features, that allowed meaningful conclusions to be drawn regarding the features of these solutions. The IMP is addressed through the proposal of a robust heuristic method, based on the most relevant features, which is effective and efficient when compared with the state-of-the-art approaches.

Flavien Lucas (IMT Nord Europe, France)
Diego Perdigão Martino (Université Clermont Auvergne, France)
Romain Billot (IMT Atlantique, France)
Philippe Lacomme (Université Clermont Auvergne, France)
Optimizing Inventory Routing: A Data-Driven Perspective

ABSTRACT. In recent years, the convergence of Machine Learning and Operations Research methods has gained widespread popularity. This presentation explores the application of data mining techniques to interpret the features that contribute to the formulation of both effective and suboptimal solutions. The focus is on understanding the characteristics that lead to favorable outcomes and how to emphasize these while mitigating the undesirable ones.

Our main investigation lies in the Inventory Routing Problem (IRP), a multi-period transportation and inventory management problem. The objective function is to minimize the sum of the transportation costs for the supplier as well as the inventory costs for both the supplier and the customers.

Using classical instances proposed in the literature and encompassing a huge number of solutions per instance, ongoing efforts involve the implementation of decision rules. This analysis aims to provide valuable insights into the intricate dynamics of features influencing solution quality within the context of the IRP, acknowledging that the results are still a work in progress.

Beatrice Musizza (Università degli Studi di Udine, Italy)
Luca Di Gaspero (DPIA - University of Udine, Italy)
Data Analytics for Police Deployment Optimization in France

ABSTRACT. This research focuses on optimizing the distribution of police officers across French departments by employing a data-driven strategy that integrates open-source governmental criminality data with socio-economic factors, resulting in over 100 independent variables. We develop a regression model to forecast the criminality rates for various crimes by department. The current police officer distribution data is also sourced from open data platforms. The aim is to propose an improved allocation of law enforcement personnel that aligns with the predicted specific crime rates of each department. To facilitate this redistribution, we designed an optimization model that imposes constraints to minimize the relocation distance for officers, ensuring transfers are feasible and within reasonable proximity to their current locations. This optimization framework incorporates a graph structure to define compatible departmental transfers, addressing geographical and operational compatibility. The study is ongoing, with efforts to refine the model to enhance its implementation and effectiveness in optimizing police deployment. The work is carried out within the Artificial Intelligence 2022–2025 strategic plan project of the University of Udine.

Charlotte Beauthier (Cenaero, Belgium)
Rajan Filomeno Coelho (Cenaero, Belgium)
Sylverio Pool Marquez (UNamur, naXys, Belgium)
Caroline Sainvitu (Cenaero, Belgium)
Annick Sartenaer (UNamur, naXys, Belgium)
Affinity-based distance to deal with categorical variables in a surrogate-based evolutionary algorithm

ABSTRACT. In practice, various industrial design problems have continuous, discrete, and categorical variables. Our objective is to manage efficiently these different types of variables within a surrogate-based optimization process. Indeed, a globally effective approach to high-fidelity optimization problems based on computationally expensive analysis lies in the exploitation of surrogate models. The developments presented are carried out in Minamo, the in-house design space exploration and multi-disciplinary optimization platform of the research center Cenaero. In this work, we propose to redefine the notion of distance between the possible values of a categorical variable (named "attributes"), through the concept of "affinity". The notion of affinities between attributes can be interpreted as a weighted relationship between attributes. These affinities are usually defined based on a physical intuition of the designer, but we also consider here how to set these affinities mathematically, using clustering or projection methods. Indeed, affinities are generally implicitly associated to the behavior of one or several outputs that behave(s) similarly for various attributes. In order to study the impact of the use of affinities, numerical results are presented on specific test problems coming from structural design framework.

10:15-12:15 Session 13E: New VRP and extensions 1
Caroline Prodhon (Université de Technologie de Troyes, France)
Location: Salle Colbert 1
Edgar Ricardo Silva Russi (Université de Technologie de Troyes, France)
Nacima Labadie (University of Technology of Troyes, France)
Caroline Prodhon (LOSI, Université de Technologie de Troyes, France)
The Multi-objective C2P Collaborative Network Vehicle Routing Problem for Urban Deliveries

ABSTRACT. The use of intermediate stations such as lockers or pick-up points, also known as Customer-to-parcel (C2P) stations, is one of the most prevailing delivery strategies adopted by logistics operators to address the challenges inherent to urban deliveries. These challenges include vehicle congestion, unexpected deliveries, and air pollution. Although these stations have the potential to decrease delivery costs and greenhouse gas (GHG) emissions, existing literature has scarcely addressed their impact on customer satisfaction levels, as well as the evaluation of GHG emissions generated by end-customer trips to the stations.

In this context, the present research focuses on analyzing the potential benefits of collaborating through the co-utilization of C2P station networks belonging to different logistics operators. The study presents a mathematical formulation (MILP) to address this problem and proposes an epsilon-constraint exact-method for solving small instances maximizing customer satisfaction while minimizing GHG emissions. Considering the NP-Hard nature of the problem, a multi-objective metaheuristic based on an Adaptative Evolutionary Multi-Directional Local Search (ELS) technique is introduced to solve larger scale instances.

Karl Doerner (University of Vienna, Austria)
Georg E. A. Fröhlich (University of Vienna, Austria)
Margaretha Gansterer (University of Klagenfurt, Austria)
A rolling horizon framework for the time-dependent multi-visit dynamic safe street snow plowing problem

ABSTRACT. As a major real-world problem, snow plowing has been studied extensively. However, most studies focus on deterministic settings with little urgency yet enough time to plan. In contrast, we assume a severe snowstorm with little known data and little time to plan. We introduce a novel time-dependent multi-visit dynamic safe street snow plowing problem. A time-discretized mixed integer program would be very challenging to solve, even if snowstorm move- ment is predictable; therefore, we address the problem on a rolling time horizon. The proposed framework splits the problem into smaller problems, and predicts the future snowfall and the state of the system before solving each subproblem. The subproblems are, hence, considered to be deterministic and solutions are generated using adaptive large neighborhood search. Due to considering a real- world problem with dynamic changing data, the rolling horizon framework has only a very limited computation time to calculate a solution for a given sub- problem, therefore a metaheuristic solution technique is used. During this time, the solution for the previous subproblem is executed. We validate the efficacy of the adaptive large neighborhorhood search on team orienteering arc routing problem benchmark instances.

Banu Ulusoy Dereli (Technical University of Munich, Germany)
Gerhard Hiermann (Technical University of Munich, Germany)
Maximilian Schiffer (Technical University of Munich, Germany)
An Adaptive Large Neighborhood Search Approach to Solve Large-Scale Two-Echelon Location Routing Problem in City Logistics

ABSTRACT. With increasing e-commerce transactions and traffic congestion, handling large volumes of parcel deliveries efficiently in city logistics becomes more challenging. To this end, we aim to design a distribution system where trucks originating from a central depot outside the city deliver parcels to micro-depots in the city center. Smaller vehicles like cargo bikes handle customer deliveries from these micro-depots. We decide on the location of micro-depots, the first-level routes from the central depot to the micro-depots, and the second-level routes of cargo bikes from the micro-depots to customers to minimize the total costs incurred. From the perspective of a logistics service provider, it is important to find a good distribution plan quickly for thousands of deliveries. To solve such large-scale problems efficiently, we propose a metaheuristic that integrates a set covering problem with an adaptive large neighborhood search (ALNS) algorithm. Our ALNS generates a set of promising routes and micro-depot locations in destroy and repair combined with a local search. We then utilize the set cover problem during our search to find better network configurations. We show the efficacy of our algorithm on well-known benchmark datasets and provide managerial insights based on a case study for the city of Munich.

Roberto Montemanni (University of Modena and Reggio Emilia, Italy)
Mauro Dell'Amico (University of Modena and Reggio Emilia, Italy)
Andrea Corsini (University of Modena and Reggio Emilia, Italy)
Combining Heuristics and Constraint Programming for the Parallel Drone Scheduling Vehicle Routing Problem with Collective Drones

ABSTRACT. Last-mile delivery problems where trucks and drones collaborate to deliver goods to final customers are considered. We focus on settings where a fleet with several homogeneous trucks work in parallel to collaborative drones, able to combine with each other to optimize deliverines. A heuristic for the min-max vehicle routing problem is coupled with constraint programming models, leading to an effective method able to provide several state-of-the-art solutions for the instances commonly adopted in the literature.

12:15-14:00Lunch Break

Meet in the "Compagnie des Indes" room on the ground floor.

20:00-23:59 Gala dinner

Meet in the "Compagnie des Indes" room on the ground floor.