In this paper,we propose an adaptive large neighborhood search heuristic for the Two-Echelon Vehicle Routing Problem (2E-VRP) and the Location Routing Problem (LRP).The 2E-VRP arises in two-level transportation systems such as those encountered in the context of city logistics. In such systems, freight arrives at a major terminal and is shipped through intermediate satellite facilities to the final customers. The LRP can be seen as a special case of the 2E-VRP in which vehicle routing is performed only at the second level. We have developed new neighborhood search operators by exploiting the structure of the two problem classes considered and have also adapted existing operators from the literature. The operators are used in a hierarchical scheme reflecting the multi-level nature of the problem. Computational experiments conducted on several sets of instances from the literature show that our algorithm out performs existing solution methods for the 2E-VRP and achieves excellent results on the LRP.

A wireless mesh network is a mesh network implemented over a wireless network system such as wireless LANs. Wireless Mesh Networks(WMNs) are promising for numerous applications such as broadband home networking, enterprise networking, transportation systems, health and medical systems, security surveillance systems, etc. Therefore, it has received considerable attention from both industrial and academic researchers. This dissertation explores schemes for resource management and optimization in WMNs by means of network routing and network coding. In this dissertation, we propose three optimization schemes. (1) First, a triple-tier optimization scheme is proposed for load balancing objective. The first tier mechanism achieves long-term routing optimization, and the second tier mechanism, using the optimization results obtained from the first tier mechanism, performs the short-term adaptation to deal with the impact of dynamic channel conditions. A greedy sub-channel allocation algorithm is developed as the third tier optimization scheme to further reduce the congestion level in the network. We conduct thorough theoretical analysis to show the correctness of our design and give the properties of our scheme. (2) Then, a Relay-Aided Network Coding scheme called RANC is proposed to improve the performance gain of network coding by exploiting the physical layer multi-rate capability in WMNs. We conduct rigorous analysis to find the design principles and study the tradeoff in the performance gain of RANC. Based on the analytical results, we provide a practical solution by decomposing the original design problem into two sub-problems, flow partition problem and scheduling problem. (3) Lastly, a joint optimization scheme of the routing in the network layer and network coding-aware scheduling in the MAC layer is introduced. We formulate the network optimization problem and exploit the structure of the problem via dual decomposition. We find that the original problem is composed of two problems, routing problem in the network layer and scheduling problem in the MAC layer. These two sub-problems are coupled through the link capacities. We solve the routing problem by two different adaptive routing algorithms. We then provide a distributed coding-aware scheduling algorithm. According to corresponding experiment results, the proposed schemes can significantly improve network performance.

Thesis (MSc.) -- University of Limpopo, 2017 / The notion of ubiquitous computing, Internet of things (IoT), big data, cloud computing and other emerging technologies has brougt forward the innovative paradigms and incredible developments in wireless communication technologies. The Wireless Mesh Networks (WMNs) technology has recently emerged as the promising high speed wireless technology to provide the last mile broadband Internet access and deliver flexible and integrated wireless communication solutions. The WMNs has the potential to enable people living in rural, peri-urban areas and small businesses to interconnect their networks and share the affordable Internet connectivity. The recent multimedia applications developed, such as voice over Internet protocol (VoIP), online gaming, cloud storage, instant messaging applications, and video sharing applications require high speed communication media and networks. These applications have witnessed enormous growth in the recent decade and continue to enhance communication amongst the users. Hence, the WMNs must have adequate capacity to support high bandwidth and real-time and multimedia applications. While the wireless communications networks are dependent on the radio frequency (RF) spectrum, the traditional wireless technologies utilise the RF spectrum bands inefficiently, resulting in sporadic and underutilisation of the RF spectrum. This inefficient usage of RF spectrum calls for novel techniques to leverage the available RF spectrum amongst different players in the wireless communication arena. There have been developments on integration of the WMNs with cognitive ratios to allow unlicensed users of RF spectrum to operate in the licensed portions of spectrum bands. This integration will provide the required bandwidth to support the required high speed broadband communication infrastructure. In this dissertation, we focus our research on the routing layer in a multi-hop wireless network environment. We addressed the routing challenges in both the WMNs and the cognitive radio based wireless mesh networks (CR-WMNs). The primary focus was to identify the routing protocols most suitable for the dynamic WMN environment. Once identified, the routing protocol was then ported to the CR-WMN environment to evaluate its performance given all the dynamics of cognitive radio environment. vi We further proposed the routing protocol called the extended weighted cumulative expected transmission time (xWCETT) routing protocol for the CR-WMNs. The design of our proposed xWCETT routing protocol is based on the multi-radio multi-channel architecture as it gives the base framework matching the cognitive radio environment. The xWCETT integrates features from the Ad-hoc On-demand Distance Vector (AODV) routing protocol and the weighted cumulative expected transmission time (WCETT) routing metric. The xWCETT was implemented using the Cognitive Radio Cognitive Network (CRCN) patch ported in network simulator (NS2) to incorporate the shared and dynamic spectrum access features. We compared the performance of our proposed xWCETT routing protocol with the AODV, dynamic source routing (DSR), the optimised link source routing (OLSR), Destination Sequences Distance Vector (DSDV), and the CRCN-WCETT routing protocols. The extensive simulation and numerical results show that the proposed xWCETT protocol obtained on average, around 10% better performance results in the CR-WNNs as compared to its routing counterparts. The comparative analysis and evaluation was performed in terms of the average end-to-end latency, throughput, jitter, packet delivery ratio, as well as the normalised routing load. The performance results obtained indicates that the proposed xWCETT routing protocol is a promising routing solution for dynamic CR-WMNs environment. / National Research Foundation (NRF)

