Increasing Internet Capacity Using Local Search

Open Shortest Path First (OSPF) is one of the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow evenly at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network operator. The weights could be set proportional to the physical lengths of the links, but often the main goal is to avoid congestion, i.e. overloading of links, and the standard heuristic recommended by Cisco (a major router vendor) is to make the weight of a link inversely proportional to its capacity.We study the problem of optimizing OSPF weights for a given a set of projected demands so as to avoid congestion. We show this problem is NP-hard, even for approximation, and propose a local search heuristic to solve it. We also provide worst-case results about the performance of OSPF routing vs. an optimal multi-commodity flow routing. Our numerical experiments compare the results obtained with our local search heuristic to the optimal multi-commodity flow routing, as well as simple and commonly used heuristics for setting the weights. Experiments were done with a proposed next-generation AT&T WorldNet backbone as well as synthetic internetworks.     

LP extreme points and cuts for the fixed-charge network design problem

Many design decisions in transporation, communication, and manufacturing planning can be modeled as problems of routing multiple commodities between various origin and destination nodes of a directed network. Each arc of the network is uncapacitated and carries a fixed charge as well as a cost per unit of flow. We refer to the general problem of selecting a subset of arcs and routing the required multi-commodity flows along the chosen arcs at a minimum total cost as the fixed charge network design problem. This paper focuses on strenghthening the linear programming relaxation of a path-flow formulation for this problem. The considerable success achieved by researchers in solving many related design problems with algorithms that use strong linear programming-based lower bounds motivates this study. We first develop a convenient characterization of fractional extreme points for the network design linear programming relaxation. An auxiliary graph introduced for this characterization also serves to generate two families of cuts that exclude some fractional solutions without eliminating any feasible integer solutions. We discuss a separation procedure for one class of inequalities and demonstrate that many of our results generalize known properties of the plant location problem. Supported in part by grant number ECS-831-6224 of the National Science Foundation.     

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.     

Emergency Logistics Planning in Natural Disasters

Logistics planning in emergency situations involves dispatching commodities (e.g., medical materials and personnel, specialised rescue equipment and rescue teams, food, etc.) to distribution centres in affected areas as soon as possible so that relief operations are accelerated. In this study, a planning model that is to be integrated into a natural disaster logistics Decision Support System is developed. The model addresses the dynamic time-dependent transportation problem that needs to be solved repetitively at given time intervals during ongoing aid delivery. The model regenerates plans incorporating new requests for aid materials, new supplies and transportation means that become available during the current planning time horizon. The plan indicates the optimal mixed pick up and delivery schedules for vehicles within the considered planning time horizon as well as the optimal quantities and types of loads picked up and delivered on these routes. In emergency logistics context, supply is available in limited quantities at the current time period and on specified future dates. Commodity demand is known with certainty at the current date, but can be forecasted for future dates. Unlike commercial environments, vehicles do not have to return to depots, because the next time the plan is re-generated, a node receiving commodities may become a depot or a former depot may have no supplies at all. As a result, there are no closed loop tours, and vehicles wait at their last stop until they receive the next order from the logistics coordination centre. Hence, dispatch orders for vehicles consist of sets of “broken” routes that are generated in response to time-dependent supply/demand. The mathematical model describes a setting that is considerably different than the conventional vehicle routing problem. In fact, the problem is a hybrid that integrates the multi-commodity network flow problem and the vehicle routing problem. In this setting, vehicles are also treated as commodities. The model is readily decomposed into two multi-commodity network flow problems, the first one being linear (for conventional commodities) and the second integer (for vehicle flows). In the solution approach, these sub-models are coupled with relaxed arc capacity constraints using Lagrangean relaxation. The convergence of the proposed algorithm is tested on small test instances as well as on an earthquake scenario of realistic size.     

Branch-and-price-and-cut algorithms for solving the reliable <Emphasis Type="Italic">h</Emphasis>-paths problem

