Algorithms for network design and routing problems

In this thesis we study three combinatorial optimization problems belonging to the classes of Network Design and Vehicle Routing problems that are strongly linked in the context of the design and management of transportation networks: the Non-Bifurcated Capacitated Network Design Problem (NBP), the Period Vehicle Routing Problem (PVRP) and the Pickup and Delivery Problem with Time Windows (PDPTW). These problems are NP-hard and contain as special cases some well known difficult problems such as the Traveling Salesman Problem and the Steiner Tree Problem. Moreover, they model the core structure of many practical problems arising in logistics and telecommunications. The NBP is the problem of designing the optimum network to satisfy a given set of traffic demands. Given a set of nodes, a set of potential links and a set of point-to-point demands called commodities, the objective is to select the links to install and dimension their capacities so that all the demands can be routed between their respective endpoints, and the sum of link fixed costs and commodity routing costs is minimized. The problem is called non- bifurcated because the solution network must allow each demand to follow a single path, i.e., the flow of each demand cannot be splitted. Although this is the case in many real applications, the NBP has received significantly less attention in the literature than other capacitated network design problems that allow bifurcation. We describe an exact algorithm for the NBP that is based on solving by an integer programming solver a formulation of the problem strengthened by simple valid inequalities and four new heuristic algorithms. One of these heuristics is an adaptive memory metaheuristic, based on partial enumeration, that could be applied to a wider class of structured combinatorial optimization problems. In the PVRP a fleet of vehicles of identical capacity must be used to service a set of customers over a planning period of several days. Each customer specifies a service frequency, a set of allowable day-combinations and a quantity of product that the customer must receive every time he is visited. For example, a customer may require to be visited twice during a 5-day period imposing that these visits take place on Monday-Thursday or Monday-Friday or Tuesday-Friday. The problem consists in simultaneously assigning a day- combination to each customer and in designing the vehicle routes for each day so that each customer is visited the required number of times, the number of routes on each day does not exceed the number of vehicles available, and the total cost of the routes over the period is minimized. We also consider a tactical variant of this problem, called Tactical Planning Vehicle Routing Problem, where customers require to be visited on a specific day of the period but a penalty cost, called service cost, can be paid to postpone the visit to a later day than that required. At our knowledge all the algorithms proposed in the literature for the PVRP are heuristics. In this thesis we present for the first time an exact algorithm for the PVRP that is based on different relaxations of a set partitioning-like formulation. The effectiveness of the proposed algorithm is tested on a set of instances from the literature and on a new set of instances. Finally, the PDPTW is to service a set of transportation requests using a fleet of identical vehicles of limited capacity located at a central depot. Each request specifies a pickup location and a delivery location and requires that a given quantity of load is transported from the pickup location to the delivery location. Moreover, each location can be visited only within an associated time window. Each vehicle can perform at most one route and the problem is to satisfy all the requests using the available vehicles so that each request is serviced by a single vehicle, the load on each vehicle does not exceed the capacity, and all locations are visited according to their time window. We formulate the PDPTW as a set partitioning-like problem with additional cuts and we propose an exact algorithm based on different relaxations of the mathematical formulation and a branch-and-cut-and-price algorithm. The new algorithm is tested on two classes of problems from the literature and compared with a recent branch-and-cut-and-price algorithm from the literature.

The Determinants of Individual Performance: Empirical Essays on the Importance of Soft Skills and Monetary Incentives

This dissertation consists of three papers. The first paper "Managing the Workload: an Experiment on Individual Decision Making and Performance" experimentally investigates how decision-making in workload management affects individual performance. I designed a laboratory experiment in order to exogenously manipulate the schedule of work faced by each subject and to identify its impact on final performance. Through the mouse click-tracking technique, I also collected interesting behavioral measures on organizational skills. I found that a non-negligible share of individuals performs better under externally imposed schedules than in the unconstrained case. However, such constraints are detrimental for those good in self-organizing. The second chapter, "On the allocation of effort with multiple tasks and piecewise monotonic hazard function", tests the optimality of a scheduling model, proposed in a different literature, for the decisional problem faced in the experiment. Under specific assumptions, I find that such model identifies what would be the optimal scheduling of the tasks in the Admission Test. The third paper "The Effects of Scholarships and Tuition Fees Discounts on Students' Performances: Which Monetary Incentives work Better?" explores how different levels of monetary incentives affect the achievement of students in tertiary education. I used a Regression Discontinuity Design to exploit the assignment of different monetary incentives, to study the effects of such liquidity provision on performance outcomes, ceteris paribus. The results show that a monetary increase in the scholarships generates no effect on performance since the achievements of the recipients are all centered near the requirements for non-returning the benefit. Secondly, students, who are actually paying some share of the total cost of college attendance, surprisingly, perform better than those whose cost is completely subsidized. A lower benefit, relatively to a higher aid, it motivates students to finish early and not to suffer the extra cost of a delayed graduation.

