Search

Traditional stochastic programming methods are widely used for solving hydroelectric reservoirs management problems under uncertainty. With these methods, random parameters are described using a scenario tree possessing an unstructured topology. Therefore, traditional methods can potentially handle high-order time-correlation effects, but their computational requirements grow exponentially with the branching level used to represent parameters (e.g., load, inflows, prices). Consequently, random parameters must be discretized very coarsely and, as a result, numerical solutions of mid-term optimization models can be quite sensitive to small perturbations to the tree parameters. In this paper, we propose a new approach for managing high-capacity reservoirs over an extended horizon (1–3 years). We partition the planning horizon in two stages and assume that a memory loss occurs at the end of the first stage. We propose a new Benders decomposition algorithm designed specifically to exploit this simplification. The low memory requirement of our method enables to consider a much higher branching level than would be possible with previous methods. The proposed approach is tested on a 104-week production planning problem with stochastic inflows.

This paper considers timetable design at a European freight railway operator. The timetable is designed by choosing the time of service for customer unit train demands among a set of discrete points. These discrete points are all found within the a time-window. The objective of the model is to minimize cost while adhering to constraints regarding infrastructure usage, demand coverage, and engine availability. The model is solved by a column generation scheme where feasible engine schedules are designed in a label setting algorithm with time-dependent cost and service times. In this paper we consider timetable design at a European freight railway operator. The timetable is designed by choosing the time of service for customer unit train demands among a set of discrete points. These discrete points are all found within the a time-window. The objective of the model is to minimize cost while adhering to constraints regarding infrastructure usage, demand coverage, and engine availability. The model is solved by a column generation scheme where feasible engine schedules are designed in a label setting algorithm with time-dependent cost and service times.

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. 654, 367-379 2015

This paper proposes a solution approach based on heuristic methods for a model integrating production planning and maintenance scheduling in imperfect production systems. Performance of population-based heuristics is considerably influenced by the population management tools that are generally aimed to keep the diversity and to force the search process to examine unvisited areas within the solution space. We use genetic algorithm hybridize with a standard tabu search as well as population management strategies to efficiently solve the complicated nonlinear model. Exploiting population data in order to define new solutions from unvisited sections of response space, learning from the population to extract the specifications of promising solutions and maintaining the population diversity are the most important particularities of the proposed approach. Comparing the algorithm with conventional implementation of GA and tabu search, demonstrates its surpassing performance in terms of solution time and quality.

The dairy transportation problem (DTP) consists of determining the best routes to be performed for collecting milk from farms and delivering it to processing plants. We study the particular case of the province of Quebec, where the Fédération des producteurs de lait du Québec is responsible for negotiating the transportation costs on behalf of producers. Several issues are highlighted in the actual process of designing contracts such as using historical data. We propose an approach based on scenario analysis that consists of revising both the steps and the information used to construct the routes. We develop a generalized tabu search algorithm that integrates the different characteristics of the DTP.

In this paper, we address the problem of determining the optimal fleet size for three vehicle routing problems, i.e., multi-depot VRP, periodic VRP and multi-depot periodic VRP. In each of these problems, we consider three kinds of constraints that are often found in reality, i.e., vehicle capacity, route duration and budget constraints. To tackle the problems, we propose a new Modular Heuristic Algorithm (MHA) whose exploration and exploitation strategies enable the algorithm to produce promising results. Extensive computational experiments show that MHA performs impressively well, in terms of solution quality and computational time, for the three problem classes.

a matheuristic based for the VRPCD is proposed.the method is based on large neighborhood search search and branch-and-check.this method improves many best known solutions. The vehicle routing problem with cross-docking (VRPCD) consists in defining a set of routes that satisfy transportation requests between a set of pickup points and a set of delivery points. The vehicles bring goods from pickup locations to a cross-docking platform, where the items may be consolidated for efficient delivery. In this paper we propose a new solution methodology for this problem. It is based on large neighborhood search and periodically solving a set partitioning and matching problem with third-party solvers. Our method improves the best known solution in 19 of 35 instances from the literature.