School districts providing busing services for students who live too far to walk to school. In many districts a fleet of school buses is used in sequence to transport high school students, then middle school students, and then elementary school students. The result is that high school classes must start much earlier in the morning than the elementary school, and buses may traverse similar routes three times each morning and afternoon. In light of recent research on the benefits of later high school start times and the need to control transportation costs, school districts are seeking efficient school bus routing plans that meet student needs at low cost. This study uses 2018 data for schools in Northampton, Massachusetts, to identify the potential to achieve two objectives: 1) start the high school classes as late as possible in the day, and 2) minimize the cost of busing. The proposed procedure makes use of existing school bus data to optimize bus routes, which can be applicable for smaller cities. A revised routing plan that mixes high school and middle school students on the same buses allows the high school to start 30 minutes later while reducing total school bus operations.

The thesis focuses on how to optimize vehicle routes for distributing logistics. This vehicle route optimization is known as a vehicle routing problem (VRP). The VRP has been extended in numerous directions for instance by some variations that can be combined. One of the extension forms of VRP is a capacitated VRP with stochastics demands (CVRPSD), where the vehicle capacity limit has a non-zero probability of being violated on any route. So, a failure to satisfy the amount of demand can appear. A strategy is required for updating the routes in case of such an event. This strategy is called as recourse action in the thesis. The main objective of the research is how to design the model of CVRPSD and find the optimal solution. The EEV (Expected Effective Value) and FCM (Fuzzy C-Means) – TSP (Travelling Salesman Problem) approaches are described and used to solve CVRPSD. Results have confirmed that the EEV approach has given a better performance than FCM-TSP for solving CVRPSD in small instances. But EEV has disadvantage, that the EEV is not capable to solve big instances in an acceptable running time because of complexity of the problem. In the real situation, the FCM –TSP approach is more suitable for implementations than the EEV because the FCM – TSP can find the solution in a shorter time. The disadvantage of this algorithm is that the computational time depends on the number of customers in a cluster.

This project seeks to demonstrate routing optimization that would allow pedestrian and micromobility user groups to select and prioritize different route features according to their preferences. Through the creation of a routing demonstrator that considers both static and dynamic parameters in the form of pavement quality, elevation climb, travel time, and air quality, along with user-specified weights for their prioritization of each of these parameters, a number of routes were created and mapped to qualitatively compare against routes representing only a shortest path. / <p>Examensarbetet är utfört vid Institutionen för teknik och naturvetenskap (ITN) vid Tekniska fakulteten, Linköpings universitet</p>

The study of matrices have been of interest to mathematicians for some time. Recently the use of matrices has assumed greater importance also in the fields of management, social science, and natural science because they are very useful in the organization and presentation of data and in the solution of linear equations. The theory of matrices is yet another type of mathematical model which we can use to solve many problems that arise in these fields. The aim of this paper is to show how we can use matrices and their mathematical model to solve some problems in the process of routing. First we will introduce the term of routing and the new approach in the process of selecting paths. We will show some simple examples. We will also pint out how we can learn about matrices in the classroom. At the end we will discuss about advantages and potential disadvantages that may occur in the described technique.

There is a seemingly endless miniaturization of electronic components, which has enabled designers to build sophisticated computing structureson silicon chips. Consequently, electronic systems are continuously improving with new and more advanced functionalities. Design complexity ofthese Systems on Chip (SoC) is reduced by the use of pre-designed cores. However, several problems related to the interconnection of coresremain. Network on Chip (NoC) is a new SoC design paradigm, which targets the interconnect problems using classical network concepts. Still,SoC cores show large variance in size and functionality, whereas several NoC benefits relate to regularity and homogeneity. This thesis studies some network aspects which are characteristic to NoC systems. One is the issue of area wastage in NoC due to cores of varioussizes. We elaborate on using oversized regions in regular mesh NoC and identify several new design possibilities. Adverse effects of regions oncommunication are outlined and evaluated by simulation. Deadlock freedom is an important region issue, since it affects both the usability and performance of routing algorithms. The concept of faultyblocks, used in deadlock free fault-tolerant routing algorithms has similarities with rectangular regions. We have improved and adopted one suchalgorithm to provide deadlock free routing in NoC with regions. This work also offers a methodology for designing topology agnostic, deadlockfree, highly adaptive application specific routing algorithms. The methodology exploits information about communication among tasks of anapplication. This is used in the analysis of deadlock freedom, such that fewer deadlock preventing routing restrictions are required. A comparative study of the two proposed routing algorithms shows that the application specific algorithm gives significantly higher performance.But, the fault-tolerant algorithm may be preferred for systems requiring support for general communication. Several extensions to our work areproposed, for example in areas such as core mapping and efficient routing algorithms. The region concept can be extended for supporting reuse ofa pre-designed NoC as a component in a larger hierarchical NoC.

