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.

Models for pheromone evaluation in Ant Systems for Mobile Ad-hoc networks

On a mobile ad-hoc network environment, where the resources are scarce, the knowledge about the network's link state is essential to optimize the routing procedures. This paper presents a study about different pheromone evaluation models and how they react to possible changes in traffic rate. Observing how the pheromone value on a link changes, it could be possible to identify certain patterns which can indicate the path status. For this study, the behavior of the Ant System evaluation model was compared with a Temporal Active Pheromone model (a biological approach) and a Progressive Pheromone Reduction model with and without a maximum pheromone limit.

Optimisation and design of post-tensioning anchorage corner blisters in concrete box girder bidges

The design of anchorage blisters of internal continuity post-tensioning tendons of bridges built by the cantilever method, presents some peculiarities, not only because they are intermediate anchorages but also because these anchorages are located in blisters, so the prestressing force has to be transferred from the blister the bottom slab and web of the girder. The high density of steel reinforcement in anchorage blisters is the most common reason for problems with concrete cast in situ, resulting in zones with low concrete compacity, leading to concrete crushing failures under the anchor plates. A solution may involve improving the concrete compression and tensile strength. To meet these requirements a high-performance fibre reinforced self-compacting mix- ture (HPFRC) was used in anchorage corner blisters of post-tensioning tendons, reducing the concrete cross-section and decreasing the reinforcement needed. To assess the ultimate capacity and the adequate serviceability of the local anchorage zone after reducing the minimum concrete cross-section and the confining reinforcement, specified by the anchorage device supplier for the particular tendon, load transfer tests were performed. To investigate the behaviour of anchorage blisters regarding the transmission of stresses to the web and the bottom slab of the girder, and the feasibility of using high performance concrete only in the blister, two half scale models of the inferior corner of a box girder existing bridge were studied: a reference specimen of ordinary reinforced concrete and a HPFRC blister specimen. The design of the reinforcement was based in the tensile forces obtained on strut-and-tie models. An experimental program was carried out to assess the models used in design and to study the feasibility of using high performance concrete only in the blister, either with casting in situ, or with precast solutions. A non-linear finite element analysis of the tested specimens was also performed and the results compared.