In this paper we propose a hybrid approach for solving vehicle routing problems. The main idea is to combine an Ant System (AS) with a problem specific constructive heuristic, namely the well known Savings algorithm. This differs from previous approaches, where the subordinate heuristic was the Nearest Neighbor algorithm initially proposed for the TSP. We compare our approach with some other classic, powerful meta-heuristics and show that our results are competitive. / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

General routing problems deal with transporting some commodities and/or travelling along the axes of a given network in some optimal manner. In the modern world such problems arise in several contexts such as distribution of goods, transportation of commodities and/or people etc.In this thesis we focus on two classical routing problems, namely the Travelling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP). The TSP can be described as a salesman travels from his home city, visits each of the other ( n - 1) cities exactly once and returns back to the home city such that the total distance travelled by him is minimised. The VRP may be stated as follows: A set of n customers (with known locations and demands for some commodity) is to be supplied from a single depot using a set of delivery vehicles each with a prescribed capacity. A delivery route starts from the depot, visits some customers and returns back to the depot. The VRP is to determine the delivery routes for each vehicle such that the total distance travelled by all the vehicles is minimised.These routing problems are simple to state in terms of describing them in words. But they are very complex in terms of providing a suitable mathematical formulation and a valid procedure to solve them. These routing problems are simple to state in terms of describing them in words. But they are very complex in terms of providing a suitable mathematical formulation and a valid procedure to solve them. These problems belong to the class of NP-hard (Non- deterministic Polynomial) problems. With the present knowledge, it is believed that the problems in NP-hard are unlikely to have any good algorithms to arrive at optimal solutions to a general problem. Hence researchers have focused their effort on; (i) developing exact algorithms to solve as large size problems as possible; (ii) developing heuristics to produce ++ / near optimal solutions.The exact algorithms for such problems have not performed satisfactorily as they need an enormous amount of computational time to solve moderate size problems. For instance, in the literature, TSP of size 225-city, 4461-city and 7397-city were solved using computational time of 1 year, 1.9 years and 4 years respectively (Junger et al., 1995). Thus heuristics, in particular the probabilistic methods such as tabu search, play a significant role in obtaining near optimal solutions. In the literature there is very little comparison between the various exact algorithms and heuristics. (Very often the real-life problems are too large and no optimal solution can be found in a reasonable time.)One of the problems with a probabilistic heuristic is that different implementations (runs) of the same probabilistic heuristic on a given problem may produce distinct solutions of different quality. Thus the desired quality and reproducibility of the solution cannot be ensured. Furthermore, the performance of the heuristics on the benchmark problems provide no Guarantee of the quality of solutions that can be obtained for the problem faced by a researcher. Most of the documentation on the performance of heuristics in literature problems provides no information regarding the computational effort (CPU time) spent in obtaining the claimed solution, reproducibility of the claimed solution and the hardware environment of the implementation. This thesis focuses on some of these deficiencies.Most of the heuristics for general combinatorial optimisation problems are based on neighbourhood search methods. This thesis explores and provides a formal setup for defining neighbourhood structures, definitions of local optimum and global optimum. Furthermore it highlights the dependence and drawbacks of such methods on the neighbourhood structure.It is necessary to emphasise ++ / the need for a statistical analysis of the output to be part of any such probabilistic heuristic. Some of the statistical tools used for the two probabilistic heuristics for TSP and VRP are developed. Furthermore, these heuristics axe part of a bigger class called tabu search heuristics for combinatorial optimisation problems. Hence it includes an overview of the TSP, VRP and tabu search methods in Chapters 2, 3 and 4 respectively. Subsequently in Chapters 5, 6, 7 and 8 ideas of neighbourhood structure, local optimum etc. are developed and the required statistical analysis for some heuristics on the TSP and VRP is demonstrated. In Chapter 9, the conclusion of this thesis is drawn and the direction of future work is outlined. The following is a brief outline of the contribution of this thesis.In Chapter 5, the ideas of neighbourhood structure, local optimum, global optimum and probabilistic heuristics for any combinatorial optimisation problem sare developed. The drawbacks of the probabilistic heuristics for such problems axe highlighted. Furthermore, the need to select the best heuristic on the basis of testing a statistical hypothesis and related statistical analysis is emphasised.Chapter 6 illustrates some of the ideas presented in Chapter 5 using the GENIUS algorithm proposed for the TSP. Statistical analysis is performed for 36 variations of GENIUS algorithm based on different neighbourhood parameters, different types of insertion methods used and two types of constructions of starting solutions. The analysis is performed on 27 literature problems with size ranging from 100 cities to 532 cities and 20 randomly generated problems with size ranging from 100 cities to 480 cities. In both cases the best heuristic is selected. Furthermore, the fitting of the Weibull Distribution to the objective function values of the heuristic solutions provides an estimate of the ++ / optimal objective function value and a corresponding confidence interval for both the literature and randomly generated problems. In both cases the estimate of the optimal objective function values are within 8.2% of the best objective function value known.Since the GENIUS algorithm proved to be efficient, a hybrid heuristic for the TSP combining the branch and bound method and GENIUS algorithm to solve large dimensional problems is proposed. The algorithm is tested on both the literature problems with sizes ranging from 575 cities to 724 cities and randomly generated problems with sizes ranging from 500 cities to 700 cities. Though problems could not be solved to optimality within the 10 hours time limit, solutions were found within 2.4% of the best known objective function value in the literature.In Chapter 7, a similar statistical analysis for the TABUROUTE algorithm proposed for the VRP is conducted. The analysis is carried out based on the different neighbourhood parameters and tested using 14 literature problems with sizes ranging from 50 cities to 199 cities and 49 randomly generated problems with sizes ranging from 60 cities to 120 cities. In both sets of the problems, the statistical tests accepted the hypothesis that there is no significant difference in the solution produced between the various parameters used for the TABUROUTE algorithm. By fitting the Weibull distribution to the objective function values of the local optimal solutions, the optimal objective function value and a corresponding confidence intervals for each problem is estimated. These estimates give values that are to within 6.1% and 18.3% of the best known values for the literature problems and randomly generated problems respectively.In Chapter 8, the general neighbourhood search method for a general combinatorial optimisation problem is presented. Very often, the neighbourhood structure ++ / can be defined suitably only on a superset S of the set of feasible solutions S. Thus the solutions in SS are infeasible. Several questions axe posed regarding the computational complexity of the solution space of a problem. These concepts are illustrated on the 199-city CDVRP, using the TABUROUTE algorithm.In addition, the idea of complexity of the solution space based on the samples collected over the 140 runs is explored. Some of the data collected include the number of solutions with distance and/or capacity feasible, the number of feasible neighbourhood solutions encountered for one run, etc. Questions such asHow many solutions are there for the 199-city problem ?How many numbers of local minima solutions are there for the 199-city problem?What is the size of the feasible region for the 199-city problem?are answered. Finally, the conclusion is drawn that this problem cannot be used as a benchmark based on the size of the feasible region and too many local minima.The conclusion of this thesis and directions of future work are discussed in Chapter 9. There are two appendices presented at the end of the thesis. Appendix A presents the details of the Friedman test, the expected utility function test and the estimation of the optimal objective function value based on the Weibull distribution. Appendix B presents a list of tables from Chapters 6, 7 and 8.

