Exact solutions to the short sea shipping distribution problem

Short sea shipping has several advantages over other means of transportation, recognized by EU members. The maritime transportation could be dealt like a combination of two well-known problems: the container stowage problem and routing planning problem. The integration of these two well-known problems results in a new problem CSSRP (Container stowage and ship routing problem) that is also an hard combinatorial optimization problem. The aim of this work is to solve the CSSRP using a mixed integer programming model. It is proved that regardless the complexity of this problem, optimal solutions could be achieved in a reduced computational time. For testing the mathematical model some problems based on real data were generated and a sensibility analysis was performed.

Vehicle Routing Problems that Minimize the Completion Time: Heuristics, Worst-Case Analyses, and Computational Results

In the standard Vehicle Routing Problem (VRP), we route a fleet of vehicles to deliver the demands of all customers such that the total distance traveled by the fleet is minimized. In this dissertation, we study variants of the VRP that minimize the completion time, i.e., we minimize the distance of the longest route. We call it the min-max objective function. In applications such as disaster relief efforts and military operations, the objective is often to finish the delivery or the task as soon as possible, not to plan routes with the minimum total distance. Even in commercial package delivery nowadays, companies are investing in new technologies to speed up delivery instead of focusing merely on the min-sum objective. In this dissertation, we compare the min-max and the standard (min-sum) objective functions in a worst-case analysis to show that the optimal solution with respect to one objective function can be very poor with respect to the other. The results motivate the design of algorithms specifically for the min-max objective. We study variants of min-max VRPs including one problem from the literature (the min-max Multi-Depot VRP) and two new problems (the min-max Split Delivery Multi-Depot VRP with Minimum Service Requirement and the min-max Close-Enough VRP). We develop heuristics to solve these three problems. We compare the results produced by our heuristics to the best-known solutions in the literature and find that our algorithms are effective. In the case where benchmark instances are not available, we generate instances whose near-optimal solutions can be estimated based on geometry. We formulate the Vehicle Routing Problem with Drones and carry out a theoretical analysis to show the maximum benefit from using drones in addition to trucks to reduce delivery time. The speed-up ratio depends on the number of drones loaded onto one truck and the speed of the drone relative to the speed of the truck.

A new physarum network based genetic algorithm for bandwidth-delay constrained least-cost multicast routing

Bandwidth-delay constrained least-cost multicast routing is a typical NP-complete problem. Although some swarm-based intelligent algorithms (e.g., genetic algorithm (GA)) are proposed to solve this problem, the shortcomings of local search affect the computational effectiveness. Taking the ability of building a robust network of Physarum network model (PN), a new hybrid algorithm, Physarum network-based genetic algorithm (named as PNGA), is proposed in this paper. In PNGA, an updating strategy based on PN is used for improving the crossover operator of traditional GA, in which the same parts of parent chromosomes are reserved and the new offspring by the Physarum network model is generated. In order to estimate the effectiveness of our proposed optimized strategy, some typical genetic algorithms and the proposed PNGA are compared for solving multicast routing. The experiments show that PNGA has more efficient than original GA. More importantly, the PNGA is more robustness that is very important for solving the multicast routing problem.

A new genetic algorithm based on modified Physarum network model for bandwidth-delay constrained least-cost multicast routing

A mobile ad hoc network is a kind of popular self-configuring network, in which multicast routing under the quality of service constraints, is a significant challenge. Many researchers have proved that such problem can be formulated as a NP-complete problem and proposed some swarm-based intelligent algorithms to solve the optimal solution, such as the genetic algorithm (GA), bees algorithm. However, a lower efficiency of local search ability and weak robustness still limit the computational effectiveness. Aiming to those shortcomings, a new hybrid algorithm inspired by the self-organization of Physarum, is proposed in this paper. In our algorithm, an updating scheme based on Physarum network model (PM) is used for improving the crossover operator of traditional GAs, in which the same parts of parent chromosomes are reserved and the new offspring by the PM is generated. In order to estimate the effectiveness of our proposed optimized scheme, some typical genetic algorithms and their updating algorithms (PMGAs) are compared for solving the multicast routing on four different datasets. The simulation experiments show that PMGAs are more efficient than original GAs. More importantly, the PMGAs are more robustness that is very important for solving the multicast routing problem. Moreover, a series of parameter analyses is used to find a set of better setting for realizing the maximal efficiency of our algorithm.

