Improvements in the score matrix calculation method using parallel score estimating algorithm

The increasing amount of sequences stored in genomic databases has become unfeasible to the sequential analysis. Then, the parallel computing brought its power to the Bioinformatics through parallel algorithms to align and analyze the sequences, providing improvements mainly in the running time of these algorithms. In many situations, the parallel strategy contributes to reducing the computational complexity of the big problems. This work shows some results obtained by an implementation of a parallel score estimating technique for the score matrix calculation stage, which is the first stage of a progressive multiple sequence alignment. The performance and quality of the parallel score estimating are compared with the results of a dynamic programming approach also implemented in parallel. This comparison shows a significant reduction of running time. Moreover, the quality of the final alignment, using the new strategy, is analyzed and compared with the quality of the approach with dynamic programming.

Improvements in the sensibility of MSA-GA tool using COFFEE objective function

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Semiautomatic object-space road extraction combining a stereoscopic image pair and a TIN-Based DTM

In this letter, a semiautomatic method for road extraction in object space is proposed that combines a stereoscopic pair of low-resolution aerial images with a digital terrain model (DTM) structured as a triangulated irregular network (TIN). First, we formulate an objective function in the object space to allow the modeling of roads in 3-D. In this model, the TIN-based DTM allows the search for the optimal polyline to be restricted along a narrow band that is overlaid upon it. Finally, the optimal polyline for each road is obtained by optimizing the objective function using the dynamic programming optimization algorithm. A few seed points need to be supplied by an operator. To evaluate the performance of the proposed method, a set of experiments was designed using two stereoscopic pairs of low-resolution aerial images and a TIN-based DTM with an average resolution of 1 m. The experimental results showed that the proposed method worked properly, even when faced with anomalies along roads, such as obstructions caused by shadows and trees.

Generating unconstrained two-dimensional non-guillotine cutting patterns by a Recursive Partitioning Algorithm

In this study, a dynamic programming approach to deal with the unconstrained two-dimensional non-guillotine cutting problem is presented. The method extends the recently introduced recursive partitioning approach for the manufacturer's pallet loading problem. The approach involves two phases and uses bounds based on unconstrained two-staged and non-staged guillotine cutting. The method is able to find the optimal cutting pattern of a large number of pro blem instances of moderate sizes known in the literature and a counterexample for which the approach fails to find known optimal solutions was not found. For the instances that the required computer runtime is excessive, the approach is combined with simple heuristics to reduce its running time. Detailed numerical experiments show the reliability of the method. Journal of the Operational Research Society (2012) 63, 183-200. doi: 10.1057/jors.2011.6 Published online 17 August 2011

Exact Algorithms for Different Classes of Vehicle Routing Problems

We deal with five problems arising in the field of logistics: the Asymmetric TSP (ATSP), the TSP with Time Windows (TSPTW), the VRP with Time Windows (VRPTW), the Multi-Trip VRP (MTVRP), and the Two-Echelon Capacitated VRP (2E-CVRP). The ATSP requires finding a lest-cost Hamiltonian tour in a digraph. We survey models and classical relaxations, and describe the most effective exact algorithms from the literature. A survey and analysis of the polynomial formulations is provided. The considered algorithms and formulations are experimentally compared on benchmark instances. The TSPTW requires finding, in a weighted digraph, a least-cost Hamiltonian tour visiting each vertex within a given time window. We propose a new exact method, based on new tour relaxations and dynamic programming. Computational results on benchmark instances show that the proposed algorithm outperforms the state-of-the-art exact methods. In the VRPTW, a fleet of identical capacitated vehicles located at a depot must be optimally routed to supply customers with known demands and time window constraints. Different column generation bounding procedures and an exact algorithm are developed. The new exact method closed four of the five open Solomon instances. The MTVRP is the problem of optimally routing capacitated vehicles located at a depot to supply customers without exceeding maximum driving time constraints. Two set-partitioning-like formulations of the problem are introduced. Lower bounds are derived and embedded into an exact solution method, that can solve benchmark instances with up to 120 customers. The 2E-CVRP requires designing the optimal routing plan to deliver goods from a depot to customers by using intermediate depots. The objective is to minimize the sum of routing and handling costs. A new mathematical formulation is introduced. Valid lower bounds and an exact method are derived. Computational results on benchmark instances show that the new exact algorithm outperforms the state-of-the-art exact methods.

