Дисертації з теми "ROUTING STRATEGIES"

In payment channel networks, such as the Bitcoin native Lightning Network, the routing nodes receive a fee as compensation for displaced liquidity, time value of money and operational costs. Currently this fee is manually set procuring sub optimal profits to the node operator. The network dynamics may be modeled as a graph and each node as an actor utilizing strategies in fee price setting, preferential attachment, timing, allocation and funding akin to game theoretic models. Further assuming rational actors and strategy propagation are proportional to population suggest similar methodology to evolutionary game theory where a strategy’s fitness will emerge as a fraction of population size. A simulation study was performed where strategies were played against each other to find emergent equilibria under competitive market pressure. Where such equilibrium may lie have further consequences for the network in form of total throughput, routing cost and robustness. This study suggests a model for the optimal fee price and that a robust network topology with short average paths along with an exponential revenue distribution will emerge from a selection bias induced by free competition

Thesis (Ph. D.) -- University of Maryland, College Park, 2006.
Thesis research directed by: Electrical Engineering. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

Vehicles that today are searching for a place to stop impacts other vehicles in cities. It can also be seen that the number of vehicles that desire to conduct a pick-up or drop-off increases with an increased number of ride-hailing services. New technology routing advises for such vehicles could improve the overall performance of a traffic network. This thesis analyses therefore how a routing strategy, that incorporates curbside availability information, can impact the performance. To analyse the effects of how curbside availability information can impact a network, a microscopic traffic simulation model was constructed in PTV Vissim and two different routing strategies were developed and implemented in the model. One strategy that represents the scenario of today where vehicles searches the traffic network while attempting to make a stop at a pick-up and drop-off slot. The second strategy routes vehicles to a slot based on curbside availability information. This strategy directs vehicles to an available slot and therefore reduces the time a vehicle is cruising before a stop has been made. A simulation experiment was set-up to compare the strategies that were developed with different penetration rates of vehicles that desired to stop. The results shows that the average travel time can be reduced with up to 25.2\% when vehicles have information compared to the scenario with no information. Similar findings is identified for average delay per vehicle which is reduced with up to 49.0\% and average traveled distance decreased with up to 15.5\%. The results of this thesis needs however to be studied in a wider context in order to draw reliable conclusions. The thesis propose further investigations whether a strategy that incorporates availability information can be implemented in a real world scenario and further investigations whether an implementation of a strategy like this would be socioeconomic beneficial.

This research addresses efficient use of the available energy in resource constrained mobile sensor nodes to prevent early depletion of the battery and maximize the packet delivery rate. This research contributes two energy-aware enhancement strategies to improve the network lifetime and delivery probability for energy constrained applications in the delay-tolerant networking environment.

This thesis examines a Distributed Interference Impact Probing (DIIP) strategy for Wireless Ad hoc Networks (WANETs), using a novel cross-layer Minimum Impact Routing (MIR) protocol. Perfonnance is judged in tenns of interference reduction ratio, efficiency, and system and user capacity, which are calculated based on the measurement of Disturbed Nodes (DN). A large number of routing algorithms have been proposed with distinctive features aimed to overcome WANET's fundamental challenges, such as routing over a dynamic topology, scheduling broadcast signals using dynamic Media Access Control (MAC), and constraints on network scalability. However, the scalability problem ofWANET cannot simply adapt the frequency reuse mechanism designed for traditional stationary cellular networks due to the relay burden, and there is no single comprehensive algorithm proposed for it. DIIP enhances system and user capacity using a cross layer routing algorithm, MIR, using feedback from DIIP to balance transmit power in order to control hop length, which consequently changes the number of relays along the path. This maximizes the number of simultaneous transmitting nodes, and minimizes the interference impact, i.e. measured in tenns of 'disturbed nodes'. The perfonnance of MIR is examined compared with simple shortest-path routing. A WANET simulation model is configured to simulate both routing algorithms under multiple scenarios. The analysis has shown that once the transmitting range of a node changes, the total number of disturbed nodes along a path changes accordingly, hence the system and user capacity varies with interference impact variation. By carefully selecting a suitable link length, the neighbouring node density can be adjusted to reduce the total number of DN, and thereby allowing a higher spatial reuse ratio. In this case the system capacity can increase significantly as the number of nodes increases. In contrast, if the link length is chosen regardless ofthe negative impact of interference, capacity decreases. In addition, MIR diverts traffic from congested areas, such as the central part of a network or bottleneck points.

This study presents an analysis of detour operations as a concept of congestion management. Since a large portion of traffic delay emanates from traffic incidents, the goal of the study was to alleviate incident-induced impacts on freeways by diverting congested traffic on to adjacent roadway facilities. To balance the demand between freeway and arterial systems, optimization was required through Integrated Corridor Management (ICM). This thesis examines the justification and optimization of dynamic traffic routing strategies. Previous studies have justified detour operations based solely on traffic simulation results. This study quantifies the impacts from freeway incidents on a parallel arterial roadway using a data-driven signal processing technique, with operating speeds adopted as a performance measure. Results show that rerouting traffic to an adjacent arterial road, due to a freeway incident, can mitigate the mobility of the corridor with a probability of up to 88% depending on the type of incident and occurrence time. Results also indicate that diverting traffic during off-peak hours, especially for minor incidents, provides minimal mobility benefits. A secondary focus of this study explored the optimum dynamic traffic diversion, to an adjacent arterial roadway, from incident-induced freeway congestion to better utilize the freeway’s available corridor capacity. VISSIM, a microsimulation tool, was employed to simulate a freeway incident and measure the performance of detour operations. A 23 full factorial central composite design was used to establish a relationship between the performance of the detour operation and three control factors: incident duration, diversion rate, and demand level. The resulting regression equation predicts the corridor delay with over 83% accuracy. The findings of this study can potentially serve as a building block in the understanding and development of future ICM systems and incident management plans.

Thesis (M.S.C.E. ) -- University of Maryland, College Park, 2005.
Thesis research directed by: Civil Engineering. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

Thesis: S.M., Massachusetts Institute of Technology, Department of Civil and Environmental Engineering, February, 2021
Cataloged from the official PDF of thesis.
Includes bibliographical references (pages 57-58).
We develop and numerically test a new strategy for the vehicle routing problem with stochastic customer demands. In our proposed approach, drivers are assigned to predetermined delivery routes in which adjacent routes share some customers. This overlapping assignment structure, which is inspired by the open chain design from the field of manufacturing process flexibility, enables drivers to adapt to variable customer demands while still maintaining largely consistent routes. Through an extensive computational study and scenario analysis, we show that relative to a system without customer sharing, such flexible routing strategies partly mitigate the transportation costs of filling unexpected customer demands, and the relative savings grow with the number of customers in the network. We also find that much of the cost savings is gained with just the first customer that is shared between adjacent routes. Thus, the overlapped routing model forms the basis for a practical and efficient strategy to manage costs from demand uncertainty.
by Kirby Ledvina.
S.M.
S.M. Massachusetts Institute of Technology, Department of Civil and Environmental Engineering

