Models and heuristics for hard routing and knapsack problems

Abstract

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.