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.

Development of motion analysis protocols based on inertial sensors

The aim of this thesis was to describe the development of motion analysis protocols for applications on upper and lower limb extremities, by using inertial sensors-based systems. Inertial sensors-based systems are relatively recent. Knowledge and development of methods and algorithms for the use of such systems for clinical purposes is therefore limited if compared with stereophotogrammetry. However, their advantages in terms of low cost, portability, small size, are a valid reason to follow this direction. When developing motion analysis protocols based on inertial sensors, attention must be given to several aspects, like the accuracy of inertial sensors-based systems and their reliability. The need to develop specific algorithms/methods and software for using these systems for specific applications, is as much important as the development of motion analysis protocols based on them. For this reason, the goal of the 3-years research project described in this thesis was achieved first of all trying to correctly design the protocols based on inertial sensors, in terms of exploring and developing which features were suitable for the specific application of the protocols. The use of optoelectronic systems was necessary because they provided a gold standard and accurate measurement, which was used as a reference for the validation of the protocols based on inertial sensors. The protocols described in this thesis can be particularly helpful for rehabilitation centers in which the high cost of instrumentation or the limited working areas do not allow the use of stereophotogrammetry. Moreover, many applications requiring upper and lower limb motion analysis to be performed outside the laboratories will benefit from these protocols, for example performing gait analysis along the corridors. Out of the buildings, the condition of steady-state walking or the behavior of the prosthetic devices when encountering slopes or obstacles during walking can also be assessed. The application of inertial sensors on lower limb amputees presents conditions which are challenging for magnetometer-based systems, due to ferromagnetic material commonly adopted for the construction of idraulic components or motors. INAIL Prostheses Centre stimulated and, together with Xsens Technologies B.V. supported the development of additional methods for improving the accuracy of MTx in measuring the 3D kinematics for lower limb prostheses, with the results provided in this thesis. In the author’s opinion, this thesis and the motion analysis protocols based on inertial sensors here described, are a demonstration of how a strict collaboration between the industry, the clinical centers, the research laboratories, can improve the knowledge, exchange know-how, with the common goal to develop new application-oriented systems.

Partial Discharge Phenomena in Converter and Traction Transformers: Identification and Reliability

After the development of power electronics converters, the number of transformers subjected to non-sinusoidal stresses (including DC) has increased in applications such as HVDC links and traction (electric train power cars). The effects of non-sinusoidal voltages on transformer insulation have been investigated by many researchers, but still now, there are some issues that must be understood. Some of those issues are tackled in this Thesis, studying PD phenomena behavior in Kraft paper, pressboard and mineral oil at different voltage conditions like AC, DC, AC+DC, notched AC and square waveforms. From the point of view of converter transformers, it was found that the combined effect of AC and DC voltages produces higher stresses in the pressboard that those that are present under pure DC voltages. The electrical conductivity of the dielectric systems in DC and AC+DC conditions has demonstrated to be a critical parameter, so, its measurement and analysis was also taken into account during all the experiments. Regarding notched voltages, the RMS reduction caused by notches (depending on firing and overlap angles) seems to increase the PDIV. However, the experimental results show that once PD activity has incepted, the notches increase PD repetition rate and magnitude, producing a higher degradation rate of paper. On the other hand, the reduction of mineral oil stocks, their relatively low flash point as well as environmental issues, are factors that are pushing towards the use of esters as transformer insulating fluids. This PhD Thesis also covers the study of two different esters with the scope to validate their use in traction transformers. Mineral oil was used as benchmark. The complete set of dielectric tests performed in the three fluids, show that esters behave better than mineral oil in practically all the investigated conditions, so, their application in traction transformers is possible and encouraged.

Interference Management and Energy Efficiency in Satellite Communications

The main areas of research of this thesis are Interference Management and Link-Level Power Efficiency for Satellite Communications. The thesis is divided in two parts. Part I tackles the problem of interference environments in satellite communications, and interference mitigation strategies, not just in terms of avoidance of the interferers, but also in terms of actually exploiting the interference present in the system as a useful signal. The analysis follows a top-down approach across different levels of investigation, starting from system level consideration on interference management, down to link-level aspects and to intra-receiver design. Interference Management techniques are proposed at all the levels of investigation, with interesting results. Part II is related to efficiency in the power domain, for instance in terms of required Input Back-off at the power amplifiers, which can be an issue for waveform based on linear modulations, due to their varying envelope. To cope with such aspects, an analysis is carried out to compare linear modulation with waveforms based on constant envelope modulations. It is shown that in some scenarios, constant envelope waveforms, even if at lower spectral efficiency, outperform linear modulation waveform in terms of energy efficiency.