We examine a routing problem in which network arcs fail according to independent failure probabilities. The reliable h-path routing problem seeks to find a minimum-cost set of h ≥ 2 arc-independent paths from a common origin to a common destination, such that the probability that at least one path remains operational is sufficiently large. For the formulation in which variables are used to represent the amount of flow on each arc, the reliability constraint induces a nonconvex feasible region, even when the integer variable restrictions are relaxed. Prior arc-based models and algorithms tailored for the case in which h = 2 do not extend well to the general h-path problem. Thus, we propose two alternative integer programming formulations for the h-path problem in which the variables correspond to origin-destination paths. Accordingly, we develop two branch-and-price-and-cut algorithms for solving these new formulations, and provide computational results to demonstrate the efficiency of these algorithms.     

Routing trains through a railway station based on a node packing model

In this paper, we describe the problem of routing trains through a railway station. This routing problem is a subproblem of the automatic generation of timetables for the Dutch railway system. The problem of routing trains through a railway station is the problem of assigning each of the involved trains to a route through the railway station, given the detailed layout of the railway network within the station and given the arrival and departure times of the trains. When solving this routing problem, several aspects such as capacity, safety, and customer service have to be taken into account. In this paper, we describe this routing problem in terms of a weighted node packing problem. Furthermore, we describe an algorithm for solving this routing problem to optimality. The algorithm is based on preprocessing, valid inequalities, and a branch-and-cut approach. The preprocessing techniques aim at identifying superfluous nodes which can be removed from the problem instance. The characteristics of the preprocessing techniques with respect to propagation are investigated. We also present the results of a computational study in which the model, the preprocessing techniques and the algorithm are tested based on data related to the railway stations Arnhem, Hoorn and Utrecht CS in the Netherlands.     

A lexicographic approach to bi-objective loading of a flexible assembly system

The paper presents a bi-objective integer program and an approximative lexicographic approach for a bicriterion loading and routing problem in a flexible assembly system. The problem objective is to determine an allocation of tasks among the assembly stations for a set of products so as to balance station workloads and minimize total interstation transfer time. In the approach proposed, first the station workloads are balanced using a linear relaxation-based heuristic and then assembly routes are selected based on a network flow model. An illustrative example is provided and some results of computational experiments are reported.     

多商品流电子商务供应链网络模型

针对多商品流三层供应链网络模型,将电子商务整合到多商品流供应链网络中,导出了每层网络代理商或决策者的最优性条件,给出了问题的变分不等式形式,得到了系统达到均衡的条件,给出了具体算例并进行了求解.     

Multi-depot vehicle scheduling problems with time windows and waiting costs

The multi-depot vehicle scheduling problem with time windows (MDVSPTW) consists of scheduling a fleet of vehicles to cover a set of tasks at minimum cost. Each task is restricted to begin within a prescribed time interval and vehicles are supplied by different depots. The problem is formulated as an integer nonlinear multi-commodity network flow model with time variables and is solved using a column generation approach embedded in a branch-and-bound framework. This paper breaks new ground by considering costs on exact waiting times between two consecutive tasks instead of minimal waiting times. This new and more realistic cost structure gives rise to a nonlinear objective function in the model. Optimal and heuristic versions of the algorithm have been extensively tested on randomly generated urban bus scheduling problem (UBSP) and freight transport scheduling problem (FTSP). The results show that such a general solution methodology outperforms specialized algorithms when minimal waiting costs are used, and can efficiently treat the case with exact waiting costs.     

Optimizing over the split closure

