The fog-computing paradigm provides low-latency processing and storage between Internet of Things (IoT) applications and cloud data centers. Normal IoT activity may produce infrequent yet substantial spikes in user traffic, which would require a large static fog infrastructure to service. Instead, we consider the viability of having a smaller static fog infrastructure, and supplementing additional traffic spikes with fog-enabled uncrewed aerial vehicles (fog-UAVs). This article formulates the optimal design and dimensioning of fog-UAVs and fog-UAV charging/deployment stations as a probabilistic location set covering problem (PLSCP). We model the fog-UAV PLSCP as a mixed-integer linear program (MILP), from which we derive several relaxed models, including one based on the Benders decomposition technique. Finally, we simulate our models over a set of city-wide IoT hotspots with various traffic percentile thresholds, and evaluate our results.

ABSTRACT E‐commerce operations are essentially online, with customer orders arriving dynamically. However, very little is known about the performance of online policies for warehousing with respect to optimality, particularly for order picking and batching operations, which constitute a substantial portion of the total operating costs in warehouses. We aim to close this gap for one of the most prominent dynamic algorithms, namely reoptimization (Reopt), which reoptimizes the current solution each time a new order arrives. We examine Reopt in the Online Order Batching, Sequencing, and Routing Problem (OOBSRP), in both cases when the picker uses either a manual pushcart or a robotic cart. Moreover, we examine the non‐interventionist Reopt in the case of a manual pushcart, wherein picking instructions are provided exclusively at the depot. We establish analytical performance bounds employing worst‐case and probabilistic analysis. We demonstrate that, under generic stochastic assumptions, Reopt is almost surely asymptotically optimal and, notably, we validate its near‐optimal performance in computational experiments across a broad range of warehouse settings. These results underscore Reopt's relevance as a method for online warehousing applications.

A capacitated vehicle routing problem with two-dimensional loading constraints is addressed. Associated with each customer are a set of rectangular items, the total weight of the items, and a time window. Designing exact algorithms for the problem is very challenging because the problem is a combination of two NP-hard problems. An exact branch-and-price algorithm and an approximate counterpart are proposed to solve the problem. We introduce an exact dominance rule and an approximate dominance rule. To cope with the difficulty brought by the loading constraints, a new column generation mechanism boosted by a supervised learning model is proposed. Extensive experiments demonstrate the superiority of integrating the learning model in terms of CPU time and calls of the feasibility checker. Moreover, the branch-and-price algorithms are able to significantly improve the solutions of the existing instances from literature and solve instances with up to 50 customers and 103 items. Summary of Contribution: We wish to submit an original research article entitled “Learning-based branch-and-price algorithms for a vehicle routing problem with time windows and two-dimensional loading constraints” for consideration by IJOC. We confirm that this work is original and has not been published elsewhere, nor is it currently under for publication elsewhere. In this paper, we report a study in which we develop two branch-and-price algorithms with a machine learning model injected to solve a vehicle routing problem integrated the two-dimensional packing. Due to the complexity brought by the integration, studies on exact algorithms in this field are very limited. Our study is important to the field, because we develop an effective method to significantly mitigate computational burden brought by the packing problem so that exactness turns to be achievable within reasonable time budget. The approach can be generalized to the three-dimensional case by simply replacing the packing algorithm. It can also be adapted for other VRPs when high-dimensional loading constraints are concerned. Broadly speaking, the study is a typical example of adopting supervised learning to achieve acceleration for operations research algorithms, which expands the envelop of computing and operations research. Hence, we believe this manuscript is appropriate for publication by IJOC.

Internet of Things (IoT) applications depend on reliable external storage and processing such as cloud data centers. In response to high latency from cloud, fog computing has been introduced as a network of microdata centers closer to IoT devices that provides a geo-distributed low-latency response. Current contributions regarding design and dimensioning of fog infrastructures are developed to service a static set of IoT traffic and a reliable fog network. However, these designs are not fault tolerant. This article explores the implementation of reliable and fault-tolerant fog infrastructures via dynamically available fog nodes—standby nodes that activate when a nearby fog node fails. We formulate the design and dimensioning of dynamically available nodes as a set partitioning problem, which is solved via a mixed-integer linear program (MILP). This MILP formulation proves to be intractable; we therefore introduce a column generation approach to increase scalability with little loss to optimal design and dimensioning cost. Compared to other benchmark heuristic methods, our column generation approach yields reduced cost, with proportional solution time.

