[pt] No cenário atual da economia mundial, é essencial aumentar a integração entre os diferentes atores da cadeia de suprimentos das empresas, reduzindo custos operacionais e melhorando a eficiência. O roteamento de navios é parte imprescindível dessa integração no comércio marítimo global, sendo objeto de estudo de muitos autores. Neste trabalho, apresentamos diferentes metodologias para resolver variantes do Problema de Roteamento Marítimo com Estoques. Esse problema envolve um grande número de variáveis e é computacionalmente complexo de ser resolvido. Nossa principal motivação é resolver um caso real de roteamento de navios de uma grande empresa do setor de Óleo e Gás, obtendo soluções de alta qualidade em tempos computacionais plausíveis e melhorando os resultados atuais da empresa. Todas as metodologias desenvolvidas são baseadas em uma combinação de uma meta-heurística com um modelo matemático de programação linear. Uma das principais diferenças entre as metodologias está no modelo matemático para resolver o problema de estoque, onde testamos abordagens de tempo discreto e tempo contínuo. As outras diferenças dizem respeito ao número de produtos avaliados (único ou múltiplos produtos) e à meta-heurística usada (heurística de busca local com um fator de probabilidade de Simulated Annealing ou Hybrid Variable Neighborhood Search). Para a metodologia que utiliza um modelo de tempo discreto, os resultados são satisfatórios, com violações baixas e pontuais do estoque em um tempo computacional aceitável. Para a metodologia que utiliza um modelo de tempo contínuo, os resultados são ainda melhores, uma vez que, em reduzido tempo computacional, as violações de estoque permanecem baixas ou inexistentes, dependendo do cenário avaliado e da meta-heurística utilizada. Os resultados obtidos neste trabalho são notáveis e permitem sua aplicação prática em casos reais. / [en] In the current scenario of the world economy, it is essential to increase the integration between the different players in the companies supply chain, reducing operational costs, and improving efficiency. Ship routing is a substantial part of this integration regarding global maritime commerce, being the object of study by many authors. In this work, we present different methodologies to solve variants of the Maritime Inventory Routing Problem. This problem involves a large number of variables and is a computationally complex problem to solve. Our primary motivation is to solve a ship routing real case of a large company in the Oil and Gas sector, achieving high-quality solutions in plausible processing times and improving companies current results. All developed methodologies are based on a metaheuristic combination with a linear mathematical model. One of the main differences between the methodologies lies in the mathematical model to solve the inventory problem, where we tested discrete-time and continuous-time approaches. Other differences concern the number of evaluated products (single or multi-product) and the metaheuristic used (local search heuristics with a Simulated Annealing probability factor or Hybrid Variable Neighborhood Search). For the methodology using the discretetime model, the results are satisfactory, with low and punctual inventory violations in an acceptable computational time. For the methodology using the continuous-time model, the results are better once, in reduced computational time, inventory violations remain low or non-existent, depending on the scenario evaluated and the metaheuristic used. The results obtained in this work are remarkable and allow its practical application for real cases.

A case study for this project is performed at Autoliv in Thailand the company uses a lean production flow approach. This manufacturing plant operates on the level of Industry 3.0, which automates processes using information technology. The case study scenario in manufacturing plants that runs in industrial automation 3.0 has some problems in material handling under the logistics division. By implementing AGV (Automated Guided Vehicle) with help of simulation, the time reduction factor through route and time optimization can be processed and displayed. This will have a direct impact on increasing the material handling efficiency in the production plant. The simulation used for AGV in plant layout is Discrete Event Simulation (DES), which divides each event according to its time. Siemens’s Tecnomatix Plant Simulation software is used as a software. This software handles complex production systems and provides control methods. In this thesis work, the entire plant is implemented in the simulated environment based on the plant layout as per dimensions. Then the AGV routing is done from source to destination. The stations are made as per the requirements between the source and the destination for loading from/ unloading to AGV. The processing time of these stations is given as inputs and the simulation is run for a shift to get the throughput. The specification of the AGV such as speed and dimensions given in the simulated environment is taken from the case study of AGV. A total of 55 AGV models’ are studied and 40 of them are selected for this particular plant layout, they are selected based on their features along with the throughput of units transferred from source to destination. The parameters of the AGV are based on the case study of AGV models. The unit throughput acquired in the simulated environment by the AGV is 20% to 22.5% more efficient than manual material handling.

