A conceptual framework for multiple‐criteria routing in QoS IP networks

The provision of quality of service (QoS) in IP‐based networks, namely QoS IP networks, has led to new demands for routing methods, protocols and algorithms. It is widely recognized that such QoS routing should take into account multiple criteria. In this case, contemporary approaches in multiple‐criteria analysis should be taken into account, and they differ essentially from classical routing approaches. An alternative to classical routing algorithms that are not quite able to respond to all the challenges of QoS IP networks, especially from the perspective of Future Internet, is to change routing approaches and algorithms to provide for consistent multiple‐criteria routing approaches. This is also related to the understanding of the concept of hierarchy in routing, discussed in the paper. The paper recalls the concept of objective ranking, shows its appropriateness for consistent multiple‐criteria routing and presents a conceptual framework for routing based on objective ranking, including hierarchy of routing optimization and multiple routing tables. The paper has a conceptual nature, with the purpose of analyzing possible approaches to multiple‐criteria routing that might be useful if not today, then in the engineering of future networks. However, a network engineering interpretation of the concepts proposed here is also presented.     

Applications of meta‐heuristics to traffic engineering in IP networks

Intra‐domain routing protocols are based on shortest path first (SPF) routing, where shortest paths are calculated between each pair of nodes (routers) using pre‐assigned link weights, also referred to as link metric. These link weights can be modified by network administrators in accordance with the routing policies of the network operator. The operator's objective is usually to minimize traffic congestion or minimize total routing cost subject to the traffic demands and the protocol constraints. However, determining a link weights combination that best suits the network operator's requirements is a difficult task. This paper provides a survey of meta‐heuristic approaches to traffic engineering, focusing on local search approaches and extensions to the basic problem taking into account changing demands and robustness issues with respect to network failures.     

VNS methods for home care routing and scheduling problem with temporal dependencies,and multiple structures and specialties

The need for optimization in the Home Care Service is becoming more and more legitimate in the face of the increase of demand and cost all over the world. Recently, many researchers in the Operation Research community have been attracted by this issue, which presents interesting aspects related to the vehicle routing problems. In this paper, we consider a new variant called the vehicle routing problem with time windows, temporal dependencies (synchronization, precedence, and disjunction), multi‐structures, and multispecialties problem (VRPTW‐TD‐2MS). This new variant is an extension of the vehicle routing problems with time windows and synchronization constraints (VRPTW‐S) that is well‐studied in literature. We present a Mixed Integer Programming method, and propose three Variable Neighborhood Search approaches. Extensive experiments show the effectiveness and efficiency of the General Variable Neighborhood Search with Ejection Chains‐based local search for solving VRPTW‐TD‐2MS and VRPTW‐S.     

Solving scalarized multi‐objective network flow problems using an interior point method

In this paper, we present a primal‐dual interior‐point algorithm to solve a class of multi‐objective network flow problems. More precisely, our algorithm is an extension of the single‐objective primal infeasible dual feasible inexact interior point method for multi‐objective linear network flow problems. Our algorithm is contrasted with standard interior point methods and experimental results on bi‐objective instances are reported. The multi‐objective instances are converted into single objective problems with the aid of an achievement function, which is particularly adequate for interactive decision‐making methods.     

移动Ad hoc网络中路由协议的能耗-性能联合比较

移动Adhoc网络是一种完全由移动主机构成的网络,网络拓扑易变,带宽,能源有限是其的突出特点。因此,高效路由协议的设计是Adhoc网络的基本问题之一。目前提出的各种路由协议各有它们的特点和优点。但是对这些路由协议的评价仅仅局限于单纯的网络性能或者能量消耗。该文在引入一种性能—能耗联合度量的基础上,对常见的DSR、AODV、TORA和DSDV四种路由协议进行了比较和评价。     

An evolutionary algorithm for the multi‐objective pick‐up and delivery pollution‐routing problem

The design of sustainable logistics solutions poses new challenges for the study of vehicle‐routing problems. The design of efficient systems for transporting products via a heterogeneous fleet of vehicles must consider the minimization of cost, emissions of greenhouse gases, and the ability to serve every customer within an available time slot. This phenomenon gives rise to a multi‐objective problem that considers the emission of greenhouse gases, the total traveling time, and the number of customers served. The proposed model is approached with an ε‐constraint technique that allows small instances to be solved and an evolutionary algorithm is proposed to deal with complex instances. Results for small instances show that all the points that approach the Pareto frontier found by the evolutionary algorithm are nondominated by any solution found by the multi‐objective model. For complex instances, nondominated solutions that serve most of the requests are found with low computational requirements.     

Multi‐objective memetic algorithm: comparing artificial neural networks and pattern search filter method approaches

