Home About us Contact
|
Home About us Contact | ||
|
|
||
Routing Problem (routing + problem)
Kinds of Routing Problem Selected AbstractsGPSPA: a new adaptive algorithm for maintaining shortest path routing trees in stochastic networksINTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 10 2004Sudip Misra Abstract This paper presents a new efficient solution to the Dynamic Shortest Path Routing Problem, using the principles of Generalized Pursuit Learning. It proposes an efficient algorithm for maintaining shortest path routing trees in networks that undergo stochastic updates in their structure. It involves finding the shortest path in a stochastic network, where there are continuous probabilistically based updates in link-costs. In vast, rapidly changing telecommunications (wired or wireless) networks, where links go up and down continuously and rapidly, and where there are simultaneous random updates in link costs, the existing algorithms are inefficient. In such cases, shortest paths need to be computed within a very short time (often in the order of microseconds) by scanning and processing the minimal number of nodes and links. The proposed algorithm, referred to as the Generalized Pursuit Shortest Path Algorithm (GPSPA), will be very useful in this regard, because after convergence, it seems to be the best algorithm to-date for this purpose. Indeed, it has the advantage that it can be used to find the shortest path within the ,statistical' average network, which converges irrespective of whether there are new changes in link-costs or not. Existing algorithms are not characterized by such a behaviour inasmuch as they would recalculate the affected shortest paths after each link-cost update. The algorithm has been rigorously evaluated experimentally, and it has been found to be a few orders of magnitude superior to the algorithms available in the literature. Copyright © 2004 John Wiley & Sons, Ltd. [source] Classical and modern heuristics for the vehicle routing problemINTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 4-5 2000G. Laporte Abstract This article is a survey of heuristics for the Vehicle Routing Problem. It is divided into two parts: classical and modern heuristics. The first part contains well-known schemes such as, the savings method, the sweep algorithm and various two-phase approaches. The second part is devoted to tabu search heuristics which have proved to be the most successful metaheuristic approach. Comparative computational results are presented. [source] The one-commodity pickup-and-delivery traveling salesman problem: Inequalities and algorithmsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2007Hipólito Hernández-Pérez Abstract This article concerns the "One-commodity Pickup-and-Delivery Traveling Salesman Problem" (1-PDTSP), in which a single vehicle of fixed capacity must either pick up or deliver known amounts of a single commodity to a given list of customers. It is assumed that the product collected from the pickup customers can be supplied to the delivery customers, and that the initial load of the vehicle leaving the depot can be any quantity. The problem is to find a minimum-cost sequence of the customers in such a way that the vehicle's capacity is never exceeded. This article points out a close connection between the 1-PDTSP and the classical "Capacitated Vehicle Routing Problem" (CVRP), and it presents new inequalities for the 1-PDTSP adapted from recent inequalities for the CVRP. These inequalities have been implemented in a branch-and-cut framework to solve to optimality the 1-PDTSP that outperforms a previous algorithm (Hernández-Pérez and Salazar-González, Discrete Appl Math 145 (2004), 126,139). Larger instances (with up to 100 customers) are now solved to optimality. The classical "Traveling Salesman Problem with Pickups and Deliveries" (TSPPD) is a particular case of the 1-PDTSP, and this observation gives an additional motivation for this article. The here-proposed algorithm for the 1-PDTSP was able to solve to optimality TSPPD instances with up to 260 customers. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 258,272 2007 [source] Exact methods based on node-routing formulations for undirected arc-routing problemsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2006R. Baldacci Abstract This article proposes a new transformation of undirected arc-routing problems into equivalent node-routing problems, with emphasis on the transformation of Capacitated Arc Routing Problems (CARP) into Capacitated Vehicle Routing Problems (CVRP). For this last case, an analogue transformation has already been proposed in Pearn et al., where each required CARP edge is mapped onto a triplet of CVRP nodes. In our case, only two CVRP nodes are needed for every CARP required edge. The transformed instances have a structure and a dimension that make most CARP benchmarks solvable by state of the art CVRP techniques. We thus propose a general purpose transformation of arc into node-routing problems and new results on lower bounds and exact methods for CARP instances. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 47(1), 52,60 2006 [source] k -Splittable delay constrained routing problem: A branch-and-price approachNETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2010Jérôme Truffot Abstract Routing problems, which include a QoS-based path control, play a key role in broadband communication networks. We analyze here an algorithmic procedure based on branch-and-price algorithm and on the flow deviation method to solve a nonlinear k -splittable flow problem. The model can support end-to-end delay bounds on each path and we compare the behavior of the algorithm with and without these constraints. The trade-off between QoS guarantees and CPU time is clearly established and we show that minimizing the average delay on all arcs will yield solutions close to the optimal one at a significant computational saving. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010 [source] A bicriterion approach for routing problems in multimedia networksNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2003João C. N. Clímaco Abstract Routing problems in communication networks supporting multiple services, namely, multimedia applications, involve the selection of paths satisfying multiple constraints (of a technical nature) and seeking simultaneously to "optimize" the associated metrics. Although traditional models in this area are single-objective, in many situations, it is important to consider different, eventually conflicting, objectives. In this paper, we consider a bicriterion model dedicated to calculating nondominated paths for specific traffic flows (associated with video services) in multiservice high-speed networks. The mathematical formulation of the problem and the bicriterion algorithmic approach developed for its resolution are presented together with computational tests regarding an application to video-traffic routing in a high-speed network. The algorithmic approach is an adaptation of recent work by Ernesto Martins and his collaborators, namely, the MPS algorithm. © 2003 Wiley Periodicals, Inc. [source] Implicit schemes with large time step for non-linear equations: application to river flow hydraulicsINTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN FLUIDS, Issue 6 2004J. Burguete Abstract In this work, first-order upwind implicit schemes are considered. The traditional tridiagonal scheme is rewritten as a sum of two bidiagonal schemes in order to produce a simpler method better suited for unsteady transcritical flows. On the other hand, the origin of the instabilities associated to the use of upwind implicit methods for shock propagations is identified and a new stability condition for non-linear problems is proposed. This modification produces a robust, simple and accurate upwind semi-explicit scheme suitable for discontinuous flows with high Courant,Friedrichs,Lewy (CFL) numbers. The discretization at the boundaries is based on the condition of global mass conservation thus enabling a fully conservative solution for all kind of boundary conditions. The performance of the proposed technique will be shown in the solution of the inviscid Burgers' equation, in an ideal dambreak test case, in some steady open channel flow test cases with analytical solution and in a realistic flood routing problem, where stable and accurate solutions will be presented using CFL values up to 100. Copyright © 2004 John Wiley & Sons, Ltd. [source] Hybrid adaptive predictive control for a dynamic pickup and delivery problem including traffic congestionINTERNATIONAL JOURNAL OF ADAPTIVE CONTROL AND SIGNAL PROCESSING, Issue 2 2008Cristián E. Cortés Abstract This paper presents a hybrid adaptive predictive control approach to incorporate future information regarding unknown demand and expected traffic conditions, in the context of a dynamic pickup and delivery problem with fixed fleet size. As the routing problem is dynamic, several stochastic effects have to be considered within the analytical expression of the dispatcher assignment decision objective function. This paper is focused on two issues: one is the extra cost associated with potential rerouting arising from unknown requests in the future, and the other is the potential uncertainty in travel time coming from non-recurrent traffic congestion from unexpected incidents. These effects are incorporated explicitly in the objective function of the hybrid predictive controller. In fact, the proposed predictive control strategy is based on a multivariable model that includes both discrete/integer and continuous variables. The vehicle load and the sequence of stops correspond to the discrete/integer variable, adding the vehicle position as an indicator of the traffic congestion conditions. The strategy is analyzed under two scenarios. The first one considers a predictable congestion obtained using historical data (off-line method) requiring a predictive model of velocities distributed over zones. The second scenario that accepts unpredictable congestion events generates a more complex problem that is managed by using both fault detection and isolation and fuzzy fault-tolerant control approaches. Results validating these approaches are presented through a simulated numerical example. Copyright © 2007 John Wiley & Sons, Ltd. [source] An efficient pursuit automata approach for estimating stable all-pairs shortest paths in stochastic network environments,INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 4 2009Sudip Misra Abstract This paper presents a new solution to the dynamic all-pairs shortest-path routing problem using a fast-converging pursuit automata learning approach. The particular instance of the problem that we have investigated concerns finding the all-pairs shortest paths in a stochastic graph, where there are continuous probabilistically based updates in edge-weights. We present the details of the algorithm with an illustrative example. The algorithm can be used to find the all-pairs shortest paths for the ,statistical' average graph, and the solution converges irrespective of whether there are new changes in edge-weights or not. On the other hand, the existing popular algorithms will fail to exhibit such a behavior and would recalculate the affected all-pairs shortest paths after each edge-weight update. There are two important contributions of the proposed algorithm. The first contribution is that not all the edges in a stochastic graph are probed and, even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the final list involving all pairs of nodes in the graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. The second contribution is designing a data structure, the elements of which represent the probability that a particular edge in the graph lies in the shortest path between a pair of nodes in the graph. All the algorithms were tested in environments where edge-weights change stochastically, and where the graph topologies undergo multiple simultaneous edge-weight updates. Its superiority in terms of the average number of processed nodes, scanned edges and the time per update operation, when compared with the existing algorithms, was experimentally established. Copyright © 2008 John Wiley & Sons, Ltd. [source] On the construction of maximum residual energy resource broadcast trees with minimum diameter in static ad hoc wireless networksINTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 1 2006Chor Ping Low Abstract Each node in a wireless ad hoc network runs on a local energy source that has a limited energy life span. Thus, energy conservation is a critical issue in such networks. In addition, it is in general desirable to construct routes with low hop counts as a route with a high hop count is more likely to be unstable (because the probability that intermediate nodes will move away is higher). In this paper, we address these two issues concurrently with energy conservation as the primary objective and low hop count as the secondary objective. One way of addressing the energy conservation issue is to construct routes that maximize the minimum residual battery capacity available among all nodes in each route. A broadcast tree with all routes satisfying this condition is referred to as a maximum residual energy resource broadcast tree. A maximum residual energy resource broadcast tree with the least diameter is referred to as a minimum diameter maximum residual energy resource broadcast tree and the problem of constructing such a tree is referred to as the minimum diameter maximum residual energy resource broadcast routing problem (MDMRERBRP). We propose an algorithm for MDMRERBRP and prove that MDMRERBRP is optimally solvable in polynomial time using the proposed algorithm. Copyright © 2005 John Wiley & Sons, Ltd. [source] Tightest constraint first: An efficient delay sensitive multicast routing algorithmINTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 7 2005Gang FengArticle first published online: 1 APR 200 Abstract As a key issue in multicast routing with quality of service (QoS) support, constrained minimum Steiner tree (CMST) problem has been a research focus for more than a decade, and tens of heuristics have been developed to solve this NP-complete problem. Among all the previously proposed algorithms, the bounded shortest path algorithm (BSMA) (IEEE INFOCOM'95 1995; 1:377,385) have been proved to be capable of producing a multicast tree that has on average the lowest cost. However, such an excellent cost performance is accompanied with an extremely high time complexity. Recently, Feng et al. presented an alternative implementation of BSMA, which makes use of the latest research results on the delay-constrained least cost (DCLC) routing problem. Simulations indicate that, in comparison with the original implementation, the alternative implementation has a much lower time complexity with virtually identical cost performance, and it also runs much faster than many renowned heuristics such as KPP (IEEE/ACM Trans. Networking 1993; 1(3):286,292) and CAO (The design and evaluation of routing algorithms for real-time channels. Technical Report ICSI TR-94-024, International Computer Science Institute, University of California at Berkeley, June 1994). In this paper, we propose a brand new heuristic TCF, which is based on an idea called ,tightest constraint first.' TCF runs a DCLC heuristic only once for each destination and therefore has a provably low time complexity. We further propose an iterative heuristic ITCF, which uses TCF to obtain an initial tree and then gradually refines it. Extensive simulations demonstrate that, in the average sense, TCF can achieve a cost performance comparable to or better than that of BSMA, the cost performance of ITCF is even better than that of TCF, TCF runs approximately twice as fast as ITCF, and ITCF runs 2,4 times as fast as the best implementation of BSMA. Copyright © 2005 John Wiley & Sons, Ltd. [source] A new delay-constrained algorithm for multicast routing tree constructionINTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 10 2004Mohamed Aissa Abstract New multimedia applications provide guaranteed end-to-end quality of service (QoS) and have stringent constraints on delay, delay-jitter, bandwidth, cost, etc. The main task of QoS routing is to find a route in the network, with sufficient resources to satisfy the constraints. Most multicast routing algorithms are not fast enough for large-scale networks and where the source node uses global cost information to construct a multicast tree. We propose a fast and simple heuristic algorithm (EPDT) for delay-constrained routing problem for multicast tree construction. This algorithm uses a greedy strategy based on shortest-path and minimal spanning trees. It combines the minimum cost and the minimum radius objectives by combining respectively optimal Prim's and Dijkstra's algorithms. It biases routes through destinations. Besides, it uses cost information only from neighbouring nodes as it proceeds, which makes it more practical, from an implementation point of view. Copyright © 2004 John Wiley & Sons, Ltd. [source] A JavaÔ universal vehicle router for routing unmanned aerial vehiclesINTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 3 2004R.W. Harder Abstract We consider vehicle routing problems in the context of the Air Force operational problem of routing unmanned aerial vehicles from base locations to various reconnaissance sites. The unmanned aerial vehicle routing problem requires consideration of heterogeneous vehicles, vehicle endurance limits, time windows, and time walls for some of the sites requiring coverage, site priorities, and asymmetric travel distances. We propose a general architecture for operational research problems, specified for vehicle routing problems, that encourages object-oriented programming and code reuse. We create an instance of this architecture for the unmanned aerial vehicle routing problem and describe the components of this architecture to include the general user interface created for the operational users of the system. We employ route building heuristics and tabu search in a symbiotic fashion to provide a user-defined level-of-effort solver interface. Empirical tests of solution algorithms parameterized for solution speed reveal reasonable solution quality is attained. [source] Classical and modern heuristics for the vehicle routing problemINTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 4-5 2000G. Laporte Abstract This article is a survey of heuristics for the Vehicle Routing Problem. It is divided into two parts: classical and modern heuristics. The first part contains well-known schemes such as, the savings method, the sweep algorithm and various two-phase approaches. The second part is devoted to tabu search heuristics which have proved to be the most successful metaheuristic approach. Comparative computational results are presented. [source] Optimal feeder bus routes on irregular street networksJOURNAL OF ADVANCED TRANSPORTATION, Issue 2 2000Steven Chien The methodology presented here seeks to optimize bus routes feeding a major intermodal transit transfer station while considering intersection delays and realistic street networks. A model is developed for finding the optimal bus route location and its operating headway in a heterogeneous service area. The criterion for optimality is the minimum total cost, including supplier and user costs. Irregular and discrete demand distributions, which realistically represent geographic variations in demand, are considered in the proposed model. The optimal headway is derived analytically for an irregularly shaped service area without demand elasticity, with non-uniformly distributed demand density, and with a many-to-one travel pattern. Computer programs are designed to analyze numerical examples, which show that the combinatory type routing problem can be globally optimized. The improved computational efficiency of the near-optimal algorithm is demonstrated through numerical comparisons to an optimal solution obtained by the exhaustive search (ES) algorithm. The CPU time spent by each algorithm is also compared to demonstrate that the near-optimal algorithm converges to an acceptable solution significantly faster than the ES algorithm. [source] Flexibility and complexity in periodic distribution problemsNAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 2 2007Peter Francis Abstract In this paper, we explore trade-offs between operational flexibility and operational complexity in periodic distribution problems. We consider the gains from operational flexibility in terms of vehicle routing costs and customer service benefits, as well as the costs of operational complexity in terms of modeling, solution methods, and implementation challenges for drivers and customers. The period vehicle routing problem (PVRP) is a variation of the classic vehicle routing problem in which delivery routes are constructed for a period of time; the PVRP with service choice (PVRP-SC) extends the PVRP to allow service (visit) frequency to become a decision of the model. For the periodic distribution problems represented by PVRP and PVRP-SC, we introduce operational flexibility levers and a set of quantitative measures to evaluate the trade-offs between flexibility and complexity. We develop a Tabu Search heuristic to incorporate a range of operational flexibility options. We analyze the potential value and the increased operational complexity of the flexibility levers. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007 [source] A branch-and-cut algorithm for the quay crane scheduling problem in a container terminalNAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 1 2006Luigi Moccia Abstract The quay crane scheduling problem consists of determining a sequence of unloading and loading movements for cranes assigned to a vessel in order to minimize the vessel completion time as well as the crane idle times. Idle times originate from interferences between cranes since these roll on the same rails and a minimum safety distance must be maintained between them. The productivity of container terminals is often measured in terms of the time necessary to load and unload vessels by quay cranes, which are the most important and expensive equipment used in ports. We formulate the quay crane scheduling problem as a vehicle routing problem with side constraints, including precedence relationships between vertices. For small size instances our formulation can be solved by CPLEX. For larger ones we have developed a branch-and-cut algorithm incorporating several families of valid inequalities, which exploit the precedence constraints between vertices. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006 [source] k -Splittable delay constrained routing problem: A branch-and-price approachNETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2010Jérôme Truffot Abstract Routing problems, which include a QoS-based path control, play a key role in broadband communication networks. We analyze here an algorithmic procedure based on branch-and-price algorithm and on the flow deviation method to solve a nonlinear k -splittable flow problem. The model can support end-to-end delay bounds on each path and we compare the behavior of the algorithm with and without these constraints. The trade-off between QoS guarantees and CPU time is clearly established and we show that minimizing the average delay on all arcs will yield solutions close to the optimal one at a significant computational saving. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010 [source] A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windowsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2009Eric Prescott-Gagnon Abstract Given a fleet of vehicles assigned to a single depot, the vehicle routing problem with time windows (VRPTW) consists of determining a set of feasible vehicle routes to deliver goods to a set of customers while minimizing, first, the number of vehicles used and, second, total distance traveled. A large number of heuristic approaches for the VRPTW have been proposed in the literature. In this article, we present a large neighborhood search algorithm that takes advantage of the power of branch-and-price which is the leading methodology for the exact solution of the VRPTW. To ensure diversification during the search, this approach uses different procedures for defining the neighborhood explored at each iteration. Computational results on the Solomo's and the Gehring and Homberge's benchmark instances are reported. Compared to the best known methods, the proposed algorithm produces better solutions, especially on the largest instances where the number of vehicles used is significantly reduced. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source] Edge assembly-based memetic algorithm for the capacitated vehicle routing problemNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2009Yuichi Nagata Abstract Vehicle routing problems are at the heart of most decision support systems for real-life distribution problems. In vehicle routing problem a set of routes must be determined at lowest total cost for a number of resources (i.e., fleet of vehicles) located at one or several points (e.g., depots, warehouses) to efficiently service a number of demand or supply points. In this article a new memetic algorithm is suggested for the standard capacitated vehicle routing problem. The proposed algorithm combines the edge assembly (EAX) crossover with well-known local searches and allows for infeasible solutions with respect to capacity and route duration constraints after invoking the crossover. To address the constraint violation, an efficient modification algorithm is also suggested. Experimental tests on 47 standard benchmarks demonstrate that the suggested method is robust and competitive, finding new best-known solution to 20 well-studied instances and repeating the existing best-known solution for 24 problems in a reasonable computing time. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source] The fractional congestion bound for efficient edge disjoint routingNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2008Alok Baveja Abstract This article investigates the following problem: Given the fractional relaxation of the edge disjoint routing problem, how small a fractional congestion is sufficient to guarantee efficient edge disjoint routing? That is, what is the largest possible value v such that a fractional flow with congestion at most v, can be efficiently converted into an edge disjoint routing? Leighton, Lu, Rao, and Srinivasan (SIAM J Comput 2001) have established that fractional congestion of at most the order of O(1/(d log k)) is sufficient, where d is the maximum path length in the fractional relaxation, and k is the number of pairs to be routed. It is also known that ,(1/d) is the correct bound, if we are only interested in an existence result (Leighton, Rao, and Srinivasan, Hawaii International Conference on System Sciences, 1998). Motivated by the fact that d is small for many types of routing problems, specifically, polylogarithmic for expander graphs, this article improves upon the former result by showing O(1/(d log d)) fractional congestion to suffice. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008 [source] Path inequalities for the vehicle routing problem with time windowsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2007Brian Kallehauge Abstract In this paper we introduce a new formulation of the vehicle routing problem with time windows (VRPTW) involving only binary variables. The new formulation is based on the formulation of the asymmetric traveling salesman problem with time windows by Ascheuer et al. (Networks 36 (2000) 69,79) and has the advantage of avoiding additional variables and linking constraints. In the new formulation, time windows are modeled using path inequalities that eliminate time and capacity infeasible paths. We present a new class of strengthened path inequalities based on the polyhedral results obtained by Mak (Ph.D. Thesis, 2001) for a variant of the TSP. We study the VRPTW polytope and determine its dimension. We show that the lifted path inequalities are facet defining under certain assumptions. We also introduce precedence constraints in the context of the VRPTW. Computational experiments are performed with a branch and cut algorithm on the Solomon test problems with wide time windows. Based on results on 25-node problems, the outcome is promising compared to leading algorithms in the literature. In particular, we report a solution to a previously unsolved 50-node Solomon test problem R208. The conclusion is therefore that a polyhedral approach to the VRPTW is a viable alternative to the path formulation of Desrochers et al. (Oper Res 40 (1992), 342,354). © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 273,293 2007 [source] Metaheuristics for the vehicle routing problem with loading constraintsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2007Karl F. Doerner Abstract We consider a combination of the capacitated vehicle routing problem and a class of additional loading constraints involving a parallel machine scheduling problem. The work is motivated by a real-world transportation problem occurring to a wood-products retailer, which delivers its products to a number of customers in a specific region. We solve the problem by means of two different metaheuristics algorithms: a Tabu Search and an Ant Colony Optimization. Extensive computational results are given for both algorithms, on instances derived from the vehicle routing literature and on real-world instances. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 294,307 2007 [source] A GRASP with path-relinking for private virtual circuit routing,NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2003Mauricio G. C. Resende Abstract A frame relay service offers virtual private networks to customers by provisioning a set of long-term private virtual circuits (PVCs) between customer endpoints on a large backbone network. During the provisioning of a PVC, routing decisions are made without any knowledge of future requests. Over time, these decisions can cause inefficiencies in the network and occasional offline rerouting of the PVCs is needed. In this paper, the offline PVC routing problem is formulated as an integer multicommodity flow problem with additional constraints and with an objective function that minimizes propagation delays and/or network congestion. We propose variants of a GRASP with path-relinking heuristic for this problem. Experimental results for realistic-size problems are reported, showing that the proposed heuristics are able to improve the solutions found with standard routing techniques. Moreover, the structure of our objective function provides a useful strategy for setting the appropriate value of its weight parameter, to achieve some quality of service (QoS) level defined by a desired balance between propagation delay and delay due to network congestion. © 2003 Wiley Periodicals, Inc. [source] Fast permutation routing in a class of interconnection networksNETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2002Ehab S. Elmallah Abstract This paper considers the following permutation routing problem: Given an N × N augmented data manipulator (ADM) network and a permutation , between its N inputs and outputs, can all the traffic connections of , be routed through the network in one pass? A number of backtrack search algorithms have been devised for recognizing ADM admissible permutations. None of the published results, however, appears to settle the time complexity of the problem. The goal of this paper was to answer the question positively by showing the first polynomial time bound for solving the problem. The devised algorithm requires O(N1.695) time to decide whether a given permutation , is admissible and compute a setting of the switches whenever , is admissible. For many practical applications, the obtained bound compares favorably with the O(N lg N) size of an N -input ADM network. © 2002 Wiley Periodicals, Inc. [source] Routing complexity of faulty networksRANDOM STRUCTURES AND ALGORITHMS, Issue 1 2008Omer Angel Abstract One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This article investigates how big the failure probability can be, before the capability to efficiently find a path in the network is lost. Our main results show tight upper and lower bounds for the failure probability, which permits routing both for the hypercube and for the d -dimensional mesh. We use tools from percolation theory to show that in the d -dimensional mesh, once a giant component appears,efficient routing is possible. A different behavior is observed when the hypercube is considered. In the hypercube there is a range of failure probabilities in which short paths exist with high probability, yet finding them must involve querying essentially the entire network. Thus the routing complexity of the hypercube shows an asymptotic phase transition. The critical probability with respect to routing complexity lies in a different location than that of the critical probability with respect to connectivity. Finally we show that an oracle access to links (as opposed to local routing) may reduce significantly the complexity of the routing problem. We demonstrate this fact by providing tight upper and lower bounds for the complexity of routing in the random graph Gn,p. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source] A tabu search procedure for coordinating production, inventory and distribution routing problemsINTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 2 2010André Luís Shiguemoto Abstract This paper addresses the problem of optimally coordinating a production-distribution system over a multi-period finite horizon, where a facility production produces several items that are distributed to a set of customers by a fleet of homogeneous vehicles. The demand for each item at each customer is known over the horizon. The production planning determines how much to produce of each item in every period, while the distribution planning defines when customers should be visited, the amount of each item that should be delivered to customers and the vehicle routes. The objective is to minimize the sum of production and inventory costs at the facility, inventory costs at the customers and distribution costs. We also consider a related problem of inventory routing, where a supplier receives or produces known quantities of items in each period and has to solve the distribution problem. We propose a tabu search procedure for solving such problems, and this approach is compared with vendor managed policies proposed in the literature, in which the facility knows the inventory levels of the customers and determines the replenishment policies. [source] Network service scheduling and routingINTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 6 2004G. Groves Abstract Real-life vehicle routing problems generally have both routing and scheduling aspects to consider. Although this fact is well acknowledged, few heuristic methods exist that address both these complicated aspects simultaneously. We present a graph theoretic heuristic to determine an efficient service route for a single service vehicle through a transportation network that requires a subset of its edges to be serviced, each a specified (potentially different) number of times. The times at which each of these edges are to be serviced should additionally be as evenly spaced over the scheduling time window as possible, thus introducing a scheduling consideration to the problem. Our heuristic is based on the tabu search method, used in conjunction with various well-known graph theoretic algorithms, such as those of Floyd (for determining shortest routes) and Frederickson (for solving the rural postman problem). This heuristic forms the backbone of a decision support system that prompts the user for certain parameters from the physical situation (such as the service frequencies and travel times for each network link as well as bounds in terms of acceptability of results) after which a service routing schedule is suggested as output. The decision support system is applied to a special case study, where a service routing schedule is sought for the South African national railway system by Spoornet (the semi-privatised South African national railways authority and service provider) as part of their rationalisation effort, in order to remain a lucrative company. [source] A JavaÔ universal vehicle router for routing unmanned aerial vehiclesINTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 3 2004R.W. Harder Abstract We consider vehicle routing problems in the context of the Air Force operational problem of routing unmanned aerial vehicles from base locations to various reconnaissance sites. The unmanned aerial vehicle routing problem requires consideration of heterogeneous vehicles, vehicle endurance limits, time windows, and time walls for some of the sites requiring coverage, site priorities, and asymmetric travel distances. We propose a general architecture for operational research problems, specified for vehicle routing problems, that encourages object-oriented programming and code reuse. We create an instance of this architecture for the unmanned aerial vehicle routing problem and describe the components of this architecture to include the general user interface created for the operational users of the system. We employ route building heuristics and tabu search in a symbiotic fashion to provide a user-defined level-of-effort solver interface. Empirical tests of solution algorithms parameterized for solution speed reveal reasonable solution quality is attained. [source] A solution approach for log truck scheduling based on composite pricing and branch and boundINTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 5 2003Myrna Palmgren Abstract The logging truck scheduling problem is one of the most complex routing problems where both pick-up and delivery operations are included. It consists in finding one feasible route for each vehicle in order to satisfy the demands of the customers and in such a way that the total transport cost is minimized. We use a mathematical formulation of the log truck scheduling problem where each column represents a feasible route. We generate a large pool of columns based on solving a transportation problem. Then we apply a composite pricing algorithm, which mainly consists of pricing the pool of columns and maintain an active set of these, for solving the LP relaxed model. A branch and price approach is used to obtain integer solutions in which we apply composite pricing to generate new columns. Numerical results from case studies at Swedish forestry companies are presented. [source] | |||||||||||||