Hybrid constraint programming and metaheuristic methods for large scale optimization problems

This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches. The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent. Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques. Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts. In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner. Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from local search and metaheuristic methods which are highly problem specific. In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching. We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.

Modeling of Electric Hybrid Vehicles based on Innovative Energy Storage Technologies for Super Sports Cars Applications

Today, the contribution of the transportation sector on greenhouse gases is evident. The fast consumption of fossil fuels and its impact on the environment has given a strong impetus to the development of vehicles with better fuel economy. Hybrid electric vehicles fit into this context with different targets, starting from the reduction of emissions and fuel consumption, but also for performance and comfort enhancement. Vehicles exist with various missions; super sport cars usually aim to reach peak performance and to guarantee a great driving experience to the driver, but great attention must also be paid to fuel consumption. According to the vehicle mission, hybrid vehicles can differ in the powertrain configuration and the choice of the energy storage system. Lamborghini has recently invested in the development of hybrid super sport cars, due to performance and comfort reasons, with the possibility to reduce fuel consumption. This research activity has been conducted as a joint collaboration between the University of Bologna and the sportscar manufacturer, to analyze the impact of innovative energy storage solutions on the hybrid vehicle performance. Capacitors have been studied and modeled to analyze the pros and cons of such solution with respect to batteries. To this aim, a full simulation environment has been developed and validated to provide a concept design tool capable of precise results and able to foresee the longitudinal performance on regulated emission cycles and real driving conditions, with a focus on fuel consumption. In addition, the target of the research activity is to deepen the study of hybrid electric super sports cars in the concept development phase, focusing on defining the control strategies and the energy storage system’s technology that best suits the needs of the vehicles. This dissertation covers the key steps that have been carried out in the research project.