A multiobjective-model-based predictive control approach is proposed to solve a dynamic pickup and delivery problem in the context of a potential dial-a-ride service implementation. A dynamic objective function including two relevant dimensions, user and operator costs, is considered. Because these two components typically have opposing goals, the problem is formulated and solved using multiobjective model predictive control to provide the dispatcher with a more transparent tool for his/her decision-making process. An illustrative experiment is presented to demonstrate the potential benefits in terms of the operator cost and quality of service perceived by the users.

This paper proposes a state-of-the-art branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands (VRPSD). We adapt the model of Christiansen and Lysgaard [6] and formulate the VRPSD as a set partitioning model with additional constraints. Feasible routes are generated using a dynamic programming algorithm executed over a state-space graph. Our method combines 2-cycle elimination with ng -routes. In addition, our pricing problem is significantly accelerated by the introduction of a new aggregate dominance rule. To speed up the generation of negative reduced cost columns, we use a tabu search heuristic and a bidirectional labeling algorithm. We also add capacity and subset-row inequalities dynamically in order to strengthen the linear relaxation of the master problem. As extensive computational tests illustrate, our algorithm is very competitive with the one of [6] . We solve 20 additional instances from the 40-instance set considered by these authors and we considerably improve the computing times for instances already closed. We also solve 17 new instances from the literature.

This paper describes an exact algorithm for solving a two-dimensional orthogonal packing problem with unloading constraints, which occurs as a subproblem of mixed vehicle routing and loading problems. The packing considered in this work is basically a feasibility problem involving a single bin. The problem is addressed through a decomposition approach wherein a branch-and-cut algorithm is designed for solving a one-dimensional relaxation of the original problem. When an integer solution is found in the branching tree, a subsidiary problem is solved to identify a two-dimensional packing that does not lead to any overlap and satisfies the unloading constraints. Cuts are added when the subsidiary problem proves to be infeasible. Several preprocessing techniques aimed at reducing the size of the solution space and uncovering infeasibility are also described. A numerical comparison with the best known exact method is reported at the end based on benchmark instances.

In order to improve profitability, freight forwarding companies try to organize their operational transportation planning systematically, considering not only their own fleet but also external resources. Such external resources include vehicles from closely related subcontractors in vertical cooperations, autonomous common carriers on the transportation market, and cooperating partners in horizontal coalitions. In this paper, the transportation planning process of forwarders is studied and the benefit of including external resources is analyzed. By introducing subcontracting, the conventional routing of own vehicles is extended to an integrated operational transportation planning, which simultaneously constructs fulfillment plans with overall lowest costs using the own fleet and subcontractors’ vehicles. This is then combined with planning strategies, which intend to increase the profitability by exchanging requests among members in horizontal coalitions. Computational results show considerable cost reductions using the proposed planning approach.

This paper formulates an optimal design model for assembly/disassembly manufacturing networks. The objective is to maximize production rate subject to a total cost constraint. Machines are chosen from a list of products available on the market, and sizes of the buffers are chosen within a predetermined range. Each machine type is characterized by its total cost of ownership, failure rate, repair rate and processing time. The buffers are also characterized by their total cost of ownership coefficients associated with the buffer size. To estimate assembly/disassembly network performance, a decomposition-type approximation is used. The optimal design model is formulated as a combinatorial optimization one in which the decision variables are buffers and types of machines. A genetic algorithm is proposed as an optimization technique. Numerical examples are used to highlight the benefit of selecting simultaneously the buffers and the machines.

This paper addresses the scheduled service network design problem for freight rail transportation. The proposed model integrates service selection and scheduling, car classification and blocking, train makeup, and routing of time-dependent customer shipments based on a cyclic three-layer space–time network representation of the associated operations and decisions and their relations and time dimensions. This paper also proposes a matheuristic solution methodology integrating slope scaling, a dynamic block-generation mechanism, long-term-memory-based perturbation strategies, and ellipsoidal search, a new intensification mechanism to thoroughly explore very large neighborhoods of elite solutions restricted using information from the history of the search. Experimental results show that the proposed solution method is efficient and robust, yielding high-quality solutions for realistically sized problem instances.

