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.

Jasmonates and abscisic acid influence fruit ripening and plant water use: practical, physiological and morphological aspects

The aim of the present thesis was to better understand the physiological role of the phytohormones jasmonates (JAs) and abscisic acid (ABA) during fruit ripening in prospect of a possible field application of JAs and ABA to improve fruit yield and quality. In particular, the effects of exogenous application of these substances at different fruit developmental stages and under different experimental conditions were evaluated. Some aspects of the water relations upon ABA treatment were also analysed. Three fruit species, peach (Prunus persica L. Batsch), golden (Actinidia chinensis) and green kiwifruit (Actinidia deliciosa), and several of their cvs, were used for the trials. Different experimental models were adopted: fruits in planta, detached fruit, detached branches with fruit, girdled branches and micropropagated plants. The work was structured into four sets of experiments as follows: (i) Pre-harvest methyl jasmonate (MJ) application was performed at S3/S4 transition under field conditions in Redhaven peach; ethylene production, ripening index, fruit quality and shelf-life were assessed showing that MJ-treated fruit were firmer and thus less ripe than controls as confirmed by the Index of Absorbance Difference (IAD), but exhibited a shorter shelf-life due to an increase in ethylene production. Moreover, the time course of the expression of ethylene-, auxin- and other ripening-related genes was determined. Ripening-related ACO1 and ACS1 transcript accumulation was inhibited though transiently by MJ, and gene expression of the ethylene receptor ETR2 and of the ethylene-related transcription factor ERF2 was also altered. The time course of the expression of several auxin-related genes was strongly affected by MJ suggesting an increase in auxin biosynthesis, altered auxin conjugation and release as well as perception and transport; the need for a correct ethylene/auxin balance during ripening was confirmed. (ii) Pre- and post-harvest ABA applications were carried out under field conditions in Flaminia and O’Henry peach and Stark Red Gold nectarine fruit; ethylene production, ripening index, fruit quality and shelf-life were assessed. Results show that pre-harvest ABA applications increase fruit size and skin color intensity. Also post-harvest ABA treatments alter ripening-related parameters; in particular, while ethylene production is impaired in ABA-treated fruit soluble solids concentration (SSC) is enhanced. Following field ABA applications stem water potential was modified since ABA-treated peach trees retain more water. (iii) Pre- and post-harvest ABA and PDJ treatments were carried out in both kiwifruit species under field conditions at different fruit developmental stages and in post-harvest. Ripening index, fruit quality, plant transpiration, photosynthesis and stomatal conductance were assessed. Pre-harvest treatments enhance SSC in the two cvs and flesh color development in golden kiwifruit. Post-harvest applications of either ABA or ABA plus PDJ lead to increased SSC. In addition, ABA reduces gas exchanges in A. deliciosa. (iv) Spray, drench and dipping ABA treatments were performed in micropropagated peach plants and in peach and nectarine detached branches; plant water use and transpiration, biomass production and fruit dehydration were determined. In both plants and branches ABA significantly reduces water use and fruit dehydration. No negative effects on biomass production were detected. The present information, mainly arising from plant growth regulator application in a field environment, where plants have to cope with multiple biotic and abiotic stresses, may implement the perspectives for the use of these substances in the control of fruit ripening.

Expression profiling in developing peach seed and mesocarp as affected by growth regulators