Planning and flexible operation of storage systems in power grids: from transmission to distribution networks

The first part of the thesis has been devoted to the transmission planning with high penetration of renewable energy sources. Both stationary and transportable battery energy storage (BES, BEST) systems have been considered in the planning model, so to obtain the optimal set of BES, BEST and transmission lines that minimizes the total cost in a power network. First, a coordinated expansion planning model with fixed transportation cost for BEST devices has been presented; then, the model has been extended to a planning formulation with a distance-dependent transportation cost for the BEST units, and its tractability has been proved through a case study based on a 190-bus test system. The second part of this thesis is then devoted to the analysis of planning and management of renewable energy communities (RECs). Initially, the planning of photovoltaic and BES systems in a REC with an incentive-based remuneration scheme according to the Italian regulatory framework has been analysed, and two planning models, according to a single-stage, or a multi-stage approach, have been proposed in order to provide the optimal set of BES and PV systems allowing to achieve the minimum energy procurement cost in a given REC. Further, the second part of this thesis is devoted to the study of the day-ahead scheduling of resources in renewable energy communities, by considering two types of REC. The first one, which we will refer to as “cooperative community”, allows direct energy transactions between members of the REC; the second type of REC considered, which we shall refer to as “incentive-based”, does not allow direct transactions between members but includes economic revenues for the community shared energy, according to the Italian regulation framework. Moreover, dispatchable renewable energy generation has been considered by including producers equipped with biogas power plants in the community.

Valutazione dell'efficacia e della sicurezza dell'Infliximab e della Ciclosporina Orale Microemulsione (Neoral) nei pazienti con colite ulcerosa severa refrattari agli steroidi per via endovenosa. Risultati preliminari di uno studio randomizzato controllato

Background. Intravenous steroids represent the mainstay of therapy for severe attacks of Ulcerative Colitis (UC). In steroid refractory patients, both iv cyclosporine (CsA) and infliximab (IFX) are valid rescue therapies. Several studies have shown that oral microemulsion CsA (Neoral) is equivalent to iv CsA in term of safety and efficacy in UC patients. Aim. To investigate the efficacy and safety of oral microemulsion CsA vs IFX in patients with severe attack of UC, refractory to iv steroids. Material and methods. From May 2006, all consecutive pts admitted for severe UC were considered eligible. Pts were treated with iv steroid, according to the Oxford regime. After 1 week of intensive treatment, pts non responder to the therapy and not candidate to the surgery, were asked to participate to the trial. They were randomised to receive IFX 5 mg/kg or oral CsA 5 mg/kg. Results. A total of 30 patients were randomised, 17 in the IFX group and 13 in the CsA group. One month after study inclusion, 9 patients of the IFX group (53%) and 7 pts of the CsA group (54%) were in clinical remission (p=0.96), with a Powell-Tuck index ≤ 3. At the end of the follow-up, 7 pts in the IFX group (41%) vs 4 in the CsA group (31%) (p=0.35) underwent colectomy. The total cost of the IFX therapy with IFX was 8.052,84 € versus 1.106,82 €, for each patient. Conclusions. Oral microemulsion CsA and IFX seem to be equivalent in term of efficacy and safety in severe UC patients refractory to iv steroids. In patients treated with IFX the cost of therapy were significantly higher.

Development of a Computer-Based methodology for tolerance selection and optimization applied to the automotive sector

The design optimization of industrial products has always been an essential activity to improve product quality while reducing time-to-market and production costs. Although cost management is very complex and comprises all phases of the product life cycle, the control of geometrical and dimensional variations, known as Dimensional Management (DM), allows compliance with product and process requirements. Hence, the tolerance-cost optimization becomes the main practice to provide an effective application of Design for Tolerancing (DfT) and Design to Cost (DtC) approaches by enabling a connection between product tolerances and associated manufacturing costs. However, despite the growing interest in this topic, a profitable application in the industry of these techniques is hampered by their complexity: the definition of a systematic framework is the key element to improving design optimization, enhancing the concurrent use of Computer-Aided tools and Model-Based Definition (MBD) practices. The present doctorate research aims to define and develop an integrated methodology for product/process design optimization, to better exploit the new capabilities of advanced simulations and tools. By implementing predictive models and multi-disciplinary optimization, a Computer-Aided Integrated framework for tolerance-cost optimization has been proposed to allow the integration of DfT and DtC approaches and their direct application for the design of automotive components. Several case studies have been considered, with the final application of the integrated framework on a high-performance V12 engine assembly, to achieve both functional targets and cost reduction. From a scientific point of view, the proposed methodology provides an improvement for the tolerance-cost optimization of industrial components. The integration of theoretical approaches and Computer-Aided tools allows to analyse the influence of tolerances on both product performance and manufacturing costs. The case studies proved the suitability of the methodology for its application in the industrial field, providing the identification of further areas for improvement and refinement.