Multiobjective design of survivable IP networks

Modern communication networks often use Internet Protocol routing and the intra-domain protocol OSPF (Open Shortest Path First). The routers in such a network calculate the shortest path to each destination and send the traffic on these paths, using load balancing. The issue of survivability, i.e. the question of how much traffic the network will be able to accommodate if components fail, is increasingly important. We consider the problem of designing a survivable IP network, which also requires determining the routing of the traffic. This is done by choosing the weights used for the shortest path calculations.     

Routing of Railway Carriages

In the context of organizing timetables for railway companies the following railway carriage routing problem occurs. Given a timetable containing rail links with departure and destination times/stations and the composition of the trains, find a routing of railway carriages such that the required carriages are always available when a train departs. The problem is formulated as an integer multi-commodity network flow problem with nonlinear objective function. We will present a local search approach for this NP-hard problem. The approach uses structural properties of the integer multi-commodity network flow formulation of the problem. Computational results for a real world instance are given.     

Jittering performance of random deflection routing in packet networks

This paper reports a study of random deflection routing protocol and its impact on delay-jitter over packet networks. In case of congestion, routers with a random deflection routing protocol can forward incoming packets to links laying off shortest paths; namely, packets can be “deflected” away from their original paths. However, random deflection routing may send packets to several different paths, thereby introducing packet re-ordering. This could affect the quality of receptions, it could also impair the overall performance in transporting data traffic. Nevertheless, the present study reveals that deflection routing could actually reduce delay-jitter when the traffic loading on the network is not heavy.     

Graceful reassignment of excessively long communications paths in networks

Modern broadband telecommunications networks transport diverse classes of traffic through flexible end-to-end communications paths. For instance, Internet Protocol (IP) networks with Multi-Protocol Label Switching (MPLS) carry traffic through label switched paths. These flexible paths are often changed in real, or near-real, time in response to congestion and failures detected in the network. As a result, over time, some of these communications paths become excessively long (referred to as out-of-kilter), leading to poor service performance and waste of network resources. An effective reassignment scheme may require reassignment of communications paths with acceptable length (referred to as in-kilter) in order to generate spare capacity on certain links for the out-of-kilter paths. A graceful reassignment solution provides an ordered sequence of reassignments that satisfies the following: (i) the total number of reassigned communications paths does not exceed a specified limit, (ii) no temporary capacity violations are incurred on any network link during the execution of the sequence of reassignments (reassignments are executed sequentially, one at a time), (iii) a communications path is reassigned only as a unit without being split among multiple alternate routes (iv) all reassigned communications paths will be in-kilter, (v) none of the reassignments of communications paths that were originally in-kilter can be excluded from the specified solution without resulting in some capacity violation, and (vi) the sequence of reassignments approximately optimizes a predefined objective, such as maximizing the number of reassigned out-of-kilter communications paths or maximizing the total load reassigned from out-of-kilter communications paths. The resulting problem is formulated as a multi-period, multi-commodity network flow problem with integer variables. We present a search heuristic that takes advantage of certain problem properties to find subsequences of reassignments that become part of the solution, without performing an exhaustive search. Each subsequence reassigns at least one out-of-kilter communication path.     

Tree network design avoiding congestion

We introduce in this paper an optimal method for tree network design avoiding congestion. We see this problem arising in telecommunication and transportation networks as a flow extension of the Steiner problem in directed graphs, thus including as a particular case any alternative approach based on the minimum spanning tree problem. Our multi-commodity formulation is able to cope with the design of centralized computer networks, modern multi-cast multi-party or hub-based transportation trees. The objective in such cases is the minimization of the sum of the fixed (structural) and variable (operational) costs of all the arcs composing an arborescence that links the origin node (switching center, server, station) to every demand node (multi-cast participants, users in general). The non-linear multi-commodity flow model is solved by a generalized Benders decomposition approach.     

On the Hardness of Equal Shortest Path Routing

In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities.In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible.     

A conic quadratic formulation for a class of convex congestion functions in network flow problems