Stochastic block models (SBMs) are often used to find assortative community structures in networks, such that the probability of connections within communities is higher than in between communities. However, classic SBMs are not limited to assortative structures. In this study, we discuss the implications of this model-inherent indifference towards assortativity or disassortativity, and show that this characteristic can lead to undesirable outcomes for networks which are presupposedy assortative but which contain a reduced amount of information. To circumvent this issue, we introduce a constrained SBM that imposes strong assortativity constraints, along with efficient algorithmic approaches to solve it. These constraints significantly boost community recovery capabilities in regimes that are close to the information-theoretic threshold. They also permit to identify structurally-different communities in networks representing cerebral-cortex activity regions.

In this article, we address a real life optimization problem, the rail track inspection scheduling problem. This problem consists of scheduling railway network inspection tasks. The objective is to minimize the total deadhead distance while performing all inspection tasks. Different 0–1 integer formulations for the problem are presented. A heuristic based on both Benders and Dantzig‐Wolfe decompositions is proposed to solve this rich arc routing problem. Its performance is analyzed on a real life dataset provided by the French national railway company. The proposed algorithm is compared to a dynamic programming‐based heuristic. Its ability to schedule the inspection tasks of 1 year on a sparse graph with thousand nodes and arcs is assessed. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(1), 40–56 2015

The quadratic minimum spanning tree problem (QMSTP) consists of finding a spanning tree of a graph G such that a quadratic cost function is minimized. In its adjacent only version (AQMSTP), interaction costs only apply for edges that share an endpoint. Motivated by the weak lower bounds provided by formulations in the literature, we present a new linear integer programming formulation for AQMSTP. In addition to decision variables assigned to the edges, it also makes use of variables assigned to the stars of G. In doing so, the model is naturally linear (integer), without the need of implementing usual linearization steps, and its linear programming relaxation better estimates the interaction costs between edges. We also study a reformulation derived from the new model, obtained by projecting out the decision variables associated with the stars. Two exact solution approaches are presented: a branch‐and‐cut‐and‐price algorithm, based on the first formulation, and a branch‐and‐cut algorithm, based on its projection. Our computational results indicate that the lower bounds introduced here are much stronger than previous bounds in the literature. Being designed for the adjacent only case, our duality gaps are one order of magnitude smaller than the Gilmore–Lawler lower bounds for AQMSTP. As a result, the two exact algorithms introduced here outperform the previous exact solution approaches in the literature. In particular, the branch‐and‐cut method we propose managed to solve AQMSTP instances with as many as 50 vertices to proven optimality. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 367–379 2015

Timing problems involve the choice of task execution dates within a predetermined processing sequence, and under various additional constraints or objectives such as time windows, time‐dependent costs, or flexible processing times, among others. Their efficient resolution is critical in branch and bound and neighborhood search methods for vehicle routing, project and machine scheduling, as well as in various applications in network optimization, resource allocation, and statistical inference. Timing‐related problems have been studied for years, yet research on this subject suffers from a lack of consensus, and most knowledge is scattered among operations research and applied mathematics domains. This article introduces a classification of timing problems and features, as well as a unifying multidisciplinary analysis of timing algorithms. In relation to frequent application cases within branching schemes or neighborhood searches, the efficient resolution of series of similar timing subproblems is also analyzed. A dedicated formalism of reoptimization “by concatenation” is introduced to that extent. The knowledge developed through this analysis is valuable for modeling and algorithmic design, for a wide range of combinatorial optimization problems with time characteristics, including rich vehicle routing settings and emerging nonregular scheduling applications, among others. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(2), 102–128 2015

Thanks to their flexibility and their simple installation, Wireless Mesh Networks (WMNs) allow a low cost deployment of a network infrastructure. They can be used to extend the wired network coverage allowing connectivity anytime and anywhere. Network stability is a key performance metric in supporting real time communication over the network. Because of high bandwidth demand and dynamic traffic variation, several paths in WMNs are expected to be unstable. High levels of network instability can lead to interferences, packet losses and high delays. In this paper, we address the stability problem of WMNs; instability in these networks is caused mainly by link quality fluctuations and frequent route flapping. Indeed, most routing protocols try to optimize a routing metric locally or globally without considering network stability. First, we present the key factors that may cause network instability; then, we propose a new technique, called Local Node Stability-based Routing (LNS), using the entropy function (known as a measure of the uncertainty and the disorder in a system) to define a node stability. Simulation results show that the stability can be improved in WMNs using LNS compared to other routing schemes namely RLBDR, MIC and ETX.

