A clustering approach for vehicle routing problems with hard time windows

Dissertação para obtenção do Grau de Mestre em Logica Computicional

Sistema de Informação Geográfica aplicado ao transporte de reclusos

Trabalho de Projeto apresentado como requisito parcial para obtenção do grau de Mestre em Ciência e Sistemas de Informação Geográfica

Heuristics and policies for online pickup and delivery problems

Master Thesis

Multipath inter-domain policy routing

Dissertação submetida para a obtenção do grau de Doutor em Engenharia Electrotécnica e de Computadores

Multipath policy routing in packet switched networks

Dissertação apresentada para obtenção do Grau de Mestre em Engenharia Electrotécnica e de Computadores, pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia

Planning and verification of multipath routing protocols

Conventionally the problem of the best path in a network refers to the shortest path problem. However, for the vast majority of networks present nowadays this solution has some limitations which directly affect their proper functioning, as well as an inefficient use of their potentialities. Problems at the level of large networks where graphs of high complexity are commonly present as well as the appearing of new services and their respective requirements, are intrinsically related to the inability of this solution. In order to overcome the needs present in these networks, a new approach to the problem of the best path must be explored. One solution that has aroused more interest in the scientific community considers the use of multiple paths between two network nodes, where they can all now be considered as the best path between those nodes. Therefore, the routing will be discontinued only by minimizing one metric, where only one path between nodes is chosen, and shall be made by the selection of one of many paths, thereby allowing the use of a greater diversity of the present paths (obviously, if the network consents). The establishment of multi-path routing in a given network has several advantages for its operation. Its use may well improve the distribution of network traffic, improve recovery time to failure, or it can still offer a greater control of the network by its administrator. These factors still have greater relevance when networks have large dimensions, as well as when their constitution is of high complexity, such as the Internet, where multiple networks managed by different entities are interconnected. A large part of the growing need to use multipath protocols is associated to the routing made based on policies. Therefore, paths with different characteristics can be considered with equal level of preference, and thus be part of the solution for the best way problem. To perform multi-path routing using protocols based only on the destination address has some limitations but it is possible. Concepts of graph theory of algebraic structures can be used to describe how the routes are calculated and classified, enabling to model the routing problem. This thesis studies and analyzes multi-path routing protocols from the known literature and derives a new algebraic condition which allows the correct operation of these protocols without any network restriction. It also develops a range of software tools that allows the planning and the respective verification/validation of new protocols models according to the study made.

A public transport bus assignment problem: parallel metaheuristics assessment

Combinatorial Optimization Problems occur in a wide variety of contexts and generally are NP-hard problems. At a corporate level solving this problems is of great importance since they contribute to the optimization of operational costs. In this thesis we propose to solve the Public Transport Bus Assignment problem considering an heterogeneous fleet and line exchanges, a variant of the Multi-Depot Vehicle Scheduling Problem in which additional constraints are enforced to model a real life scenario. The number of constraints involved and the large number of variables makes impracticable solving to optimality using complete search techniques. Therefore, we explore metaheuristics, that sacrifice optimality to produce solutions in feasible time. More concretely, we focus on the development of algorithms based on a sophisticated metaheuristic, Ant-Colony Optimization (ACO), which is based on a stochastic learning mechanism. For complex problems with a considerable number of constraints, sophisticated metaheuristics may fail to produce quality solutions in a reasonable amount of time. Thus, we developed parallel shared-memory (SM) synchronous ACO algorithms, however, synchronism originates the straggler problem. Therefore, we proposed three SM asynchronous algorithms that break the original algorithm semantics and differ on the degree of concurrency allowed while manipulating the learned information. Our results show that our sequential ACO algorithms produced better solutions than a Restarts metaheuristic, the ACO algorithms were able to learn and better solutions were achieved by increasing the amount of cooperation (number of search agents). Regarding parallel algorithms, our asynchronous ACO algorithms outperformed synchronous ones in terms of speedup and solution quality, achieving speedups of 17.6x. The cooperation scheme imposed by asynchronism also achieved a better learning rate than the original one.

Autonomous behaviors for an unmanned mini-aerial vehicle

This thesis aims at addressing the development of autonomous behaviors, for search and exploration with a mini-UAV (Unmanned Aerial Vehicle), or also called MAV (Mini Aerial Vehicle) prototype, in order to gather information in rescue scenarios. The platform used in this work is a four rotor helicopter, known as quad-rotor from the German company Ascending Technologies GmbH, which is later assembled with a on-board processing unit (i.e. a tiny light weight computer) and a on-board sensor suite (i.e. 2D-LIDAR and Ultrasonic Sonar). This work can be divided into two phases. In the first phase an Indoor Position Tracking system was settled in order to obtain the Cartesian coordinates (i.e. X, Y, Z) and orientation (i.e.heading) which provides the relative position and orientation of the platform. The second phase was the design and implementation of medium/high level controllers on each command input in order to autonomously control the aircraft position, which is the first step towards an autonomous hovering flight, and any autonomous behavior (e.g. Landing, Object avoidance, Follow the wall). The main work is carried out in the Laboratory ”Intelligent Systems for Emergencies and Civil Defense”, in collaboration with ”Dipartimento di Informatica e Sistemistica” of Sapienza Univ. of Rome and ”Istituto Superiore Antincendi” of the Italian Firemen Department.