The posterior parietal cortex: a bridge between vision and action

The present work takes into account three posterior parietal areas, V6, V6A, and PEc, all operating on different subsets of signals (visual, somatic, motor). The work focuses on the study of their functional properties, to better understand their respective contribution in the neuronal circuits that make possible the interactions between subject and external environment. In the caudalmost pole of parietal lobe there is area V6. Functional data suggest that this area is related to the encoding of both objects motion and ego-motion. However, the sensitivity of V6 neurons to optic flow stimulations has been tested only in human fMRI experiments. Here we addressed this issue by applying on monkey the same experimental protocol used in human studies. The visual stimulation obtained with the Flow Fields stimulus was the most effective and powerful to activate area V6 in monkey, further strengthening this homology between the two primates. The neighboring areas, V6A and PEc, show different cytoarchitecture and connectivity profiles, but are both involved in the control of reaches. We studied the sensory responses present in these areas, and directly compared these.. We also studied the motor related discharges of PEc neurons during reaching movements in 3D space comparing also the direction and depth tuning of PEc cells with those of V6A. The results show that area PEc and V6A share several functional properties. Area PEc, unlike V6A, contains a richer and more complex somatosensory input, and a poorer, although complex visual one. Differences emerged also comparing the motor-related properties for reaches in depth: the incidence of depth modulations in PEc and the temporal pattern of modulation for depth and direction allow to delineate a trend among the two parietal visuomotor areas.

Reconstruction from image correspondences

A single picture provides a largely incomplete representation of the scene one is looking at. Usually it reproduces only a limited spatial portion of the scene according to the standpoint and the viewing angle, besides it contains only instantaneous information. Thus very little can be understood on the geometrical structure of the scene, the position and orientation of the observer with respect to it remaining also hard to guess. When multiple views, taken from different positions in space and time, observe the same scene, then a much deeper knowledge is potentially achievable. Understanding inter-views relations enables construction of a collective representation by fusing the information contained in every single image. Visual reconstruction methods confront with the formidable, and still unanswered, challenge of delivering a comprehensive representation of structure, motion and appearance of a scene from visual information. Multi-view visual reconstruction deals with the inference of relations among multiple views and the exploitation of revealed connections to attain the best possible representation. This thesis investigates novel methods and applications in the field of visual reconstruction from multiple views. Three main threads of research have been pursued: dense geometric reconstruction, camera pose reconstruction, sparse geometric reconstruction of deformable surfaces. Dense geometric reconstruction aims at delivering the appearance of a scene at every single point. The construction of a large panoramic image from a set of traditional pictures has been extensively studied in the context of image mosaicing techniques. An original algorithm for sequential registration suitable for real-time applications has been conceived. The integration of the algorithm into a visual surveillance system has lead to robust and efficient motion detection with Pan-Tilt-Zoom cameras. Moreover, an evaluation methodology for quantitatively assessing and comparing image mosaicing algorithms has been devised and made available to the community. Camera pose reconstruction deals with the recovery of the camera trajectory across an image sequence. A novel mosaic-based pose reconstruction algorithm has been conceived that exploit image-mosaics and traditional pose estimation algorithms to deliver more accurate estimates. An innovative markerless vision-based human-machine interface has also been proposed, so as to allow a user to interact with a gaming applications by moving a hand held consumer grade camera in unstructured environments. Finally, sparse geometric reconstruction refers to the computation of the coarse geometry of an object at few preset points. In this thesis, an innovative shape reconstruction algorithm for deformable objects has been designed. A cooperation with the Solar Impulse project allowed to deploy the algorithm in a very challenging real-world scenario, i.e. the accurate measurements of airplane wings deformations.

Non-Covalent Interaction: Revealed by Rotational Spectroscopy