Abstract In the swapping problem (SP), every vertex of a complete graph may supply and demand an object of a known type. A vehicle of unit capacity starting and ending its tour at an arbitrary vertex is available for carrying objects of given types between vertices. The SP consists of determining a minimum cost route that allows the vehicle to satisfy every supply and demand. This article investigates the preemptive version of the SP in which the objects are allowed to be dropped at temporary locations along the route. The problem is modeled as a mixed integer linear program which is solved by branch‐and‐cut. Computational results on random geometric instances containing up to 100 vertices and eight object types are reported. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Abstract This article studies the pickup and delivery traveling salesman problem with multiple stacks. The vehicle contains a number of (horizontal) stacks of finite capacity for loading items from the rear of the vehicle. Each stack must satisfy the last‐in‐first‐out constraint that states that any new item must be loaded on top of a stack and any unloaded item must be on top of its stack. A branch‐and‐cut algorithm is proposed for solving this problem. Computational results are reported on different types of randomly generated instances as well as on classical instances for some well‐known special cases of the problem. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

Abstract This article studies a single vehicle pickup and delivery problem with loading constraints. In this problem, the vehicle contains a number of (horizontal) stacks of finite capacity for loading items from the rear of the vehicle. Each stack must satisfy a last‐in‐first‐out constraint where any new item must be loaded on top of a stack and any unloaded item must be on top of its stack. A large neighborhood search is proposed for solving this problem. Computational results are reported on different types of randomly generated instances. Results are also reported on benchmark instances for two special cases of our problem and a comparison is provided with state‐of‐the‐art methods. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

We propose two adaptive variants of a multiple neighborhood iterated local search algorithm. These variants employ online learning techniques, also called adaptive operation selection, in order to select which perturbation to apply at each iteration step from a set of available move operators. Using a common software interface (the HyFlex framework), the proposed algorithms are tested across four hard combinatorial optimisation problems: permutation flow shop, 1D bin packing, maximum satisfiability, and personnel scheduling (including instance data from real-world industrial applications). Using the HyFlex framework, exactly the same high level search strategy can be applied to all the domains and instances. Our results confirm that the adaptive variants outperform a baseline iterated local search with uniform random selection of the move operators. We argue that the adaptive algorithms proposed are general yet powerful, and contribute to the goal of increasing the generality and applicability of heuristic search.

Abstract This article considers the swapping problem on a tree. In this problem at most one object of some type is available at each vertex, and each vertex also requests at most one object of a given type. The total demand and the total supply of each object type are identical. The problem is to determine a minimum cost routing plan starting and ending at a prespecified vertex which is the depot, for a single vehicle of unit capacity and m object types, so that all vertex requests are satisfied. We consider the preemptive mode in which objects may be temporarily dropped along the way. It is shown that this problem is NP‐hard. A heuristic with a worst‐case performance ratio of 1.5 is developed. Finally, it is shown that the case where m = 1 is polynomially solvable. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Abstract We consider the stochastic fixed‐charge capacitated multicommodity network design (S‐CMND) problem with uncertain demand. We propose a two‐stage stochastic programming formulation, where design decisions make up the first stage, while recourse decisions are made in the second stage to distribute the commodities according to observed demands. The overall objective is to optimize the cost of the first‐stage design decisions plus the total expected distribution cost incurred in the second stage. To solve this formulation, we propose a metaheuristic framework inspired by the progressive hedging algorithm of Rockafellar and Wets. Following this strategy, scenario decomposition is used to separate the stochastic problem following the possible outcomes, scenarios, of the random event. Each scenario subproblem then becomes a deterministic CMND problem to be solved, which may be addressed by efficient specialized methods. We also propose and compare different strategies to gradually guide scenario subproblems to agree on the status of design arcs and aim for a good global design. These strategies are embedded into a parallel solution method, which is numerically shown to be computationally efficient and to yield high‐quality solutions under various problem characteristics and demand correlations. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011.

In this paper we address a real world optimisation problem, the Rail Track Inspection Scheduling Problem (RTISP). This problem consists of scheduling network inspection tasks. The objective is to minimise total deadhead distance. A mixed integer formulation of the problem is presented. A column generation based algorithm is proposed to solve this rich arc routing problem. Its performance is analysed by benchmarking a real world dataset from the French national railway company (SNCF). The efficiency of the algorithm is compared to an enhanced greedy algorithm. Its ability to schedule one year of inspection tasks on a sparse graph with thousand nodes, arcs and edges is assessed.

An important challenge within hyper-heuristic research is to design search methodologies that work well, not only across different instances of the same problem, but also across different problem domains. This article conducts an empirical study involving three different domains in combinatorial optimisation: bin packing, permutation flow shop and personnel scheduling. Using a common software interface (HyFlex), the same algorithms (high-level strategies or hyper-heuristics) can be readily run on all of them. The study is intended as a proof of concept of the proposed interface and domain modules, as a benchmark for testing the generalisation abilities of heuristic search algorithms. Several algorithms and variants from the literature were implemented and tested. From them, the implementation of iterated local search produced the best overall performance. Interestingly, this is one of the most conceptually simple competing algorithms, its advantage as a robust algorithm is probably due to two factors: (i) the simple yet powerful exploration/exploitation balance achieved by systematically combining a perturbation followed by local search; and (ii) its parameter-less nature. We believe that the challenge is still open for the design of robust algorithms that can learn and adapt to the available low-level heuristics, and thus select and apply them accordingly.