The polyhedron defined by all the split cuts obtainable directly (i.e. without iterated cut generation) from the LP-relaxation P of a mixed integer program (MIP) is termed the (elementary, or rank 1) split closure of P. This paper deals with the problem of optimizing over the elementary split closure. This is accomplished by repeatedly solving the following separation problem: given a fractional point, say x, find a rank-1 split cut violated by x or show that none exists. Following Caprara and Letchford [17], we formulate this separation problem as a nonlinear mixed integer program that can be treated as a parametric mixed integer linear program (PMILP) with a single parameter in the objective function and the right hand side. We develop an algorithmic framework to deal with the resulting PMILP by creating and maintaining a dynamically updated grid of parameter values, and use the corresponding mixed integer programs to generate rank 1 split cuts. Our approach was implemented in the COIN-OR framework using CPLEX 9.0 as a general purpose MIP solver. We report our computational results on well-known benchmark instances from MIPLIB 3.0 and several classes of structured integer and mixed integer problems. Our computational results show that rank-1 split cuts close more than 98% of the duality gap on 15 out of 41 mixed integer instances from MIPLIB 3.0. More than 75% of the duality gap can be closed on an additional 10 instances. The average gap closed over all 41 instances is 72.78%. In the pure integer case, rank-1 split cuts close more than 75% of the duality gap on 13 out of 24 instances from MIPLIB 3.0. On average, rank 1 split cuts close about 72% of the duality gap on these 24 instances. We also report results on several classes of structured problems: capacitated versions of warehouse location, single-source facility location, p-median, fixed charge network flow, multi-commodity network design with splittable and unsplittable flows, and lot sizing. The fraction of the integrality gap closed varies for these problem classes between 100 and 67%. We also gathered statistics on the average coefficient size (absolute value) of the disjunctions generated. They turn out to be surprisingly small. Research was supported by the National Science Foundation through grant #DMI-0352885 and by the Office of Naval Research through contract N00014-03-1-0133.     

Service network design for freight railway transportation: the Italian case

In this paper, we present a case study on freight railway transportation in Italy, which is a by-product of research collaboration with a major Italian railway company. We highlight the main features of the Italian reality and propose a customized mathematical model to design the service network, that is, the set of origin-destination connections. More specifically, the model suggests the services to provide, the number of trains travelling on each connection, the number of cars and their type. We consider both full and empty freight car movements and take handling costs into account. All decisions are taken in order to minimize the total costs. The quality of service is guaranteed by satisfying all the transportation demand and by implicitly minimizing the waiting time of cars at intermediate railway stations. Our approach yields to a multi-commodity network design problem with a concave cost function. To solve this problem, we implement a specialized tabu search procedure. Computational results on realistic instances show a significant improvement over current practice.     

Development of a new approach for deterministic supply chain network design

This paper proposes a mixed integer linear programming model and solution algorithm for solving supply chain network design problems in deterministic, multi-commodity, single-period contexts. The strategic level of supply chain planning and tactical level planning of supply chain are aggregated to propose an integrated model. The model integrates location and capacity choices for suppliers, plants and warehouses selection, product range assignment and production flows. The open-or-close decisions for the facilities are binary decision variables and the production and transportation flow decisions are continuous decision variables. Consequently, this problem is a binary mixed integer linear programming problem. In this paper, a modified version of Benders’ decomposition is proposed to solve the model. The most difficulty associated with the Benders’ decomposition is the solution of master problem, as in many real-life problems the model will be NP-hard and very time consuming. In the proposed procedure, the master problem will be developed using the surrogate constraints. We show that the main constraints of the master problem can be replaced by the strongest surrogate constraint. The generated problem with the strongest surrogate constraint is a valid relaxation of the main problem. Furthermore, a near-optimal initial solution is generated for a reduction in the number of iterations.     

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.     

Periodic airline fleet assignment with time windows,spacing constraints,and time dependent revenues

Given the sets of flights and aircraft of an airline carrier, the fleet assignment problem consists of assigning the most profitable aircraft type to each flight. In this paper we propose a model for the periodic fleet assignment problem with time windows in which departure times are also determined. Anticipated profits depend on the schedule and the selection of aircraft types. In addition, short spacings between consecutive flights which serve the same origin–destination pair of airports are penalized. We propose a non-linear integer multi-commodity network flow formulation. We develop new branch-and-bound strategies which are embedded in our branch-and-price solution strategy. Finally, we present computational results for periodic daily schedules on three real-world data sets.     

Design of a recovery network for WEEE collection: the case of Galicia,Spain

This research aims to optimize the design of the reverse logistic network for the collection of Waste of Electric and Electronic Equipment (WEEE), in the Spanish region of Galicia. As a basis for our study a three-phase hierarchical approach is proposed. In the first phase a facility location problem is formulated and solved by means of a mixed integer linear programming; in the second phase a new integer programming formulation for the corresponding heterogeneous fleet vehicle routing problem is presented, and a savings-based heuristic algorithm is developed to efficiently solve the related collection routing problems; in the third phase a simulation study is performed on the collection routes in order to assess the overall performance of the recovery system. The results show a good performance of the proposed procedure, and an improved configuration of the recovery network compared to the one currently in use (particularly transportation costs are reduced by 29.2%).     