Optimal Supervisory Control of Hybrid Vehicles

Hybrid vehicles (HV), comprising a conventional ICE-based powertrain and a secondary energy source, to be converted into mechanical power as well, represent a well-established alternative to substantially reduce both fuel consumption and tailpipe emissions of passenger cars. Several HV architectures are either being studied or already available on market, e.g. Mechanical, Electric, Hydraulic and Pneumatic Hybrid Vehicles. Among the others, Electric (HEV) and Mechanical (HSF-HV) parallel Hybrid configurations are examined throughout this Thesis. To fully exploit the HVs potential, an optimal choice of the hybrid components to be installed must be properly designed, while an effective Supervisory Control must be adopted to coordinate the way the different power sources are managed and how they interact. Real-time controllers can be derived starting from the obtained optimal benchmark results. However, the application of these powerful instruments require a simplified and yet reliable and accurate model of the hybrid vehicle system. This can be a complex task, especially when the complexity of the system grows, i.e. a HSF-HV system assessed in this Thesis. The first task of the following dissertation is to establish the optimal modeling approach for an innovative and promising mechanical hybrid vehicle architecture. It will be shown how the chosen modeling paradigm can affect the goodness and the amount of computational effort of the solution, using an optimization technique based on Dynamic Programming. The second goal concerns the control of pollutant emissions in a parallel Diesel-HEV. The emissions level obtained under real world driving conditions is substantially higher than the usual result obtained in a homologation cycle. For this reason, an on-line control strategy capable of guaranteeing the respect of the desired emissions level, while minimizing fuel consumption and avoiding excessive battery depletion is the target of the corresponding section of the Thesis.

Graph algorithms for bioinformatics

Biological data are inherently interconnected: protein sequences are connected to their annotations, the annotations are structured into ontologies, and so on. While protein-protein interactions are already represented by graphs, in this work I am presenting how a graph structure can be used to enrich the annotation of protein sequences thanks to algorithms that analyze the graph topology. We also describe a novel solution to restrict the data generation needed for building such a graph, thanks to constraints on the data and dynamic programming. The proposed algorithm ideally improves the generation time by a factor of 5. The graph representation is then exploited to build a comprehensive database, thanks to the rising technology of graph databases. While graph databases are widely used for other kind of data, from Twitter tweets to recommendation systems, their application to bioinformatics is new. A graph database is proposed, with a structure that can be easily expanded and queried.

Many-core Algorithms for Combinatorial Optimization

Combinatorial Optimization is becoming ever more crucial, in these days. From natural sciences to economics, passing through urban centers administration and personnel management, methodologies and algorithms with a strong theoretical background and a consolidated real-word effectiveness is more and more requested, in order to find, quickly, good solutions to complex strategical problems. Resource optimization is, nowadays, a fundamental ground for building the basements of successful projects. From the theoretical point of view, Combinatorial Optimization rests on stable and strong foundations, that allow researchers to face ever more challenging problems. However, from the application point of view, it seems that the rate of theoretical developments cannot cope with that enjoyed by modern hardware technologies, especially with reference to the one of processors industry. In this work we propose new parallel algorithms, designed for exploiting the new parallel architectures available on the market. We found that, exposing the inherent parallelism of some resolution techniques (like Dynamic Programming), the computational benefits are remarkable, lowering the execution times by more than an order of magnitude, and allowing to address instances with dimensions not possible before. We approached four Combinatorial Optimization’s notable problems: Packing Problem, Vehicle Routing Problem, Single Source Shortest Path Problem and a Network Design problem. For each of these problems we propose a collection of effective parallel solution algorithms, either for solving the full problem (Guillotine Cuts and SSSPP) or for enhancing a fundamental part of the solution method (VRP and ND). We endorse our claim by presenting computational results for all problems, either on standard benchmarks from the literature or, when possible, on data from real-world applications, where speed-ups of one order of magnitude are usually attained, not uncommonly scaling up to 40 X factors.