Optical networks based on Wavelength Division Multiplexing (WDM) technology show many clear benefits in terms of high capacity, flexibility and low power consumption. All these benefits make WDM networks the preferred choice for today’s and future transports solutions which are strongly driven by a plethora of emerging online services. In such a scenario, capability to provide high capacity during the service provisioning phase is of course very important, but it is not the only requirement that plays a central role. Traffic dynamicity is another essential aspect to consider because in many scenarios, e.g., in the case of real time multimedia services, the connections are expected to be provisioned and torn down quickly and relatively frequently. High traffic dynamicity may put a strain on the network control and management operations (i.e., the overhead due to control message exchange can grow rapidly) that coordinate any provisioning mechanisms. Furthermore, survivability, in the presence of new failure scenarios that goes beyond the single failure assumption, is still of the utmost importance to minimize the network disruptions and data losses. In other words, protection against any possible future failure scenario where multiple faults may struck simultaneously, asks for highly reliable provisioning solutions. The above consideration have a general validity i.e., can be equally applied to any network segment and not just limited to the core part. So, we also address the problem of service provisioning in the access paradigm. Long reach Passive Optical Networks (PONs) are gaining popularity due to their cost, reach, and bandwidth advantages in the access region. In PON, the design of an efficient bandwidth sharing mechanism between multiple subscribers in the upstream direction is crucial. In addition, Long Reach PONs (LR-PONs) introduces additional challenges in terms of packet delay and network throughput, due to their extended reach. It becomes apparent that effective solutions to the connection provisioning problem in both the core and access optical networks with respect to the considerations made above can ensure a truly optimal end-to-end connectivity while making an efficient usage of resources. The first part of this thesis focuses on a control and management framework specifically designed for concurrent resource optimization in WDM-based optical networks in a highly dynamic traffic scenario. The framework and the proposed provisioning strategies are specifically designed with the objective of: (i) allowing for a reduction of the blocking probability and the control overhead in a Path Computation Element (PCE)-based network architecture, (ii)  optimizing resource utilization for a traffic scenario that require services with diverse survivability requirements which are achieved by means of  dedicated and shared path-protection, and (iii) designing provisioning mechanism that guarantees high connection availability levels in Double Link Failures (DLF) scenarios. The presented results show that the proposed dynamic provisioning approach can significantly improve the network blocking performance while making an efficient use of primary/backup resources whenever protection is required by the provisioned services. Furthermore, the proposed DLF schemes show good performance in terms of minimizing disruption periods, and allowing for enhanced network robustness when specific services require high connection availability levels. In the second part of this thesis, we propose efficient resource provisioning strategies for LR-PON. The objective is to optimize the bandwidth allocation in LR-PONs, in particular to: (i) identify the performance limitations associated with traditional (short reach) TDM-PON based Dynamic Bandwidth Allocation (DBA) algorithms when employed in long reach scenarios, and (ii) devise efficient DBA algorithms that can mitigate the performance limitations imposed by an extended reach. Our proposed schemes show noticeable performance gains when compared with conventional DBA algorithms for short-reach PON as well as specifically devised approaches for long reach.

QC 20130520

The exponential growth of Internet applications has created new challenges for the control and administration of large-scale networks, which consist of heterogeneous elements under dynamically changing traffic conditions. These emerging applications need guaranteed service levels, beyond those supported by best-effort networks, to deliver the intended services to the end user. Several models have been proposed for a Quality of Service (QoS) framework that can provide the means to transport these services. It is desirable to find efficient routing strategies that can meet the strict routing requirements of these applications. QoS routing is considered as one of the major components of the QoS framework in communication networks. In QoS routing, paths are selected based upon the knowledge of resource availability at network nodes and the QoS requirements of traffic. Several QoS routing schemes have been proposed that differ in the way they gather information about the network state and the way they select paths based on this information. The biggest downside of current QoS routing schemes is the frequent maintenance and distribution of global state information across the network, which imposes huge communication and processing overheads. Consequently, scalability is a major issue in designing efficient QoS routing algorithms, due to the high costs of the associated overheads. Moreover, inaccuracy and staleness of global state information is another problem that is caused by relatively long update intervals, which can significantly deteriorate routing performance. Localized QoS routing, where source nodes take routing decisions based solely on statistics collected locally, was proposed relatively recently as a viable alternative to global QoS routing. It has shown promising results in achieving good routing performance, while at the same time eliminating many scalability related problems. In localized QoS routing each source-destination pair needs to determine a set of candidate paths from which a path will be selected to route incoming flows. The goal of this thesis is to enhance the scalability of QoS routing by investigating and developing new models and algorithms based on the localized QoS routing approach. For this thesis, we have extensively studied the localized QoS routing approach and demonstrated that it can achieve a higher routing performance with lower overheads than global QoS routing schemes. Existing localized routing algorithms, Proportional Sticky Routing (PSR) and Credit-Based Routing (CBR), use the blocking probability of candidate paths as the criterion for selecting routing paths based on either flow proportions or a crediting mechanism, respectively. Routing based on the blocking probability of candidate paths may not always reflect the most accurate state of the network. This has motivated the search for alternative localized routing algorithms and to this end we have made the following contributions. First, three localized bandwidth-constrained QoS routing algorithms have been proposed, two are based on a source routing strategy and the third is based on a distributed routing strategy. All algorithms utilize the quality of links rather than the quality of paths in order to make routing decisions. Second, a dynamic precautionary mechanism was used with the proposed algorithms to prevent candidate paths from reaching critical quality levels. Third, a localized delay-constrained QoS routing algorithm was proposed to provide routing with an end-to-end delay guarantee. We compared the performance of the proposed localized QoS routing algorithms with other localized and global QoS routing algorithms under different network topologies and different traffic conditions. Simulation results show that the proposed algorithms outperform the other algorithms in terms of routing performance, resource balancing and have superior computational complexity and scalability features.

In recent years transportation professionals have shown increasing interest in evacuation planning. With the advances in computing technologies it is possible to simulate urban transportation networks with great detail. These details from the traffic simulation model can be used for devising strategies for evacuation and emergency response in case of a disaster. This thesis describes the modeling, calibration, and validation of the VISSIM traffic simulation model coded for downtown San Jose. The network is then used to test various evacuation scenarios to assess evacuation strategies that would be effective in case of a human-caused disaster. The network modeled in the simulation software VISSIM required a large amount of data regarding network geometry, signal timings, signal coordination schemes, and turning movement volumes. Turning movement counts at intersections were used to validate the network with an empirical formula to assess the differences between observed and simulated counts. For freeways the simulation model was validated using the actual travel time information. Once the base network was validated, various scenarios were tested to estimate evacuation and emergency response vehicle arrival times. It was found that in the event of coordinated terrorist attacks (specified in the disaster scenario) simultaneously occurring at four locations in the downtown San Jose area, severe bottlenecks would result due to evacuee traffic. To alleviate the congestion, contraflow lanes should be used on Montgomery Street (which becomes Bird Avenue) to help reduce congestion. While contraflow lanes helped the situation, traffic incidents potentially resulting from all the chaos could complicate evacuations. The investigators found that reducing the number of vehicles on the road through public transit ridership would be the optimal approach, while leaving area roads uncongested for the emergency response personnel. In the scenario where 30% of the evacuees used transit at Diridon Transit Center, the travel times for the remaining evacuees, as well as the first responders, were minimized. None the less, the other scenarios were also critical to this study, since they provided a response strategy in case the transit station is affected by the attacks.

Overlay networks have recently gained popularity as a viable alternative to overcome functionality limitations of the Internet (e.g., lack of QoS, multicast routing). They offer enhanced functionality to end-users by forming an independent and customizable virtual network over the native network. Typically, the routing at the overlay layer operates independent of that at the underlying native layer. There are several potential problems with this approach because overlay networks are selfish entities that are chiefly concerned with achieving the routing objective of their own users. This leads to complex cross-layer interactions between the native and overlay layers, and often tends to degrade the achieved performance for both layers. As overlay applications proliferate and the amount of selfish overlay traffic surges, there is a clear need for understanding the complex interactions and for strategies to manage them appropriately. Our work addresses these issues in the context of "service overlay networks", which represent virtual networks formed of persistent nodes that collaborate to offer improved services to actual end-systems. Typically, service overlays alter the route between the overlay nodes in a dynamic manner in order to satisfy a selfish objective. The objective of this thesis is to improve the stability and performance of overlay routing in this multi-layer environment.

We investigate the common problems of functionality overlap, lack of cross-layer awareness, mismatch or misalignment in routing objectives and the contention for native resources between the two layers. These problems often lead to deterioration in performance for the end-users. This thesis presents an analysis of the cross-layer interaction during fault recovery, inter-domain policy enforcement and traffic engineering in the multi-layer context. Based on our characterization of the interaction, we propose effective strategies that improve overall routing performance, with minimal side-effects on other traffic. These strategies typically 1) increase the layer-awareness (awareness of information about the other layer) at each layer, 2) introduce better control over routing dynamics and 3) offer improved overlay node placement options. Our results demonstrate how applying these strategies lead to better management of the cross-layer interaction, which in turn leads to improved routing performance for end-users.