In this work, two methodologies to reduce the computation time of expensive multi‐objective optimization problems are compared. These methodologies consist of the hybridization of a multi‐objective evolutionary algorithm (MOEA) with local search procedures. First, an inverse artificial neural network proposed previously, consisting of mapping the decision variables into the multiple objectives to be optimized in order to generate improved solutions on certain generations of the MOEA, is presented. Second, a new approach based on a pattern search filter method is proposed in order to perform a local search around certain solutions selected previously from the Pareto frontier. The results obtained, by the application of both methodologies to difficult test problems, indicate a good performance of the approaches proposed.     

Efficient techniques and tools for intra‐domain traffic engineering

Intra‐domain routing protocols are based on Shortest Path First (SPF) routing, where shortest paths are calculated between each pair of nodes (routers) using pre‐assigned link weights, also referred to as link metric. These link weights can be modified by network administrators in accordance with the routing policies of the network operator. The operator's objective is usually to minimize traffic congestion or minimize total routing costs subject to the traffic demands and the protocol constraints. However, determining a link weight combination that meets a network operator's objectives is a difficult task. In this paper, we study the link weight optimization problem in intra‐domain networks. This problem is proved to be NP‐hard with hard protocol constraints, e.g., a flow is evenly distributed along the shortest paths between its origin and destination nodes. We present two fast heuristic approaches to generate efficient link metrics for intra‐domain routing. Some promising experimental results are reported.     

Solving the bi‐objective capacitated p‐median problem with multilevel capacities using compromise programming and VNS

A bi‐objective optimisation using a compromise programming (CP) approach is proposed for the capacitated p‐median problem (CPMP) in the presence of the fixed cost of opening facility and several possible capacities that can be used by potential facilities. As the sum of distances between customers and their facilities and the total fixed cost for opening facilities are important aspects, the model is proposed to deal with those conflicting objectives. We develop a mathematical model using integer linear programming (ILP) to determine the optimal location of open facilities with their optimal capacity. Two approaches are designed to deal with the bi‐objective CPMP, namely CP with an exact method and with a variable neighbourhood search (VNS) based matheuristic. New sets of generated instances are used to evaluate the performance of the proposed approaches. The computational experiments show that the proposed approaches produce interesting results.     

Multiclass AQM on a TCP/IP router: A control theory approach

Active queue management (AQM) is a well‐known technique to improve routing performance under congested traffic conditions. It is often deployed to regulate queue sizes, thus aiming for constant transmission delay. This work addresses AQM using an approach based on control theory ideas. Compared with previous results in the literature, the novelty is the consideration of heterogeneous traffic, ie, multiclass traffic. Thus, each traffic class may have different discarding policies, queue sizes, and bandwidth share. This feature brings the proposal nearer to real network management demands than previous approaches in the literature. The proposed technique assumes that each class already has a simple controller, designed a priori, and focuses on designing a static state‐feedback controller for the multiclass system, where the design is based on using LMIs for the calculations. For this, optimization problems with LMI constraints are proposed to compute the state‐feedback gains that ensure stability for a large set of admissible initial conditions. These conditions ensure not only closed‐loop stability but also some level of performance. As far as we know, this is the first control theory based approach for the AQM problem on TCP/IP routers that allows a multiclass AQM while also considering time‐varying delays and input saturation. This is an important step to frame AQM in a more formal, yet realistic context, enabling it to address important service level agreement (SLA) directives. The proposal is tested on a simulated system at the end of this paper, showing the feasibility and performance of the approach in the presence of multiclass traffic.     

A reactive MILP approach to the multidepot heterogeneous fleet vehicle routing problem with time windows

The time‐window‐constrained vehicle routing problem (VRPTW) is a well‐known combinatorial problem. Its goal is to discover the best set of routes for a vehicle fleet in order to service a given number of customers at minimum cost. Vehicle capacity, maximum service time and time‐window constraints must be satisfied. Most proposed VRPTW optimizing approaches intend to discover the best or a near‐optimal solution at once. Improvement methods are old strategies that apply heuristics to insert customers into tours and/or rearrange nodes to obtain better routes. They are performed until no further improvement is achieved. Little research has been focused on model‐based reactive approaches seeking a better solution by exploring a small solution space around the current solution. This work presents a new model‐based improvement methodology for the multi‐depot heterogeneous‐fleet VRPTW problem to enhance an initial solution through solving a series of MILP mathematical problems that allow exchanges of nodes among tours and node reordering on every route. By restricting the range of improvement options, the problem size can be bounded and a limited number of binary variables is required for real‐world problems. The improvement formulation is based on a continuous time‐domain representation that handles assignment and sequencing decisions through different sets of binary variables and uses the notion of a generalized predecessor instead of a direct predecessor. Several types of VRPTW problems have been efficiently solved.     