In a few years, the Internet has quickly evolved from a research network connecting a handful of users to the largest distributed system ever built. The Internet connects more than 20,000 Autonomous Systems (ASs) which are administratively independent networks. While the initial Internet was designed to provide a best-effort connectivity among these ASs, there is nowadays a growing trend to deploy new services such as Voice/Video over IP or VPNs. To support these emergent services, ASs need to better engineer their Internet traffic. Traffic Engineering encompasses several goals such as better spreading the traffic load inside a network and obtaining better end-to-end performance (lower latency or higher bandwidth).<br><br> Engineering the traffic inside a single AS is feasible and pretty well understood. To the opposite, interdomain traffic engineering is still a difficult problem. The main issue comes from the current Internet routing architecture, articulated around the Border Gateway Protocol (BGP). BGP propagates a subset of the Internet topology for scalability and stability reasons and does not optimize a single global objective. This limits the control each AS has on its routing and has dramatic implications for interdomain traffic engineering.<br><br> In this thesis, we evaluate the primitive BGP-based routing control mechanisms. For this purpose, we designed and implemented a new approach for modeling BGP on large Internet-scale network topologies. Finally, to overcome the limitations of BGP in terms of routing control, we propose Virtual Peerings, a new mechanism based on a combination of BGP and IP tunneling. We apply Virtual Peerings to solve various interdomain traffic engineering problems such as balancing the load of Internet traffic received by an AS or decreasing the end-to-end latency of Internet paths.