This dissertation addresses the development of enhanced formulations for minimax and mixed-integer programming models for certain industrial and logistical systems, along with the design and implementation of efficient algorithmic strategies. We first examine the general class of minimax mixed-integer 0-1 problems of the type that frequently arise in decomposition approaches and in a variety of location and scheduling problems. We conduct an extensive polyhedral analysis of this problem in order to tighten its representation using the Reformulation-Linearization/Convexification Technique (RLT), and demonstrate the benefits of the resulting lifted formulations for several classes of problems. Specifically, we investigate RLT-enhanced Lagrangian dual formulations for the class of minimax mixed-integer 0-1 problems in concert with deflected/conjugate subgradient algorithms. In addition, we propose two general purpose lifting mechanisms for tightening the mathematical programming formulations associated with such minimax optimization problems. Next, we explore novel continuous nonconvex as well as lifted discrete formulations for the notoriously challenging class of job-shop scheduling problems with the objective of minimizing the maximum completion time (i.e., minimizing the makespan). In particular, we develop an RLT-enhanced continuous nonconvex model for the job-shop problem based on a quadratic formulation of the job sequencing constraints on machines. The tight linear programming relaxation that is induced by this formulation is then embedded in a globally convergent branch-and-bound algorithm. Furthermore, we design another novel formulation for the job-shop scheduling problem that possesses a tight continuous relaxation, where the non-overlapping job sequencing constraints on machines are modeled via a lifted asymmetric traveling salesman problem (ATSP) construct, and specific sets of valid inequalities and RLT-based enhancements are incorporated to further tighten the resulting mathematical program. The efficacy of our enhanced models is demonstrated by an extensive computational experiment using classical benchmark problems from the literature. Our results reveal that the LP relaxations produced by the lifted ATSP-based models provide very tight lower bounds, and directly yield a 0\% optimality gap for many benchmark problems, thereby substantially dominating other alternative mixed-integer programming models available for this class of problems. Notably, our lifted ATSP-based formulation produced a 0\% optimality gap via the root node LP relaxation for 50\% of the classical problem instances due to Lawrence. We also investigate enhanced model formulations and specialized, efficient solution methodologies for applications arising in four particular industrial and sports scheduling settings. The first of these was posed to us by a major trucking company (Volvo Logistics North America), and concerns an integrated assembly and routing problem, which is a unique study of its kind in the literature. In this context, we examine the general class of logistical systems where it is desirable to appropriately ascertain the joint composition of the sequences of vehicles that are to be physically connected along with determining their delivery routes. Such assembly-routing problems occur in the truck manufacturing industry where different models of vehicles designed for a network of customers need to be composed into compatible groups (assemblies) and subsequently dispatched via appropriately optimized delivery routes that are restricted by the particular sequence in which the trucks are connected. A similar structure is exhibited in the business of shipping goods via boat-towed barges along inland waterways, or via trains through railroad networks. We present a novel modeling framework and column generation-based optimization approach for this challenging class of joint vehicle assembly-routing problems. In addition, we suggest several extensions to accommodate particular industrial restrictions where assembly sequence-dependent delivery routes are necessary, as well as those where limited driver- and equipment-related resources are available. Computational experience is provided using large-scale realistic data to demonstrate the applicability of our suggested methodology in practice. The second application addressed pertains to a production planning problem faced by a major motorcycle manufacturing firm (Harley-Davidson Motor Company). We consider the problem of partitioning and sequencing the production of different manufactured items in mixed-model assembly lines, where each model has various specific options and designated destinations. We propose a mixed-integer programming formulation (MPSP1) for this problem that sequences the manufactured goods within production batches in order to balance the motorcycle model and destination outputs as well as the load demands on material and labor resources. An alternative (relaxed) formulation (MPSP2) is also presented to model a closely related case where all production decisions and outputs are monitored within a common sequence of batches, which permits an enhanced tighter representation via an additional set of hierarchical symmetry-defeating constraints that impart specific identities amongst batches of products under composition. The latter model inspires a third set partitioning-based formulation in concert with an efficient column generation approach that directly achieves the joint partitioning of jobs into batches along with ascertaining the sequence of jobs within each composed batch. Finally, we investigate a subgradient-based optimization strategy that exploits a non-differentiable optimization formulation, which is prompted by the flexibility in the production process as reflected in the model via several soft-constraints, thereby providing a real-time decision-making tool. Computational experience is presented to demonstrate the relative effectiveness of the different proposed formulations and the associated optimization strategies for solving a set of realistic problem instances. The third application pertains to the problem of matching or assigning subassembly parts in assembly lines, where we seek to minimize the total deviation of the resulting final assemblies from a vector of nominal and mean quality characteristic values. We introduce three symmetry-defeating enhancements for an existing assignment-based model, and highlight the critical importance of using particular types of symmetry-defeating hierarchical constraints that preserve the model structure. We also develop an alternative set partitioning-based formulation in concert with a column generation approach that efficiently exploits the structure of the problem. A special complementary column generation feature is proposed, and we provide insights into its vital role for the proposed column generation strategy, as well as highlight its benefits in the broader context of set partitioning-based formulations that are characterized by columns having relatively dense non-zero values. In addition, we develop several heuristic procedures. Computational experience is presented to demonstrate the relative effectiveness of the different adopted strategies for solving a set of realistic problem instances. Finally, we analyze a doubles tennis scheduling problem in the context of a training tournament as prompted by a tennis club in Virginia, and develop two alternative 0-1 mixed-integer programming models, each with three different objective functions that attempt to balance the partnership and the opponentship pairings among the players. Our analysis and computational experience demonstrate the superiority of one of these models over the other, and reflect the importance of model structure in formulating discrete optimization problems. Furthermore, we design effective symmetry-defeating strategies that impose certain decision hierarchies within the models, which serve to significantly enhance algorithmic performance. In particular, our study provides the insight that the special structure of the mathematical program to which specific tailored symmetry-defeating constraints are appended can greatly influence their pruning effect. We also propose a novel nonpreemptive multi-objective programming strategy in concert with decision hierarchies, and highlight its effectiveness and conceptual value in enhancing problem solvability. Finally, four specialized heuristics are devised and are computationally evaluated along with the exact solution schemes using a set of realistic practical test problems. Aside from the development of specialized effective models and algorithms for particular interesting and challenging applications arising in different assembly, routing, and scheduling contexts, this dissertation makes several broader contributions that emerge from the foregoing studies, which are generally applicable to solving formidable combinatorial optimization problems. First, we have shown that it is of utmost importance to enforce symmetry-defeating constraints that preserve the structure of mathematical programs to which they are adjoined, so that their pruning effects are most efficiently coupled with the branch-and-bound strategies that are orchestrated within mathematical programming software packages. In addition, our work provides the insight that the concept of symmetry compatible formulations plays a crucial role in the effectiveness of implementing any particular symmetry-defeating constraints. In essence, if the root node LP solution of the original formulation does not conform relatively well with the proposed symmetry-defeating hierarchical constraints, then a significant branching effort might be required to identify a good solution that is compatible with the pattern induced by the selected symmetry-defeating constraints. Therefore, it is advisable to enforce decision hierarchies that conform as much as possible with the problem structure as well as with the initial LP relaxation. Second, we have introduced an alternative concept for defeating symmetry via augmented objective functions. This concept prompts the incorporation of objective perturbation terms that discriminate amongst subsets of originally undistinguishable solution structures and, in particular, leads to the development of a nonpreemptive multiobjective programming approach based on, and combined with, symmetry-defeating constraints. Interestingly, nonpreemptive multiobjective programming approaches that accommodate symmetry-defeating hierarchical objective terms induce a root node solution that is compatible with the imposed symmetry-defeating constraints, and hence affords an automated alternative to the aforementioned concept of symmetry compatible formulations. Third, we have proposed a new idea of complementary column generation in the context of column generation approaches that generally provide a versatile framework for analyzing industrial-related, integrated problems that involve the joint optimization of multiple operational decisions, such as assembly and routing, or partitioning and scheduling. In such situations, we have reinforced the insight that assignment-related problems that involve collections of objects (production batches, final assemblies, etc.) whose permutation yields equivalent symmetric solutions may be judiciously formulated as set partitioning models. The latter can then be effectively tackled via column generation approaches, thereby implicitly obviating the foregoing combinatorial symmetric reflections through the dynamic generation of attractive patterns or columns. The complementary column generation feature we have proposed and investigated in this dissertation proves to be particularly valuable for such set partitioning formulations that involve columns having relatively dense non-zero values. The incorporation of this feature guarantees that every LP iteration (involving the solution of a restricted master program and its associated subproblem) systematically produces a consistent set of columns that collectively qualify as a feasible solution to the problem under consideration. Upon solving the problem to optimality as a linear program, the resultant formulation encompasses multiple feasible solutions that generally include optimal or near-optimal solutions to the original integer-restricted set partitioning formulation, thereby yielding a useful representation for designing heuristic methods as well as exact branch-and-price algorithms. In addition, using duality theory and considering set partitioning problems where the number of patterns needed to collectively compose a feasible solution is bounded, we have derived a lower bound on the objective value that is updated at every LP phase iteration. By virtue of this sequence of lower bounds and the availability of upper bounds via the restricted master program at every LP phase iteration, the LP relaxation of the set partitioning problem is efficiently solved as using a pre-specified optimality tolerance. This yields enhanced algorithmic performance due to early termination strategies that successfully mitigate the tailing-off effect that is commonly witnessed for simplex-based column generation approaches.
Ph. D.