The planning of snow removal routes is complicated by the fact that the amount it snows, and thus the amount of resources, that is, vehicles, needed to clear it, varies from year to year. This variation has created a demand for a way to quickly generate efficient snow removal plans that take the resources that are available into account. In this report we describe the development of an ad hoc heuristic algorithm that improves already existing feasible solutions to the snow removal problem. It accomplishes this by reassigning tasks from the vehicles with the longest tours to those with the shortest tours, followed by reordering their tasks to ensure that the solution remains feasible. This algorithm is meant to be implemented in a larger piece of software and it is tested on a set of pre-generated solutions for a given network and number of vehicles, including the best known ones. Over half of the previously best known solutions were improved by this algorithm.

As the older population grows larger there is a growing need to provide health care at home. This services are generally done without operational research. As more people will require home care there will be a need to increase the efficiency of the service while keeping the quality high. The purpose of this thesis is to investigate how we can use operation research in home care as well as define how we can model the quality and use those quality parameters in order to offer the best possible service. The model uses VRP with Time windows in order to schedule the routes and incorporates service requirements at the customers. A solution is obtained by first constructing an initial solution that fulfills the duration constraint. Then it uses a local search with a dynamic insertion heuristic to improve on the solution. Tabu search is used as a meta-heuristic to prevent the solution the get stuck in a local minima. The solver is used in order to optimize the quality parameters. The result obtained can be used to help home care providers to determine the level of quality they can supply with a limited budget / När den äldre befolkningen blir större växer behovet av att tillhandahålla vård i hemmet. Denna tjänst använder i allmänhet inte systemteori. Eftersom fler människor kommer att behöva hemtjänst kommer det att finnas behov av att öka effektiviteten samtidigt som kvaliteten hålls hög. Syftet med denna avhandling är att undersöka hur vi kan använda systemteori och optimering inom hemtjänst samt definiera hur vi kan modellera kvaliteten och använda dessa kvalitetsparametrar för att erbjuda bästa möjliga service. Modellen använder VRP med Time windows för att schemalägga rutterna och inkorporerar servicebehov hos kunderna. En lösning erhålles genom att först bygga en initial lösning. Sedan använder den en lokal sökning med en dynamisk heuristisk för att förbättra lösningen. Tabu search används som en meta-heuristik för att förhindra att lösningen fastnar i lokala minima. Algoritmen används för att optimera kvalitetsparametrarna. Resultatet kan användas för att hjälpa leverantörer av hemtjänst att bestämma vilken kvalitetsnivå de kan leverera med en begränsad budget

Wireless Sensor Networks (WSNs) experiences several technical challenges such as limited energy, short transmission range, limited storage capacities, and limited computational capabilities. Moreover, the sensor nodes are deployed randomly and massively over an inaccessible or hostile region. Hence, WSNs are vulnerable to adversaries and are usually operated in a dynamic and unreliable environment. Animal tracking using wireless sensors is one such application of WSN where power management plays a vital role. In this paper, an energy-efficient hybrid routing method is proposed that divides the whole network into smaller regions based on sensor location and chooses the routing scheme accordingly. The sensor network consists of a base station (BS) located at a distant place outside the network, and a relay node is placed inside the network for direct communications from nodes nearer to it. The nodes are further divided into two categories based on the supplied energy; such that the ones located far away from BS and relay have higher energy than the nodes nearer to them. The network performance of the proposed method is compared with protocols like LEACH, SEP, and SNRP, considering parameters like stability period, throughput and energy consumption. Simulation result shows that the proposed method outperforms other methods with better network performance.

With the emergence of various applications that have different Quality of Service (QoS) requirements, the capability of a network to support QoS becomes more and more important and necessary. This dissertation explores QoS in Cognitive Packet Networks (CPN) by using adaptive routing, flow and congestion control. We present a detailed description and analysis of our proposed routing algorithms based on single and multiple QoS constraints. An online estimation of packet loss rate over a path is introduced. We implement and evaluate the adaptive routing scheme in an experimental CPN test-bed. Our experiments support our claims that the users can achieve their desired best-effort QoS through this routing scheme. We also propose a QoS-based flow and congestion control scheme that is built in the transport layer and specially designed to work with CPN to support users' QoS while remaining friendly to TCP. Theoretical models and experimental analysis are presented. Finally we experimentally demonstrate that the proposed flow and congestion control scheme can effectively control the input flows, react to the congestion and work with our proposed adaptive routing scheme to achieve users' QoS.

