Skip to main content

Title: Improved models for a single vehicle continuous-time inventory routing problem with pickups and deliveries

Authors: Agostinho Agra (CIDMA, DM, UA), Marielle Christiansen (Norwegian University of Science and Technology) and Laurence Wolsey (CORE, UCLouvain)

Abstract: An inventory routing problem in which a single vehicle is responsible for the transport of a commodity from a set of supply locations to a set of demand locations is considered. At each location the inventory must be kept within predefined bounds, and the location specific supply and demand rates are constant throughout the time horizon. Each location can be visited several times during the time horizon, and the vehicle can visit the locations in any order as long as the capacity of the vehicle is not exceeded. Two models are presented, each defined on a different extended network. In a location-event model, the nodes are indexed by the location and the number of visits made so far to that location, while in a vehicle-event model the nodes are indexed by the location and the number of visits so far on the vehicle route. Both models are based on continuous time formulations. Bounds on the number of vehicle visits are discussed and a new branching algorithm is proposed. Computational tests based on a set of maritime transportation instances are reported to compare both models and test the new branching algorithm.

Title: Exploiting an Integer Linear Programming Formulation for the Hypervolume Subset Selection Problem

Authors: Andreia P. Guerreiro (INESC-ID, CEGIST, IST, UL), Vasco Manquinho (INESC-ID, CEGIST, DEI,  IST, UL) and José Rui Figueira (CEGIST, DEG, IST, UL)

Abstract: Multiobjective optimization problems consist of the simultaneous minimization (or maximization) of multiple objective functions. Due to the usually conflicting nature of objectives, typically no single optimal solution exist, but instead there is a (possibly large) set of Pareto-optimal solutions. Often the aim in multiobjective optimization is to find a diverse subset of the Pareto-optimal solutions, for example, to present to the Decision Maker only a small number of Pareto-optimal solutions. This may be interpreted as a subset selection problem where the goal is to find a bounded-size subset of solutions that maximize a given set-quality indicator. Such indicators are used to evaluate solution sets by mapping (the image of) a solution set into a single scalar value. The hypervolume indicator is one of the most commonly used quality indicators due to its theoretical properties. The Hypervolume Subset Selection Problem (HSSP) consists of selecting a subset of k points out of a set of n points that maximizes the hypervolume indicator. This problem may arise not only when selecting which solutions to present to the Decision Maker but also within the search process, for example, in the selection step of evolutionary multiobjective optimization algorithms. Hence, it is important that the HSSP can be computed in a reasonable amount of time. Although polynomial-time algorithms exist for solving the HSSP with 2 objectives, already with 3 objectives the HSSP is solved efficiently only for particular cases, such as k = n-1, or by computing an approximation with greedy algorithms. Even though a few exact algorithms exist to compute the HSSP for 3 or more objectives and k < n-1, faster algorithms are required to make its use more practical. In this talk, a new integer linear programming formulation for the HSSP is presented, as well as an algorithm that exploits such formulation to considerably speed up the computation time of the HSSP.

Title: The family traveling salesman problem with incompatibility constraints

Authors: Raquel Bernardino (CMAFcIO, ISEG, UL)  e Ana Paias (CMAFcIO, DEIO, Ciências, UL)

Abstract: Consider a depot and a partition of the set of nodes into subsets, called families. The objective of the family traveling salesman problem (FTSP) is to find the minimum cost route that starts and ends at the depot and visits a given number of nodes per family. The FTSP finds its practical application in the order picking problem in warehouses with chaotic storage, such as those of Amazon. We propose a new variant of the FTSP by introducing incompatibilities between the families, that is, incompatible families cannot be visited in the same route. Thus, the FTSP with incompatibility constraints (FTSP-IC) consists of determining the minimum cost set of routes that begins and ends at the depot; visits a given number of cities in each family; and does not visit incompatible nodes in the same route. We propose compact and non-compact formulations for the FTSP-IC, which model the incompatibility constraints for each family implicitly in the compatibility graph. We also present a new set of valid inequalities. To evaluate the different models, we used the benchmark instances for the FTSP and generated incompatibility matrices. The computational experiment shows that the non-compact models outperform the compact ones. As the exact methods are unable to address the largest sized instances, we developed two heuristic methods, namely an ant colony optimization algorithm and an iterated local search. Both heuristic algorithms are able to efficiently obtains solutions with a lower value than the branch-and-cut algorithm for most of the instances with an unknown optimal value.