Jasmonates (JAs) and spermidine (Sd) influence fruit (and seed) development and ripening. In order to unravel their effects in peach fruit, at molecular level, field applications of methyl jasmonate (MJ) and propyl dihydrojasmonate (PDJ), and Sd were performed at an early developmental stage (late S1). At commercial harvest, JA-treated fruit were less ripe than controls. Realtime RT-PCR analyses confirmed a down-regulation of ethylene biosynthetic, perception and signaling genes, and flesh softening-related genes. The expression of cell wall-related genes, of a sugar-transporter and hormone-related transcript levels was also affected by JAs. Seeds from JA-treated fruit showed a shift in the expression of developmental marker genes suggesting that the developmental program was probably slowed down, in agreement with the contention that JAs divert resources from growth to defense. JAs also affected phenolic content and biosynthetic gene expression in the mesocarp. Levels of hydroxycinnamic acids, as well as those of flavan-3-ols, were enhanced, mainly by MJ, in S2. Transcript levels of phenylpropanoid pathway genes were up-regulated by MJ, in agreement with phenolic content. Sd-treated fruits at harvest showed reduced ethylene production and flesh softening. Sd induced a short-term and long-term response patterns in endogenous polyamines. At ripening the up-regulation of the ethylene biosynthetic genes was dramatically counteracted by Sd, leading to a down-regulation of softening-related genes. Hormone-related gene expression was also altered both in the short- and long-term. Gene expression analyses suggest that Sd interfered with fruit development/ripening by interacting with multiple hormonal pathways and that fruit developmental marker gene expression was shifted ahead in accord with a developmental slowing down. 24-Epibrassinolide was applied to Flaminia peaches under field conditions early (S1) or later (S3) during development. Preliminary results showed that, at harvest, treated fruit tended to be larger and less mature though quality parameters did not change relative to controls.

Caratterizzazione morfologica e neurochimica dei neuroni sensitivi e motori del trigono vescicale e del muscolo uretrale di maiale

Il trigono della vescica urinaria (UBT) è un'area limitata attraverso la quale penetrano nella vescica la maggior parte dei vasi e fibre e in cui le fibre nervose e neuroni intramurali sono più concentrati. Mediante l’utilizzo combinato di un tracciante retrogrado(FB) e dell’immunoistochimica sono stati valutati il fenotipo e l’area del soma dei neuroni dei gangli spinali (DRG), dei neuroni post-gangliari, il fenotipo dei gangli della catena simpatica (STG) e i gangli mesenterici caudali (CMG) innervanti l’UBT. - Caratterizzazione dei neuroni dei DRG con: peptide correlato al gene della calcitonina (CGRP)(30±3%, 29±3%, rispettivamente), sostanza P(SP)(26±8%, 27±12%), ossido nitrico sintasi neuronale (nNOS)(21±4%; 26±7%), neurofilamento 200kDa (NF200)(75±14%, 81±7% ) , transient receptor potential vanilloid1 (TRPV1)(48±13%, 43±6%) e isolectina-B4-positivi (IB4) (56±6%;43±10%). I neuroni sensoriali, distribuiti da L2 a Ca1 (DRG), hanno presentato una localizzazione segmentale, mostrando maggior densità nei DRG L4-L5 e S2-S4. I neuroni sensoriali lombari sono risultati significativamente più grandi di quelle sacrali (1.112±624μm2 vs716±421μm2). Complessivamente, questi dati indicano che le vie lombari e sacrali probabilmente svolgono ruoli diversi nella trasmissione sensitiva del trigono della vescica urinaria. -I neuroni FB+ della STG e dei CMG sono risultati immunoreattivi per la tirosina idrossilasi (TH)(66±10,1%, 53±8,2%, rispettivamente), la dopamina beta-idrossilasi (DβH)(62±6,2%, 52±6,2%), neuropeptideY (NPY)(59±8%; 66±7%), CGRP(24±3%, 22±3%), SP(22±2%; 38±8%), polipeptide intestinale vasoattivo (VIP)(19±2%; 35±4%), nNOS(15±2%; 33±8%), trasportatore vescicolare dell'acetilcolina (VAChT)(15±2%; 35±5%), leu-encefalina (LENK)(14±7%; 26±9%), e somatostatina (SOM)(12±3%;32±7%).Il numero medio di neuroni FB+ (1845,1±259,3) era nella STG in L1-S3, con i pirenofori più piccoli (465,6±82.7μm2). Un gran numero (4287,5±1450,6) di neuroni FB+ di piccole dimensioni (476,1±103,9μm2) sono stati localizzati lungo il margine dei CMG. Il maggior numero (4793,3±1990,8) di neuroni FB + è stato osservato nel plesso pelvico, dove i neuroni marcati erano raggruppati in micro-gangli e con pirenoforo ancora più piccolo (374,9±85,4 μm2).