A Calculus of Evolving Objects

The demands of developing modern, highly dynamic applications have led to an increasing interest in dynamic programming languages and mechanisms. Not only applications must evolve over time, but the object models themselves may need to be adapted to the requirements of different run-time contexts. Class-based models and prototype-based models, for example, may need to co-exist to meet the demands of dynamically evolving applications. Multi-dimensional dispatch, fine-grained and dynamic software composition, and run-time evolution of behaviour are further examples of diverse mechanisms which may need to co-exist in a dynamically evolving run-time environment How can we model the semantics of these highly dynamic features, yet still offer some reasonable safety guarantees? To this end we present an original calculus in which objects can adapt their behaviour at run-time to changing contexts. Both objects and environments are represented by first-class mappings between variables and values. Message sends are dynamically resolved to method calls. Variables may be dynamically bound, making it possible to model a variety of dynamic mechanisms within the same calculus. Despite the highly dynamic nature of the calculus, safety properties are assured by a type assignment system.

A Calculus of Evolving Objects

The demands of developing modern, highly dynamic applications have led to an increasing interest in dynamic programming languages and mechanisms. Not only must applications evolve over time, but the object models themselves may need to be adapted to the requirements of different run-time contexts. Class-based models and prototype-based models, for example, may need to co-exist to meet the demands of dynamically evolving applications. Multi-dimensional dispatch, fine-grained and dynamic software composition, and run-time evolution of behaviour are further examples of diverse mechanisms which may need to co-exist in a dynamically evolving run-time environment. How can we model the semantics of these highly dynamic features, yet still offer some reasonable safety guarantees? To this end we present an original calculus in which objects can adapt their behaviour at run-time. Both objects and environments are represented by first-class mappings between variables and values. Message sends are dynamically resolved to method calls. Variables may be dynamically bound, making it possible to model a variety of dynamic mechanisms within the same calculus. Despite the highly dynamic nature of the calculus, safety properties are assured by a type assignment system.

Statistical model-based segmentation of the proximal femur in digital antero-posterior (AP) pelvic radiographs.

PURPOSE    Segmentation of the proximal femur in digital antero-posterior (AP) pelvic radiographs is required to create a three-dimensional model of the hip joint for use in planning and treatment. However, manually extracting the femoral contour is tedious and prone to subjective bias, while automatic segmentation must accommodate poor image quality, anatomical structure overlap, and femur deformity. A new method was developed for femur segmentation in AP pelvic radiographs. METHODS    Using manual annotations on 100 AP pelvic radiographs, a statistical shape model (SSM) and a statistical appearance model (SAM) of the femur contour were constructed. The SSM and SAM were used to segment new AP pelvic radiographs with a three-stage approach. At initialization, the mean SSM model is coarsely registered to the femur in the AP radiograph through a scaled rigid registration. Mahalanobis distance defined on the SAM is employed as the search criteria for each annotated suggested landmark location. Dynamic programming was used to eliminate ambiguities. After all landmarks are assigned, a regularized non-rigid registration method deforms the current mean shape of SSM to produce a new segmentation of proximal femur. The second and third stages are iteratively executed to convergence. RESULTS    A set of 100 clinical AP pelvic radiographs (not used for training) were evaluated. The mean segmentation error was [Formula: see text], requiring [Formula: see text] s per case when implemented with Matlab. The influence of the initialization on segmentation results was tested by six clinicians, demonstrating no significance difference. CONCLUSIONS    A fast, robust and accurate method for femur segmentation in digital AP pelvic radiographs was developed by combining SSM and SAM with dynamic programming. This method can be extended to segmentation of other bony structures such as the pelvis.

