During an emergency evacuation, most people will use their vehicles to evacuate. However, there is a group of people who do not have access to reliable transportation or for some reason cannot drive, even if they have their own automobiles - the carless. There are different groups of carless (disabled, medically homebound, poor or immigrant populations, etc.) who require different forms of transportation assistance during an emergency evacuation. In this study we focus on those carless who are physically intact and able to walk to a set of designated locations for transportation during an emergency, and we propose using public transit and school buses to evacuate this carless group. A model has been developed to accommodate the use of public transit and school buses to efficiently and effectively evacuate the carless. The model has two parts. Part 1 is a location problem which aims at congregating the carless at some specific locations called evacuation sites inside the affected area. To achieve this goal, the affected area is partitioned into zones and this congregating of the carless has been formulated as a Single Source Capacitated Facility Location Problem. Changes in the demand of the carless in zones over different periods of a day and over different days of the week have been considered and included in the model. A walking time constraint is explicitly considered in the model. A heuristic developed by Klincewicz and Luss (1986) has been used to solve this location model.Part 2 is a routing problem which aims at obtaining itineraries of buses to pick up the carless at evacuation sites and transport them to safe locations outside the affected area, such that the total number of carless evacuated with the given time limit is maximized. A Tabu search heuristic has been developed for solving the routing problem. Computational results show that the Tabu search heuristic efficiently and effectively solves the routing problem; in particular, the initial heuristic produces a high quality initial solution in very short time. This study has also made slight contribution to the development of the Tabu search technique.

O presente trabalho aborda o Problema de Coleta Domiciliar Urbana (PCDU) de resíduos sólidos, tratado no nível tático de planejamento, em que zonas de coleta são definidas para cada dia da semana e designadas aos veículos coletores, cuja frota deve ser dimensionada. O problema estudado é baseado em um caso real, o qual possui como particularidades: cada zona de coleta é formada por regiões adjacentes e será representada por um nó-semente; a demanda de cada zona deverá ser atendida dentro do período de uma semana, conforme múltiplos programas possíveis de coleta; em um turno de um dia de trabalho um veículo poderá realizar múltiplas viagens; e há uma garagem para a frota e uma estação de transbordo, a qual possibilita que o veículo seja esvaziado para realizar outras viagens. A literatura apresenta alguns métodos heurísticos para a resolução de variantes deste problema, sendo os métodos exatos utilizados somente na resolução de instâncias pequenas, dado que o problema de VRP (Vehicle Routing Problem) é classificado como NP-hard. A imposição de adjacência é uma característica particular, a qual é justificada pela possível melhoria na utilização dos veículos em posterior planejamento operacional. São propostos um modelo matemático e um método heurístico para resolver o problema, sobre os quais são realizados experimentos computacionais. O método heurístico é aplicado sobre um estudo de caso de um problema de escala real, sendo obtida solução heurística como resultado. / The present work addresses the Urban Household Solid Waste Problem (UHSWP) on a tactical planning level, wherein collection zones are assigned to every week daywork and collection vehicles, which fleet is to be sized. The studied problem is based on a real case, such peculiarities as: each collection zone is a set of adjacent areas and a seed node represents it; the demand each zone must attended within a week, according to the several possible collection schedule; on a work day shift a vehicle can be assigned to multiple trips; and there is a base depot for the fleet and a transfer station, where the vehicles are unloaded, restoring their load capacity for the next trips. Literature presents heuristic methods for the solving of its problem variants, in which exact methos are only applied to small instances, due to the VRP (Vehicle Routing Problem) NP-hard property. The adjacency imposition is a peculiar feature, which is justified by the potential improvement on vehicle usage considering a posterior operational planning. A mathematical model and a heuristic method are proposed for the problem solving and evaluated by computational experiments. A real scale problem case study is solved by the heuristic method and the results are presented.

O presente trabalho aborda o Problema de Coleta Domiciliar Urbana (PCDU) de resíduos sólidos, tratado no nível tático de planejamento, em que zonas de coleta são definidas para cada dia da semana e designadas aos veículos coletores, cuja frota deve ser dimensionada. O problema estudado é baseado em um caso real, o qual possui como particularidades: cada zona de coleta é formada por regiões adjacentes e será representada por um nó-semente; a demanda de cada zona deverá ser atendida dentro do período de uma semana, conforme múltiplos programas possíveis de coleta; em um turno de um dia de trabalho um veículo poderá realizar múltiplas viagens; e há uma garagem para a frota e uma estação de transbordo, a qual possibilita que o veículo seja esvaziado para realizar outras viagens. A literatura apresenta alguns métodos heurísticos para a resolução de variantes deste problema, sendo os métodos exatos utilizados somente na resolução de instâncias pequenas, dado que o problema de VRP (Vehicle Routing Problem) é classificado como NP-hard. A imposição de adjacência é uma característica particular, a qual é justificada pela possível melhoria na utilização dos veículos em posterior planejamento operacional. São propostos um modelo matemático e um método heurístico para resolver o problema, sobre os quais são realizados experimentos computacionais. O método heurístico é aplicado sobre um estudo de caso de um problema de escala real, sendo obtida solução heurística como resultado. / The present work addresses the Urban Household Solid Waste Problem (UHSWP) on a tactical planning level, wherein collection zones are assigned to every week daywork and collection vehicles, which fleet is to be sized. The studied problem is based on a real case, such peculiarities as: each collection zone is a set of adjacent areas and a seed node represents it; the demand each zone must attended within a week, according to the several possible collection schedule; on a work day shift a vehicle can be assigned to multiple trips; and there is a base depot for the fleet and a transfer station, where the vehicles are unloaded, restoring their load capacity for the next trips. Literature presents heuristic methods for the solving of its problem variants, in which exact methos are only applied to small instances, due to the VRP (Vehicle Routing Problem) NP-hard property. The adjacency imposition is a peculiar feature, which is justified by the potential improvement on vehicle usage considering a posterior operational planning. A mathematical model and a heuristic method are proposed for the problem solving and evaluated by computational experiments. A real scale problem case study is solved by the heuristic method and the results are presented.