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.

Tabu search based algorithms are among the widely used heuristic algorithms for combinatorial optimization problems. In this project, we propose an improved enhanced tabu search algorithm for the well-known combinatorial optimization problem, the quadratic assignment problem (QAP). The new algorithm was tested on a number of instances from the library of the QAP instances  QAPLIB. The results obtained from the experiments show that the proposed algorithm appears to be superior to the earlier "pure" tabu search algorithms on many instances of the QAP.

In the last two decades, the western world witnessed a continuous rise in the health expenditure. Meanwhile, complaints from patients on excessive waiting times are also increasing. In the past, many researchers have tried to devise appointment scheduling rules to provide trade-offs between maximizing patients’ satisfaction and minimizing the costs of the health providers. For instance, this challenge appears appointment scheduling problems (ASP). Commonly used methods in ASP include analytical methods, simulation studies, and combination of simulation with heuristic approaches. Analytical methods (e.g., queuing theory and mathematical programming) face challenges of fully capturing the complexities of systems and usually make strong assumptions for tractability of problems. These methods simplify the whole system to a single-stage unit and ignore the actual system factors such as the presence of multiple stages and/or resource constraints. Simulation studies, conversely, are able to model most complexities of the actual system, but they typically lack an optimization strategy to deliver optimal appointment schedules. Also, heuristic approaches normally are based on intuitive rules and do not perform well as standalone methods. In order to reach an optimal schedule while considering complexities in actual health care systems, this thesis proposes efficient and effective methods that yield (near) optimal appointment schedules by integrating mathematical programming, a tabu search optimization algorithm and discrete event simulation. The proposed methodologies address the challenges and complexities of scheduling in real world multistage healthcare units in the presence of stochastic service durations, a mix of patient types, patients with heterogeneous service sequence, and resource constraints. Moreover, the proposed methodology is capable of finding the optimum considering simultaneously multiple performance criteria. A Pareto front (a set of optimal solutions) for the performance criteria can be obtained using the proposed methods. Healthcare management can use the Pareto front to choose the appropriate policy based on different conditions and priorities. In addition, the proposed method has been applied to two case studies of Operating Rooms departments in two major Canadian hospitals. The comparison of actual schedules and the ones yielded by the proposed method indicates that proposed method can improve the appointment scheduling in realistic clinical settings.

To understand evolution, and to discover how different species are related, gene order analysis is a useful tool. Problems in this area can usually be formulated in a combinatorial language. We regard genomes as signed, or unsigned permutations, and thus evolutionary operations like inversions (reversing the order of a segment of genes) are easy to describe combinatorially. A commonly studied problem is to determine the evolutionary distance between two species. This is estimated by several combinatorial distances between gene order permutations, for instance the inversion distance. The main objective of this work was to survey the existing algorithms for genome comparison and to present new approach for solving this problem. The work led to these results: - We have surveyed existing approaches of genome comparison, namely comparison by inversion distance in signed and unsigned cases. It appeared that sorting signed genomes by inversions is done in quadratic time, but sorting unsigned genomes by inversions is NP-hard. - We have proposed the method of how to apply heuristic algorithms for sorting unsigned genomes by inversions. - We have applied tabu search and genetic algorithm to solve the sorting unsigned genomes by inversions problem. - We have experimentally proven, that the worst case solutions to sorting unsigned genomes by inversions found by heuristics (tabu search and genetic algorithm) are better then ones expected from best known approximating algorithm used for... [to full text]