Proceedings of the Twentieth Annual Biochemical Engineering Symposium

The 20th Annual Biochemical Engineering Symposium was held at Kansas State University on April 21,1990. The objectives of the symposium were to provide: (i) a forum for informal discussion of biochemical engineering research being conducted at the participating institutions and (ii) an opportunity for students to present and publish their work. Twenty-eight papers presented at the symposium are included in this proceedings. Some of the papers describe the progress of ongoing projects, and others contain the results of completed projects. Only brief summaries are given of the papers that will be published in full elsewhere. The program of the symposium and a list of the participants are included in the proceedings. ContentsCell Separations and Recycle Using an Inclined Settler, Ching-Yuan Lee, Robert H. Davis and Robert A. Sclafani Micromixing and Metabolism in Bioreactors: Characterization of a 14 L Fermenter, K.S. Wenger and E.H. Dunlop Production, Purification, and Hydrolysis Kinetics of Wild-Type and Mutant Glucoamylases from Aspergillus Awamori, Ufuk Bakir, Paul D. Oates, Hsiu-Mei Chen and Peter J. Reilly Dynamic Modeling of the Immune System, Barry Vant-Hull and Dhinakar S. Kompala Dynamic Modeling of Active Transport Across a Biological Cell: A Stochastic Approach, B.C. Shen, S.T. Chou, Y.Y. Chiu and L.T. Fan Electrokinetic Isolation of Bacterial Vesicles and Ribosomes, Debra T.L. Hawker, Robert H. Davis, Paul W. Todd, and Robert Lawson Application of Dynamic Programming for Fermentative Ethanol Production by Zymomonas mobilis, Sheyla L. Rivera and M. Nazmul Karim Biodegradation of PCP by Pseudomonas cepacia, R. Rayavarapu, S.K. Banerji, and R.K. Bajpai Modeling the Bioremediation of Contaminated Soil Aggregates: a Phenomenological Approach, S. Dhawan, L.E. Erickson and L.T. Fan Biospecific Adsorption of Glucoamylase-I from Aspergillus niger on Raw Starch, Bipin K. Dalmia and Zivko L. Nikolov Overexpression in Recombinant Mammalian Cells: Effect on Growth Rate and Genetic Instability, Jeffrey A. Kern and Dhinakar S. Kompala Structured Mathematical Modeling of Xylose Fermentation, A.K. Hilaly, M.N. Karim, I. C. Linden and S. Lastick A New Culture Medium for Carbon-limited Growth of Bacillus thuringiensis, W. -M. Liu and R.K. Bajpai Determination of Sugars and Sugar Alcohols by High Performance Ion Chromatography, T. J. Paskach, H.-P. Lieker, P.J. Reilly, and K. Thielecke Characterization of Poly-Asp Tailed B-Galactosidase, M.Q. Niederauer, C.E. Glatz, l.A. Suominen, C.F. Ford, and M.A. Rougvie Computation of Conformations and Energies of cr-Glucosyl Disaccharides, Jing Zepg, Michael K. Dowd, and Peter J. Reilly Pentachlorophenol Interactions with Soil, Shein-Ming Wei, Shankha K. Banerji, and Rakesh K. Bajpai Oxygen Transfer to Viscous Liquid Media in Three-Phase Fluidized Beds of Floating Bubble Freakers, Y. Kang, L.T. Fan, B.T. Min and S.D. Kim Studies on the Invitro Development of Chick Embryo, A. Venkatraman and T. Panda The Evolution of a Silicone Based Phase-Separated Gravity-Independent Bioreactor, Peter E. Villeneuve and Eric H. Dunlop Biodegradation of Diethyl Phthalate, Guorong Zhang, Kenneth F. Reardon and Vincent G. Murphy Microcosm Treatability of Soil Contaminated with Petroleum Hydrocarbons, P. Tuitemwong, S. Dhawan, B.M. Sly, L.E. Erickson and J.R. Schlup