Supervised machine learning in multimodal learning analytics for estimating success in project‐based learning

Multimodal learning analytics provides researchers new tools and techniques to capture different types of data from complex learning activities in dynamic learning environments. This paper investigates the use of diverse sensors, including computer vision, user‐generated content, and data from the learning objects (physical computing components), to record high‐fidelity synchronised multimodal recordings of small groups of learners interacting. We processed and extracted different aspects of the students' interactions to answer the following question: Which features of student group work are good predictors of team success in open‐ended tasks with physical computing? To answer this question, we have explored different supervised machine learning approaches (traditional and deep learning techniques) to analyse the data coming from multiple sources. The results illustrate that state‐of‐the‐art computational techniques can be used to generate insights into the "black box" of learning in students' project‐based activities. The features identified from the analysis show that distance between learners' hands and faces is a strong predictor of students' artefact quality, which can indicate the value of student collaboration. Our research shows that new and promising approaches such as neural networks, and more traditional regression approaches can both be used to classify multimodal learning analytics data, and both have advantages and disadvantages depending on the research questions and contexts being investigated. The work presented here is a significant contribution towards developing techniques to automatically identify the key aspects of students success in project‐based learning environments, and to ultimately help teachers provide appropriate and timely support to students in these fundamental aspects.     

An Overview and Experimental Study of Learning-Based Optimization Algorithms for the Vehicle Routing Problem

The vehicle routing problem(VRP) is a typical discrete combinatorial optimization problem, and many models and algorithms have been proposed to solve the VRP and its variants. Although existing approaches have contributed significantly to the development of this field, these approaches either are limited in problem size or need manual intervention in choosing parameters. To solve these difficulties, many studies have considered learning-based optimization(LBO) algorithms to solve the VRP. This p...     

Multiaspect‐based opinion classification model for tourist reviews

Tourist reviews on social media websites reflect the tourist's opinions concerning various aspects of a tourist place or service (e.g., “comfortable room” and “terrible service” in hotel reviews). Extracting these aspects from reviews is a challenging task in opinion mining. Therefore, aspect‐based opinion mining has emerged as a new area of social review mining. Existing approaches in this area focus on extracting explicit aspects and classification of opinions around these aspects. However, the implicit and coreferential aspects during aspect extraction are often neglected, and the classification of multiaspect opinions is relatively less emphasized in prior art. In this paper, we propose a model, namely, “enhanced multiaspect‐based opinion classification” that addresses existing challenges by automatically extracting both explicit and implicit aspects and classifying the multiaspect opinions. In this model, first, a probabilistic co‐occurrence‐based method is proposed that utilizes the co‐occurrence between aspects and sentiment words to identify the coreferential aspects and merge them into groups. Second, an implicit aspect extraction method is proposed that associates the sentiment words with suitable aspects to build an aspect‐sentiment hierarchy. Third, a multiaspect opinion classification approach is proposed that employs multilabel classification algorithms to classify opinions into different polarity classes. The effectiveness of the proposed model is evaluated by conducting experiments on benchmark and real‐world datasets. The experimental results revealed the supremacy of multilabel classifiers by achieving 90% accuracy per label on classification when extracting 87% domain‐relevant aspects. A state‐of‐the‐art performance comparison is conducted that also verifies the advantages of the proposed model.     

互联网域间路由可扩展性

互联网域间路由可扩展性问题是下一代互联网体系结构设计必须首先解决的关键问题之一.通过引入路由信息熵的概念,深入阐述Internet路由可扩展性问题的内在本质,并基于这一理论模型,分别从3个方面归纳解决路由可扩展性问题的3种可行思路.重点讨论了这3种思路应用于互联网路由系统的出发点和局限性.并就典型的具体提案从体系结构的角度进行了分析评价.最后总结路由可扩展性问题的挑战性,并展望了未来可扩展路由的研究发展方向.     

Restricted dynamic programming: A flexible framework for solving realistic VRPs

Most successful solution methods for solving large vehicle routing and scheduling problems are based on local search. These approaches are designed and optimized for specific types of vehicle routing problems (VRPs). VRPs appearing in practice typically accommodate restrictions that are not accommodated in classical VRP models, such as time-dependent travel times and driving hours regulations. We present a new construction framework for solving VRPs that can handle a wide range of different types of VRPs. In addition, this framework accommodates various restrictions that are not considered in classical vehicle routing models, but that regularly appear in practice. Within this framework, restricted dynamic programming is applied to the VRP through the giant-tour representation. This algorithm is a construction heuristic which for many types of restrictions and objective functions leads to an optimal algorithm when applied in an unrestricted way. We demonstrate the flexibility of the framework for various restrictions appearing in practice. The computational experiments demonstrate that the framework competes with state of the art local search methods when more realistic constraints are considered than in classical VRPs. Therefore, this new framework for solving VRPs is a promising approach for practical applications.     