The objective of the research is to study optimal routing policy (ORP) problems and to develop an optimal adaptive routing algorithm practical for large-scale Stochastic Time-Dependent (STD) real-life networks, where a traveler could revise the route choice based upon en route information. The routing problems studied can be viewed as counterparts of shortest path problems in deterministic networks. A routing policy is defined as a decision rule that specifies what node to take next at each decision node based on realized link travel times and the current time. The existing routing policy algorithm is for explorative purpose and can only be applied to hypothetical simplified network. In this research, important changes have been made to make it practical in a large-scale real-life network. Important changes in the new algorithm include piece-wise linear travel time representation, turn-based, label-correcting, criterion of stochastic links, and dynamic blocked links. Complete dependency perfect online information (CDPI) variant is then studied in a real-life network (Pioneer Valley, Massachusetts). Link travel times are modeled as random variables with time-dependent distributions which are obtained by running Dynamic Traffic Assignment (DTA) using data provided by Pioneer Valley Planning Commission (PVPC). A comprehensive explanation of the changes by comparing the two algorithms and an in-depth discussion of the parameters that affects the runtime of the new algorithm is given. Computational tests on the runtime changing with different parameters are then carried out and the summary of its effectiveness are presented. To further and fully understand the applicability and efficiency, this algorithm is then tested in another large-scale network, Stockholm in Sweden, and in small random networks. This research is also a good starting point to investigate strategic route choice models and strategic route choice behavior in a real-life network. The major tasks are to acquire data, generate time-adaptive routing policies, and estimate the runtime of the algorithm by changing the parameters in two large-scale real-life networks, and to test the algorithm in small random networks. The research contributes to the knowledge base of ORP problems in stochastic time-dependent (STD) networks by developing an algorithm practical for large-scale networks that considers complete time-wise and link-wise stochastic dependency.

Congestion is a world-wide problem in transportation. One major reason is random interruptions. The traffic network is inherently stochastic, and strong dependencies exist among traffic quantities, e.g., travel time, traffic speed, link volume. Information in stochastic networks can help with adaptive routing in terms of minimizing expected travel time or disutility. Routing in such networks is different from that in deterministic networks or when stochastic dependencies are not taken into account. This dissertation addresses the optimal routing problems, including the optimal a priori path problem and the optimal adaptive routing problem with different information scenarios, in stochastic and time-dependent networks with explicit consideration of the correlations between link travel time random variables. There are a number of studies in the literature addressing the optimal routing problems, but most of them ignore the correlations between link travel times. The consideration of the correlations makes the problem studied in this dissertation difficult, both conceptually and computationally. The optimal path finding problem in such networks is different from that in stochastic and time-dependent networks with no consideration of the correlations. This dissertation firstly provides an empirical study of the correlations between random link travel times and also verifies the importance of the consideration of the spatial and temporal correlations in estimating trip travel time and its reliability. It then shows that Bellman's principle of optimality or non-dominance is not valid due to the time-dependency and the correlations. A new property termed purity is introduced and an exact label-correcting algorithm is designed to solve the problem. With the fast advance of telecommunication technologies, real-time traffic information will soon become an integral part of travelers' route choice decision making. The study of optimal adaptive routing problems is thus timely and of great value. This dissertation studies the problems with a wide variety of information scenarios, including delayed global information, real-time local information, pre-trip global information, no online information, and trajectory information. It is shown that, for the first four partial information scenarios, Bellman's principle of optimality does not hold. A heuristic algorithm is developed and employed based on a set of necessary conditions for optimality. The same algorithm is showed to be exact for the perfect online information scenario. For optimal adaptive routing problem with trajectory information, this dissertation proves that, if the routing policy is defined in a similar way to other four information scenarios, i.e., the trajectory information is included in the state variable, Bellman's principle of optimality is valid. However, this definition results in a prohibitively large number of the states and the computation can hardly be carried out. The dissertation provides a recursive definition for the trajectory-adaptive routing policy, for which the information is not included in the state variable. In this way, the number of states is small, but Bellman's principle of optimality or non-dominance is invalid for a similar reason as in the optimal path problem. Again purity is introduced to the trajectory-adaptive routing policy and an exact algorithm is designed based on the concept of decreasing order of time.