Proceedings of the Twenty-Sixth Annual Biochemical Engineering Symposium

This volume contains the Proceedings of the Twenty-Sixth Annual Biochemical Engineering Symposium held at Kansas State University on September 21, 1996. The program included 10 oral presentations and 14 posters. Some of the papers describe the progress of ongoing projects, and others contain the results of completed projects. Only brief summaries are given of some of the papers; many of the papers will be published in full elsewhere. A listing of those who attended is given below. ContentsForeign Protein Production from SV40 Early Promoter in Continuous Cultures of Recombinant CHO Cells - Gautam Banik, Paul Todd, and Dhinakar Kampala Enhanced Cell Recruitment Due to Cell-Cell Interactions - Brad Farlow and Matthias Nollert The Recirculation of Hybridoma Suspension Cultures: Effects on Cell Death, Metabolism and Mab Productivity - Peng Jin and Carole A. Heath The Importance of Enzyme Inactivation and Self-Recovery in Cometabolic Biodegradation of Chlorinated Solvents - Xi-Hui Zhang, Shanka Banerji, and Rakesh Bajpai Phytoremediation of VOC contaminated Groundwater using Poplar Trees - Melissa Miller, Jason Dana, L.C. Davis, Murlidharan Narayanan, and L.E. Erickson Biological Treatment of Off-Gases from Aluminum Can Production: Experimental Results and Mathematical Modeling - Adeyma Y. Arroyo, Julio Zimbron, and Kenneth F. Reardon Inertial Migration Based Separation of Chlorella Microalgae in Branched Tubes - N.M. Poflee, A.L. Rakow, D.S. Dandy, M.L. Chappell, and M.N. Pons Contribution of Electrochemical Charge to Protein Partitioning in Aqueous Two-Phase Systems - Weiyu Fan and Charles C. Glatz Biodegradation of Some Commercial Surfactants Used in Bioremediation - Jun Gu, G.W. Preckshot, S.K. Banerji, and Rakesh Bajpai Modeling the Role of Biomass in Heavy Metal Transport Ln Vadose Zone - K.V. Nedunuri, L.E. Erickson, and R.S. Govindaraju Multivariable Statistical Methods for Monitoring Process Quality: Application to Bioinsecticide Production by 73 89 Bacillus Thuringiensis - c. Puente and M.N. Karim The Use of Polymeric Flocculants in Bacterial Lysate Streams - H. Graham, A.S. Cibulskas and E.H. Dunlop Effect of Water Content on transport of Trichloroethylene in a Chamber with Alfalfa Plants - Muralidharan Narayanan, Jiang Hu, Lawrence C. Davis, and Larry E. Erickson Detection of Specific Microorganisms using the Arbitrary Primed PCR in the Bacterial Community of Vegetated Soil - X. Wu and L.C. Davis Flux Enhancement Using Backpulsing - V.T. Kuberkar and R.H. Davis Chromatographic Purification of Oligonucleotides: Comparison with Electrophoresis - Stephen P. Cape, Ching-Yuan Lee, Kevin Petrini, Sean Foree, Micheal G. Sportiello and Paul Todd Determining Singular Arc Control Policies for Bioreactor Systems Using a Modified Iterative Dynamic Programming Algorithm - Arun Tholudur and W. Fred Ramirez Pressure Effect on Subtilisins Measured via FTIR, EPR and Activity Assays, and Its Impact on Crystallizations - J.N. Webb, R.Y. Waghmare, M.G. Bindewald, T.W. Randolph, J.F. Carpenter, C.E. Glatz Intercellular Calcium Changes in Endothelial Cells Exposed to Flow - Laura Worthen and Matthias Nollert Application of Liquid-Liquid Extraction in Propionic Acid Fermentation - Zhong Gu, Bonita A. Glatz, and Charles E. Glatz Purification of Recombinant T4 Lysozyme from E. Coli: Ion-Exchange Chromatography - Weiyu Fan, Matt L. Thatcher, and Charles E. Glatz Recovery and Purification of Recombinant Beta-Glucuronidase from Transgenic Corn - Ann R. Kusnadi, Roque Evangelista, Zivko L. Nikolov, and John Howard Effects of Auxins and cytokinins on Formation of Catharanthus Roseus G. Don Multiple Shoots - Ying-Jin Yuan, Yu-Min Yang, Tsung-Ting Hu, and Jiang Hu Fate and Effect of Trichloroethylene as Nonaqueous Phase Liquid in Chambers with Alfalfa - Qizhi Zhang, Brent Goplen, Sara Vanderhoof, Lawrence c. Davis, and Larry E. Erickson Oxygen Transport and Mixing Considerations for Microcarrier Culture of Mammalian Cells in an Airlift Reactor - Sridhar Sunderam, Frederick R. Souder, and Marylee Southard Effects of Cyclic Shear Stress on Mammalian Cells under Laminar Flow Conditions: Apparatus and Methods - M.L. Rigney, M.H. Liew, and M.Z. Southard