Hoje em dia, as redes intra chip (NoC) são cada vez mais utilizadas como uma arquitetura de comunicação alternativa para sistemas complexos, pois estas permitem flexibilidade e desempenho da comunicação. Porém, o grande número de interconexões da rede, aliado à diminuição das dimensões dos transistores fabricados nas tecnologias nanométricas, fazem com que a NoC possa ter um grande número de falhas durante sua fabricação, ou por desgaste durante sua vida útil. Sabe-se que, em futuras tecnologias os circuitos integrados terão uma taxa de falhas permanentes de 20 a 30%. Entretanto, mesmo na presença de falhas, é desejável que a NoC permaneça funcionando corretamente. A partir do diagnóstico das falhas, a NoC deve ser capaz de buscar alternativas para manter a comunicação entre os núcleos, evitando os canais e os roteadores com falhas. O objetivo deste trabalho é propor mecanismos adaptativos de proteção contra falhas permanentes. Mesmo quando são adicionados componentes extras para a substituição em SoCs, a ocorrência de falhas permanentes na rede intrachip impede a substituição ou reparo de um componente no sistema intrachip. Portanto a tolerância a falhas na NoC será crucial para reduzir custo de manufatura, e aumentar o rendimento e o tempo de vida do circuito integrado. O mecanismo proposto é capaz de evitar falhas sabendo anteriormente, na fase de teste e diagnóstico, a localização especifica da falha. Portanto, as técnicas se adaptam em cada roteador para evitar as falhas permanentes, sempre buscando manter desempenho, aumentar o rendimento e a confiabilidade do sistema.
Nowadays, networks-on-chip (NoCs) have been used as an alternative communication architecture inside complex system on-chip. They offer better scalability and performance than the traditional bus. However, the growing number of interconnects that have to be inserted using smaller transistors means that NoCs have a growing number of faults, either from manufacturing or due to aging. In future systems-on-chip (SoCs), the fault rate will be around 20 to 30% of the contact and transistors of integrated circuits. Therefore, even in the presence of a fault, it is still desirable that NoCs properly work. The main idea of this work is to implement adaptive mechanisms to protect NoCs against permanent faults. The main advantage of such mechanism is to manage failures based on data from the testing and diagnosing phase. The mechanisms are adapted in each router in order to sustain performance, increasing the system yield and reliability even in the presence of failures. Even if one adds extra blocks for replacement, the occurrence of permanent faults in a NoC might preclude the replacement or repair of a faulty component within the SoC. In such case, fault-tolerant NoCs are able to reduce manufacturing costs, increase yield and the lifetime of the chip.

In recent years, the global adoption of commercial electric vehicles (CEVs) has been on the rise due to stricter emission standards worldwide. New government regulations and incentives are promoting the large-scale adoption of CEVs, particularly in urban settings where cargo, freight, and delivery entities are prevalent. Charging of CEVs is typically performed at depots and public charging stations along their routes. Returnto- base charging, which involves charging the vehicles at dedicated charging stations at depots, is common. However, simultaneous charging of CEVs can increase peak demand that increases costs and affects infrastructure upgrades. As CEV fleets grow, upgrading the power infrastructure at depots to add charging stations can be costly and impractical. Therefore, it is imperative to effectively manage the charging of large CEV fleets at depots with limited charging infrastructure, while taking into account their operational conditions. These challenges of depot charging also influence the public charging schedules of CEVs along their routes, significantly impacting both the operational costs and the sustainability of logistics services. To address these issues, this thesis presents novel strategies for coordinating CEV fleet charging at depots and public charging stations. For return-to-base charging, a smart charging system is proposed that manages a CEV fleet with the objective of minimizing the peak demand at the depot, considering different operating conditions of the depots and CEVs, such as the vehicle to grid (V2G) technology and demand response programs. Simulation studies demonstrate that the proposed solution can reduce demand charges by up to 54% compared to uncontrolled charging schemes. For CEVs that require public charging, an optimization algorithm is developed to address optimal charging and routing problems. The algorithm considers various charging variants, including peak demand, time-of-use tariffs, partial recharging, waiting times, and characteristics of public stations. Results indicate the effectiveness of the developed algorithm in achieving optimal routes that maximize logistics company benefits while satisfying all constraints. Finally, a new charging strategy for managing the charging of large CEV fleets is being put forward. Specifically, the proposed strategy involves the allocation and coordination of CEV fleets at both limited depot charging stations and public charging stations, taking into account operational schedules, demand charges, and the features of public charging stations. The findings demonstrate the effectiveness of this approach in optimizing CEV charging at different stations, ensuring uninterrupted logistics service, and reducing total travel costs by 30% relative to current solutions.

O transporte de cargas desempenha um papel fundamental nos sistemas logísticos uma vez que possibilita o fluxo de produtos entre os elementos dos canais de distribuição, além de representar um elevado percentual de participação nos custos logísticos totais. Desse modo, a eficiência dos serviços de transporte depende diretamente de um adequado processo de planejamento em nível estratégico, tático e operacional. O transporte rodoviário, em particular, apresenta em nível operacional, problemas de elevada complexidade como a roteirização e o carregamento de veículos. Durante os últimos 50 anos estes problemas vêm sendo objeto de intensos estudos e desenvolvimentos, porém de forma separada, conduzindo a resultados difíceis de serem implementados nas situações práticas, devido à grande interdependência existente entre roteirização e carregamento de veículos. A resolução integrada destes dois problemas é recente na literatura, o que abre um campo bastante promissor para novos desenvolvimentos. Assim, esta tese tem como objetivo propor uma abordagem integrada de resolução para o problema de roteirização e carregamento de veículos onde, além das restrições de carregamento tridimensionais, as restrições de tempo de ciclo e distribuição de peso nos eixos são consideradas. Este modelo adota uma abordagem aproximativa que combina o uso de heurísticas para construção dos carregamentos com a metaheurística de Busca Tabu para melhoria dos roteiros de entrega. Para execução dos testes computacionais é proposto um conjunto de 12 instâncias que buscam simular situações práticas encontradas nas operações de entrega feitas por empresas de transporte e prestadores de serviços logísticos. A partir desse conjunto de instâncias são construídos cenários que avaliam o uso de diferentes tipos de veículos e os respectivos custos operacionais. Testes complementares realizados com um conjunto de 27 instâncias disponíveis na literatura, demonstram a capacidade do modelo proposto de atingir boas soluções em um tempo de processamento aceitável.
Freight transportation plays a fundamental role in logistics systems, once it enables the product flow between distribution channels elements, besides to represents a high percentage of participation on the total logistics costs. In this way, transport service efficiency depends directly of a suitable process of planning in strategic, tactical and operational level. The road transportation, in particular, shows in operational level high complexity problems as routing and loading of vehicles. During the last 50 years, these problems has been object of deep studies and developments, but in a separate manner, leading to results that are difficult to implement in practical situation due to the interdependence between routing and loading of vehicles. The integrated resolution of these two problems is recent in the literature, what opens a quite promising field for new developments. Thus, this thesis has as objective to propose an integrated resolution approach for the vehicle routing and loading where, besides the three-dimensional loading constraints, constraints, the time cicle and the distribution load over de axles are considered. This model adopts an approximated approach that combines the use of heuristics for loading construction with Tabu Search metaheuristics to improve the delivery routes. For computational tests execution is proposed a 12 instances set that tries to simulate practical situation found in delivery operations made by freight firms and thirty party logistics. From this instance set, it is built scenarios that evaluate the use of different vehicle types and the respectives operational costs. Complementary tests made with a 27 instances set available in literature show the capacity of proposed model to get good solutions in an acceptable computational time.