This paper studies optimization methods for a routing problem encountered in daily maintenance operations of a road network. Stochastic service and travel times on road segments are considered. The problem is formulated as a variation of the capacitated arc routing problem (CARP). A chance-constrained programming model is firstly developed and solved by a branch-and-cut algorithm. A stochastic programming model with recourse is also proposed to take into account the recourse costs in case of route failure. The problem is solved by an adaptive large neighborhood search algorithm. The computational experiments demonstrate the effectiveness of the algorithm.

In this work, we investigate the Resilient Multi-level Hop-constrained Network Design (RMHND) problem, which consists of designing hierarchical telecommunication networks, assuring resilience against random failures and maximum delay guarantees in the communication. Three mathematical formulations are proposed and algorithms based on the proposed formulations are evaluated. A Branch-and-price algorithm, which is based on a delayed column generation approach within a Branch-and-bound framework, is proven to work well, finding optimal solutions for practical telecommunication scenarios within reasonable time. Computational results show that algorithms based on the compact formulations are able to prove optimality for instances of limited size in the scenarios of interest while the proposed Branch-and-price algorithm exhibits a much better performance.

The vehicle routing problem with multiple routes consists in determining the routing of a fleet of vehicles when each vehicle can perform multiple routes during its operations day. This problem is relevant in applications where the duration of each route is limited, for example when perishable goods are transported. In this work, we assume that a fixed-size fleet of vehicles is available and that it might not be possible to serve all customer requests, due to time constraints. Accordingly, the objective is first to maximize the number of served customers and then, to minimize the total distance traveled by the vehicles. An adaptive large neighborhood search, exploiting the ruin-and-recreate principle, is proposed for solving this problem. The various destruction and reconstruction operators take advantage of the hierarchical nature of the problem by working either at the customer, route or workday level. Computational results on Euclidean instances, derived from well-known benchmark instances, demonstrate the benefits of this multi-level approach.

Volumetric-modulated arc therapy (VMAT) treatment planning is an efficient treatment technique with a high degree of flexibility in terms of dose rate, gantry speed, and aperture shapes during rotation around the patient. However, the dynamic nature of VMAT results in a large-scale nonconvex optimization problem. Determining the priority of the tissues and voxels to obtain clinically acceptable treatment plans poses additional challenges for VMAT optimization. The main purpose of this paper is to develop an automatic planning approach integrating dose-volume histogram (DVH) criteria in direct aperture optimization for VMAT, by adjusting the model parameters during the algorithm. The proposed algorithm is based on column generation, an optimization technique that sequentially generates the apertures and optimizes the corresponding intensities. We take the advantage of iterative procedure in this method to modify the weight vector of the penalty function based on the DVH criteria and decrease the use of trial-and-error in the search for clinically acceptable plans. We evaluate the efficiency of the algorithm and treatment quality using a clinical prostate case and a challenging head-and-neck case. In both cases, we generate 15 random initial weight vectors to assess the robustness of the algorithm. In the prostate case, our methodology obtained clinically acceptable plans in all instances with only a 10% increase in the computational time, while simple VMAT optimization found just three acceptable plans. To have an idea with respect to the existing software, we compared the obtained DVH to a commercial software. The quality of the diagrams of the proposed method, especially for the healthy tissues, is significantly better while the computational time is less. In the head-and-neck case, 93.3% of the clinically acceptable plans are obtained while no plan was acceptable in simple VMAT. In sum, the results demonstrate the ability of the proposed optimization algorithm to obtain clinically acceptable plans without human intervention and also its robustness to weight parameters. Moreover, our proposed weight adjustment procedure proves to reduce the symmetry in the solution space and the time required for the post-optimization phase.

The south coast of Newfoundland (Canada) includes both open sea and semi-enclosed waterways which collectively account for over 20,000 vessel movements annually. Every such movement poses the risk of an oil spill which can endanger the fragile marine life and tourism locales in the region, and is a source of concern to the communities. In an effort to analyze the problem, we present a two-stage stochastic programming approach which tackles both the location and stockpile of equipment at the emergency response facilities. The proposed optimization program was tested on realistic data collected from publicly available reports and through personal communications with emergency response personnel. These data were then varied to solve a number of scenarios which account for the stochastic nature of the problem parameters. Although only two response facilities seem to be appropriate for almost all scenarios, the size of equipment stockpile is a function of both the societal disutility factor and the trade-off between environmental cost and facility and equipment acquisition cost.