Compatibilidad del principio de óptimo de Bellman con los métodos secuenciales de optimización de redes de tuberías

En el proceso de cálculo de redes de tuberías se maneja un conjunto de variables con unas características muy peculiares, ya que son discretas y estandarizadas. Por lo tanto su evolución se produce por escalones (la presión nominal, el diámetro y el costo de los tubos). Por otro lado la presión de diseño de la red es una función directa de la presión de cabecera. En el proceso de optimización mediante programación dinámica la presión de cabecera se va reduciendo gradualmente en cada secuencia del proceso, haciendo que evolucione a la par la presión de diseño, lo que genera a su vez saltos discriminados en la presión nominal de los tramos, y con ello en su costo y en su gradiente de cambio. En esta tesis doctoral se analiza si estos cambios discriminados que se producen en el gradiente de cambio de algunos tramos en el curso de una secuencia, ocasionados por la evolución de la presión de cabecera de la red, generan interferencias que alteran el proceso secuencial de la programación dinámica. La modificación del gradiente de cambio durante el transcurso de una secuencia se conoce con el nombre de mutación, la cual puede ser activa cuando involucra a un tramo optimo modificando las condiciones de la transacción o pasiva si no crea afección alguna. En el análisis realizado se distingue entre la mutación del gradiente de cambio de los tramos óptimos (que puede generarse exclusivamente en el conjunto de los trayectos que los albergan), y entre los efectos que el cambio de timbraje produce en el resto de los tramos de la red (incluso los situados aguas abajo de los nudos con holgura de presión nula) sobre el mecanismo iterativo, estudiando la compatibilidad de este fenómeno con el principio de óptimo de Bellman. En el proceso de investigación llevado a cabo se destaca la fortaleza que da al proceso secuencial del método Granados el hecho de que el gradiente de cambio siempre sea creciente en el avance hacia el óptimo, es decir que el costo marginal de la reducción de las pérdidas de carga de la red que se consigue en una iteración siempre sea más caro que el de la iteración precedente. Asimismo, en el estudio realizado se revisan los condicionantes impuestos al proceso de optimización, incluyendo algunos que hasta ahora no se han tenido en cuenta en los estudios de investigación, pero que están totalmente integrados en la ingeniería práctica, como es la disposición telescópica de las redes (reordenación de los diámetros de mayor a menor de cabeza a cola de la red), y la disposición de un único diámetro por tramo, en lugar de que estén compartidos por dos diámetros contiguos (con sus salvedades en caso de tramos de gran longitud, o en otras situaciones muy específicas). Finalmente se incluye un capítulo con las conclusiones, aportaciones y recomendaciones, las cuales se consideran de gran utilidad para la ingeniería práctica, entre las que se destaca la perfección del método secuencial, la escasa transcendencia de las mutaciones del gradiente de cambio y la forma en que pueden obviarse, la inocuidad de las mutaciones pasivas y el cumplimiento del principio de Bellman en todo el proceso de optimización. The sizing process of a water distribution network is based on several variables, being some of them special, as they are discrete and their values are standardized: pipe pressure rating, pipe diameter and pipe cost. On another note, the sizing process is directly related with the pressure at the network head. Given that during the optimization by means of the Granados’ Method (based on dynamic programming) the pressure at the network head is being gradually reduced, a jump from one pipe pressure rating to another may arise during the sequential process, leading to changes on the pipe cost and on the gradient change (unitary cost for reducing the head losses). This chain of changes may, in turn, affect the sequential process diverting it from an optimal policies path. This thesis analyses how the abovementioned alterations could influence the results of the dynamic programming algorithm, that is to say the compatibility with the Bellman’s Principle of Optimality, which states that the sequence has to follow a route of optimal policies, and that past decisions should not influence the remaining ones. The modification of the gradient change is known as mutation. Mutations are active when they affect the optimal link (the one which was selected to be changed during iteration) or passive when they do not alter the selection of the optimal link. The thesis analysed the potential mutations processes along the network, both on the optimal paths and also on the rest of the network, and its influence on the final results. Moreover, the investigation analysed the practical restrictions of the sizing process that are fully integrated in the applied engineering, but not always taken into account by the optimization tools. As the telescopic distribution of the diameters (i.e. larger diameters are placed at the network head) and the use of a unique diameter per link (with the exception of very large links, where two consecutive diameters may be placed). Conclusions regarding robustness of the dynamic programming algorithm are given. The sequence of the Granados Method is quite robust and it has been shown capable to auto-correct the mutations that could arise during the optimization process, and to achieve an optimal distribution even when the Bellman’s Principle of Optimality is not fully accomplished. The fact that the gradient change is always increasing during the optimization (that is to say, the marginal cost of reducing head losses is always increasing), provides robustness to the algorithm, as looping are avoided in the optimization sequence. Additionally, insight into the causes of the mutation process is provided and practical rules to avoid it are given, improving the current definition and utilization of the Granados’ Method.

