Title: Multi-period Single-Allocation Hub Location-Routing: models and heuristic solutions
Authors: Afaf Aloullal (INESC-ID and IST, ULisboa), Francisco Saldanha da Gama (CMAFcIO, Ciências, ULisboa) and Raca Todosijević (INSA Hauts-de-France, Valenciennes, France)
Abstract: This work investigates the use of time-dependent decisions in the context of hub-location routing. Instead of setting up the entire system at once, a planning horizon partitioned into several periods is considered during which the system is to be phased-in. In addition to installing the hubs, decisions are also to be made concerning the hub-level network, namely, the hub edges to use. The origin-destination flows are assumed to be time-dependent as well as the costs underlying the problem which include, set up costs for hubs and hub edges and variable operational costs at the hubs. A mathematical model is developed for the problem that can be solved up to proven optimality with a general-purpose solver for small instances of the problem. For larger instances, a four-phase matheuristic that combines principles of relax-and-fix, variable neighborhood descent and local branching schemes is proposed. In addition, two variants of the matheuristic have been developed.
Title: A Multi-Objective Mixed Integer Linear Programming Model for Thesis Defence Scheduling
Authors: João Almeida (CEGIST, IST, ULisboa), Daniel Santos (CEGIST, IST, ULisboa), José Rui Figueira (CEGIST, IST, ULisboa) and Alexandre P. Francisco (INESC-ID)
Abstract: In this presentation, we address the thesis defence scheduling problem, a critical academic scheduling management process, which has been overshadowed in the literature by its counterparts, course timetabling and exam scheduling. Specifically, we address the single defence assignment type of thesis defence scheduling problems, where each committee is assigned to a single defence, scheduled for a specific day, hour and room. We formulate a multi-objective mixed-integer linear programming model, which aims to be applicable to a broader set of cases than other single defence assignment models present in the literature, which have a focus on the characteristics of their universities. For such a purpose, we introduce a different decision variable, propose constraint formulations that are not regulation and policy specific, and cover and offer new takes on the more common objectives seen in the literature. We also include new objective functions based on our experience with the problem at our university and by applying knowledge from other academic scheduling problems. We also propose a two-stage solution approach. The first stage is employed to find the number of schedulable defences, enabling the optimisation of instances with unschedulable defences. The second stage is an implementation of the augmented e-constraint method, which allows for the search of a set of different and non-dominated solutions while skipping redundant iterations. The methodology is tested for case-studies from our university, significantly outperforming the solutions found by human schedulers. A novel instance generator for thesis scheduling problems is presented. Its main benefit is the generation of the availability of committee members and rooms in availability and unavailability blocks, resembling their real-world counterparts. A set of 96 randomly generated instances of varying sizes is solved and analysed regarding their relative computational performance, the number of schedulable defences and the distribution of the considered types of iterations. The proposed method can find the optimal number of schedulable defences and present non-dominated solutions within the set time limits for every tested instance.
Title: Multi-depot routing with split deliveries
Authors: Markus Leitner (Department of Operations Analytics, Vrije Universiteit Amsterdam, Netherlands) and Luís Gouveia (CMAFcIO, Ciências, ULisboa)
Abstract: We study the multi-depot split-delivery vehicle routing problem (MDSDVRP) which combines the advantages and potential cost-savings of multiple depots and split-deliveries and develop the first exact algorithm for this problem. We propose an integer programming formulation using a small number of decision variables and several sets of valid inequalities. These inequalities focus on ensuring the vehicles' capacity limits and that vehicles return to their initial depot. As we show that the new constraints do not guarantee these aspects our branch-and-cut framework also includes an efficient feasibility check for candidate solutions and explicit feasibility cuts. The algorithm which also uses a comparably simple, yet effective heuristic to compute high-quality initial solutions is tested on the MDSDVRP and two well-known special cases, the split-delivery vehicle routing problem (SDVRP) and the multi-depot traveling salesman problem (MDTSP). The results show that the new inequalities tighten the linear programming relaxation, increase the performance of the branch-and-cut algorithm, and reduce the number of required feasibility cuts. We report the first proven optimal results for the MDSDVRP and show that our algorithm significantly outperforms the state-of-the-art for the MDTSP while being competitive on the SDVRP. For the latter, 20 instances are solved for the first time and new best primal and dual bounds are found for others.
Authors: Raquel Bernardino (CEMAPRE, ISEG, ULisboa), Luís Gouveia (CMAFcIO, Ciências, ULisboa), Ana Paias (CMAFcIO, Ciências, ULisboa) and Daniel Santos (CEGIST, IST, ULisboa)
Abstract: In this presentation, we address the Multi-Depot Family Traveling Salesman Problem (MDFTSP) and two clustered variants, the Soft-Clustered MDFTSP (SC-MDFTSP) and the Hard-Clustered MDFTSP. These problems are related to warehouse activities supported by scattered storage systems, which motivates their practical application. For these three problems, we present several mixed integer linear programming formulations and develop appropriate Branch-&-Cut based algorithms which are tested with a newly generated data set including instances with up to 200 nodes and 40 depots. The results from the computational experiments allow us to identify the main differences between the three problems concerning modeling approaches as well as solution methods and put in evidence that these problems are challenging problems, in particular the SC-MDFTSP.