The continuous growth of traffic demand driven by the brisk increase in number of Internet users and emerging online services creates new challenges for communication networks. The latest advances in Wavelength Division Multiplexing (WDM) technology make it possible to build Transparent Optical Networks (TONs) which are expected to be able to satisfy this rapidly growing capacity demand. Moreover, with the ability of TONs to transparently carry the optical signal from source to destination, electronic processing of the tremendous amount of data can be avoided and optical-to-electrical-to-optical (O/E/O) conversion at intermediate nodes can be eliminated. Consequently, transparent WDM networks consume relatively low power, compared to their electronic-based IP network counterpart. Furthermore, TONs bring also additional benefits in terms of bit rate, signal format, and protocol transparency. However, the absence of O/E/O processing at intermediate nodes in TONs has also some drawbacks. Without regeneration, the quality of the optical signal transmitted from a source to a destination might be degraded due to the effect of physical-layer impairments induced by the transmission through optical fibers and network components. For this reason, routing approaches specifically tailored to account for the effect of physical-layer impairments are needed to avoid setting up connections that don’t satisfy required signal quality at the receiver. Transparency also makes TONs highly vulnerable to deliberate physical-layer attacks. Malicious attacking signals can cause a severe impact on the traffic and for this reason proactive mechanisms, e.g., network design strategies, able to limit their effect are required. Finally, even though energy consumption of transparent WDM networks is lower than in the case of networks processing the traffic at the nodes in the electronic domain, they have the potential to consume even less power. This can be accomplished by targeting the inefficiencies of the current provisioning strategies applied in WDM networks. The work in this thesis addresses the three important aspects mentioned above. In particular, this thesis focuses on routing and wavelength assignment (RWA) strategies specifically devised to target: (i) the lightpath transmission quality, (ii) the network security (i.e., in terms of vulnerability to physical-layer attacks), and (iii) the reduction of the network energy consumption. Our contributions are summarized below. A number of Impairment Constraint Based Routing (ICBR) algorithms have been proposed in the literature to consider physical-layer impairments during the connection provisioning phase. Their objective is to prevent the selection of optical connections (referred to as lightpaths) with poor signal quality. These ICBR approaches always assign each connection request the least impaired lightpath and support only a single threshold of transmission quality, used for all connection requests. However, next generation networks are expected to support a variety of services with disparate requirements for transmission quality. To address this issue, in this thesis we propose an ICBR algorithm supporting differentiation of services at the Bit Error Rate (BER) level, referred to as ICBR-Diff. Our approach takes into account the effect of physical-layer impairments during the connection provisioning phase where various BER thresholds are considered for accepting/blocking connection requests, depending on the signal quality requirements of the connection requests. We tested the proposed ICBR-Diff approach in different network scenarios, including also a fiber heterogeneity. It is shown that it can achieve a significant improvement of network performance in terms of connection blocking, compared to previously published non-differentiated RWA and ICBR algorithms.  Another important challenge to be considered in TONs is their vulnerability to physical-layer attacks. Deliberate attacking signals, e.g., high-power jamming, can cause severe service disruption or even service denial, due to their ability to propagate in the network. Detecting and locating the source of such attacks is difficult, since monitoring must be done in the optical domain, and it is also very expensive. Several attack-aware RWA algorithms have been proposed in the literature to proactively reduce the disruption caused by high-power jamming attacks. However, even with attack-aware network planning mechanisms, the uncontrollable propagation of the attack still remains an issue. To address this problem, we propose the use of power equalizers inside the network nodes in order to limit the propagation of high-power jamming attacks. Because of the high cost of such equipment, we develop a series of heuristics (incl. Greedy Randomized Adaptive Search Procedure (GRASP)) aiming at minimizing the number of power equalizers needed to reduce the network attack vulnerability to a desired level by optimizing the location of the equalizers. Our simulation results show that the equalizer placement obtained by the proposed GRASP approach allows for 50% reduction of the sites with the power equalizers while offering the same level of attack propagation limitation as it is possible to achieve with all nodes having this additional equipment installed. In turn, this potentially yields a significant cost saving.    Energy consumption in TONs has been the target of several studies focusing on the energy-aware and survivable network design problem for both dedicated and shared path protection. However, survivability and energy efficiency in a dynamic provisioning scenario has not been addressed. To fill this gap, in this thesis we focus on the power consumption of survivable WDM network with dynamically provisioned 1:1 dedicated path protected connections. We first investigate the potential energy savings that are achievable by setting all unused protection resources into a lower-power, stand-by state (or sleep mode) during normal network operations. It is shown that in this way the network power consumption can be significantly reduced. Thus, to optimize the energy savings, we propose and evaluate a series of energy-efficient strategies, specifically tailored around the sleep mode functionality. The performance evaluation results reveal the existence of a trade-off between energy saving and connection blocking. Nonetheless, they also show that with the right provisioning strategy it is possible to save a considerable amount of energy with a negligible impact on the connection blocking probability. In order to evaluate the performance of our proposed ICBR-Diff and energy-aware RWA algorithms, we develop two custom-made discrete-event simulators. In addition, the Matlab program of GRASP approach for power equalization placement problem is implemented.

QC 20120508

The industrial gas industry represents a multi-billion dollar global market and provides essential product to manufacturing and service organizations that drive the global economy. In this dissertation, we focus on improving distribution efficiency in the industrial gas industry by addressing the strategic level problem of bulk tank allocation (BTA) while considering the effects of important operational issues. The BTA problem determines the preferred size of bulk tanks to assign to customer sites to minimize recurring gas distribution costs and initial tank installation costs. The BTA problem has a unique structure which includes a resource allocation problem and an underlying vehicle routing problem with split deliveries. In this dissertation, we provide an exact solution approach that solves the BTA problem to optimality and recommends tank allocations, provides a set of delivery routes, and determines delivery amounts to customers on each delivery route within reasonable computational time. The exact solution approach is based on a branch-and-price algorithm that solves problem instances with up to 40 customers in reasonable computational time. Due to the complexity of the problem and the size of industry representative problems, the solution approaches published in the literature rely on heuristics that require a set of potential routes as input. In this research, we investigate and compare three alternative route generation algorithms using data sets from an industry partner. When comparing the routes generation algorithms, a sweep-based heuristic was the preferred heuristic for the data sets evaluated. The existing BTA solution approaches in the literature also assume a single bulk tank can be allocated at each customer site. While this assumption is valid for some customers due to space limitations, other customer sites may have the capability to accommodate multiple tanks. We propose two alternative mathematical models to explore the possibility and potential benefits of allocating multiple tanks at designated customer site that have the capacity to accommodate more than one tank. In a case study with 20 customers, allowing multiple tank allocation yield 13% reduction in total costs. In practice, industrial gas customer demands frequently vary by time period. Thus, it is important to allocate tanks to effectively accommodate time varying demand. Therefore, we develop a bulk tank allocation model for time varying demand (BTATVD) which captures changing demands by period for each customer. Adding this time dimension increases complexity. Therefore, we present three decomposition-based solution approaches. In the first two approaches, the problem is decomposed and a restricted master problem is solved. For the third approach, a two phase periodically restricting heuristic approach is developed. We evaluate the solution approaches using data sets provided by an industrial partner and solve the problem instances with up to 200 customers. The results yield approximately 10% in total savings and 20% in distribution cost savings over a 7 year time horizon. The results of this research provide effective approaches to address a variety of distribution issues faced by the industrial gas industry. The case study results demonstrate the potential improvements for distribution efficiency.
Ph. D.

