Title: Period-disaggregated formulations for the Period Travelling Salesman Problem
Authors: Sofia Henriques*, Ana Paias* (* CMAFcIO, Ciências, ULisboa)
Abstract: The Period Travelling Salesman Problem (PTSP) generalizes the TSP. We consider a time horizon with different periods and a directed graph with a depot and n customers, in which each customer has a required number of periods to be visited in. The objective of the PTSP is to assign each client to as many periods as it is required while determining the set of routes, one for each period, with minimum cost. Each route starts and ends at the depot and visits the clients assigned to that specific period only once. The PTSP combines an assignment and a routing problem in a single problem, making it very difficult to solve to optimality, even for instances with few clients. We will present, both compact and non-compact, ILP formulations for the PTSP and new valid inequalities, generalizing the work available in the literature. The main conclusions from our theoretical study will be presented, as well as preliminary computational tests on instances with up to 7 periods.
Authors : Leonor Santiago Pinto*, Raquel Bernardino*, João Janela*, Carlos Martins*, Cândida Mourão*, Filipe Rodrigues (* CEMAPRE & ISEG, ULisboa)
Abstract: This presentation introduces the multi-trip vehicle routing with release dates and interrelated periods (MTVRP-RDIP), motivated by a car components distribution to repair centers (warehouses) application. The routes start at different departure periods and have various durations. Thus, two routes starting at different periods may be active simultaneously, leading to interrelated periods. Moreover, a route may only start at a departure period if a vehicle is available, and the availability of a vehicle depends on the existing ones and on the active routes at that time period. The clients are classified according to their importance and represent warehouses that require car components, thus leading to the consideration of release dates. Delays in satisfying client orders result in penalty costs that must be minimized. The objective to minimize also includes routing costs and vehicle utilization costs. Mixed integer linear formulations and a matheuristic based on a rolling-horizon process are presented. Computational experience with 150 generated instances shows that the formulation provides solutions for the smaller ones, and the matheuristic obtains solutions in a reasonable time for the larger ones.
This work was partially supported by the Projects CEMAPRE/REM - UIDB /05069/2020 and CMAFcIO - UIDB/04561/2020, financed by FCT/MCTES through national funds.
Title: Algorithms for Solving the Multiobjective Quasi-clique Problem
Authors: Daniela Santos (CISUC, Dep. Informatics Engineering, University of Coimbra), Kathrin Klamroth (School of Mathematics and Natural Sciences, University of Wuppertal), P. Martins (Coimbra Business School - ISCAC, Polytechnic Institute of Coimbra), L. Paquete (CISUC, Dep. Informatics Engineering, University of Coimbra)
Abstract: Given a simple undirected graph G, any subgraph of G is a quasi clique if its density reaches or exceeds a specified threshold. Two combinatorial optimization problems are commonly associated with quasi-cliques: the first asks for a quasi-clique that maximizes the size (number of vertices) subject to a given minimum density threshold, and the second seeks a quasi-clique that maximizes density subject to a given size. However, when no a priori information about size and density is available, a possible way of address ing this problem is to consider a multiobjective perspective where size and density are objectives to be maximized simultaneously. This leads to the for mulation of the Multiobjective Quasi-clique (MOQC) problem. To efficiently address MOQC, we propose three exact solution strategies: a baseline ap proach based on the ε-constraint method; a Two-phase strategy combining dichotomic search to identify the extreme-supported points and ε-constraint scalarization to identify the remaining weakly-nondominated points; and a Three-phase method that integrates dichotomic search, vertex degree-based local search and ε-constraint scalarization. Our presentation will discuss these strategies and their effectiveness in real-life instances.
Daniela Scherer dos Santos acknowledges the Foundation for Science and Technology (FCT) for the Ph.D. fellowship 2022.12082.BD. This work is partially funded by the FCT, I.P./MCTES through national funds (PIDDAC), within the scope of CISUC R&D Unit- UID/CEC/00326/2020
Authors: João Almeida*, José Rui Figueira*, Alexandre P. Francisco**, Daniel Santos* (* CEGIST, Instituto Superior Técnico, ULisboa) (** INESC-ID, Instituto Superior Técnico, ULisboa)
Abstract: This work presents a hybrid meta-heuristic for generating feasible course timetables, focusing on large-scale problems. We test it on instances from our university, for which the currently used commercial software takes several hours to find feasible solutions and often fails to comply with some constraints. The methodology includes elements from adaptive large neighbourhood search (ALNS), guided local search (GLS), variable neighbourhood search (VNS), and a novel instance decomposition technique. The constraint violations from different groups of constraints are regarded as objective functions to be minimised. The neighbourhood structures focus the search on the time slots where the most violations are identified. After a certain number of iterations without improvements, the most challenging constraint groups are given new weights, guiding the search towards non-dominated solutions, which improve the performance of these objectives, even if the total sum of the effective violations increases. If this mechanism fails to escape these “local optima”, a shaking phase is conducted. The decomposition mechanism operates as follows: curricula are iteratively introduced to the problem, and new feasible solutions are found considering the increasing set of lectures. The assignments from each iteration can be modified if needed in subsequent iterations. This methodology is tested in real-world instances from our university and in random sub-divisions of those. For sub-divisions with 400 curricula timetables, decomposition reduces the solution times to up to 27%. For real-world instances, with 1288 curricula timetables, the reduction is 18%. The experiments also reveal that clustering curricula with more lectures and professors in common when incrementing the instances improved the solution times by 18% more than a random increment order. Using our methodology, feasible solutions for the real-world instance are found in 21 minutes, on average, whereas the commercial software takes several hours.