Optical Burst Switching (OBS) networks are candidate to play an important role in next generation optical networks. Routing and wavelength assignment may have a decisive impact on the performance of these all-optical networks. We propose a novel Integer Linear Programming (ILP) formulation for the routing problem which is, at the contrast of existing models, specific to the nature of OBS networks and is based on the network topology. To resolve efficiently this model, we propose a genetic algorithm. Also, we propose a wavelength assignment heuristic which uses the solution of the routing optimization model. Simulation results show the effectiveness of our model in improving the performance of OBS networks.

Channel assignment schemes in Multi-Radio Wireless Mesh Networks (MR-WMNs) usually leave several links sharing the same channel within overlapped transmissions or interference ranges; this is especially true when only one radio is used or when the number of radios is very small compared to the number of orthogonal channels. In order to further improve MR-WMN performance, especially for mobile multimedia users, we propose a new assignment scheme that takes into account the presence of non uniform handoff traffic besides the non uniform traffic load. In fact, following handoffs of a large number of mesh clients (MCs), several ongoing flows associated to these clients need to be re-routed along other paths through other mesh routers (MRs). Re-routing that involves MRs (e.g., second-hop MR) further first-hop MRs will result in a much higher service disruption (i.e., data losses), during handoff, than one that involves only first-hop MR due to much bigger re-routing latency. This is not acceptable for real-time multimedia flows. Therefore, in this paper, we propose a dynamic scheme that carefully re-assigns channels to interfaces with the purpose of limiting the re-routing overhead/latency during client handoffs. The proposed scheme chooses a channel re-assignment that achieves a better load balancing among MRs. Therefore, it increases the capacity of MR-WMNs by accepting more users while satisfying their QoS requirements. Simulation results show that our proposed approach achieves good performance in terms of delay, loss rate and overall throughput.

Channel assignment schemes in Multi-Radio Wireless Mesh Networks (MR-WMNs) usually leave several links sharing the same channel within overlapped transmissions or interference ranges; this is especially true when only one radio is used or when the number of radios is very small compared to the number of orthogonal channels. In this paper, we propose a new multi-objective optimization model for channel assignment (CA) performed during the MR-WMNs planning process. Given the expected traffic demand, the goal is to (1) minimize user handoff overhead; (2) minimize traffic load variances to achieve load balancing; (3) maximize overall throughput; and (4) maximize Jain's fairness index to achieve fairness among mesh clients. We also propose a variable neighborhood search (VNS) meta-heuristic to solve our model. Simulation results show that our proposed approach achieves good performance in terms of delay, loss rate, overall throughput and fairness in the MR-WMNs.

Optical Burst Switching (OBS) is a promising switching paradigm for the next generation Internet. A bufferless OBS network can be implemented simply and cost-effectively without the need for either wavelength converters or optical buffers which are, currently, neither cost-effective nor technologica

Optical Burst Switching (OBS) is a promising switching technology for the next generation all-optical networks. An OBS network without wavelength converters and fiber delay lines can be implemented simply and cost-effectively using the existing technology. However, this kind of networks suffers from a relatively high burst loss probability at the OBS core nodes. To overcome this issue and consolidate OBS networks with QoS provisioning capabilities, we propose an absolute QoS differentiation scheme, called Absolute Fair Quality of service Differentiation (AFQD), which is based on a wavelength partitioning scheme, called Optimization Topology-aware Wavelength Partitioning scheme (OTWP). AFQD is the first absolute QoS provisioning scheme that guarantees loss-free transmission for high priority traffic inside the OBS network. Simulation results show that AFQD not only guarantees loss-free transmission for high priority traffic but also substantially decreases the loss probability of best effort traffic to a remarkable level compared to the existing schemes.

In the design of wireless mesh networks (WMNs), one of the fundamental considerations is the reliability and availability of communication paths between network pairs in the presence of nodes failure. The reliability and deployment cost are important and are largely determined by network topology. Usually, network performance and reliability are considered separately. In this paper, we propose a new algorithm based on ear decomposition for constructing reliable WMN infrastructure that resists the failure of a single mesh node and ensures full coverage to all mesh clients (MCs). Via a case study, we show the tied relationship between network deployment cost, performance and reliability in a simultaneous optimization of cost and load balance over network channels. The optimization model proposed is solved using metaheuristics which provides the network operator with a set of reliable tradeoff solutions.