In this thesis, an investigation of the performance of multipath routing in Wireless Sensor Networks (WSN) is performed. The communication in the network under study is to take place from individual nodes to the sink node. The investigation involved multipath finding methods in WSN. Also, it involves investigating the weight assignment, traffic splitting and route selection methods for the different paths discovered by each node in the WSN. Also, a comparison between Hybrid Routing Protocol, Source Routing Protocol and Diffusion Routing Protocol is performed. A simple traffic routing algorithm for each routing protocol has been developed to conceptualize how the network traffic is routed on a set of active paths. The investigation of the Hybrid, Source and Diffusion Routing Protocol involved using multiple paths simultaneously to transmit messages that belong to the same flow by using a weight assigned to each path and transmit each message as a whole. Finally, the power consumption and the QoS in terms of message delays for a WSN were investigated and compared between different protocols.

In this thesis, an investigation of the performance of multipath routing in Wireless Sensor Networks (WSN) is performed. The communication in the network under study is to take place from individual nodes to the sink node. The investigation involved multipath finding methods in WSN. Also, it involves investigating the weight assignment, traffic splitting and route selection methods for the different paths discovered by each node in the WSN. Also, a comparison between Hybrid Routing Protocol, Source Routing Protocol and Diffusion Routing Protocol is performed. A simple traffic routing algorithm for each routing protocol has been developed to conceptualize how the network traffic is routed on a set of active paths. The investigation of the Hybrid, Source and Diffusion Routing Protocol involved using multiple paths simultaneously to transmit messages that belong to the same flow by using a weight assigned to each path and transmit each message as a whole. Finally, the power consumption and the QoS in terms of message delays for a WSN were investigated and compared between different protocols.

User demand for seamless connectivity has encouraged the development of alternatives to traditional communications infrastructure networks. Potential solutions have to be low-cost, easily deployable and adaptive to the environment. One approach that has gained tremendous attention over the past few years is the deployment of a backbone of access points wirelessly interconnected, allowing users to access the wired infrastructure via wireless multi-hop communication. Wireless Mesh Networks (WMN) fall into this category and constitute a technology that could revolutionize the way wireless network access is provided. However, limited transfer capacity and interference resulting from the shared nature of the transmission medium will prevent widespread deployment if the network performance does not meet users' expectations. It is therefore imperative to provide efficient mechanisms for such networks. Resource management encompasses a number of different issues, including routing. Although a profusion of routing mechanisms have been proposed for other wireless technologies, the unique characteristics of WMNs (i.e. fixed wireless backbone, with the possibility to embed multiple interfaces) prevent their straight forward adoption in WMNs. Moreover, the severe performance degradations that can result from the interference generated by concurrent data transmissions and environmental noise call for the development of interference-aware routing mechanisms. In this thesis, we investigated the impact of interference on the network performance of wireless mesh networks. We designed algorithms to associate routers to gateways that minimize the interference level in single-channel and multi-channel networks. We then studied the performance of existing routing metrics and their suitability for mesh networks. As a result of this analysis, we designed a novel routing metric and showed its benefits over existing ones. Finally, we provided an analytical evaluation of the probability of finding two non interfering paths given a network topology.