Mobile Ad hoc NETworks (MANETs) have attracted great research interest in recent years. Among many issues, lack of motivation for participating nodes to collaborate forms a major obstacle to the adoption of MANETs. Many contemporary collaboration enforcement techniques employ reputation mechanisms for nodes to avoid and penalize malicious participants. Reputation information is propagated among participants and updated based on complicated trust relationships to thwart false accusation of benign nodes. The aforementioned strategy suffers from low scalability and is likely to be exploited by adversaries. To address these problems, we first propose a finite state model. With this technique, no reputation information is propagated in the network and malicious nodes cannot cause false penalty to benign hosts. Misbehaving node detection is performed on-demand; and malicious node punishment and avoidance are accomplished by only maintaining reputation information within neighboring nodes. This scheme, however, requires that each node equip with a tamper-proof hardware. In the second technique, no such restriction applies. Participating nodes classify their one-hop neighbors through direct observation and misbehaving nodes are penalized within their localities. Data packets are dynamically rerouted to circumvent selfish nodes. In both schemes, overall network performance is greatly enhanced. Our approach significantly simplifies the collaboration enforcement process, incurs low overhead, and is robust against various malicious behaviors. Simulation results based on different system configurations indicate that the proposed technique can significantly improve network performance with very low communication cost.

In recent years, the development of a large variety of mobile computing devices has led to wide scale deployment and use of wireless ad hoc and sensor networks. Wireless Sensor Networks consist of battery powered, tiny and cheap "motes", having sensing and wireless communication capabilities. Although wireless motes have limited battery power, communication and computation capabilities, the range of their application is vast. In the first part of the dissertation, we have addressed the specific application of Biomedical Sensor Networks. To solve the problem of data routing in these networks, we have proposed the Adaptive Least Temperature Routing (ALTR) algorithm that reduces the average temperature rise of the nodes in the in-vivo network while routing data efficiently. For delay sensitive biomedical applications, we proposed the Hotspot Preventing Routing (HPR) algorithm which avoids the formation of hotspots (regions having very high temperature) in the network. HPR forwards the packets using the shortest path, bypassing the regions of high temperature and thus significantly reduces the average packet delivery delay, making it suitable for real-time applications of in-vivo networks. We also proposed another routing algorithm suitable for being used in a network of id-less biomedical sensor nodes, namely Routing Algorithm for networks of homogeneous and Id-less biomedical sensor Nodes (RAIN). Finally we developed Biocomm, a cross-layer MAC and Routing protocol co-design for Biomedical Sensor Networks, which optimizes the overall performance of an in-vivo network through cross-layer interactions. We performed extensive simulations to show that the proposed Biocomm protocol performs much better than the other existing MAC and Routing protocols in terms of preventing the formation of hotspots, reducing energy consumption of nodes and preventing network congestion when used in an in-vivo network. In the second part of the dissertation, we have addressed the problems of habitat-monitoring sensor networks, broadcast algorithms for sensor networks and the congestion problem in sensor networks as well as one non-sensor network application, namely, on-chip communication networks. Specifically, we have proposed a variation of HPR algorithm, called Hotspot Preventing Adaptive Routing (HPAR) algorithm, for efficient data routing in Networks On-Chip catering to their specific hotspot prevention issues. A protocol similar to ALTR has been shown to perform well in a sensor network deployed for habitat monitoring. We developed a reliable, low overhead broadcast algorithm for sensor networks namely Topology Adaptive Gossip (TAG) algorithm. To reduce the congestion problem in Wireless Sensor Networks, we proposed a tunable cross-layer Congestion Reducing Medium Access Control (CRMAC) protocol that utilizes buffer status information from the Network layer to give prioritized medium access to congested nodes in the MAC layer and thus preventing congestion and packet drops. CRMAC can also be easily tuned to satisfy different application-specific performance requirements. With the help of extensive simulation results we have shown how CRMAC can be adapted to perform well in different applications of Sensor Network like Emergency Situation that requires a high network throughput and low packet delivery latency or Long-term Monitoring application requiring energy conservation.