Crew pairing at Air France

In the airline industry, crew schedules consist of a number of pairings. These are round trips originating and terminating at the same crew home base composed of legal work days, called duties, separated by rest periods. The purpose of the airline crew pairing problem is to generate a set of minimal cost crew pairings covering all flight legs. The set of pairings must satisfy all the rules in the work convention and all the appropriate air traffic regulations. The resulting constraints can affect duty construction, may restrict each pairing, or be imposed on the overall crew schedule.The pairing problem is formulated as an integer, nonlinear multi-commodity network flow problem with additional resource variables. Nonlinearities occur in the objective function as well as in a large subset of constraints. A branch-and-bound algorithm based on an extension of the Dantzig-Wolfe decomposition principle is used to solve this model. The master problem becomes a Set Partitioning type model, as in the classical formulation, while pairings are generated using resource constrained shortest path subproblems. This primal approach implicitly considers all feasible pairings and also provides the optimality gap value on a feasible solution. A nice feature of this decomposition process is that it isolates all nonlinear aspects of the proposed multi-commodity model in the subproblems which are solved by means of a specialized dynamic programming algorithm.We present the application and implementation of this approach at Air France. It is one of the first implementations of an optimal approach for a large airline carrier. We have chosen a subproblem network representation where the duties rather than the legs are on the arcs. This ensures feasibility relative to duty restrictions by definition. As opposed to Lavoie, Minoux and Odier (1988), the nonlinear cost function is modeled without approximations. The computational experiments were conducted using actual Air France medium haul data. Even if the branch-and-bound trees were not fully explored in all cases, the gaps certify that the computed solutions are within a fraction of one percentage point of the optimality. Our results illustrate that our approach produced substantial improvements over solutions derived by the expert system in use at Air France. Their magnitude led to the eventual implementation of the approach.     

The <Emphasis Type="SmallCaps">Mcf</Emphasis>-separator: detecting and exploiting multi-commodity flow structures in MIPs

Given a general mixed integer program, we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of Scip and Cplex. We make use of the complemented mixed integer rounding framework but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of mixed integer programs coming from network design problems by a factor two on average. We show that almost 10% of the instances in general testsets contain consistent embedded networks. For these instances the computation time is decreased by 18% on average.     

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.     

An improved local branching approach for train formation planning

The train formation plan (TFP) determines routing and frequency of trains, and assigns the demands to trains. In this paper, an improved local branching algorithm is proposed for the TFP model in Iranian railway. This solution strategy is exact in nature, although it is designed to improve the heuristic behavior of the mixed integer programming (MIP) solver at hand. In the local branching algorithm, additional constraints are built in the model for the binary variables, but in the improved local branching algorithm, the additional constraints are built in the model for integer variables. A state-of-the-art method is applied for parameter tuning using design of experiments approach. To evaluate the proposed solution method, we have simulated and solved twenty test problems. The results show the efficiency and effectiveness of the proposed approach. The proposed algorithm is implemented for Iranian Railway network as a case study.     

The fleet assignment problem: Solving a large-scale integer program

Given a flight schedule and set of aircraft, the fleet assignment problem is to determine which type of aircraft should fly each flight segment. This paper describes a basic daily, domestic fleet assignment problem and then presents chronologically the steps taken to solve it efficiently. Our model of the fleet assignment problem is a large multi-commodity flow problem with side constraints defined on a time-expanded network. These problems are often severely degenerate, which leads to poor performance of standard linear programming techniques. Also, the large number of integer variables can make finding optimal integer solutions difficult and time-consuming. The methods used to attack this problem include an interior-point algorithm, dual steepest edge simplex, cost perturbation, model aggregation, branching on set-partitioning constraints and prioritizing the order of branching. The computational results show that the algorithm finds solutions with a maximum optimality gap of 0.02% and is more than two orders of magnitude faster than using default options of a standard LP-based branch-and-bound code.This work was supported by NSF and AFORS grant DDM-9115768 and NSF grant SES-9122674.Corresponding author.