The quality of the convergence process in genetic algorithms depends on the specific choice of strategies and combinations of operators. In this paper, we address this problem and introduce an adaptive evolutionary approach that uses a genetic algorithm in an adaptive process. An application of this approach to the dynamic vehicle routing problem with time windows is presented. We compare the adaptive version of a hybrid genetic algorithm with the non-adaptive one with respect to the robustness and the quality of the generated solutions. The results obtained show the ability of our operator combination adaptation approach to produce solutions that are superior to hand-tuning and other adaptive methods with respect to performance sensitivity and robustness.

We address a particular case of the quadratic minimum spanning tree problem in which interaction costs only apply for adjacent edges. Motivated by the fact that Gilmore-Lawler procedures in the literature underestimate the contribution of interaction costs to compute lower bounds, we introduce a reformulation that allows stronger linear programming bounds to be computed. An algorithm based on dynamic column and row generation is presented for evaluating these bounds. Our computational experiments indicate that the reformulation introduced here is indeed much stronger than those in the literature.

This paper solves a particular class of Real Time Vehicle Dispatching Problems where there is need to service some customers with multiple resources subject to synchronization constraints. Real world applications are presented and a flexible heuristic based on Constraint Programming is proposed. In order to facilitate future comparisons, benchmark instances are derived from well-known vehicle routing benchmark instances and a transformation method is detailed. Results on instances containing up to 1000 requests show that solutions are sensitive to the number of synchronization constraints as well as to the requests’ arrival rate.

[1] Among the numerous methods proposed over the past decades for solving reservoir management problems, only a few are applicable on high-dimensional reservoir systems (HDRSs). The progressive hedging algorithm (PHA) was rarely used for managing reservoir systems, but this method is a promising alternative to conventionally used methods for managing HDRSs (e.g., the stochastic dual dynamic programming). The PHA is especially well suited when a new stochastic optimization model must be built upon an existing deterministic optimization model (DOM). In such case, scenario subproblems can be resolved using an existing DOM with minor modifications. In previous studies, the PHA was rarely used and only tested on problems covering short-range planning horizons (2 months with six time periods) where a small number of nonanticipativity constraints (NACs) must be satisfied. Large reservoirs often need to be managed over a much longer planning horizon (1–5 years) containing many tens of time periods. In such case, convergence becomes much more difficult to achieve because of the larger number of NACs to be satisfied. Finding a nonanticipative solution becomes particularly difficult when the input scenarios differ drastically. In this study, we demonstrate the applicability of the PHA for managing HDRSs over long-term (more than a year) horizons in highly uncertain decision environments. We apply the PHA on Hydro-Quebec's reservoir system over a 92 week (period) horizon. We analyze the performance of the PHA for different penalty parameter values. Deterministic solutions are compared to stochastic solutions.

In this paper, we consider a multi-depot periodic vehicle routing problem which is characterized by the presence of a homogeneous fleet of vehicles, multiple depots, multiple periods, and two types of constraints that are often found in reality, i.e., vehicle capacity and route duration constraints. The objective is to minimize total travel costs. To tackle the problem, we propose an efficient path relinking algorithm whose exploration and exploitation strategies enable the algorithm to address the problem in two different settings: (1) As a stand-alone algorithm, and (2) As a part of a co-operative search algorithm called integrative co-operative search. The performance of the proposed path relinking algorithm is evaluated, in each of the above ways, based on standard benchmark instances. The computational results show that the developed PRA performs well, in both solution quality and computational efficiency.