Applications using grid computing infrastructure usually require resources allocation to satisfy their quality of service (QoS) requirements. Given that the grid infrastructure is a set of computing resources geographically distributed, the support of grid applications requires the allocation of computing resources and bandwidth to enable communication among these resources. The objective is to accommodate as many applications as possible while still satisfying their requirements. Ideally, we would like to accommodate a given Grid application using a set of computing resources (e.g., one server) that are not geographically distributed (e.g., in the same LAN); however, this is not always possible. Indeed, to increase the probability of accommodating grid applications, we may need to use computing resources scattered all over the network; in this case, bandwidth allocation is required to enable communication among these resources. In this paper, we propose an optimization model that enables the "simultaneous" allocation of computing resources and bandwidth for grid application while maximizing the number of grid applications being accommodated. A heuristic is proposed to solve the model with an acceptable response time; simulations show that the proposed approach outperforms existing classical approaches.

Addressing multi-attribute, ldquorichrdquo combinatorial optimization problems in a comprehensive manner presents significant methodological and computational challenges. In this paper, we present an integrative multi-thread cooperative optimization framework that can simultaneously deal with multiple dimensions of a rich problem. We present the basic concepts and detail the design and operating principles of the methodology. We illustrate the framework on a rich combinatorial problem, an extended version of the vehicle routing problem with the duration and capacity constraints as well as time windows, multiple periods and multiple depots.

Choosing strategic locations to optimally place gateways prior to network deployment in wireless mesh networks (WMNs) can alleviate a number of performance related problems; it can also lead to better handling of network scalability. Existing solutions that address the optimal gateway placement problem differ mainly in terms of the set of constraints that the placed gateways has to satisfy; the resulting placements influence, differently, the network quality of service (QoS). In this paper, we study the WMN topology design and we propose a clustering based gateway placement algorithm (CBGPA) that guarantees end-to-end bounded delay communications with a good handling of network scalability. We show, via a case study, that CBGPA is constraints-independent algorithm that can effectively be coupled with a WMN design model; for that, we propose a multi-objective optimization model to design WMNs topologies from scratch. The two objectives of deployment cost and average congestion of gateways are simultaneously optimized in the model. The optimization model proposed is solved using a nature inspired meta-heuristic algorithm coupled with CBGPA, which provides the network operator with a set of bounded-delay tradeoff solutions. A comparative experimental study, using large size networks (up to 169 nodes) and different key parameter settings is conducted to show the effectiveness of CBGPA and to evaluate the performance of the proposed model.

Wireless mesh networks (WMNs) have attracted increasing attention from the research community as a high-performance and low-cost solution to last-mile broadband Internet access. However, it remains an open challenge to provide mesh clients with efficient handoff among different mesh routers. In this paper, we address channel switching efficiency and load balancing capability during the handoff process. More specifically, (1) we introduce the concept of clique into WMNs to handle channel conflicts among neighboring mesh routers and thus achieve scalability; and (2) we propose a dynamic load balancing strategy for the handoff process, which integrates the mechanisms of mesh router selection and traffic admission control. Simulation results show that our proposed approach achieves significant gain in the handoff delay. Moreover, it provides good performance in terms of load balancing, loss rate and overall throughput.

Recently, we proposed a multi-objective approach to optimize the planning of Wireless Mesh Networks (WMNs). Unlike other approaches where the deployment cost is the pivotal concept to optimize under typical network constraints, this approach tends to simultaneously optimize the two objectives of network deployment cost and network throughput. Optimal WMN planning solutions under this approach are more realistic and much preferred by network planners in that they have to be both cost-effective and efficient (the deployment cost is minimized while the throughput is maximized). While the deployment cost objective is straightforward, the throughput objective can be viewed from different perspectives: either minimizing the aggregation of network interferences or maximizing the culmination of the flows over the entire network. Here, we propose a third perspective that maximizes the throughput by balancing the load over the network channels. We perform a thorough comparative experimental study on these three instance models with different key-parameter settings. Preliminary results presented in this paper show that this new proposed model totally supersedes the flow aggregation based model and should be used as a contender to the interference based model.

This paper shows how local branching can be used to accelerate the classical Benders decomposition algorithm. By applying local branching throughout the solution process, one can simultaneously improve both the lower and upper bounds. We also show how Benders feasibility cuts can be strengthened or replaced with local branching constraints. To assess the performance of the different algorithmic ideas presented in this hybrid solution approach, extensive computational experiments were performed on two families of network design problems. Numerical results clearly illustrate their benefits.

Abstract Given an undirected graph with edge costs and vertex prizes, the aim of the Prize Collecting Traveling Salesman Problem (PCTSP) is to find a simple cycle minimizing the total edge cost while collecting at least a minimum amount of prizes. In this article, we present a branch‐and‐cut algorithm to solve the PCTSP. We have adapted and implemented some classical polyhedral results for the PCTSP and derived inequalities from cuts designed for the Orienteering Problem. Computational results on instances with more than 500 vertices are reported. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