Si nous en croyons les allegations de leurs dirigeants, dont la presse specialisee se fait l'echo sans toujours beaucoup de discernement, les entreprises de transport routier de marchandises sont toutes no 1 ou en voie de le devenir. Il y a celles qui affirment dominer un metier : elles sont alors leader dans la messagerie, groupes seraient meme les meilleurs en tout | d'autres entreprises cherchent a se differencier : elles assurent alors etre no 1 par leur qualite de service s, leur offre technique ou leur outil informatique. Enfin, celles qui n'ont pu pretendre aux podiums precedents, n'hesitent pas a se declarer leaders sur une zone geographique; zone qui ne s'etend pas du royaume-uni a l'espagne, ni meme de lille a marseille, mais plutot d'aurillac a tuile ou de chateaubriand a redon. Notre recherche s'attache a denouer cet echeveau de declarations et a mettre en lumiere les differentes strategies mises en place par les entreprises francaises pour participer a la competition europeenne. Elle conduit, par une analyse fine du secteur, a s'interroger sur l'existence de reelles strategies europeennes. Mais au-dela d'une analyse des strategies europeennes, notre recherche met en evidence les insuffisances theoriques de l'economie des transports dans le domaine des strategies d'entreprises, et la difficulte d'appliquer les outils des sciences de gestion. Elle se veut la premiere pierre sur laquelle se sedimenteront les apports futurs
Should we believe the allegations of their managers, often echoed withoud much thinking by the press, road haulage carriers are always no 1 or likely to be no 1. Some claim they are leaders in the trade i. E. Leaders in the parcels service, transport of refrigerated goods or bulk tanker. Some even claim they are the best in everything | others try to differentiate from the rest of the crowd. They claim to be the best through the quality of service, their technical competence or their data processing system. Last but not least, those who could not assert they were on the top of the scale, will maintain they are "leaders in the region". The socalled region doesn't stretch from the united kingdom to spain or even from lille to marseille, but from aurillac to tulle and from chateaubriand to redon. In the research we have carried out on the subject, we have tried to sort out the many the research we have carried out on the subject, we have tried to sort out the many assertions and bring out the many strategics set by french firms, in order to play a part in the european competition. Beyond an analysis of the european strategy, we would like to emphasi se the lack of thinking in the field of economics and carriage strategy and how difficult it is to apply the instruments of management. This will be the cornestone on which to build up further contributions

Background: Increasing attention has been paid to preventative health over the past few decades. However because of constraints on consultation time and medical funds general practitioners (GPs) are often unsure which measures are appropriate and when to carry them out. They need to be well informed about the cost-effectiveness and evidence regarding each preventative measure to help their patients make informed choices about what needs to be done. Due to the large number of recommended screening measures general practitioners are often unsure which to prioritise and also forget to carry out all recommended measures. Recommendations for screening in South Africa and research into preventive strategies used by general practitioners are lacking. This research attempts to find out whether the prevention strategies used by general practitioners in private practice in Grahamstown follow recommended guidelines. Methods: To obtain a broad understanding of prevention strategies used by general practitioners in Grahamstown, the following tracer conditions were selected for the study: screening for smoking, breast cancer, cervical cancer, colorectal cancer, hyperlipidaemia, prostate cancer and human immunodeficiency virus (HIV) infection. Research on routine annual health checks was included as these are used by many GPs to screen for tracer conditions. The research was done in 2 parts: 1. Review of the literature to obtain evidence on the recommended prevention strategy for each of the selected tracer conditions and 2. Interviews with GPs to evaluate the prevention strategy they used for each tracer condition. The literature was reviewed for evidence on the following parameters for each tracer condition: burden of the disease prevented; cost-effectiveness of the screening measures; sensitivity and specificity of screening tests; whether the screening measure for and treatment of the tracer condition is acceptable to patients; appropriate duration between repeated screening tests and whether there is effective treatment for the tracer condition. Eleven general practitioners were interviewed on the prevention strategies they use for each of the selected tracer conditions. Transcriptions of the interviews were analysed qualitatively and qualitatively. The prevention strategies used by the general practitioners was then compared to recommended guidelines. Results: Evidence from the literature regarding the burden of and optimal prevention strategy for each tracer condition is reported. Using this evidence an appropriate prevention strategy for each tracer condition is outlined. The prevention strategies used by the GPs for each tracer condition and the routine annual health check is reported from the analysis of the interviews. The results show a wide range of differing strategies used by the GPs, often not following recommendations from research. Discussion: The prevention strategies used by general practitioners for each tracer condition is compared with the recommendations from the literature. Important differences between what are recommended and what general practitioners are doing is discussed. Some general practitioners are practicing largely curative medicine and are not adequately screening their patients. Others are over screening with too many unnecessary tests being done annually as a routine. The interviews reveal that generally GPs do not discuss the potential harms and limitations of screening tests with their patients; do not keep check lists for each patient and do not use registers or recall systems to ensure all screening is done. Conclusion: General practitioners need to ensure their prevention strategies follow recommended guidelines. To do so they can use the routine annual health check or opportunistic case finding and prevention. They need to ensure that routine health checks are targeted to the individual patients’ health risks and avoid doing unnecessary tests. Check lists can help to ensure all screening is done on every patient. While registers and recall systems improve screening rates they are not always possible in busy general practices. Recommended prevention strategies for each of the tracer conditions are made.

Many children experience symptoms of mental health problems and a significant proportion reach clinical thresholds of psychological disorder. It has been argued that the rising incidence of these problems and widespread failure to scale effective treatments for those in need means that prevention and early intervention in the development of emotional and behavioural problems is a public health priority. Child development is shaped by many forces, including for example parenting and peer relationships, this PhD is very specifically interested in the consequences of stress for children’s emotions and behaviour. Although the effects of stress are largely deemed negative, striking individual differences are almost universally observed. In the context of equivalent stressors, some children experience poorer outcomes, some remain relatively unaffected and others appear to experience better outcomes. Understanding what causes these differences is important for advancing our knowledge of the stress process, and is also key to designing services to improve children’s emotions and behaviour. This PhD has four aims. Firstly, it examines the relationship between two routine, school- based stressors and children’s emotional and behavioural outcomes. Secondly, it investigates the role of the cognitive appraisal process in accounting for individual differences in those outcomes. Thirdly, it examines the conditions under which cognitive appraisal operates, both in terms of its role as an organiser of coping efforts and cortisol (a stress hormone) as well as the extent to which children display consistency in their appraisals across contexts. Fourthly, it outlines the implications of the study for policy and practice efforts to improve children’s emotions and behaviour. The empirical study was designed as a prospective longitudinal study, following 66 children over the course of one year in which they experienced two routine, school-based stressors (KS2 exams and transition). Participants were recruited via opportunity sampling methods, and a combination of psychological and physiological data were collected at four time points.

This thesis provides some new insight into children’s strategies and behaviours relating to problem solving. Problem solving is one of the main aims in the renewed mathematics National Curriculum 2014 and has appeared in the Using and Applying strands of previous National Curriculums. A review of the literature provided some analysis of the types of published problem solving activities and attempted to construct a definition of problem solving activities. The literature review also demonstrated this study’s relevance. It is embedded in the fact that at the time of this study there was very little current research on problem solving and in particular practitioner research. This research was conducted through practitioner research in a focus institution. The motivation for this research was, centred round the curiosity as to whether the children (Year Six, aged 10 -11 years old) in the focus institution could apply their mathematics to problem solving activities. There was some concern that these children were learning mathematics in such a way as to pass examinations and were not appreciating the subject. A case study approach was adopted using in-depth observations in one focus institution. The observations of a sample of Year Six children engaged in mathematical problem solving activities generated rich data in the form of audio, video recordings, field notes and work samples. The data was analysed using the method of thematic analysis utilising Nvivo 10 to code the data. These codes were further condensed to final overarching themes. Further discussion of the data shows both mathematical and non-mathematical overarching themes. These themes are discussed in more depth within this study. It is hoped that this study provides some new insights into children’s strategies and behaviours relating to problem solving in mathematics.