In the last two decades, the western world witnessed a continuous rise in the health expenditure. Meanwhile, complaints from patients on excessive waiting times are also increasing. In the past, many researchers have tried to devise appointment scheduling rules to provide trade-offs between maximizing patients’ satisfaction and minimizing the costs of the health providers. For instance, this challenge appears appointment scheduling problems (ASP). Commonly used methods in ASP include analytical methods, simulation studies, and combination of simulation with heuristic approaches. Analytical methods (e.g., queuing theory and mathematical programming) face challenges of fully capturing the complexities of systems and usually make strong assumptions for tractability of problems. These methods simplify the whole system to a single-stage unit and ignore the actual system factors such as the presence of multiple stages and/or resource constraints. Simulation studies, conversely, are able to model most complexities of the actual system, but they typically lack an optimization strategy to deliver optimal appointment schedules. Also, heuristic approaches normally are based on intuitive rules and do not perform well as standalone methods. In order to reach an optimal schedule while considering complexities in actual health care systems, this thesis proposes efficient and effective methods that yield (near) optimal appointment schedules by integrating mathematical programming, a tabu search optimization algorithm and discrete event simulation. The proposed methodologies address the challenges and complexities of scheduling in real world multistage healthcare units in the presence of stochastic service durations, a mix of patient types, patients with heterogeneous service sequence, and resource constraints. Moreover, the proposed methodology is capable of finding the optimum considering simultaneously multiple performance criteria. A Pareto front (a set of optimal solutions) for the performance criteria can be obtained using the proposed methods. Healthcare management can use the Pareto front to choose the appropriate policy based on different conditions and priorities. In addition, the proposed method has been applied to two case studies of Operating Rooms departments in two major Canadian hospitals. The comparison of actual schedules and the ones yielded by the proposed method indicates that proposed method can improve the appointment scheduling in realistic clinical settings.

There is an increasing interest in sustainability and a growing debate about environmental policy measures aiming at the reduction of green house gas emissions across di erent economic sectors worldwide. The transportation sector is one major greenhouse gas emitter which is heavily regulated to reduce its dependance on oil. These regulations along with the growing customer awareness about global warming has led vehicle manufacturers to seek di erent technologies to improve vehicle e ciencies and reduce the green house gases emissions while at the same time meeting customer's expectation of mobility and exibility. Plug-in hybrid electric vehicles (PHEV) is one major promising solution for a smooth transition from oil dependent transportation sector to a clean electric based sector while not compromising the mobility and exibility of the drivers. In the medium term, plug-in hybrid electric vehicles (PHEV) can lead to signi cant reductions in transportation emissions. These vehicles are equipped with a larger battery than regular hybrid electric vehicles which can be recharged from the grid. For short trips, the PHEV can depend solely on the electric engine while for longer journeys the alternative fuel can assist the electric engine to achieve extended ranges. This is bene cial when the use pattern is mixed such that and short long distances needs to be covered. The plug-in hybrid electric vehicles are well-suited for logistics since they can avoid the possible disruption caused by charge depletion in case of all-electric vehicles with tight time schedules. The use of electricity and fuel gives rise to a new variant of the classical vehicle routing with time windows which we call the plug-in hybrid electric vehicle routing problem with time windows (PHEVRPTW). The objective of the PHEVRPTW is to minimize the routing costs of a eet of PHEVs by minimizing the time they run on gasoline while meeting the demand during the available time windows. As a result, the driver of the PHEV has two decisions to make at each node: (1) recharge the vehicle battery to achieve a longer range using electricity, or (2) continue to the next open time window with the option of using the alternative fuel. In this thesis, we present a mathematical formulation for the plug-in hybrid-electric vehicle routing problem with time windows. We solve this problem using a Lagrangian relaxation and we propose a new tabu search algorithm. We also present the rst results for the full adapted Solomon instances.