The implementation of a novel, bio-inspired, robotic security system

The implementation of a robotic security solution generally requires one algorithm to route the robot around the environment and another algorithm to perform anomaly detection. Solutions to the routing problem require the robot to have a good estimate of its own pose. We present a novel security system that uses metrics generated by the localisation algorithm to perform adaptive anomaly detection. The localisation algorithm is a vision-based SLAM solution called RatSLAM, based on mechanisms within the hippocampus. The anomaly detection algorithm is based on the mechanisms used by the immune system to identify threats to the body. The system is explored using data gathered within an unmodified office environment. It is shown that the algorithm successfully reacts to the presence of people and objects in areas where they are not usually present and is tolerised against the presence of people in environments that are usually dynamic.

Design of logical topologies for wavelength-routed optical networks

his paper studies the problem of designing a logical topology over a wavelength-routed all-optical network (AON) physical topology, The physical topology consists of the nodes and fiber links in the network, On an AON physical topology, we can set up lightpaths between pairs of nodes, where a lightpath represents a direct optical connection without any intermediate electronics, The set of lightpaths along with the nodes constitutes the logical topology, For a given network physical topology and traffic pattern (relative traffic distribution among the source-destination pairs), our objective is to design the logical topology and the routing algorithm on that topology so as to minimize the network congestion while constraining the average delay seen by a source-destination pair and the amount of processing required at the nodes (degree of the logical topology), We will see that ignoring the delay constraints can result in fairly convoluted logical topologies with very long delays, On the other hand, in all our examples, imposing it results in a minimal increase in congestion, While the number of wavelengths required to imbed the resulting logical topology on the physical all optical topology is also a constraint in general, we find that in many cases of interest this number can be quite small, We formulate the combined logical topology design and routing problem described above (ignoring the constraint on the number of available wavelengths) as a mixed integer linear programming problem which we then solve for a number of cases of a six-node network, Since this programming problem is computationally intractable for larger networks, we split it into two subproblems: logical topology design, which is computationally hard and will probably require heuristic algorithms, and routing, which can be solved by a linear program, We then compare the performance of several heuristic topology design algorithms (that do take wavelength assignment constraints into account) against that of randomly generated topologies, as well as lower bounds derived in the paper.

Otimização de sistema de roteirização de coleta de resíduos sólidos domiciliares urbanos utilizando ferramentas computacionais.

A operação de coleta e transporte de resíduos sólidos urbanos é indispensável dentro de quaisquer sistema de limpeza urbana. É necessário que se intensifique a pesquisa nessa área de conhecimento afim de produzir-se material de auxílio ao poder público municipal e o setor privado. Deste modo o objetivo geral deste trabalho é o estudo da utilização de ferramentas computacionais para a otimização dos roteiros dos serviços de coleta de resíduos sólidos domiciliares. Foi feito um comparativo entre os itinerários percorridos pelos caminhões de coleta quando dimensionados de forma empírica e quando dimensionados com o auxílio de ferramentas computacionais. Verificou-se as vantagens e desvantagens de cada modelo de dimensionamento e o grande potencial de redução de custos quando utilizadas ferramentas computacionais.

基于整车配送的多仓库开路VRPTW问题的研究与实现

以整车销售物流为背景,探讨多仓库带时窗约束的车辆路线安排问题的解决方法.提出了更为复杂的基于现实的细节性要求的多配送中心开路VRPTW问题模型,并将遗传算法产生部分解和评估完整解的优化解决方法和涌现交叉算子MX1引入到带时窗的多仓库VRP问题优化中,实现了快速全局优化.提出的开路混合配送方法有利于提高车辆满载率,降低回程空载率.同时实现了运输资源的优化配置,提高车辆利用率.计算机仿真实验证明了算法的可行性.

Domain decomposition methods for welding problems