Approaches to robust ℋ︁∞ static output feedback control of discrete‐time piecewise‐affine systems with norm‐bounded uncertainties

This paper investigates the problem of robust ??_∞ static output feedback controller design for a class of discrete‐time piecewise‐affine systems with norm‐bounded time‐varying parametric uncertainties. The objective is to design a piecewise‐linear static output feedback controller guaranteeing the asymptotic stability of the resulting closed‐loop system with a prescribed ??_∞ disturbance attenuation level. Based on a piecewise Lyapunov function combined with S‐procedure, Projection lemma, and some matrix inequality convexifying techniques, several novel approaches to the static output feedback controller analysis and synthesis are developed for the underlying piecewise‐affine systems. It is shown that the controller gains can be obtained by solving a set of strict linear matrix inequalities (LMIs) or a family of LMIs parameterized by one or two scalar variables, which are numerically efficient with commercially available software. Finally, three simulation examples are provided to illustrate the effectiveness of the proposed approaches. Copyright © 2010 John Wiley & Sons, Ltd.     

Cooperative game‐theoretic features of cost sharing in location‐routing

While the interest in both collaborative logistics and location‐routing has grown considerably, horizontal cooperation in location‐routing problems remains fairly unattended. This article studies several variants of the location‐routing problem using a cooperative game‐theoretic framework. The authors derive characteristics in terms of subadditivity, convexity, and non‐emptiness of the core. Moreover, for some of the game variants, it is shown that for facility opening costs substantially larger than the costs associated with routing, the core is always nonempty. The theoretical results are supported by numerical experiments aimed at illustrating the properties and deriving insights. Among others, it is observed that, while in general it is not possible to guarantee core allocations, in a huge majority of cases the core is nonempty.     

ADAPTIVE RANKS CLONE AND k‐NEAREST NEIGHBOR LIST–BASED IMMUNE MULTI‐OBJECTIVE OPTIMIZATION

Artificial immune systems (AIS) are computational systems inspired by the principles and processes of the vertebrate immune system. The AIS‐based algorithms typically exploit the immune system's characteristics of learning and adaptability to solve some complicated problems. Although, several AIS‐based algorithms have proposed to solve multi‐objective optimization problems (MOPs), little focus have been placed on the issues that adaptively use the online discovered solutions. Here, we proposed an adaptive selection scheme and an adaptive ranks clone scheme by the online discovered solutions in different ranks. Accordingly, the dynamic information of the online antibody population is efficiently exploited, which is beneficial to the search process. Furthermore, it has been widely approved that one‐off deletion could not obtain excellent diversity in the final population; therefore, a k‐nearest neighbor list (where k is the number of objectives) is established and maintained to eliminate the solutions in the archive population. The k‐nearest neighbors of each antibody are founded and stored in a list memory. Once an antibody with minimal product of k‐nearest neighbors is deleted, the neighborhood relations of the remaining antibodies in the list memory are updated. Finally, the proposed algorithm is tested on 10 well‐known and frequently used multi‐objective problems and two many‐objective problems with 4, 6, and 8 objectives. Compared with five other state‐of‐the‐art multi‐objective algorithms, namely NSGA‐II, SPEA2, IBEA, HYPE, and NNIA, our method achieves comparable results in terms of convergence, diversity metrics, and computational time.     

Network service scheduling and routing

Real‐life vehicle routing problems generally have both routing and scheduling aspects to consider. Although this fact is well acknowledged, few heuristic methods exist that address both these complicated aspects simultaneously. We present a graph theoretic heuristic to determine an efficient service route for a single service vehicle through a transportation network that requires a subset of its edges to be serviced, each a specified (potentially different) number of times. The times at which each of these edges are to be serviced should additionally be as evenly spaced over the scheduling time window as possible, thus introducing a scheduling consideration to the problem. Our heuristic is based on the tabu search method, used in conjunction with various well‐known graph theoretic algorithms, such as those of Floyd (for determining shortest routes) and Frederickson (for solving the rural postman problem). This heuristic forms the backbone of a decision support system that prompts the user for certain parameters from the physical situation (such as the service frequencies and travel times for each network link as well as bounds in terms of acceptability of results) after which a service routing schedule is suggested as output. The decision support system is applied to a special case study, where a service routing schedule is sought for the South African national railway system by Spoornet (the semi‐privatised South African national railways authority and service provider) as part of their rationalisation effort, in order to remain a lucrative company.