[pt] As técnicas de tecnologia de grupos vêm sendo largamente usadas em muitos sistemas de manufatura. Vários algoritmos têm sido propostos para o projeto otimizado de eficientes células de manufatura. O problema de formação de células deve levar em conta vários objetivos: o número de operações gargalo, o número de máquinas e/ou peças gargalo, o fluxo intercelular, os custos de subcontratação, os custos de duplicação de máquinas e a carga da máquina e/ou célula mais sobrecarregada, entre outros. Nesta tese propõe-se uma metodologia multi- critério para resolver o problema de formação de células com múltiplos objetivos. Este enforque é baseado no uso da meta-heurística busca tabu para resolver uma seqüência de problemas com objetivos simples e restrições múltiplas, onde cada objetivo é minimizado individualmente, segundo sua ordem de importância. Resultados computacionais envolvendo uma aplicação para um problema bi-critério são apresentados para casos com até 100 máquinas e 1000 peças. / [en] Group tecnology techniques are now widely used in many manufacturing systems. Severla algorithms have been proposed for the optimal design of efficient manufacturing cells. The cell formation problem must take into account several objectives: the number of bottleneck operations, the number of bottleneck machines and/or parts, the intercell flow, the intracell workload balancing, the subcontracting cost, the machine duplication costs, and the workload of the busiest machine and/or cell, among athers. In this work, we propose a multi-criteria methodology for solving the cell formation problem with multiple objectives. This approach is based on the use of the tabu search meta-heuristic for solving a sequence of single-objective, multi-contrained problems, in wich each objective is taken and optimized in turn, following their order of relative importance. Computational results concerning an application to a bi-criteria problem are reported for instances with up 100 machines and 1000 parts.

A programação de tarefas em linhas de produção nas empresas sempre foi e continua sendo um elemento fundamental para o sucesso das organizações em um mercado tão globalizado e competitivo. A melhor utilização dos recursos instalados através da melhor alocação das tarefas gerará melhores resultados para a organização. Entende-se pela melhor utilização dos recursos a redução do tempo total de finalização das tarefas (makespan) sem prejudicar o atendimento da data de entrega. Aplica-se esta idéia para as indústrias de um modo geral, que tenham linhas de produção, podendo citar a indústria calçadista, foco neste trabalho, as indústrias de massas, biscoitos e balas, entre outras. Na literatura especializada, esta programação é conhecida como sequenciamento de tarefas em processadores. Neste trabalho aplicado junto a indústria calçadista, foca-se em uma área mais específica: o sequenciamento de tarefas em processadores paralelos. Os problemas de sequenciamento se caracterizam pela grande exigência computacional para a resolução com algoritmos de otimização. Isto remete a utilização de heurísticas para a resolução destes problemas. Neste trabalho explora-se a Meta-Heurística Busca Tabu, que se apresentou com resultados muito bons em relação ao ótimo e em relação ao trabalhador humano. / The jobs scheduling in processor lines in the companies was always, and continues being, a fundamental element to the organization’s success in a very globalized and competitive market. The best use of the installed resources, through the best distribution of the jobs will generate better results for the organization. The best utilization of the resources means the reduction of the makespan without prejudicing the due-date. This idea is applied to all industries in general, that have processor lines, for example the shoes factories, focused in this research, pasta, cookies and sugar balls factories, beyond others. In the specialized literature this subject is know as job scheduling. This researh is applyed to a shoes factory is focused on more specific area: the job scheduling in parallel machines. The scheduling problems are characterized on its computational difficulty using optimization algoritms. That is the reason why we used heuristics to solve these problems. In this research we explore the Meta-Heuristic Tabu Search, wich showed very good results comparing to the optimun and comparing to the human worker.