This paper, a 2-D non-linear electric arc-welding problem is considered. It is assumed that the moving arc generates an unknown quantity of energy which makes the problem an inverse problem with an unknown source. Robust algorithms to solve such problems e#ciently, and in certain circumstances in real-time, are of great technological and industrial interest. There are other types of inverse problems which involve inverse determination of heat conductivity or material properties [CDJ63][TE98], inverse problems in material cutting [ILPP98], and retrieval of parameters containing discontinuities [IK90]. As in the metal cutting problem, the temperature of a very hot surface is required and it relies on the use of thermocouples. Here, the solution scheme requires temperature measurements lied in the neighbourhood of the weld line in order to retrieve the unknown heat source. The size of this neighbourhood is not considered in this paper, but rather a domain decomposition concept is presented and an examination of the accuracy of the retrieved source are presented. This paper is organised as follows. The inverse problem is formulated and a method for the source retrieval is presented in the second section. The source retrieval method is based on an extension of the 1-D source retrieval method as proposed in [ILP].

Monitoring of urban transportation networks using wireless sensor networks

Dissertação de mestrado, Engenharia Informática, Faculdade de Ciências e Tecnologia, Universidade do Algarve, 2015

Route planning in wireless sensor networks for data gathering purposes

Dissertação de Mestrado, Engenharia Informática, Faculdade de Ciências e Tecnologia, Universidade do Algarve, 2015

Electromagnetism based approach to Sector design in Waste Collection

For efficient planning of waste collection routing, large municipalities may be partitioned into convenient sectors. The real case under consideration is the municipality of Monção, in Portugal. Waste collection involves more than 1600 containers over an area of 220 km2 and a population of around 20,000 inhabitants. This is mostly a rural area where the population is distributed in small villages around the 33 boroughs centres (freguesia) that constitute the municipality. In most freguesias, waste collection is usually conducted 3 times a week. However, there are situations in which the same collection is done every day. The case reveals some general and specific characteristics which are not rare, but are not widely addressed in the literature. Furthermore, new methods and models to deal with sectorization and routing are introduced, which can be extended to other applications. Sectorization and routing are tackled following a three-phase approach. The first phase, which is the main concern of the presentation, introduces a new method for sectorization inspired by Electromagnetism and Coulomb’s Law. The matter is not only about territorial division, but also the frequency of waste collection, which is a critical issue in these types of applications. Special characteristics related to the number and type of deposition points were also a motivation for this work. The second phase addresses the routing problems in each sector: new Mixed Capacitated Arc Routing with Limited Multi-Landfills models will be presented. The last phase integrates Sectoring and Routing. Computational results confirm the effectiveness of the entire novel approach.

Properties and Algorithms of the KCube Interconnection Networks

The KCube interconnection network was first introduced in 2010 in order to exploit the good characteristics of two well-known interconnection networks, the hypercube and the Kautz graph. KCube links up multiple processors in a communication network with high density for a fixed degree. Since the KCube network is newly proposed, much study is required to demonstrate its potential properties and algorithms that can be designed to solve parallel computation problems. In this thesis we introduce a new methodology to construct the KCube graph. Also, with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k). Moreover, we will find its connectivity followed by an optimal broadcasting scheme in which a source node containing a message is to communicate it with all other processors. In addition to KCube networks, we have studied a version of the routing problem in the traditional hypercube, investigating this problem: whether there exists a shortest path in a Qn between two nodes 0n and 1n, when the network is experiencing failed components. We first conditionally discuss this problem when there is a constraint on the number of faulty nodes, and subsequently introduce an algorithm to tackle the problem without restrictions on the number of nodes.

Une heuristique à grand voisinage pour un problème de confection de tournée pour un seul véhicule avec cueillettes et livraisons et contrainte de chargement

Dans ce mémoire, nous présentons un nouveau type de problème de confection de tour- née pour un seul véhicule avec cueillettes et livraisons et contrainte de chargement. Cette variante est motivée par des problèmes similaires rapportés dans la littérature. Le véhi- cule en question contient plusieurs piles où des colis de hauteurs différentes sont empilés durant leur transport. La hauteur totale des items contenus dans chacune des piles ne peut dépasser une certaine hauteur maximale. Aucun déplacement n’est permis lors de la li- vraison d’un colis, ce qui signifie que le colis doit être sur le dessus d’une pile au moment d’être livré. De plus, tout colis i ramassé avant un colis j et contenu dans la même pile doit être livré après j. Une heuristique à grand voisinage, basé sur des travaux récents dans le domaine, est proposée comme méthode de résolution. Des résultats numériques sont rapportés pour plusieurs instances classiques ainsi que pour de nouvelles instances.

Méthodes exactes et heuristiques pour le problème de tournées de véhicules avec fenêtres de temps et réutilisation de véhicules

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future.