One of the world’s biggest challenges is that living beings have to share a limited amount of resources. As people of science, we strive to find innovative ways to better use these resources, to reach and positively affect more and more people. In the field of optimization, we aim at finding an optimal allocation of limited sets of resources to maximize a certain objective. Some of these problems can be solved in polynomial time; others are more difficult to be solved. Current state-of-the-art methods can solve NP-hard problems (a class of optimization problems) in exponential time, in the worst case. To give an idea, for input size n Æ 100 and parameter k Æ 2: polynomial time nk Æ 1002 Æ 10,000; exponential time kn Æ 2100 Æ 1,267,650,600,228,229,401,496,703,205,376. Yet, many relevant and practical problems are NP-hard and have to be solved in a short amount of time. Our research focuses on formulating and solving four of these problems. Among those, three are vehicle routing problems (VRP, Chapters 2, 3 and 4). VRPs are problems where vehicles have to perform routes in order to minimize an objective function (for example, minimize routing costs) while being subjected to constraints (for example, each location has to be visited). Routing costs have a significant impact on society and on the cost of products (the transportation sector makes up 13.2% of the EU’s GDP (Joint Research Centre, 2021)). Although VRPs have been thoroughly studied for over half a century, new technologies (autonomous driving, real-time information, etc.) and new customers’ demands (increase in online shopping, a more competitive delivery market, etc.) create variants of the standard VRP that are more and more complex to formulate and solve. VRPs are well-known for being NP-hard and difficult to approximate, and hence solve. We formulated three novel VRPs and solve those both exactly via branch-and-bound (Chapters 3 and 4, the latter also uses valid inequalities) and metaheuristicly (Chapters 2 and 4). To increase generalizability, we introduced an almost non-parametric algorithm that encompasses all the most famous heuristic operators for VRP (Chapter 4). To increase performance, we proposed an adaptive, i.e., selftuning, algorithm (Chapter 2) that can detect problem’s features and steer its decisions to achieve better solutions. Lastly, Chapter 5 focuses on what we believe will be the most radical transformation in the metaheuristic field in coming years: machine learning for combinatorial optimization. Machine learning established its fundamental importance in many fields and it is currently paving its way into combinatorial optimization. We developed a selfattention based deep reinforcement learning algorithm without any problem-specific knowledge to solve one of the most studied combinatorial optimization problems. Our results suggest that machine learning can (and we conjecture that it will) tackle combinatorial optimization on its own, without problem-specific knowledge and will be a fundamental element in future state-of-the-art heuristics for combinatorial optimization. @en

Metaheuristics have been widely used to solve NP-hard problems, with excellent results. Among all NP-hard problems, the Travelling Salesman Problem (TSP) is potentially the most studied one. In this work, a variation of the TSP is considered; the main differences being, edges may have positive or negative costs and the objective is to return a Hamiltonian cycle with cost as close as possible to zero. This variation is called the balanced TSP (BTSP). To tackle this new problem, we present an adaptive variant of the iterated local search metaheuristic featuring also random restart. This algorithm was tested on the MESS2018 metaheuristic competition and achieved notable results, scoring the 5th position overall. In this paper, we detail all the components of the algorithm itself and present the best solutions identified. Even though this metaheuristic was tailored for the BTSP, with small modifications its structure can be applied to virtually any NP-hard problem. In particular, we introduce the uneven reward-and-punishment rule which is a powerful tool, applicable in many contexts where fast responses to dynamic changes are crucial.

@en

Combinatorial optimization (CO) problems are at the heart of both practical and theoretical research. Due to their complexity, many problems cannot be solved via exact methods in reasonable time; hence, we resort to heuristic solution methods. In recent years, machine learning (ML) has brought immense benefits in many research areas, including heuristic solution methods for CO problems. Among ML methods, reinforcement learning (RL) seems to be the most promising method to find good solutions for CO problems. In this work, we investigate an RL framework, whose agent is based on self-attention, to achieve solutions for the knapsack problem, which is a CO problem. Our algorithm finds close to optimal solutions for instances up to one hundred items, which leads to conjecture that RL and self-attention may be major building blocks for future state-of-the-art heuristics for other CO problems.

@en

Automated vehicles are becoming a reality. Expectations are that AVs will ultimately transform personal mobility from privately owned assets to on-demand services. This transformation will enhance the possibility of sharing trips, leading to shared AVs (SAVs). The preeminent aim of this paper is to lay foundations for fast and efficient algorithms to be used in such new driving conditions. These algorithms must be able to solve Dial-a-Ride problems with transfers (DARPT). Hence, they should efficiently assign passengers to vehicles and routes while also: administering vehicles dispatch, determining convenient parking for idling vehicles and managing vehicle routing in real-time. In this paper, we develop two integer linear programming models (one in continuous time and one in discrete time) and their extensions to solve the DARPT. Our models take into account routing, service times, constraints on maximum route time-span, unserved requests, preferred arrival and departure time, nonconstant travel times, convenient parking while optimizing routing costs and quality of the service. The models are tested on instances based on Google Maps data by solving them with a commercial solver. The results of these tests are the starting point for validating the performance of forthcoming, ad hoc metaheuristics to be used in real-life sized scenarios.@en