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.

Towards a GIS-T database design and implementation for public transit planning: the case study of Dar-Es-salaam metropolitan city, Tanzania.

Dissertation submitted in partial fulfilment of the requirements for the Degree of Master of Science in Geospatial Technologies

Utilização do processador Cell para o processamento de dados obtidos por tomografia aplicada a materiais compósitos

Dissertação de Mestrado em Engenharia Informática

The significance of Traveler's Route Knowledge for Choice of commuting mode of transport

Dissertation submitted in partial fulfillment of the requirements for the Degree of Master of Science in Geospatial Technologies.

Time diversity solutions to cope with lost packets

A dissertation submitted to Departamento de Engenharia Electrotécnica of Faculdade de Ciências e Tecnologia of Universidade Nova de Lisboa in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Engenharia Electrotécnica e de Computadores

A random access MAC protocol for MPR satellite 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

QoS in LEO satellite networks with multipacket reception

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

High ffficiency transmission techniques for broadband wireless systems

Future broadband wireless systems are expected to cope with severely time dispersive channels, due to multi-path signal propagation between the transmitter and the receiver while having high power and spectral efficiency. Thus, advanced Frequency Domain Equalization techniques are required. The implementation complexity in mobile terminals should be as low as possible to achieve highest possible efficiency. Therefore, most of the signal processing requirements will be shifted to the base station and we will employ signals compatible with an efficient, grossly nonlinear power amplification. For this reason, we will consider offset modulation signals with quasi-constant envelope and develop receivers that will obtain good BER performance. However, these signals require a bandwidth significantly above the Nyquist rate, which can be reduced by an overlap of different frequency channels.

Desenvolvimento e aplicação do algoritmo enxame de partículas na determinação da máxima injeção nodal em redes de energia elétrica

O objetivo desta dissertação é a determinação da máxima injeção nodal numa rede de energia elétrica, ou seja, qual o valor total máximo de potência ativa que é possível injetar e qual a sua distribuição pelos diversos nós da rede simultaneamente. Determinámos esta máxima injeção nodal em duas situações distintas: injeção não simultânea, injetando potência em um só nó de cada vez e injeção simultânea, injetando potência em todos os nós da rede simultaneamente. Sendo este um problema de natureza combinatória, utilizámos para esta determinação o algoritmo conhecido como nuvem ou enxame de partículas, adaptando-o ao nosso problema. Desenvolvemos o software na linguagem de programação Python utilizando o ambiente Eclipse. Para resolver o trânsito de energia utilizámos o programa PSSE University.Para os exemplos de aplicação utilizámos duas redes de energia elétrica, uma de 6 e outra de 14 barramentos. Estas redes foram baseadas nas redes IEEE 6 BUS e IEEE 14 BUS respetivamente. Concluímos que o algoritmo nuvem ou enxame de partículas cumpriu o objetivo traçado, obtendo as melhores soluções para cada um dos casos, máxima injeção nodal não simultânea e máxima injeção nodal simultânea. No contexto deste problema, o parâmetro chave do algoritmo, comprovado pelos ensaios feitos, é a velocidade máxima de deslocação das partículas, tomando valores típicos de 7 a 10 para a rede de 6 barramentos e de 20 a 25 para a de 14 barramentos.

Multipacket reception in the presence of in-band full-duplex communication

In-Band Full-DupleX (IB-FDX) is defined as the ability for nodes to transmit and receive signals simultaneously on the same channel. Conventional digital wireless networks do not implement it, since a node’s own transmission signal causes interference to the signal it is trying to receive. However, recent studies attempt to overcome this obstacle, since it can potentially double the spectral efficiency of current wireless networks. Different mechanisms exist today that are able to reduce a significant part of the Self- Interference (SI), although specially tuned Medium Access Control (MAC) protocols are required to optimize its use. One of IB-FDX’s biggest problems is that the nodes’ interference range is extended, meaning the unusable space for other transmissions and receptions is broader. This dissertation proposes using MultiPacket Reception (MPR) to address this issue and adapts an already existing Single-Carrier with Frequency-Domain Equalization (SC-FDE) receiver to IB-FDX. The performance analysis suggests that MPR and IB-FDX have a strong synergy and are able to achieve higher data rates, when used together. Using analytical models, the optimal transmission patterns and transmission power were identified, which maximize the channel capacity with the minimal energy consumption. This was used to define a new MAC protocol, named Full-duplex Multipacket reception Medium Access Control (FM-MAC). FM-MAC was designed for a single-hop cellular infrastructure, where the Access Point (AP) and the terminals implement both IB-FDX and MPR. It divides the coverage range of the AP into a closer Full-DupleX (FDX) zone and a farther Half-DupleX (HDX) zone and adds a tunable fairness mechanism to avoid terminal starvation. Simulation results show that this protocol provides efficient support for both HDX and FDX terminals, maximizing its capacity when more FDX terminals are used.