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.

Role of αvβ3 – Integrin and TLR2 in the innate response to Herpes Simplex Virus infection and Delivery of retargeted oncolytic Herpes Simplex via carrier cells

In the first part of my thesis I studied the mechanism of initiation of the innate response to HSV-1. Innate immune response is the first line of defense set up by the cell to counteract pathogens infection and it is elicited by the activation of a number of membrane or intracellular receptors and sensors, collectively indicated as PRRs, Patter Recognition Receptors. We reported that the HSV pathogen-associated molecular patterns (PAMP) that activate Toll-like receptor 2 (TLR2) and lead to the initiation of innate response are the virion glycoproteins gH/gL and gB, which constitute the conserved fusion core apparatus across the Herpesvirus. Specifically gH/gL is sufficient to initiate a signaling cascade which leads to NF-κB activation. Then, by gain and loss-of-function approaches, we found that αvβ3-integrin is a sensor of and plays a crucial role in the innate defense against HSV-1. We showed that αvβ3-integrin signals through a pathway that concurs with TLR2, affects activation/induction of interferons type 1, NF-κB, and a polarized set of cytokines and receptors. Thus, we demonstrated that gH/gL is sufficient to induce IFN1 and NF-κB via this pathway. From these data, we proposed that αvβ3-integrin is considered a class of non-TLR pattern recognition receptors. In the second part of my thesis I studied the capacity of human mesenchymal stromal cells isolated by fetal membranes (FM-hMSCs) to be used as carrier cells for the delivery of retargeted R-LM249 virus. The use of systemically administrated carrier cells to deliver oncolytic viruses to tumoral targets is a promising strategy in oncolytic virotherapy. We observed that FM-hMSCs can be infected by R-LM249 and we optimized the infection condition; then we demonstrate that stromal cells sustain the replication of retargeted R-LM249 and spread it to target tumoral cells. From these preliminary data FM-hMSCs resulted suitable to be used as carrier cells

Spectroscopic studies on Cyclodextrin and Metal Organic Framework based potential nanovectors for delivery of Anticancer and Antiviral drugs

The aim of this work is to contribute to the development of new multifunctional nanocarriers for improved encapsulation and delivery of anticancer and antiviral drugs. The work focused on water soluble and biocompatible oligosaccharides, the cyclodextrins (CyDs), and a new family of nanostructured, biodegradable carrier materials made of porous metal-organic frameworks (nanoMOFs). The drugs of choice were the anticancer doxorubicin (DOX), azidothymidine (AZT) and its phosphate derivatives and artemisinin (ART). DOX possesses a pharmacological drawback due to its self-aggregation tendency in water. The non covalent binding of DOX to a series of CyD derivatives, such as g-CyD, an epichlorohydrin crosslinked b-CyD polymer (pb-CyD) and a citric acid crosslinked g-CyD polymer (pg-CyD) was studied by UV visible absorption, circular dichroism and fluorescence. Multivariate global analysis of multiwavelength data from spectroscopic titrations allowed identification and characterization of the stable complexes. pg-CyD proved to be the best carrier showing both high association constants and ability to monomerize DOX. AZT is an important antiretroviral drug. The active form is AZT-triphosphate (AZT-TP), formed in metabolic paths of low efficiency. Direct administration of AZT-TP is limited by its poor stability in biological media. So the development of suitable carriers is highly important. In this context we studied the binding of some phosphorilated derivatives to nanoMOFs by spectroscopic methods. The results obtained with iron(III)-trimesate nanoMOFs allowed to prove that the binding of these drugs mainly occurs by strong iono-covalent bonds to iron(III) centers. On the basis of these and other results obtained in partner laboratories, it was possible to propose this highly versatile and “green” carrier system for delivery of phosphorylated nucleoside analogues. The interaction of DOX with nanoMOFs was also studied. Finally the binding of the antimalarial drug, artemisinin (ART) with two cyclodextrin-based carriers,the pb-CyD and a light responsive bis(b-CyD) host, was also studied.

Foetal heart rate recording: analysis and comparison of different methodologies

Monitoring foetal health is a very important task in clinical practice to appropriately plan pregnancy management and delivery. In the third trimester of pregnancy, ultrasound cardiotocography is the most employed diagnostic technique: foetal heart rate and uterine contractions signals are simultaneously recorded and analysed in order to ascertain foetal health. Because ultrasound cardiotocography interpretation still lacks of complete reliability, new parameters and methods of interpretation, or alternative methodologies, are necessary to further support physicians’ decisions. To this aim, in this thesis, foetal phonocardiography and electrocardiography are considered as different techniques. Further, variability of foetal heart rate is thoroughly studied. Frequency components and their modifications can be analysed by applying a time-frequency approach, for a distinct understanding of the spectral components and their change over time related to foetal reactions to internal and external stimuli (such as uterine contractions). Such modifications of the power spectrum can be a sign of autonomic nervous system reactions and therefore represent additional, objective information about foetal reactivity and health. However, some limits of ultrasonic cardiotocography still remain, such as in long-term foetal surveillance, which is often recommendable mainly in risky pregnancies. In these cases, the fully non-invasive acoustic recording, foetal phonocardiography, through maternal abdomen, represents a valuable alternative to the ultrasonic cardiotocography. Unfortunately, the so recorded foetal heart sound signal is heavily loaded by noise, thus the determination of the foetal heart rate raises serious signal processing issues. A new algorithm for foetal heart rate estimation from foetal phonocardiographic recordings is presented in this thesis. Different filtering and enhancement techniques, to enhance the first foetal heart sounds, were applied, so that different signal processing techniques were implemented, evaluated and compared, by identifying the strategy characterized on average by the best results. In particular, phonocardiographic signals were recorded simultaneously to ultrasonic cardiotocographic signals in order to compare the two foetal heart rate series (the one estimated by the developed algorithm and the other provided by cardiotocographic device). The algorithm performances were tested on phonocardiographic signals recorded on pregnant women, showing reliable foetal heart rate signals, very close to the ultrasound cardiotocographic recordings, considered as reference. The algorithm was also tested by using a foetal phonocardiographic recording simulator developed and presented in this research thesis. The target was to provide a software for simulating recordings relative to different foetal conditions and recordings situations and to use it as a test tool for comparing and assessing different foetal heart rate extraction algorithms. Since there are few studies about foetal heart sounds time characteristics and frequency content and the available literature is poor and not rigorous in this area, a data collection pilot study was also conducted with the purpose of specifically characterising both foetal and maternal heart sounds. Finally, in this thesis, the use of foetal phonocardiographic and electrocardiographic methodology and their combination, are presented in order to detect foetal heart rate and other functioning anomalies. The developed methodologies, suitable for longer-term assessment, were able to detect heart beat events correctly, such as first and second heart sounds and QRS waves. The detection of such events provides reliable measures of foetal heart rate, potentially information about measurement of the systolic time intervals and foetus circulatory impedance.