The pulsed jet Fourier transform microwave spectroscopy have been applied to several molecular complexes involving H2O, freons, methane, carboxylic acids, and rare gas. The obtained results showcase the suitability of this technique for studying the intermolecular interactions. The rotational spectra of three water adducts of halogenated organic molecules, i.e. chlorotrifluoroethylene, isoflurane and alfa,alfa,alfa,-trifluoroanisole, have been investigated. It has been found that, the halogenation of the partner molecules definitely changes the way in which water will link to the partner molecule. Quadrupole hyperfine structures and/or the tunneling splittings have been observed in the rotational spectra of difluoromethane-dichloromethane, chlorotrifluorometane-fluoromethane, difluoromethane-formaldehyde and trifluoromethane-benzene. These features have been useful to describe their intermolecular interactions (weak hydrogen bonds or halogen bonds), and to size the potential energy surfaces of their internal motions. The rotational spectrum of pyridine-methane pointed out that methane prefers to locate above the ring and link to pyridine through a C-H•••π weak hydrogen bond, rather than the C-H•••n interaction. This behavior, typical of complexes of pyridine with rare gases, suggests classifying CH4, in relation to its ability to form molecular complexes with aromatic molecules, as a pseudo rare gas. The conformational equilibria of three bi-molecules of carboxylic acids, acrylic acid-trifluoroacetic acid, difluoroacetic acid-formic acid and acrylic acid-fluoroacetic acid have been studied. The increase of the hydrogen bond length upon H→D isotopic substitution (Ubbelohde effect) has been deduced from the elongation of the carboxylic carbons C•••C distance. The van der Waals complex tetrahydrofuran-krypton shows that the systematic doubling of the rotational lines has been attributed to the residual pseudo-rotation of tetrahydrofuran in the complex, based on the values of the Coriolis coupling constants, and on the type (mu_b) of the interstate transitions.

La creazione del distretto comunale: Il caso di Reggio Emilia (XII-prima metà XIII secolo)

L’oggetto della ricerca è stato il processo di creazione del distretto del Comune di Reggio Emilia tra il XII e l’inizio del XIII secolo, di cui sono stati analizzati diversi aspetti salienti, così come emergono in primo luogo dall’analisi del liber iurium reggiano, il Liber grossus antiquus. L’elaborato è suddiviso in due parti. Nella prima parte si è cercato di ricostruire le vicende, i legami e il patrimonio delle famiglie rurali reggiane nel corso del XII secolo in particolare e gli aspetti caratteristici del Comune cittadino nella sua fase iniziale. Nella seconda parte ci si è concentrati sull’analisi dei caratteri più rilevanti del processo di creazione del distretto comunale reggiano: il rapporto tra i signori del contado, i Comuni rurali e il Comune urbano; la difesa e l’incremento dei Communia cittadini; la fondazione di borghi franchi e nuovi. Il Comune di Reggio Emilia tentò di annettere l’intero territorio diocesano al distretto cittadino, non riuscendoci completamente e adottando una politica territoriale diversificata a seconda dei caratteri delle zone controllate.

Nonlinear/electromagnetic co-simulation of microwaves and millimeter-waves links

The Ph.D. thesis describes the simulations of different microwave links from the transmitter to the receiver intermediate-frequency ports, by means of a rigorous circuit-level nonlinear analysis approach coupled with the electromagnetic characterization of the transmitter and receiver front ends. This includes a full electromagnetic computation of the radiated far field which is used to establish the connection between transmitter and receiver. Digitally modulated radio-frequency drive is treated by a modulation-oriented harmonic-balance method based on Krylov-subspace model-order reduction to allow the handling of large-size front ends. Different examples of links have been presented: an End-to-End link simulated by making use of an artificial neural network model; the latter allows a fast computation of the link itself when driven by long sequences of the order of millions of samples. In this way a meaningful evaluation of such link performance aspects as the bit error rate becomes possible at the circuit level. Subsequently, a work focused on the co-simulation an entire link including a realistic simulation of the radio channel has been presented. The channel has been characterized by means of a deterministic approach, such as Ray Tracing technique. Then, a 2x2 multiple-input multiple-output antenna link has been simulated; in this work near-field and far-field coupling between radiating elements, as well as the environment factors, has been rigorously taken into account. Finally, within the scope to simulate an entire ultra-wideband link, the transmitting side of an ultrawideband link has been designed, and an interesting Front-End co-design technique application has been setup.

Nonlinear / electromagnetic co-simulation and co-design of microwave links in highly polluted and / or strongly inhomogeneous environments