This paper addresses the problem of efficient routing in backbone wireless mesh networks (WMNs) where each mesh router is equipped with multiple radio interfaces and a subset of nodes serve as gateways to the Internet. Most routing schemes have been designed to reduce routing costs by optimizing one metric, e.g., hop count and interference ratio. However, when considering these metrics together, the complexity of the routing problem increases drastically. Thus, an efficient and adaptive routing scheme that takes into account several metrics simultaneously and considers traffic congestion around the gateways is needed. In this paper, we propose an adaptive scheme for routing traffic in WMNs, called Reinforcement Learning-based Distributed Routing (RLBDR), that (1) considers the critical areas around the gateways where mesh routers are much more likely to become congested and (2) adaptively learns an optimal routing policy taking into account multiple metrics, such as loss ratio, interference ratio, load at the gateways and end-to end delay. Simulation results show that RLBDR can significantly improve the overall network performance compared to schemes using either Metric of Interference and Channel switching, Best Path to Best Gateway, Expected Transmission count, nearest gateway (i.e., shortest path to gateway) or load at gateways as a metric for path selection.

We present a synchronized routing and scheduling problem that arises in the forest industry, as a variation of the log-truck scheduling problem. It combines routing and scheduling of trucks with specific constraints related to the Canadian forestry context. This problem includes aspects such as pick-up and delivery, multiple products, inventory stock, multiple supply points and multiple demand points. We developed a decomposition approach to solve the weekly problem in two phases. In the first phase we use a MIP solver to solve a tactical model that determines the destinations of full truckloads from forest areas to woodmills. In the second phase, we make use of two different methods to route and schedule the daily transportation of logs: the first one consists in using a constraint-based local search approach while the second one is a hybrid approach involving a constraint programming based model and a constraint-based local search model. These approaches have been implemented using COMET2.0. The method, was tested on two industrial cases from forest companies in Canada.

The use of iterative auctions is very common in procurement processes, where the market-maker often does not have access to complete and truthful information about the bidders’ private valuations of the resources on sale. The literature on the design of iterative mechanisms for combinatorial auctions has addressed only the most basic cases and has been dominated by primal-dual approaches. In this paper, we consider a general production/consumption exchange of interdependent goods, for which we investigate iterative auction mechanisms based on mathematical programming dual decomposition methods. We focus on Lagrangian relaxation and the solution of the Lagrangian dual through subgradient algorithms and the bundle method. A case study of a simulated wood chip market is used to evaluate numerically the efficiency of the mechanisms.

This paper proposes a new pro-active real-time control approach for dynamic vehicle routing problems in which the urgent delivery of goods is of utmost importance. Without assuming any distribution, stochastic knowledge about future requests is generated using past request information. The generated knowledge is integrated into the transportation process, which is controlled by a Tabu Search algorithm, in order to actively guide vehicles to request-likely areas before requests arrive there. By analyzing the results attained for various test settings, we identify structural diversity as a crucial criterion for classifying the quality of stochastic knowledge attainable from past request information. This criterion provides a promising starting point for assessing the quality of past request information in order to efficiently use the derived stochastic knowledge in real-time control approaches. We prove the efficiency of our approach by a direct comparison with a deterministic approach on test scenarios with varying structural diversity. Thanks to the proposed classification of structural diversity, differences in results obtained among the tested scenarios become explainable.

This paper presents a continuous approximation model to determine the long-term vehicle fleet composition needed to perform distribution activities. The problem is a realistic variant of the vehicle routing problem, in which the fleet size and mix are also decision variables. The types of vehicles differ in terms of their capacities, fixed costs and variable costs. The objective is to minimize the total cost, subject to capacity and route duration constraints. We assume customers are distributed over a circular service region partitioned into zones, each of which is serviced by a single vehicle. The routing costs are assessed through a continuous approximation model. We present a mixed integer non-linear formulation for the problem, followed by computationally efficient upper and lower bounding procedures. The performance of the model and of its bounds is assessed on several test instances.

International audience; The two-echelon vehicle routing problem (2E-VRP) consists in making deliveries to a set of customers using two distinct fleets of vehicles. First-level vehicles pick up requests at a distribution center and bring them to intermediate sites. At these locations, the requests are transferred to second-level vehicles, which deliver them. This paper addresses a variant of the 2E-VRP that integrates constraints arising in city logistics such as time window constraints, synchronization constraints, and multiple trips at the second level. The corresponding problem is called the two-echelon multiple-trip vehicle routing problem with satellite synchronization (2E-MTVRP-SS). We propose an adaptive large neighborhood search to solve this problem. Custom destruction and repair heuristics and an efficient feasibility check for moves have been designed and evaluated on modified benchmarks for the VRP with time windows.