In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be efficiently formulated by using conic quadratic inequalities. As most of the research on this problem is devoted to heuristic approaches, this study differs in showing that the problem can be solved to optimum by branch-and-bound solvers implementing the second-order cone programming (SOCP) algorithms. Computational experiments on the test problems from the literature show that the continuous relaxation of the formulation gives a tight lower bound and leads to optimal or near optimal integer solutions within reasonable CPU times.     

Column generation for vehicle routing problems with multiple synchronization constraints

Synchronization of workers and vehicles plays a major role in many industries such as logistics, healthcare or airport ground handling. In this paper, we focus on operational ground handling planning and model it as an archetype of vehicle routing problems with multiple synchronization constraints, coined as “abstract vehicle routing problem with worker and vehicle synchronization” (AVRPWVS). The AVRPWVS deals with routing workers to ground handling jobs such as unloading baggage or refuelling an aircraft, while meeting each job’s time window. Moreover, each job can be performed by a variable number of workers. As airports span vast distances and due to security regulations, workers use vehicles to travel between locations. Furthermore, each vehicle, moved by a driver, can carry several workers. We propose two mathematical multi-commodity flow formulations based on time-space networks to efficiently model five synchronization types including movement and load synchronization. Moreover, we develop a branch-and-price heuristic that employs both conventional variable branching and a novel variable fixing strategy. We demonstrate that the procedure achieves results close to the optimal solution in short time when compared to the two integer models.     

Large margin shortest path routing

A new discriminative approach to routing inspired by the large margin criterion serving as a basis for support vector machines is presented. The proposed formulation uses the benefit of the dualization convex program, and it is possible for standard solvers to learn the weighting metrics of the shortest path routing. In order to demonstrate this and due to its simplicity, the single path flow allocation problem is considered in this article. It was found that the weight settings performed within a few percent of that of the optimal general routing where the flow for each demand was optimally distributed over all paths between the source and destination.     

Graph Optimization Approaches for Minimal Rerouting in Symmetric Three Stage Clos Networks

We consider routing in symmetrical three stage Clos networks. Especially we search for the routing of an additional connection that requires the least rearrangements, i.e. the minimal number of changes of already routed connections. We describe polynomial methods, based on matchings and edge colorings. The basic idea is to swap colors along alternating paths. The paths need to be maximal, and the shortest of these maximal paths is chosen, since it minimizes the rerouting that needs to be done. Computational tests confirm the efficiency of the approach.     

基于道路堵塞及顾客时间要求的快件配送最优路径选择

针对道路堵塞如节假日导致的临时最短配送路径失效的问题,提出配送网络最优路径选择模型,并设计了求解快递配送网络关键边和最优路径的算法。首先,计算出整个网络的关键边,掌握配送网络特征;其次,考虑顾客时间要求,研究不完全信息(中断无法提前预知,只有到达中断边的起点处才可知)下的最优路径,根据最短路径上各边新的特点,计算出每条边中断后对应的一组备用路径,再选择运输时间小于或等于顾客可等待时间的路径为有效路径,考虑道路堵塞情况,从有效路径中选择最优路径;最后,结合配送网络的实际情况对最优路径进行了算例分析。     

Intra-domain traffic engineering with shortest path routing protocols

Throughout the last decade, extensive deployment of popular intra-domain routing protocols such as open shortest path first (OSPF) and intermediate system–intermediate system (IS-IS), has drawn an ever increasing attention to internet traffic engineering. This paper reviews optimization techniques that have been deployed for managing intra-domain routing in networks operated with shortest path routing protocols, and the state-of-the-art research that has been carried out in this direction.     

A New Multiobjective Dynamic Routing Method for Multiservice Networks: Modelling and Performance

There are potential advantages in formulating the routing problems in modern multiservice networks as multiple objective problems. This paper presents a novel hierarchical bi-level multiobjective dynamic routing model for multiservice networks. It is based on a bi-objective shortest path algorithm, with dynamically adapted soft-constraints, to compute alternative paths for each node pair and on a heuristic to synchronously select alternative routing plans for the network in a dynamic alternative routing context. It is a routing method which periodically changes alternative paths as a function of periodic updates of certain QoS related parameters obtained from real-time measurements. The performance of the proposed routing method is compared with two reference dynamic routing methods namely RTNR and DAR by means of a discrete-event simulator.A previous short version of this work was presented at INOC’03 (International Network Optimisation Conference). Work partially supported by programme POSI of the III EC programme cosponsored by FEDER and national funds.     