The objective of the Ph.D. thesis is to put the basis of an all-embracing link analysis procedure that may form a general reference scheme for the future state-of-the-art of RF/microwave link design: it is basically meant as a circuit-level simulation of an entire radio link, with – generally multiple – transmitting and receiving antennas examined by EM analysis. In this way the influence of mutual couplings on the frequency-dependent near-field and far-field performance of each element is fully accounted for. The set of transmitters is treated as a unique nonlinear system loaded by the multiport antenna, and is analyzed by nonlinear circuit techniques. In order to establish the connection between transmitters and receivers, the far-fields incident onto the receivers are evaluated by EM analysis and are combined by extending an available Ray Tracing technique to the link study. EM theory is used to describe the receiving array as a linear active multiport network. Link performances in terms of bit error rate (BER) are eventually verified a posteriori by a fast system-level algorithm. In order to validate the proposed approach, four heterogeneous application contexts are provided. A complete MIMO link design in a realistic propagation scenario is meant to constitute the reference case study. The second one regards the design, optimization and testing of various typologies of rectennas for power generation by common RF sources. Finally, the project and implementation of two typologies of radio identification tags, at X-band and V-band respectively. In all the cases the importance of an exhaustive nonlinear/electromagnetic co-simulation and co-design is demonstrated to be essential for any accurate system performance prediction.

From inverted pendulum to N-link chain: inertial sensors-based assessment of movement kinematics and dynamics for functional evaluation and rehabilitation

Despite several clinical tests that have been developed to qualitatively describe complex motor tasks by functional testing, these methods often depend on clinicians' interpretation, experience and training, which make the assessment results inconsistent, without the precision required to objectively assess the effect of the rehabilitative intervention. A more detailed characterization is required to fully capture the various aspects of motor control and performance during complex movements of lower and upper limbs. The need for cost-effective and clinically applicable instrumented tests would enable quantitative assessment of performance on a subject-specific basis, overcoming the limitations due to the lack of objectiveness related to individual judgment, and possibly disclosing subtle alterations that are not clearly visible to the observer. Postural motion measurements at additional locations, such as lower and upper limbs and trunk, may be necessary in order to obtain information about the inter-segmental coordination during different functional tests involved in clinical practice. With these considerations in mind, this Thesis aims: i) to suggest a novel quantitative assessment tool for the kinematics and dynamics evaluation of a multi-link kinematic chain during several functional motor tasks (i.e. squat, sit-to-stand, postural sway), using one single-axis accelerometer per segment, ii) to present a novel quantitative technique for the upper limb joint kinematics estimation, considering a 3-link kinematic chain during the Fugl-Meyer Motor Assessment and using one inertial measurement unit per segment. The suggested methods could have several positive feedbacks from clinical practice. The use of objective biomechanical measurements, provided by inertial sensor-based technique, may help clinicians to: i) objectively track changes in motor ability, ii) provide timely feedback about the effectiveness of administered rehabilitation interventions, iii) enable intervention strategies to be modified or changed if found to be ineffective, and iv) speed up the experimental sessions when several subjects are asked to perform different functional tests.

Knots and links in lens spaces

The aim of this dissertation is to improve the knowledge of knots and links in lens spaces. If the lens space L(p,q) is defined as a 3-ball with suitable boundary identifications, then a link in L(p,q) can be represented by a disk diagram, i.e. a regular projection of the link on a disk. In this contest, we obtain a complete finite set of Reidemeister-type moves establishing equivalence, up to ambient isotopy. Moreover, the connections of this new diagram with both grid and band diagrams for links in lens spaces are shown. A Wirtinger-type presentation for the group of the link and a diagrammatic method giving the first homology group are described. A class of twisted Alexander polynomials for links in lens spaces is computed, showing its correlation with Reidemeister torsion. One of the most important geometric invariants of links in lens spaces is the lift in 3-sphere of a link L in L(p,q), that is the counterimage of L under the universal covering of L(p,q). Starting from the disk diagram of the link, we obtain a diagram of the lift in the 3-sphere. Using this construction it is possible to find different knots and links in L(p,q) having equivalent lifts, hence we cannot distinguish different links in lens spaces only from their lift. The two final chapters investigate whether several existing invariants for links in lens spaces are essential, i.e. whether they may assume different values on links with equivalent lift. Namely, we consider the fundamental quandle, the group of the link, the twisted Alexander polynomials, the Kauffman Bracket Skein Module and an HOMFLY-PT-type invariant.