Optimización del consumo de combustible de un vehículo dependiendo de las condiciones de la carretera

El consumo de combustible en un automóvil es una característica que se intenta mejorar continuamente debido a los precios del carburante y a la creciente conciencia medioambiental. Esta tesis doctoral plantea un algoritmo de optimización del consumo que tiene en cuenta las especificaciones técnicas del vehículo, el perfil de orografía de la carretera y el tráfico presente en ella. El algoritmo de optimización calcula el perfil de velocidad óptima que debe seguir el vehículo para completar un recorrido empleando un tiempo de viaje especificado. El cálculo del perfil de velocidad óptima considera los valores de pendiente de la carretera así como también las condiciones de tráfico vehicular de la franja horaria en que se realiza el recorrido. El algoritmo de optimización reacciona ante condiciones de tráfico cambiantes y adapta continuamente el perfil óptimo de velocidad para que el vehículo llegue al destino cumpliendo el horario de llegada establecido. La optimización de consumo es aplicada en vehículos convencionales de motor de combustión interna y en vehículos híbridos tipo serie. Los datos de consumo utilizados por el algoritmo de optimización se obtienen mediante la simulación de modelos cuasi-estáticos de los vehículos. La técnica de minimización empleada por el algoritmo es la Programación Dinámica. El algoritmo divide la optimización del consumo en dos partes claramente diferenciadas y aplica la Programación Dinámica sobre cada una de ellas. La primera parte corresponde a la optimización del consumo del vehículo en función de las condiciones de tráfico. Esta optimización calcula un perfil de velocidad promedio que evita, cuando es posible, las retenciones de tráfico. El tiempo de viaje perdido durante una retención de tráfico debe recuperarse a través de un aumento posterior de la velocidad promedio que incrementaría el consumo del vehículo. La segunda parte de la optimización es la encargada del cálculo de la velocidad óptima en función de la orografía y del tiempo de viaje disponible. Dado que el consumo de combustible del vehículo se incrementa cuando disminuye el tiempo disponible para finalizar un recorrido, esta optimización utiliza factores de ponderación para modular la influencia que tiene cada una de estas dos variables en el proceso de minimización. Aunque los factores de ponderación y la orografía de la carretera condicionan el nivel de ahorro de la optimización, los perfiles de velocidad óptima calculados logran ahorros de consumo respecto de un perfil de velocidad constante que obtiene el mismo tiempo de recorrido. Las simulaciones indican que el ahorro de combustible del vehículo convencional puede lograr hasta un 8.9% mientras que el ahorro de energía eléctrica del vehículo híbrido serie un 2.8%. El algoritmo fusiona la optimización en función de las condiciones del tráfico y la optimización en función de la orografía durante el cálculo en tiempo real del perfil óptimo de velocidad. La optimización conjunta se logra cuando el perfil de velocidad promedio resultante de la optimización en función de las condiciones de tráfico define los valores de los factores de ponderación de la optimización en función de la orografía. Aunque el nivel de ahorro de la optimización conjunta depende de las condiciones de tráfico, de la orografía, del tiempo de recorrido y de las características propias del vehículo, las simulaciones indican ahorros de consumo superiores al 6% en ambas clases de vehículo respecto a optimizaciones que no logran evitar retenciones de tráfico en la carretera. ABSTRACT Fuel consumption of cars is a feature that is continuously being improved due to the fuel price and an increasing environmental awareness. This doctoral dissertation describes an optimization algorithm to decrease the fuel consumption taking into account the technical specifications of the vehicle, the terrain profile of the road and the traffic conditions of the trip. The algorithm calculates the optimal speed profile that completes a trip having a specified travel time. This calculation considers the road slope and the expected traffic conditions during the trip. The optimization algorithm is also able to react to changing traffic conditions and tunes the optimal speed profile to reach the destination within the specified arrival time. The optimization is applied on a conventional vehicle and also on a Series Hybrid Electric vehicle (SHEV). The fuel consumption optimization algorithm uses data obtained from quasi-static simulations. The algorithm is based on Dynamic Programming and divides the fuel consumption optimization problem into two parts. The first part of the optimization process reduces the fuel consumption according to foreseeable traffic conditions. It calculates an average speed profile that tries to avoid, if possible, the traffic jams on the road. Traffic jams that delay drivers result in higher vehicle speed to make up for lost time. A higher speed of the vehicle within an already defined time scheme increases fuel consumption. The second part of the optimization process is in charge of calculating the optimal speed profile according to the road slope and the remaining travel time. The optimization tunes the fuel consumption and travel time relevancies by using two penalty factors. Although the optimization results depend on the road slope and the travel time, the optimal speed profile produces improvements of 8.9% on the fuel consumption of the conventional car and of 2.8% on the spent energy of the hybrid vehicle when compared with a constant speed profile. The two parts of the optimization process are combined during the Real-Time execution of the algorithm. The average speed profile calculated by the optimization according to the traffic conditions provides values for the two penalty factors utilized by the second part of the optimization process. Although the savings depend on the road slope, traffic conditions, vehicle features, and the remaining travel time, simulations show that this joint optimization process can improve the energy consumption of the two vehicles types by more than 6%.