Title: The Discrete p-Center Location Problem with Upgraded Connections

Authors: Laura Anton-Sanchez (Departamento de Estadı́stica, Matemáticas e Informática, Centro de Investigación Operativa, Universidad Miguel Hernández), Mercedes Landete (Departamento de Estadı́stica, Matemáticas e Informática, Centro de Investigación Operativa, Universidad Miguel Hernández) and Francisco Saldanha-da-Gama (CMAFcIO, DEIO, Ciências, UL)

Abstract: In this work we investigate different upgrading strategies in the context of the p-center problem. In particular, we look into whether a better solution can be achieved by reducing in some way the allocation costs, thus obtaining the so-called upgraded solutions. We consider the possibility of upgrading a set of connections to different facilities as well as the possibility of upgrading entire facilities, i.e., all connections made to them. Two variants for these perspectives are considered: (i) a limit is imposed on the number of connections or facilities that can be upgraded; (ii) a budget exists that limits the upgrades that can be made. We introduce different MILP models for those problems and their variants as well as lower and upper bounds, and we test the new models and bounds using benchmark instances. The information provided by the models proposed in this work can be extremely useful to a decision-maker because together with the location decision, the models directly seek to find structures underlying the problem that can be ''upgraded'' in such a way that a better after-upgrading solution is obtained.

Title: Optimization approaches to the ambulance dispatching and relocation problem

Authors: Ana Sofia Carvalho (CMAFcIO, Siscog) and Maria Eugénia Captivo (CMAFcIO, DEIO, Ciências, UL) 

Abstract: In the Emergency Medical Service (EMS) context, there are three levels of decision: strategic, tactical, and operational. We focus on the operational level by solving the ambulance dispatching and relocation problems. Dispatching decisions assign ambulances to emergencies, and the relocation problem decides to which base ambulances should be (re)assigned. Different ambulance types, which vary in the equipment and crews, should be used according to the emergency severity. Having the Portuguese EMS as a case study, several real-life features are considered, such as extra time above the maximum response time, the setup time to crews to get ready, and ambulances’ working shifts. We propose a new preparedness measure to achieve a good service level for current and future emergencies, considering different ambulance types. The proposed strategy considers the preparedness measure and allows relocations to any base. A mathematical model and a pilot-method heuristic are developed to solve these problems. We develop a decision support system to help the EMS managers in the decision-making process. We use a Geographic Information System (GIS) to develop a GIS-based tool. The proposed strategy and the current Portuguese EMS strategy, which dispatches the closest available ambulance and relocates ambulances to their home bases, are embedded in this tool. Running simulations for all day, we highlight the proposed strategy's potential.

Title: Compact formulations for multi-depot routing problems

Authors: Tolga Bektaş (Dept of Operations and Supply Chain Management, Univ of Liverpool),  Luís Gouveia (CMAFcIO, DEIO, Ciências, UL) and Daniel Santos (CEGIST, IST UL)

Abstract: Multi-depot routing problems mainly arise in distribution logistics where a fleet of vehicles are used to serve clients from a number of (potential) depots. The problem concerns deciding on the routes of each vehicle and the depots from which the vehicles depart, so as to minimize the total cost of travel. This work reviews a number of existing compact formulations, and proposes new ones, for two types of multi-depot routing problems, one that includes the depot selection decisions, and the other where depots are pre-selected. The formulations are compared theoretically in terms of the strength of their linear programming relaxation, and computationally in terms of the running time needed to solve the instances to optimality.