User demand for seamless connectivity has encouraged the development of alternatives to traditional communications infrastructure networks. Potential solutions have to be low-cost, easily deployable and adaptive to the environment. One approach that has gained tremendous attention over the past few years is the deployment of a backbone of access points wirelessly interconnected, allowing users to access the wired infrastructure via wireless multi-hop communication. Wireless Mesh Networks (WMN) fall into this category and constitute a technology that could revolutionize the way wireless network access is provided. However, limited transfer capacity and interference resulting from the shared nature of the transmission medium will prevent widespread deployment if the network performance does not meet users' expectations. It is therefore imperative to provide efficient mechanisms for such networks. Resource management encompasses a number of different issues, including routing. Although a profusion of routing mechanisms have been proposed for other wireless technologies, the unique characteristics of WMNs (i.e. fixed wireless backbone, with the possibility to embed multiple interfaces) prevent their straight forward adoption in WMNs. Moreover, the severe performance degradations that can result from the interference generated by concurrent data transmissions and environmental noise call for the development of interference-aware routing mechanisms. In this thesis, we investigated the impact of interference on the network performance of wireless mesh networks. We designed algorithms to associate routers to gateways that minimize the interference level in single-channel and multi-channel networks. We then studied the performance of existing routing metrics and their suitability for mesh networks. As a result of this analysis, we designed a novel routing metric and showed its benefits over existing ones. Finally, we provided an analytical evaluation of the probability of finding two non interfering paths given a network topology.

Todays supercomputers employ the fastest processors incorporating the latest VLSI technology. Unfortunately, usable system performance is often limited by excessive interprocessor latency. To overcome this bottleneck, this thesis explores the use of all-optical path interconnection networks using a new topology defined by Coke Reed [31]. This work overcomes limitations of previous optical networks through a novel use of defection routing to minimize latency and allow more processors to collaborate on the same application and dataset. In this thesis research, the data vortex is formally characterized and tested for performance. Extra angles serve as virtual buffers to provide required system performance, even under asymmetric mode operation. The data vortex is compared to two well-known interconnection networks (omega and butterfly) using metrics of average latency and message acceptance rate. The data vortex is shown to outperform the comparison networks, with a 20-50% higher acceptance rate and comparable average latency. The impact of angle size is also studied, and a new, synchronous mode of operation is proposed where additional angles are added to increase the virtual buffering of the network. The tradeoff between virtual buffering and angle resolution backpressure is explored, and an optimal point is found at the 1:6 I/O to non-I/O (virtual buffering) angle ratio. The new mode and optimal angle count are used to form data vortex networks that perform as well as larger networks with fewer total nodes. Finally, hierarchical layering with data vortex clusters is proposed and compared to a single-level data vortex. In todays technology, similar performance is attained at high network communication locality loads (> 2/3), and a 19% latency reduction is obtained at the highest locality loads (> 95%) for current optical switching technology. For projected future technology, the clustered system is shown to yield up to a 55% reduction in latency for applications with 2/3 or better locality.

This thesis studies the applications of the network coding technique for intercon- nect optimization and improving the routability of Very-large-scale integration (VLSI) designs. The goal of the routing process is to connect the required sets of sources and sinks while minimizing the total wirelength and reducing congestion. Typically, chip interconnects include multiple sinks and are routed through intermediate nodes. The main idea of the network coding technique is to enable the intermediate nodes to generate new signals by combining the signals received over their incoming wires. This is in contrast to the traditional approaches, in which an intermediate node can only forward the incoming signals. This thesis attempts to explore the possible ben- efits of the network coding technique for reducing the total wirelengh and mitigating congestion in VLSI designs. The contribution of the thesis is three-fold. First, we extend the Hanan’s theo- rem for multi-net rectilinear coding networks. Second, we propose several exact and heuristic solutions for finding near-optimal routing topologies that utilize network coding techniques. Next, we perform extensive simulation study to evaluate the ad- vantage of network coding over the traditional approaches. The simulations help to identify routing instances where the network coding techniques are expected to be beneficial. Finally, we evaluate the potential benefits from network coding in practical settings by analyzing its performance on the International Symposium on Physical Design (ISPD) benchmarks. Our results show that while network coding shows upto 2.43% improvement on unconstrained rectilinear grids, it shows upto 4.34% improvement in cases with con- straints along the grid. In addition, it shows an improvement upto 8.4% in cases involving congestion reduction and also improves routing performance on ISPD rout- ing benchmarks.

No description available.