双机成比例无等待流水线重调度干扰管理研究

针对由异速机构成的双机成比例无等待流水线的加工特点,研究了机器扰动工况下的生产重调度问题,提出了兼顾初始调度目标(最小化制造期)和扰动修复目标(最小化工件滞后时间和)的干扰管理方法。在最短加工时间优先(SPT)排序规则的最优解特性分析基础上,证明了右移初始加工时间表是事后干扰管理的最优调度方案,建立了基于SPT规则的事前干扰管理模型,设计了基于理想点趋近的多目标处理策略,提出了离散量子微粒群优化与局部搜索机制相结合的启发式模型求解算法。算例实验结果表明,本文提出的干扰管理模型和算法是有效的。     

Path relinking for the vehicle routing problem

This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search method that explores the solution space more thoroughly than other local search based methods by overcoming local optima. Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu search on the vehicle routing problem.     

The hub location and network design problem with fixed and variable arc costs: formulation and dual-based solution heuristic

Many air, less-than-truck load and intermodal transportation and telecommunication networks incorporate hubs in an effort to reduce total cost. These hubs function as make bulk/break bulk or consolidation/deconsolidation centres. In this paper, a new hub location and network design formulation is presented that considers the fixed costs of establishing the hubs and the arcs in the network, and the variable costs associated with the demands on the arcs. The problem is formulated as a mixed integer programming problem embedding a multi-commodity flow model. The formulation can be transformed into some previously modelled hub network design problems. We develop a dual-based heuristic that exploits the multi-commodity flow problem structure embedded in the formulation. The test results indicate that the heuristic is an effective way to solve this computationally complex problem.     

A local search heuristic for the Multi-Commodity k-splittable Maximum Flow Problem

The Multi-Commodity $k$ -splittable Maximum Flow Problem consists of maximizing the amount of flow routed through a network such that each commodity uses at most $k$ paths and such that edge capacities are satisfied. The problem is $\mathcal NP $ -hard and has application in a.o. telecommunications. In this paper, a local search heuristic for solving the problem is proposed. The heuristic is an iterative shortest path procedure on a reduced graph combined with a local search procedure to modify certain path flows and prioritize the different commodities. The heuristic is tested on benchmark instances from the literature and solves 83 % of the instances to optimality. For the remaining instances, the heuristic finds good solution values which on average are 1.04 % from the optimal. The heuristic solves all instances in less than a second. Compared to other heuristics, the proposed heuristic again shows superior performance with respect to solution quality.     

A hybrid heuristic for the maximum dispersion problem

In this paper we propose a hybrid heuristic for the Maximum Dispersion Problem of finding a balanced partition of a set of objects such that the shortest intra-part distance is maximized. In contrast to clustering problems, dispersion problems aim for a large spread of objects in the same group. They arise in many practical applications such as waste collection and the formation of study groups. The heuristic alternates between finding a balanced solution, and increasing the dispersion. Balancing is achieved by a combination of a minimum cost flow algorithm to find promising pairs of parts and a branch-and-bound algorithm that searches for an optimal balance, and the dispersion is increased by a local search followed by an ejection chain method for escaping local minima. We also propose new upper bounds for the problem. In computational experiments we show that the heuristic is able to find solutions significantly faster than previous approaches. Solutions are close to optimal and in many cases provably optimal.     

Tabu search for graph partitioning

In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.     

Metric inequalities for routings on direct connections with application to line planning

We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the well-known feasibility condition for arc capacities in ordinary multi-commodity flows. The condition can be expressed in terms of a class of metric inequalities for routings on direct connections. We illustrate the concept on the example of the line planning problem in public transport and present an application to large-scale real-world problems.