In this paper, we handle the problem of picking and delivering patients among the distinct units of a hospital. This problem is found in hospitals with several (specialized) units covering a large area, and it emerges from a real situation faced by a hospital in northern Italy. Patient transportation requests arrive dynamically during the day, and the hospital transportation department must service them all using capacitated and homogeneous vehicles. Each request is associated with a patient urgency level (weight) and a time window. The objective is to design vehicle routes to serve all requests and minimize the total weighted tardiness. To solve the problem, we propose a re-optimization heuristic based on two policies that mimic the patients’ and hospital’s decision-making processes. We then improve the solutions obtained with the policies using a tabu search. Computational results show that we can obtain high-quality solutions using the tabu search compared with the policies and a simulated annealing-based heuristic from the literature.

A Geração de Colunas (GC) é uma técnica para resolver Programas Lineares com um número muito grande de variáveis. Em vez de avaliar explicitamente custos reduzidos, as variáveis são geradas dinamicamente resolvendo problemas auxiliares de otimização conhecidos como subproblemas de pricing. A GC é uma das principais técnicas de otimização, sendo também eficaz em programação inteira, em algoritmos como Branch-and-Price e Branch-Cut-and-Price. Foi aplicada com sucesso em muitos tipos de roteamento de veículos, corte e empacotamento, planejamento de companhias aéreas, programação de horários, escalonamento de tripulações, coloração de grafos, clustering, dimensionamento de lotes e programação de máquinas, entre outros problemas. A palestra fornece uma visão geral da GC. A questão central explorada é - em que circunstâncias os algoritmos baseados em GC têm o potencial de superar outros métodos existentes? A discussão baseia-se em material do recente livro “Optimizing with Column Generation - advanced Branch-Cut-and-Price Algorithms (Part I)” disponível em https://optimizingwithcolumngeneration.github.io/.

Given a finite non-decreasing sequence d = (d₁, …, dₙ) of natural numbers, the Graph Realization problem asks whether d is a graphic sequence, i.e., there exists a labeled simple graph such that (d₁, …, dₙ) is the degree sequence of this graph. Such a problem can be solved in polynomial time due to the Erdős and Gallai characterization of graphic sequences. Since vertex degree is the size of a trivial edge cut, we consider a natural generalization of Graph Realization, where we are given a finite sequence d = (d₁, …, dₙ) of natural numbers (representing the trivial edge cut sizes) and a list of nontrivial cut constraints 𝒞 composed of pairs (Sⱼ, ℓⱼ) where Sⱼ ⊆ {v₁, …, vₙ}, and ℓⱼ is a natural number. In such a problem, we are asked whether there is a simple graph with vertex set V = {v₁, …, vₙ} such that vᵢ has degree dᵢ and ∂(Sⱼ) is an edge cut of size ℓⱼ, for each (Sⱼ, ℓⱼ) ∈ 𝒞. We show that such a problem is polynomial-time solvable whenever each Sⱼ has size at most three. Conversely, assuming P ≠ NP, we prove that it cannot be solved in polynomial time when 𝒞 contains pairs with sets of size four, and our hardness result holds even assuming that each dᵢ of d equals 1.