Multi-region routing

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para a obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores

Integrando problem frames com aspectos

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Informática

A new approach to the initial value problem

5th Portuguese Conference on Automatic Control, September, 5-7, 2002, Aveiro, Portugal

Including context in a routing algorithm for the internet of things

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Informática

Scale-free networks and scalable interdomain routing

Trabalho apresentado no âmbito do Mestrado em Engenharia Informática, como requisito parcial para obtenção do grau de Mestre em Engenharia Informática

SENSITIVITY ANALYSIS OF TRACK VIBRATIONS DUE TO VERTICAL STIFFNESS VARIATION IN HIGH-SPEED RAILWAYS

High speed trains, when crossing regions with abrupt changes in vertical stiffness of the track and/or subsoil, may generate excessive ground and track vibrations. There is an urgent need for specific analyses of this problem so as to allow reliable esimates of vibration amplitude. Full understanding of these phenomena will lead to new construction solutions and mitigation of undesirable features. In this paper analytical transient solutions of dynamic response of one-dimensional systems with sudden change of foundation stiffness are derived. Results are expressed in terms of vertical displacement. Sensitivity analysis of the response amplitude is also performed. The analytical expressions presented herein, to the authors’ knowledge, have not been published yet. Although related to one-dimensional cases, they can give useful insight into the problem. Nevertheless, in order to obtain realistic response, vehicle- rail interaction cannot be omitted. Results and conclusions are confirmed using general purpose commercial software ANSYS. In conclusion, this work contributes to a better understanding of the additional vibration phenomenon due to vertical stiffness variation, permitting better control of the train velocity and optimization of the track design.

Gestão integrada da doença : uma abordagem experimental de gestão em sa

RESUMO - Os sistemas de saúde deparam-se, actualmente, com novos paradigmas, ao nível da qualidade da prestação de cuidados de saúde, bem como no que se refere à necessidade de controlo dos custos com o sector da saúde, obrigando as organizações a adaptarem-se por forma a fornecerem a resposta mais adequada às crescentes necessidades dos indivíduos. O reconhecimento desta realidade tem levado os governos de muitos países a definir políticas orientadas para problemas de saúde específicos e a adoptar estratégias de intervenção que privilegiam uma abordagem integrada com o objectivo de melhorarem progressivamente o nível de saúde das populações, a qualidade dos cuidados prestados e a eficiência na utilização de recursos. Em Portugal, a aplicação dos princípios que estiveram na base dos modelos de gestão da doença, deu origem ao modelo experimental de Gestão Integrada da Doença, que incorpora a gestão clínica da doença, centrada no doente, com especial enfoque na sua autogestão e na clarificação das melhores práticas profissionais, visando a sua uniformização; a reorganização do modelo de prestação de cuidados, com a criação de Centros de Elevada Diferenciação e Centros de Tratamento, com especiais preocupações no que concerne à orientação do doente no sistema para que os cuidados lhe seja ministrados no nível mais adequado; um modelo de financiamento específico, indexado aos resultados, que reflicta a adopção das melhores práticas; um sistema de informação que permita a monitorização e avaliação constante deste processo. O desenvolvimento deste modelo organizacional tem-se revelado como uma estratégia inovadora e como uma ferramenta de elevado potencial para a melhoria da prestação de cuidados de saúde e para a promoção de uma maior efectividade e eficiência, tal como poderá, ainda, constituirse como um veículo, importante e permanente, de informação de apoio à decisão em Saúde. Este modelo visa, no fundo, promover uma acção concertada no sentido da obtenção de uma intervenção precisa, através da mobilização de recursos adequados, que permitam uma melhoria do estado de saúde, da qualidade de vida e do bem-estar global dos doentes. Esta abordagem passa pela colaboração e coordenação dos diferentes níveis de prestação de cuidados, no sentido de oferecerem cuidados integrados de saúde, com níveis de qualidade elevados em termos de prevenção, diagnóstico, tratamento, reabilitação e acompanhamento. ------------------------ --ABSTRACT – The health systems are faced with new paradigms, on one hand in the healthcare services delivered to the populations, and on the other hand, in the need to control costs in the health sector, forcing organizations to adapt and provide the most appropriate response to the individuals growing needs. The magnitude of this problem, in terms of public health, requires the adoption of a directed, targeted, planned and integrated action, based on clear and well defined strategies in order to obtain health gains, improving the quality of care and streamlining the costs. In Portugal, the application of those principles forming the basis of the disease management models, led to the Integrated Disease Management model which, apart from the clinical management of the disease, also incorporates the healthcare delivery structure reorganization, a specific financing model based on an information system that allows the process monitoring and evaluation. The development of Integrated Disease Management models is a central strategy and a tool for improving healthcare delivery, more effectively and efficiently, and can even be an important and permanent vehicle of information for health decision support. Therefore, it is important to promote a concerted action towards achieving a precise intervention, mobilizing the resources, improving the health status, quality of life and the overall patients’ wellbeing. This action means increasing collaboration and coordination of the different levels of care, offering integrated healthcare s