Electric utilities have been using wind power to an increasing extent in order to provide clean energy. However, this resource depends on the intermittency of wind, and this makes balancing supply and demand challenging for the system operator. In this paper we propose a downscaling approach yielding daily probabilistic wind speed scenarios for the turbine hub height, thus making them useful for generating possible wind power scenarios that could be used to maintain the network balance in light of these possible outcomes.

International audience; The reliability of the power plants and transmission lines in the electricity industry is crucial for meeting demand. Consequently, timely maintenance plays a major role reducing breakdowns and avoiding expensive production shutdowns. By now, the literature contains a sound body of work focused on improving decision making in generating units and transmission lines maintenance scheduling. The purpose of this paper is to review that literature. We update previous surveys and provide a more global view of the problem: we study both regulated and deregulated power systems and explore some important features such as network considerations, fuel management, and data uncertainty.

Good Laboratory Practice has been a part of non-clinical research for over 40 years yet. Optimization Research, despite having many papers discussing standards being published over the same period of time, has yet to embrace standards that underpin its research. In this paper we argue the need to adopt standards in optimization research. Building on previous papers, many of which have suggested that the optimiza- tion research community should adopt certain standards, we suggest a concrete set of recommendations that the community should adopt. We also discuss how the proposals in this paper could be progressed.

In this work, we study a supplier selection and routing problem where a fleet of homogeneous vehicles with a predefined capacity is available for procuring different products from different suppliers with the aim to satisfy demand at the minimum traveling and purchasing cost. Decisions are further complicated by the presence of pairwise incompatibility constraints among products, implying the impossibility of loading two incompatible products on the same vehicle. The problem is known as the Multi-Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints. We study the special case in which the demand for each product is unitary and propose a column generation approach based on a Dantzig–Wolfe reformulation of the problem, where each column represents a feasible vehicle route associated with a compatible purchasing plan. To solve the pricing problem we propose a hybrid strategy exploiting the advantages of two alternative exact methods, a labeling algorithm solving a Resource-Constrained Elementary Shortest Path Problem on an expanded graph, and a tailored branch-and-cut algorithm. Due to the integrality request on variables, we embed the column generation in a branch-and-bound framework and propose different branching rules. Extensive tests, carried out on a large set of instances, show that our branch-and-price method performs well, improving on average, both in quality and in computational time, solutions obtained by a state-of-art branch-and-cut approach applied to a three-index connectivity constraints based formulation.

In this paper, we consider a specific variant of the field service routing problem. It consists in determining vehicle routes in a single period to serve two types of customers: mandatory and optional. Mandatory customers have to be served within a specified time window whereas optional customers may be served (or not) within the planning horizon. For more realism, we assume that service as well as travel times are stochastic and also that there are multiple depots. The objective is to visit as many optional customers as possible while minimizing the total travel time. To tackle this problem, we propose a 2-stage solution method: the planning stage and the execution stage. We decompose the planning stage into two phases: the design of a skeleton of mandatory customers and the insertion of optional customers in this skeleton. In the execution stage, we proceed to a real-time modification of the planned routes to face stochastic travel and service times and to enable time windows to be respected. HighlightsWe introduce the field service routing problem with stochastic travel and service times.We propose a two-stage method for solving this new problem.In the planning stage, we build routes with mandatory and then we insert optional customers.In the execution stage, we use dynamic programming algorithms to define the optimal policy to face stochasticity.

Existing approaches for optimal planning of wireless mesh networks (WMNs) deployment revolves around the deployment cost as the pivotal concept to optimize. In this paper, we adopt a new approach to optimize the planning of WMNs that guarantees an acceptable level of network performance prior to its deployment. It is a simultaneous optimization process of network deployment cost and network throughput objectives while taking into account all the parameters that have a significant impact on the network efficiency. We propose three multi-objective models for WMN planning problem, namely Load-Balanced Model, Interference Model, and Flow-Capacity Model. We devise an evolutionary swarm-based algorithm that is a hybrid combination of multi-objective Particle Swarm Optimization (MOPSO) and Genetic Algorithms (GAs) to solve the three models. We use realistic network sizes (up to 100 mesh nodes) to perform a thorough comparative experimental study on these three instance models with different key-parameter settings. Finally, we use the network simulator OMNET++ to evaluate the three models in terms of the actual performance (network throughput). The results presented in this paper show that Load-Balanced Model totally supersedes the Flow-Capacity Model and performs better than the Interference Model.