A modern wireless network can be neither successfully deployed nor successfully expanded without proper planning. In this paper we consider the wireless mesh network (WMN) planning problem where not much work has been done. We propose a more realistic multi-objective approach to model this problem where the two conflicting objectives of total deployment cost and network throughput are to be optimized while guaranteeing full coverage to all mesh clients. Previous contributions have mainly formulated and solved this problem by using single-objective integer linear programming formulations and exact methods. The main limitation of these approaches resides in their restriction to small sized instances. We propose a population-based meta-heuristic algorithm to solve the problem. This algorithm produces a set of good planning solutions for real-size networks thus enlarging the decision perspective of a network planner. We also discuss the effect of different parameters on the characteristics of the solutions.

Admission control is a key management function in wireless networks, particularly wireless mesh networks (WMNs), in order to support multimedia applications that require quality of service (QoS) guarantees. Even using state of the art schemes to provide QoS, if the amount of traffic in the network is allowed to increase in an uncontrolled manner, network performance will deteriorate significantly degrading the QoS for all network traffic. With admission control, a new flow is admitted only if the QoS requirements of all flows in the network still can be met after the new flow begins. This paper introduces a distributed admission control scheme, called RCAC (routing on cliques admission control) for WMNs. We propose an analytical model that enables computing the appropriate admission ratio to guarantee that the loss rate in the network does not exceed a target value; the model also allows computing end-to-end delay necessary to process flow requests with delay constraints. RCAC achieves scalability since it partitions the network into cliques; only clique heads are involved in the admission control procedure. Simulations, using ns-2, demonstrate that RCAC accepts new incoming flows only when the network target loss rate and end-to-end delay are satisfied and maintains relatively high resource utilization in a dynamic traffic load environment.

Optical burst switching (OBS) is a promising switching paradigm for the next generation Internet. A buffer-less OBS network can be implemented simply and cost-effectively without the need for either wavelength converters or optical buffers which are, currently, neither cost-effective nor technologically mature. However, this type of OBS networks suffers from relatively high loss probability caused by wavelength contentions at core nodes. This issue could prevent or, at least, delay the adoption of OBS networks as a solution for the next generation optical Internet. Deflection routing is one of the contention resolution approaches that have been proposed to tackle this problem. In addition to be cost-effective, it is also efficient in reducing loss probability, especially with low and moderate traffic loads. In this paper, we propose an adaptive reinforcement learning-based deflection routing scheme (RLDRS) which focuses on the route selection issue by choosing the optimal alternative output port in terms of both loss probability and delay when deflection is performed. Moreover, RLDRS limits the number of authorized deflections of each burst in order to reduce the additional traffic caused by deflection routing and to prohibit excessive deflections. Simulation results show that RLDRS reduces effectively loss probability and outperforms shortest path deflection routing (SPDR).

Our goal is to propose a unified/generalized model for the Wireless Mesh Networks (WMNs) design problem taking into account all the parameters that have a significant impact on WMNs. In the WMNs design literature, different studies take into account traffic demand, interference, multi-channel, transmission power, potential locations of wireless routers/gateways and node's characteristics (number of radios/node and number of channels/radio). In this paper, we introduce two new parameters: expansion and reliability. We will focus on refining the WMN design taking into account traffic expansion, geographic expansion and reliability without increasing the investment cost of the design.

A wise network planning becomes the most important phase in determining the network efficiency. In this paper we consider the wireless mesh network (WMN) planning problem where no much work has been done. We propose a new multi-objective optimization model for planning WMNs, where the two conflicting objectives, namely network deployment cost and network channels' interferences, are simultaneously minimized while guaranteeing end- users' full coverage and robust topologies. We also propose a novel performance metric to evaluate the network interference level and a population-based optimization heuristic to solve our model, whereby many WMN planning solutions are provided to the end-planner to choose among. We use realistic-size instances (up to 81) mesh nodes to test our multi-objective optimization model, and discuss the impact of the key parameters on the characteristics of the solutions.

Applications utilizing Grid computing infrastructure usually require resources allocation (e.g., bandwidth and CPU) to satisfy their quality of service (QoS) requirements. Given the dynamic nature of grid computing, QoS support and adaptation must be a high priority to successfully support those applications. In this paper, we present an adaptive resources provisioning scheme that optimizes the resources utilization while satisfying the required QoS. More specifically, it minimizes the request blocking probability and, thus, maximizes the revenues of the infrastructure provider.