Optical networking, employing wavelength division multiplexing (WDM), is seen as the technology of the future for the Internet. This dissertation investigates several important problems affecting optical circuit switching (OCS) and optical burst switching (OBS) networks. Novel algorithms and new approaches to improve the performance of these networks through effective routing and channel scheduling are presented. Extensive simulations and analytical modeling have both been used to evaluate the effectiveness of the proposed algorithms in achieving lower blocking probability, better fairness as well as faster switching. The simulation tests were performed over a variety of optical network topologies including the ring and mesh topologies, the U.S. Long-Haul topology, the Abilene high-speed optical network used in Internet 2, the Toronto Metropolitan topology and the European Optical topology. Optical routing protocols previously published in the literature have largely ignored the noise and timing jitter accumulation caused by cascading several wavelength conversions along the lightpath of the data burst. This dissertation has identified and evaluated a new constraint, called the wavelength conversion cascading constraint. According to this constraint, the deployment of wavelength converters in future optical networks will be constrained by a bound on the number of wavelength conversions that a signal can go through when it is switched all-optically from the source to the destination. Extensive simulation results have conclusively demonstrated that the presence of this constraint causes significant performance deterioration in existing routing and wavelength assignment (RWA) algorithms. Higher blocking probability and/or worse fairness have been observed for existing RWA algorithms when the cascading constraint is not ignored. To counteract the negative side effect of the cascading constraint, two constraint-aware routing algorithms are proposed for OCS networks: the desirable greedy algorithm and the weighted adaptive algorithm. The two algorithms perform source routing using link connectivity and the global state information of each wavelength. Extensive comparative simulation results have illustrated that by limiting the negative cascading impact to the minimum extent practicable, the proposed approaches can dramatically decrease the blocking probability for a variety of optical network topologies. The dissertation has developed a suite of three fairness-improving adaptive routing algorithms in OBS networks. The adaptive routing schemes consider the transient link congestion at the moment when bursts arrive and use this information to reduce the overall burst loss probability. The proposed schemes also resolve the intrinsic unfairness defect of existing popular signaling protocols. The extensive simulation results have shown that the proposed schemes generally outperform the popular shortest path routing algorithm and the improvement could be substantial. A two-dimensional Markov chain analytical model has also been developed and used to analyze the burst loss probabilities for symmetrical ring networks. The accuracy of the model has been validated by simulation. Effective proactive routing and preemptive channel scheduling have also been proposed to address the conversion cascading constraint in OBS environments. The proactive routing adapts the fairness-improving adaptive routing mentioned earlier to the environment of cascaded wavelength conversions. On the other hand, the preemptive channel scheduling approach uses a dynamic priority for each burst based on the constraint threshold and the current number of performed wavelength conversions. Empirical results have proved that when the cascading constraint is present, both approaches would not only decrease the burst loss rates greatly, but also improve the transmission fairness among bursts with different hop counts to a large extent.

Traffic polarization in networks refers to the phenomenon where traffic tends to concentrate along specific routes or edges when doing multipath routing, leading to imbalanced flow patterns. This spatial distribution of traffic can result in congested and overburdened links, while other routes remain underutilized. Such imbalanced traffic distribution can lead to network bottlenecks, reduced throughput, and compromised Quality of Service for critical applications. These issues emphasize the urgent necessity to address traffic polarization and its detrimental impact on network efficiency and resilience. In this master thesis, we introduce a novel approach to tackle the problem of hash polarization and evaluate the performance of our implementation. Perhaps influenced by the RFC 2992 document, previous works always use the whole value of the hash result to do the multipath routing decisions, and therefore try to mitigate the polarization problem by developing more functions or reusing them. However, we investigate if the polarizion issue can be solved by utilizing different parts of the hash result. In this case, the most critical problem would be how to choose the bits of the hash result for the multipath routing decisions. Unfortunately, during the experiment, we discovered that the optimal performance design is influenced by many factors in the network topology and traffic demand pattern, making it difficult to summarize a universal law. Nevertheless, our research has proposed a mechanism called “bit-awareness”, which can significantly alleviate the problem of selecting overlapping bits, and hence addresses the polarization issue. / Trafikpolarisering i nätverk hänvisar till fenomenet där trafik tenderar att koncentreras längs specifika rutter eller kanter när man gör flervägsdirigering, vilket leder till obalanserade flödesmönster. Denna rumsliga fördelning av trafik kan resultera i överbelastade och överbelastade länkar, medan andra vägar förblir underutnyttjade. Sådan obalanserad trafikdistribution kan leda till nätverksflaskhalsar, minskad genomströmning och försämrad tjänstekvalitet för kritiska applikationer. Dessa frågor betonar det akuta behovet av att ta itu med trafikpolarisering och dess skadliga inverkan på nätverkseffektivitet och motståndskraft. I denna masteruppsats introducerar vi ett nytt tillvägagångssätt för att tackla problemet med hashpolarisering och utvärdera prestandan för vår implementering. Kanske påverkat av RFC 2992-dokumentet, skulle tidigare arbeten använda hela värdet av hashresultatet för att fatta beslut om flervägsdirigering och därför försöka mildra polariseringsproblemet genom att utveckla fler funktioner eller återanvända dem. Vi undrar dock om problemet kan lösas genom att använda olika delar av hashresultatet. I det här fallet skulle det mest avgörande problemet vara hur man väljer bitarna i hashresultatet för besluten om flervägsdirigering. Tyvärr upptäckte vi under experimentet att den optimala prestandadesignen påverkas av många faktorer i nätverkstopologin och trafikefterfrågan, vilket gör det svårt att sammanfatta en universell lag. Ändå har vår forskning föreslagit en mekanism som kallas ”bit-medvetenhet”, som avsevärt kan lindra problemet med att välja överlappande bitar, och därmed adresserar polariseringsfrågan.