We propose an algorithmic framework that successfully addresses three vehicle routing problems: the multidepot VRP, the periodic VRP, and the multidepot periodic VRP with capacitated vehicles and constrained route duration. The metaheuristic combines the exploration breadth of population-based evolutionary search, the aggressive-improvement capabilities of neighborhood-based metaheuristics, and advanced population-diversity management schemes. Extensive computational experiments show that the method performs impressively in terms of computational efficiency and solution quality, identifying either the best known solutions, including the optimal ones, or new best solutions for all currently available benchmark instances for the three problem classes. The proposed method also proves extremely competitive for the capacitated VRP.

A bilevel procedure for dimensionality reduction makes it possible to discover the underlying global geometry of a complex natural observations dataset-such as human handwriting or faces under different viewing positions-with higher precision than existing methods.

Optimal channel assignment (CA) in multi-radio wireless mesh networks is an NP-hard problem for which solutions usually leave several links interfering. Most of these solutions usually consider the overall throughput as the main optimization objective. However, other objectives have to be considered in order to provide better quality wireless connections to non stationary users. In this paper, we propose a multi-objective optimization model that, besides maximizing throughput, improves fairness and handoff experience of mesh clients. In this model, we use the Jain's index to maximize users' fairness and we allow same-channel assignments to links involved in the same high handoff traffic, thus reducing handoff-triggered re-routing characterized by its high latency. Then, we propose a centralized variable neighborhood search and a Tabu search heuristics to efficiently solve our model as an offline CA process. Moreover, in order to adapt to traffic dynamics caused especially by user handoffs, we propose an online CA scheme that carefully re-assigns channels to interfaces with the purpose of continuously minimizing the re-routing overhead/latency during user handoffs. We further improve this online scheme using load balancing. Simulation results show the good performance of our proposed approach in terms of delay, loss rate, overall throughput and fairness. Particularly, performance results of our online handoff-aware CA show the effectiveness of handoffs not involving path re-routing in decreasing the delay, especially when considering load balancing.

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 © 2012 Wiley Periodicals, Inc.

With the advances in wireless technologies and the explosive growth of the Internet, wireless networks, especially Wireless Mesh Networks (WMNs), are going through an important evolution. Designing efficient WMNs has become a major task for networks operators. Over the last few years, a plethora of studies has been carried out to improve the efficiency of wireless networks. However, only a few studies are related to WMNs design and are mainly concerned with protocol design and routing metrics optimization. In this paper, we survey different aspects of WMNs design and examine various methods that have been proposed either to improve the performance of an already deployed network or to improve its performance by a careful planning of its deployment.

This paper considers a vehicle routing problem where each vehicle performs delivery operations over multiple routes during its workday and where new customer requests occur dynamically. The proposed methodology for addressing the problem is based on an adaptive large neighborhood search heuristic, previously developed for the static version of the problem. In the dynamic case, multiple possible scenarios for the occurrence of future requests are considered to decide about the opportunity to include a new request into the current solution. It is worth noting that the real-time decision is about the acceptance of the new request, not about its service which can only take place in some future routes (a delivery route being closed as soon as a vehicle departs from the depot). In the computational results, a comparison is provided with a myopic approach which does not consider scenarios of future requests.