The design/planning of WMNs is a key phase before any deployment. Few proposals can be found in the open literature that deals with the design problem; however, they do not take into account all the parameters that have an impact on the outcome of the design and they assume the existence of a physical topology where the location and the characteristics of nodes (e.g., number of channels, number of radios) are fixed.In this paper, we define a generalized model for the WMNs design problem that takes into account all the parameters that have a significant impact on the network (interference, multi-channel, transmission power, etc.), expected traffic, the constraints of the physical environment (potential locations of wireless routers and gateways), etc. To resolve the generalized model, we propose a combination of genetic and tabu search algorithms. The objective is to minimize the cost of the network and its operations while satisfying the requirements.

Abstract This article addresses the well‐known Capacitated Vehicle Routing Problem (CVRP), in the special case where the demand of a customer consists of a certain number of two‐dimensional weighted items. The problem calls for the minimization of the cost of transportation needed for the delivery of the goods demanded by the customers, and carried out by a fleet of vehicles based at a central depot. In order to accommodate all items on the vehicles, a feasibility check of the two‐dimensional packing (2L) must be executed on each vehicle. The overall problem, denoted as 2L‐CVRP, is NP‐hard and particularly difficult to solve in practice. We propose a Tabu Search algorithm, in which the loading component of the problem is solved through heuristics, lower bounds, and a truncated branch‐and‐bound procedure. The effectiveness of the algorithm is demonstrated through extensive computational experiments. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

for the Vehicle Routing Problem with Two-Dimensional Loading Constraints" by M. Gendreau et al., which appeared in the January issue of Networks (Networks 51 (2008), 4-18), the last author's name was misspelled. Silvano Martello's

Design/planning of WMNs is the key phase before any deployment. Few proposals can be found in the open literature that deal with the design problem; moreover, they do not take into account all the parameters that have an impact on the outcome of the design and they assume the existence of a physical topology where the location and the characteristics of nodes (e.g., number of channels, number of radios) are fixed. In this paper, we define a generalized model for the WMNs design problem that takes into account all the parameters that have a significant impact on the network (interference, multi-channel, transmission power, etc.), the requirements of providers (expected amount of traffic/users), the constraints of the physical environment (potential locations of wireless routers, e.g., poles, and gateways, e.g., data centers), etc. The objective is to minimize the cost of the network and its operations while satisfying the requirements. The proposed model is shown to outperform considerably existing solutions.

Abstract In this article, we propose a solution procedure for the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). A relaxed version of this problem in which the path does not have to be elementary has been the backbone of a number of solution procedures based on column generation for several important problems, such as vehicle routing and crew pairing. In many cases relaxing the restriction of an elementary path resulted in optimal solutions in a reasonable computation time. However, for a number of other problems, the elementary path restriction has too much impact on the solution to be relaxed or might even be necessary. We propose an exact solution procedure for the ESPPRC, which extends the classical label correcting algorithm originally developed for the relaxed (nonelementary) path version of this problem. We present computational experiments of this algorithm for our specific problem and embedded in a column generation scheme for the classical Vehicle Routing Problem with Time Windows. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 216–229 2004

The fixed charge capacitated multicommodity network design problem is a well-known problem, of both practical and theoretical significance. This paper presents an efficient procedure to determine tight upper bounds on the optimal solution of realistically sized problem instances. Feasible solutions are obtained by using a tabu search framework that explores the space of the continuous flow variables by combining pivot moves with column generation, while evaluating the actual mixed integer objective. Computational experiments on a large set of randomly generated test problems show that this procedure outperforms the other available methods and is particularly suited to large problem instances with many commodities.

The Steiner Tree Problem (STP) in graphs is a well-known NP-hard problem. It has regained attention due to the introduction of new telecommunication technologies, such as ATM, since it appears as the inherent mathematical structure behind multicast communications. In this paper, we present a tabu search algorithm for the STP in graphs. The main feature of this algorithm is a sophisticated strategy for quickly obtaining a very good solution and powerful diversification mechanisms. Computational results on the benchmark problems of the OR-Library, for which optimal solutions are known, indicate that the proposed algorithm outperforms other recent heuristics. © 1999 John Wiley & Sons, Inc. Networks 34: 162–172, 1999

We consider the problem of optimally swapping objects between N workstations, which we refer to as nodes, located on a line. There are m types of objects, and the set of object-types is denoted by S = {1, ..., m}. Object-type 0 is a dummy type, the null object. Each node v contains one unit of a certain object-type $a_v \in S \cup \{0\}$ and requires one unit of object-type $b_v \in S \cup \{0\}$. We assume that the total supply equals the total demand for each of the object-types separately. A vehicle of unit capacity ships the objects so that the requirements of all nodes are satisfied. The set of object-types is partitioned into two sets: objects that may be temporarily dropped at intermediate nodes before reaching their destination and objects that have to be shipped directly from their origin to their destination. The objective is to design a route that starts and ends at the depot and a feasible assignment of object-types to the route's arcs so that the total distance is minimized. We propose an O(N 2 ) algorithm to compute the optimal solution for this problem.