Il lavoro di ricerca svolto riguarda la realizzazione di strategie di routing innovative per servizi real-time session-based nell’evoluzione verso architetture full-IP. Esso si inquadra nell’ambito dell’evoluzione dei modelli di interconnessione e di platform enablement per un Operatore di Rete, considerando il punto di vista e l’approccio operativo del carrier internazionale Telecom Italia Sparkle (TIS). TIS al momento utilizza una suite software (iXtools) al fine di eseguire il Routing & Pricing (R&P) del servizio voce. Ciò implica vari processi volti ad ottimizzare il ritorno economico del carrier sulla base degli accordi commerciali wholesale stipulati, di aspetti tecnici di rete (ad esempio la capacità disponibile), della qualità del servizio richiesta dal cliente e del traffico previsto per numerose destinazioni in tutto il mondo. In particolare, nel presente lavoro si considera uno scenario all-IP, in cui vari servizi possano essere forniti tramite un'unica rete dati IP, piuttosto che da molteplici reti separate -- una per telefonia tradizionale, una per traffico dati IP, una per TV, ecc. Tale scenario è molto probabile data la sempre maggiore convergenza delle reti di accesso di prossima generazione (Next Generation Access Networks, NGAN), fisse e mobili, e della sempre maggiore offerta di servizi forniti tramite protocollo IP (ad es. VoIP, instant messaging, video streaming / on-demand, ecc). In un tale scenario è però richiesta un’evoluzione dei processi, delle soluzioni tecniche e commerciali al fine di poter fornire servizi con adeguate qualità. La presente tesi di dottorato si concentra quindi sulla possibilità di realizzare nuovi modelli di business basati su soluzioni tecniche / commerciali che presuppongano una differenziazione di qualità (QoS, Quality of Service) del traffico IP. In particolare, verrà proposta una possibile evoluzione del modello software adottato per il servizio voce (iXtools) verso un contesto all-IP multi-service, e un modello software basato su un criterio di routing innovativo (massimizzazione del margine operativo piuttosto che minimizzazione del costo).

Product innovation is a key driver of any company’s growth. The biggest challenge in managing product innovation is in determining the most promising new product development (NPD) projects from the many ideas generated, known as portfolio management. In practice, NPD portfolio management still bears some problematic issues, including focusing mainly on portfolio selection rather than managing the entire process, the vague links between the process and business strategy, and a lack of formal process. Therefore, a study that looks at NPD portfolio management through different perspectives is required. NPD portfolio management deals with dynamic decision-making processes, involving not only selection decisions, but also decisions to delay, continue or even terminate projects. To understand this integrative process, a systematic literature review that explored four knowledge domains, i.e., NPD portfolio management, decision- making, strategy and organisational routines, was carried out. It involved 40 articles published from 1981-2012. The review focused on revealing how decision-making processes in NPD portfolio management are conducted and how they relate to the strategy process and organisational routines. The key findings show that decisions in the NPD portfolio management process are made through interaction between cognitive and political factors, overlooking the organisational factors in the process. Furthermore, the extant literature does not explicitly explain how to link the NPD portfolio management process to the strategy process. Also, the findings indicate that the concept of organisational routines had not been used when investigating NPD portfolio management. These are the research gaps that led to the three research questions: 1) How are organisational factors involved with the cognitive and political factors in the decision-making processes in NPD portfolio management?; 2) How do the decision-making processes in NPD portfolio management link to the business strategy?; and 3) To what extent are organisational routines related to the decision-making processes in NPD portfolio management?

Cette thèse s’inscrit dans la perspective d’un diagnostic stratégique du secteur de Transport Routier Interurbain des Voyageurs (TRIV) en Afrique de l’Ouest (Cas du Burkina Faso, du Mali et du Niger).L’organisation du transport et le fonctionnement des entreprises dudit secteur à l’aune de la mondialisation et de la modernisation laissent encore à désirer. Nombreuses sont les difficultés recensées à divers niveaux du système entravant ainsi le développement économique du secteur.Pour l’Afrique de l’Ouest, de nombreuses études et recherches ont déjà été réalisées sur le système de transport urbain et sur le transport des marchandises avec diagnostics et préconisations . Cependant le sous-secteur du TRIV a aussi son importance et il convient de le prendre en compte dans le schéma d’intégration sous régionale en Afrique. Notre recherche démontre que l’analyse du TRIV ne doit pas se limiter à ses aspects réglementaires et institutionnels et qu’elle doit intégrer les entreprises comme éléments clés du développement du secteur. Celles-ci sont désormais confrontées au défi de la concurrence sur les marchés tant intérieurs que sous-régionaux du transport des voyageurs. La modernisation du secteur et son développement ultérieur impliquent des adaptations des entreprises artisanales, des changements dans l’organisation et les conditions de fonctionnement de cette activité.Notre démarche aborde dans un premier temps, la configuration actuelle du marché de TRIV. L’analyse met en évidence l’indispensable complémentarité de l’offre des sociétés de transport et des artisans transporteurs. A partir de ce constat, des modèles de stratégies potentielles sont élaborés pour les entreprises contraintes à la compétitivité.Cependant, compte tenu de l’organisation du marché de TRIV au Niger, de la multiplicité des entreprises et de l’absence des données, nous avons défini des groupes contrastés d’entreprises, le regroupement se faisant à partir des caractéristiques techniques, organisationnelles (types de véhicules utilisés, organisation des services) et géographique (lignes desservies).Cette approche nous a permis de mettre en lumière les spécificités des maillons du marché mais aussi les grands déséquilibres existants en matière de desserte dans les principales zones. A travers les modèles de stratégies développés, notre ambition est de donner un cadre de référence aux entreprises à partir duquel et compte tenu de leurs ressources internes, elles organiseront leur stratégie. Ces entreprises devraient pouvoir y parvenir dans le cadre d’une politique publique des transports prenant en compte les attentes des principaux acteurs
This thesis is registered in the perspective of a strategic diagnosis of the Transport sector Intercity Road of travellers (TRIV) in West Africa (case of Burkina Faso, Mali and Niger). The transport organization and the functioning of enterprises of the sector to the yardstick of globalization and the modernization is still inadequate. There are many difficulties identified at various levels of the system thus hindering the economic development of the sector. For West Africa, many studies and research have already been carried out on the system of urban transport and on the transport of goods with diagnostics and recommendations . However, the sub-sector of TRIV also has its importance and it should be taken into account in the schema of sub-regional integration in Africa. Our research shows that the analysis of TRIV must not be limited to its aspects regulatory and institutional and that it must integrate the companies as the key elements of the development of the sector. These are now faced the challenge of competition on the markets both the domestic that sub-regional passenger transport. The modernization of the sector and its subsequent development involve adjustments of craft businesses, changes in the organization and the conditions of operation of this activity. Our approach addresses in the first time, the current configuration of the market of TRIV The analysis highlights the indispensable complementarity of the offer of transport companies and craftsmen carriers. From this finding, models of potential strategies are developed for firms forced to competitiveness. However, in light of the organization of the market of TRIV in Niger, of the multiplicity of enterprises and absence of data, we defined groups contrasting of enterprises, the consolidation at from the technical characteristics, organizational (types of vehicles used, organization of the services) and the geographical (lines served). This approach has allowed us to highlight the specificities of links in the market but also the major imbalances existing in the field of service in the main areas. Through the models of strategies developed, our ambition is to give a reference framework for companies from which and taking into account their internal resources, they organize their strategy. These companies should be able to achieve in the framework of a public policy of transport taking into account the expectations of key actors

L’objet de notre recherche est double : comprendre le phénomène de fabrique d’une compétence organisationnelle stratégique induite par les usages des TI, d’une part, et aller au-delà des modèles existants d’analyse des impacts des TI en intégrant une approche multidimensionnelle, d’autre part. Nous avons privilégié une approche empirique qui a débuté par une étude de cas pilote qui nous a permis de délimiter un cadre théorique de manière abductive, par un aller-retour constant entre le terrain et les construits théoriques existants. Le cadre conceptuel se veut une synthèse des différents courants RBV intégrant le concept d’apprentissage organisationnel. Les résultats d’une étude multicas soulignent le caractère diffus et partiellement intentionnel d’un processus requérant l’interaction de ressources complémentaires fortement dépendantes du passé et aboutissant à l’amélioration de l‘efficience des routines et de la capacité dynamique d’apprentissage. Nous proposons une modélisation du processus et nous discutons des concepts significatifs quant à l'étude d'un tel phénomène
Our research object is twofold: understand a strategic organizational competences bulding using IT, on the one hand, and go beyond the existing analysis of impacts of the IT models, integrating a multidimensional approach, on the other hand. We privileged an empirical approach beginning with a pilot case study that allowed us to define a theoretical framework of an abductive way, by a constant back and forth between the field and the theoretical existing constructs. The conceptual framework is a synthesis of the various RBV strands integrating the concept of organizational learning. The results of a multicase study underline the diffused and partially intentional character of a process, requiring interaction of additional resources highly dependent from the past, and leading to improve efficiency of the routines and dynamic adaptability. We propose a design of the process and discuss significant concepts for the study of this phenomenon