Os problemas logísticos estão se apoiando de forma bastante expressiva na pesquisa operacional a fim de obter uma maior eficiência em suas operações. Dentre os vários problemas relacionados à designação de veículos em um sistema logístico, o de escalonamento de veículos com múltiplas garagens, MDVSP (Multiple Depot Vehicle Scheduling Problem), vem sendo abordado em diversas pesquisas. O MDVSP pressupõe a existência de garagens que interferem no planejamento das sequências com as quais as viagens devem ser executadas. Frequentemente, métodos exatos não podem resolver as grandes instâncias encontradas na prática e, para poder levá-las em consideração, várias abordagens heurísticas estão sendo desenvolvidas. O principal objetivo deste trabalho, portanto, foi solucionar o MDVSP através de uma heurística utilizando o método de busca-tabu. A principal motivação para a realização deste trabalho surgiu a partir da indicação de que apenas recentemente o uso de meta-heurísticas está sendo aplicado ao MDVSP (Pepin et al. 2008) e das limitações elencadas no estudo de Rohde (2008), o qual utilizou o algoritmo branch-and-bound em uma das etapas da heurística apresentada para resolver o problema, o que fez aumentar o tempo de resolução do problema. O método de pesquisa para solução deste problema foi baseado em adaptações das tradicionais técnicas de pesquisa operacional, e propiciou a resolução do MDVSP apresentando resultados bastante competitivos quanto ao custo da função objetivo, número de veículos utilizados e tempo computacional necessário. / Currently the logistical problems are relying quite significantly on Operational Research in order to achieve greater efficiency in their operations. Among the various problems related to the vehicles scheduling in a logistics system, the Multiple Depot Vehicle Scheduling Problem (MDVSP) has been addressed in several studies. The MDVSP presupposes the existence of depots that affect the planning of sequences to which travel must be performed. Often, exact methods cannot solve large instances encountered in practice and in order to take them into account, several heuristic approaches are being developed. The aim of this study was thus to solve the MDVSP using a meta-heuristic based on tabu-search method. The main motivation for this work came from the indication that only recently the use of meta-heuristics is being applied to MDVSP context (Pepin et al. 2008) and, also, the limitations listed by Rohde (2008) in his study, which used the branch-and-bound in one of the steps of the heuristic presented to solve the problem, which has increased the time resolution. The research method for solving this problem was based on adaptations of traditional techniques of Operational Research, and provided resolutions presenting very competitive results for the MDVSP such as the cost of the objective function, number of vehicles used and computational time.

O desenho e a gestão de uma cadeia de suprimentos apresentam-se, hoje, como um dos problemas mais importantes e de difícil resolução encontrado pelos gestores. A gestão da cadeia de suprimentos é uma das áreas de maior interesse da Pesquisa Operacional aplicada, buscando determinar a melhor estratégia de produção, transporte e estoque com menor custo e tempo possíveis. Esta dissertação apresenta os resultados de um estudo que objetivou implementar e avaliar uma heurística baseada em Busca Tabu para otimização de uma rede de cadeia de suprimentos. Para tanto, foi utilizada uma modelagem single-source proposta por Farias e Borenstein (2012). O problema foi resolvido com uma adaptação do método de Lee e Kwon (2010), buscando por meio de operações de troca de centros de distribuição (CDs) e arcos encontrar a configuração de menor custo para uma rede de cadeia de suprimentos. Foram resolvidas as 22 instâncias propostas por Farias e Borenstein (2012) e os resultados comprovam que, para esses cenários, o método aplicado teve um bom desempenho computacional, obtendo resultados com uma redução de 81,03% no tempo médio de processamento; contudo, as soluções obtidas pela heurística apresentaram custos médios 4,98% superiores aos resultados ótimos. Por fim, o problema foi resolvido para outras quatro instâncias com características reais, comprovando a eficiência da heurística para problemas de grande escala, visto que todas as soluções foram obtidas em um tempo inferior a 2 minutos de processamento. / The design and supply chain management are currently one of the most important and difficult problems encountered by business managers. Supply chain management is one of the most engaging areas in applied Operations Research, which seeks to determine the best strategy regarding production, shipping and storage at the lowest cost and shortest time possible. This thesis shows the results of a research that aimed to implement and evaluate a heuristic based on Tabu Search to optimize a supply chain network. For this purpose, a single-source model proposed by Farias and Borenstein (2012) was used. The problem was solved by adapting the Lee and Kwon method (2010), exchanging distribution centers (DCs) and arcs, to find the lowest cost for a supply chain network. Twenty two instances proposed by Farias and Borenstein (2012) were resolved and the results indicate that, for these scenarios, the applied method had a good computational performance, getting results with 81.03% of reduction in the average processing time. However, there was an increase of 4.98% in the average cost of the solutions obtained through the heuristic method when compared to the optimal results. Finally, the problem was solved for four other instances with real features, proving the efficiency of the heuristic for large-scale problems, since all solutions were obtained in a time less than 2 minutes of processing.