The Selective Traveling Salesman Problem (STSP) is defined on a graph in which profits are associated with vertices and costs are associated with edges. Some vertices are compulsory. The aim is to construct a tour of maximal profit including all compulsory vertices and whose cost does not exceed a preset constant. We developed several classes of valid inequalities for the symmetric STSP and used them in a branch-and-cut algorithm. Depending on problem parameters, the proposed algorithm can solve instances involving up to 300 vertices. © 1998 John Wiley & Sons, Inc. Networks 32:263–273, 1998

Emerging high-speed networks will support a number of real-time services required by distributed multimedia applications, such as video-on-demand. To support these services, appropriate routing procedures should be used; upon receipt of a request to open a new connection with certain quality of service (QoS) requirements, an appropriate routing procedure calculates an "optimal" route (with respect to a certain cost function) which satisfies the connection requirements. Most existing routing procedures for real-time connections determine routes which satisfy only a subset of QoS requirements and optimize in terms of QoS information (e.g. a route with the smallest end-to-end delay). The authors present a routing procedure which finds a route, if it does exist, which satisfies the whole set of QoS requirements; the route could be optimal in terms of QoS information, money to pay for the utilization of network resources, or network reliability; it is up to the network operator to select the optimization criteria to be used by the routing procedure. They also describe how the proposed routing procedure can be used in ATM environment.

In this paper we present a classification of parallel tabu search metaheuristics based, on the one hand, on the control and communication strategies used in the design of the parallel tabu search procedures, and on the other hand, on how the search space is partitioned. These criteria are then used to review the parallel tabu search implementations described in the literature. The taxonomy is further illustrated by the results of several parallelization implementations of a tabu search procedure for multicommodity location-allocation problems with balancing requirements.

We propose a tabu search heuristic capable of solving three well-known routing problems: the periodic vehicle routing problem, the periodic traveling salesman problem, and the multi-depot vehicle routing problem. Computational experiments carried out on instances taken from the literature indicate that the proposed method outperforms existing heuristics for all three problems. © 1997 John Wiley & Sons, Inc. Networks 30: 105–119, 1997

The Capacitated Shortest Spanning Tree Problem consists of determining a shortest spanning tree in a vertex weighted graph such that the weight of every subtree linked to the root by an edge does not exceed a prescribed capacity. We propose a tabu search heuristic for this problem, as well as dynamic data structures developed to speed up the algorithm. Computational results on new randomly generated instances and on instances taken from the literature indicate that the proposed approach produces high-quality solutions within reasonable computing times. © 1997 John Wiley & Sons, Inc. Networks 29: 161–171, 1997

Abstract In this work, the following location problem is analyzed. Let N = (V,E) be an undirected connected simple network, where V is the vertex set, |V| = n and E is the edge set. There is a nonnegative demand wj associated with every vertex uj. It is assumed that every edge (ui,uj) has a probability of failure pij and that failures can never occur on two edges simultaneously. The problem consists of locating p facilities on the network so that the total expected demand disconnected from the facilities is minimized. This problem occurs naturally in the fields of computer and telecommunications networks. A number of important results are proved. First, there always exists a solution in which all facilities are located at vertices. Second, the problem can always be solved optimally on the so‐called leaf‐tree associated with the network. Third, when p = 1, the problem is a 1‐median problem. When p > 1, there always exists an optimal solution for which all facilities are located at pendent vertices of the tree. Finally, when p > 2, the problem with p + 1 facilities can be solved in a greedy fashion, starting from a solution to the problem with p facilities. An exact algorithm for this problem is described. It can be executed in either O(np + |E|) time or in O(n log n + |E|) time. A numerical example is provided.

A reliability measure that takes into account routing and rerouting policies after failures as well as the capacity of the network to satisfy its demand is proposed. The measure, based on the evaluation of the lost call traffic, needs resolution of a routing model for the states of perfect functioning as well as the most probable failure states. A type of routing model useful for network planning is also proposed. The model is closer to reality and easier to implement than the other classical multicommodity formulations. A convex-simplex implementation with a reoptimization feature explicitly adapted to the proposed model is used.>

A general mathematical model for a network design problem with reliability constraints and a revised formulation which seems particularly appropriate for fiber-optics networks is presented. Upper and lower bounding procedures based on continuous relaxations of this modified formulation are described. Preliminary computational results are reported. Limited computational results indicate a good performance of the algorithm, producing a gap between lower and upper bounds that is sufficiently small for a branch-and-bound procedure to be applicable.>