Nous présentons dans cette thèse de nouveaux protocoles de routage capables de prendre en compte des aspects stratégiques lorsqu’il s’agit de choisir le chemin à emprunter et ce à l’échelle du réseau de communication Internet. Le point de vue adopté dans cette étude est que les nouvelles architectures de routage donnent aux réseaux et aux applications une plus grande diversité de chemins, ce qui leur permet de choisir plus rationnellement leur stratégie lorsqu'ils décident le chemin à suivre pour transférer leur trafic, en tenant compte des coûts opérationnels ainsi que des objectifs de performance. Nous présentons des comportements améliorés au noyau décisionnel de trois protocoles de routage, le protocole BGP (Border Gateway Protocol), le protocole LISP (Locator / Identifier Separation Protocol) et, dans une moindre mesure, le protocole MPTCP (Multipath TCP). Pour chaque cadre protocolaire, nous présentons comment les stratégies de routage peuvent être déterminées, sélectionnées et réellement exploitées par des systèmes réels, en appliquant également les concepts de la théorie des jeux non coopératifs, en évaluant l’impact des solutions de routage en termes de coûts opérationnels et de performances réseau. La thèse adopte une méthodologie expérimentale permettant de tester et d'évaluer les propositions via des simulations réalistes et la mise en œuvre et l'observation réelles de systèmes réels. La plupart des résultats sont reproductibles grâce à la publication du code source
We present in this thesis novel routing protocols able to take into consideration strategic aspects when deciding which path among many to take, and that at the Internet communication network scale. The standpoint adopted in this study is that novel routing architectures are exposing a higher path diversity to networks and applications so that networks and applications can be made capable to more intelligently select their strategy when selecting toward which path to forward their traffic, taking into consideration operational costs as well as performance goals. We present enhanced behaviors to the decision-making core of three routing protocols, the Border Gateway Protocol (BGP), the Locator/Identifier Separation Protocol (LISP) and, at a minor extent, the Multipath TCP (MPTCP) protocol. For each protocol framework we present how routing strategies can be computed, selected and actually operated by real systems, also applying concepts from non-cooperative game theory, evaluating the impact of the routing solutions in terms of operational costs and network performance. The thesis adopts an experimental methodology willing to experiment and evaluate proposals via realistic simulations or actual implementation and observation of real systems. Most of the results are made reproducible by open sourcing the corresponding code

Submitted by Fernanda Ciolfi (fernanda.ciolfi@puc-campinas.edu.br) on 2016-08-16T18:29:14Z No. of bitstreams: 1 Juliano Silva Mar?al.pdf: 14418180 bytes, checksum: e94d4d5adc61aeda0c174d60cabfa216 (MD5)
Made available in DSpace on 2016-08-16T18:29:14Z (GMT). No. of bitstreams: 1 Juliano Silva Mar?al.pdf: 14418180 bytes, checksum: e94d4d5adc61aeda0c174d60cabfa216 (MD5) Previous issue date: 2016-06-27
Pontif?cia Universidade Cat?lica de Campinas ? PUC Campinas
In the current technological environment from the point of view of optical transmission, multiplexing technologies for wavelength division (Wavelength Oivision Multiplexing - WOM) working with fixed 50 GHz grid will not support the existing demand for the next 10 years. This scarcity occurs due to several reasons: channels with fixed width of 50 GHz, limitation of 80 optical channels per link, maximum transmission capacity of 100 Gb / s per channel. In search of viable forward solutions to this paradigm that presents technology proposal comes known as Optical Networks Elastic (Elastic Optical Network - EON), a technology that enables optical channels with bandwidths of 3,125, 6,250, 12,500, 25 and 50 GHz transmission capability of rates supported by the WOM yet rates of 200 Gb / s, 400 Gb / s and 1 Tb / s, and can be implemented on the same optical infrastructure WOM already existing thus corresponding to a highly cost less if compared to deployment of new networks. The efficiency of this proposed new technology is mainly in routing algorithms and spectral assignment (Routing and Spectrum Assignment - RSA) aimed at maximizing network availability of resources by reducing the likelihood of blocking. The use of RSAs on the EONS networks fragmentation results in the generation of reducing the availability of network resources. Within this scenario, the present work-studies the feasibility of defragmentation use based on the relocation of the link to submit further fragmentation indexo This paper studies the adoption of two indices: consecutiveness index and more FSUs index busy, both indexes allow the selection of the link to be defragmented. The results of this study were obtained from the development of version 5 of the simulator Elastic Optical Network Simulator (EONSim). To obtain the results, different transmission rates were evenly distributed for each traffic load between 45 and 100 Erlang (E), the First-Fit RSA (FF) was adopted for ali the simulations to reduce the defragmentation processing were performed from an R number of released connections (R = 10, R = 50 and R = 100). For the scenario using the consecutiveness index gain of up to 44 was measured to 55 E and average gain of 15 compared to results without defragmentation scenario for the use of higher index number of occupied FSUs, gain was observed 26 to 55 E and average gain of 10. From the results it can be concluded that the adoption of defragmentation strategies for eons networks are likely to be used since they have decreased blocking probability and increase the availability of network resources.
Na atual conjuntura tecnol?gica do ponto de vista de transmiss?es ?pticas, as tecnologias de multiplexa??o por divis?o de comprimento de onda (Wavelength Oivision Multiplexing - WOM) que trabalham com grade fixa de 50 GHz n?o ir?o comportar a demanda existente para os pr?ximos 10 anos. Esta escassez ocorre por v?rios motivos: canais com largura fixa de 50 GHz, limita??o de 80 canais ?pticos por enlace, capacidade m?xima de transmiss?o de 100 Gb/s por canal. Em busca de solu??es vi?veis frente a este paradigma que se apresenta, surge a proposta da tecnologia conhecida como Redes ?pticas El?sticas (Elastic Optical Network- EON), uma tecnologia que permite canais ?pticos com larguras de banda de 3.125, 6.250, 12.500, 25 e 50 GHz, capacidade de transmiss?o das taxas suportadas pela tecnologia WDM e ainda taxas de 200 Gb/s, 400 Gb/s e 1 Tb/s, e podem ser implantadas sobre a mesma infraestrutura ?ptica WDM j? existente correspondendo assim a um custo altamente inferior se comparado a implanta??o de novas redes. A efici?ncia desta nova proposta de tecnologia est? principalmente nos algoritmos de roteamento e atribui??o espectral (Routing and Spectrum Assignment - RSA) que visam a maximiza??o dos recursos de disponibilidade da rede atrav?s da diminui??o da probabilidade de bloqueio. O uso do RSA resulta na gera??o de fragmenta??o diminuindo a disponibilidade de recursos da rede. Dentro deste cen?rio, o presente trabalho estuda a viabilidade do uso de desfragmenta??o baseada na realoca??o sobre o enlace que apresentar maior ?ndice de fragmenta??o e analisa a ado??o de dois ?ndices: ?ndice de consecutividade e ?ndice de maior n?mero de FSUs ocupados, para a sele??o do enlace a ser desfragmentado. Os resultados deste estudo foram obtidos a partir do desenvolvimento da vers?o 5 do simulador Elastic Op tica I Network Simulator (EONSim). Para a obten??o dos resultados, diferentes taxas de transmiss?o foram distribu?das uniformemente para cada uma carga de tr?fego entre 45 e 100 erlang (E), o RSA First-Fit (FF) foi adotado para todas as simula??es, para diminuir o processamento as desfragmenta??es foram executadas a partir de um n?mero R de conex?es liberadas (R= 10, R= 50 e R= 100). Para o cen?rio utilizando o ?ndice de consecutividade, foi aferido ganho de at? 44 para 55 E e ganho m?dio de 15 quando comparado aos resultados do cen?rio sem desfragmenta??o, para o uso do ?ndice de maior n?mero de FSUs ocupados, foi observado ganho de 26 para 55 E com ganho m?dio de 10. A partir dos resultados obtidos ? poss?vel concluir que a ado??o de estrat?gias de desfragmenta??o para redes EONs s?o pass?veis de serem utilizadas pois apresentam diminui??o da probabilidade de bloqueio e aumento da disponibilidade dos recursos da rede