A proper design of Wireless Mesh Networks (WMNs) is a fundamental task that should be addressed carefully to allow the deployment of scalable and efficient networks. Specifically, choosing strategic locations to optimally place gateways prior to network deployment can alleviate a number of performance/scalability related problems. In this paper, we first, propose a novel clustering based gateway placement algorithm (CBGPA) to effectively select the locations of gateways. Existing solutions for optimal gateway placement using clustering approaches are tree-based and therefore are inherently less reliable since a tree topology uses a smaller number of links. Independently from the tree structure, CBGPA strategically places the gateways to serve as many routers as possible that are within a bounded number of hops. Next, we devise a new multi-objective optimization approach that models WMN topologies from scratch. The three objectives of deployment cost, network throughput and average congestion of gateways are simultaneously optimized using a nature inspired meta-heuristic algorithm coupled with CBGPA. This provides the network operator with a set of bounded-delay trade-off solutions. Comparative simulation studies with different key parameter settings are conducted to show the effectiveness of CBGPA and to evaluate the performance of the proposed model.

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 © 2012 Wiley Periodicals, Inc.

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. © 2011 Wiley Periodicals, Inc.

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 © 2011 Wiley Periodicals, Inc.

In this paper we study the computational complexity of the vehicle routing problem (VRP) and of the split delivery vehicle routing problem (SDVRP) on some special classes of instances, characterized by special structures of the underlying graph, namely a line, a star, a tree and a circle. We both study the problems in the case of unlimited fleet (UF) and under the constraint that a limited fleet is available (LF).

Quality-of-service (QoS) provisioning is an essential feature in next-generation networks. In this paper, we investigate the ability of optical burst switching (OBS) networks to guarantee loss-free transmission inside the network for guaranteed bursts. More specifically, we propose a QoS approach, called path-based QoS provisioning (PQP), to provide absolute QoS provisioning for OBS networks. PQP relies on: 1) routing and wavelength assignment to establish, whenever possible, nonoverlapping paths between each pair of OBS edge nodes and 2) a synchronization scheme to guarantee QoS when the solution in 1) contains overlapping paths because of the limited number of wavelengths. For 1), we propose a routing and wavelength assignment approach, which uses an efficient integer linear programming (ILP) model to determine routing paths and a tabu search algorithm to assign wavelengths to these paths. For 2), we propose a path synchronization scheme, called path-based synchronous transmission scheme (PST). PST synchronizes the transmissions in each set of overlapping paths while maximizing the capacity of each path to transmit guaranteed traffic and guaranteeing fairness when allocating bandwidth to conflicting paths; this is performed using efficient ILP formulations. To improve the performance of best effort traffic and preserve statistical multiplexing gain and high resource utilization of the OBS network, we propose a wavelength selection scheme, called path-based best effort wavelength selection scheme, to send best effort bursts. Simulation results using ns-2 simulator show that PQP successfully provides absolute QoS provisioning for guaranteed traffic and improves significantly the performance of best effort traffic.

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 node failures. Reliability and deployment cost are important and are largely determined by network topology. In fact, adding redundant network components increases the reliability of a network, but also increases the cost substantially. 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 tight relationship between network deployment cost, performance and reliability in a simultaneous optimization in terms of cost and traffic load balancing over network channels. The proposed multi-objective optimization model is solved using meta-heuristics which provides the network operator with a set of reliable tradeoff solutions.

In this paper, we introduce a variant of the orienteering problem in which travel and service times are stochastic. If a delivery commitment is made to a customer and is completed by the end of the day, a reward is received, but if a commitment is made and not completed, a penalty is incurred. This problem reflects the challenges of a company who, on a given day, may have more customers than it can serve. In this paper, we discuss special cases of the problem that we can solve exactly and heuristics for general problem instances. We present computational results for a variety of parameter settings and discuss characteristics of the solution structure.

Railroad transportation of hazardous materials did not receive as much attention as highway transportation in the academic literature, although comparable volumes are shipped via these two transport modes in North America and Europe. In this paper, we present an optimization methodology for the railroad tactical planning problem with risk and cost objectives. We determine the routes to be used for each shipment, the yard activities, and the number of trains of different types needed in the network. The transport risk assessment component of our model incorporates the differentiating characteristics of railroad operations. We develop a memetic algorithm-based solution methodology, which combines genetic and local searches, to solve the biobjective model. The railroad infrastructure in the midwestern United States is used as a basis for generating problem instances of the size encountered in real life. Our analyses of the solutions of instances indicate that it is possible to achieve significant reductions in population exposure without incurring unacceptable increases in operational costs.