A Tabu Search with Slope Scaling for the Multicommodity Capacitated Location Problem with Balancing Requirements

In this paper, a tabu search heuristic is combined with slope scaling to solve a discrete depot location problem, known as the multicommodity location problem with balancing requirements. Although the uncapacitated version of this problem has already been addressed in the literature, this is not the case for the more challenging capacitated version, where each depot has a fixed and finite capacity. The slope scaling approach is used during the initialization phase to provide the tabu search with good starting solutions. Numerical results are reported on various types of large-scale randomly generated instances. The quality of the heuristic is assessed by comparing the solutions obtained with those of a commercial mixed-integer programming code.     

Grasp Embedded Scatter Search for the Multicommodity Capacitated Network Design Problem

A GRASP embedded Scatter Search is developed for the multicommodity capacitated network design problem. Difficulty for this problem arises from the fact that selection of the optimal network design is an NP-complete combinatorial problem. There exist no polynomial exact algorithms which can solve this problem in a reasonable period of time for realistically sized instances. In such cases, heuristic procedures are commonly used. Two strategies were designed for GRASP: a traditional approach and a memory based technique. As for Scatter Search, 5 different strategies were used to update the reference set. Computational results on a large set of randomly generated instances show the convenience of the proposed procedures.     

A hybrid simulated annealing and column generation approach for capacitated multicommodity network design

This paper presents a hybrid simulated annealing (SA) and column generation (CG) algorithm for the path-based formulation of the capacitated multicommodity network design (PCMND) problem. In the proposed method, the SA metaheuristic algorithm manages open and closed arcs. Several strategies for adding and dropping arcs are suggested and evaluated. For a given design vector in the proposed hybrid approach, the PCMND problem becomes a capacitated multicommodity minimum cost flow (CMCF) problem. The exact evaluation of the CMCF problem is performed using the CG algorithm. The parameter tuning is done by means of design of experiments approach. The performance of the proposed algorithm is evaluated by solving several benchmark instances. The results of the proposed algorithm are compared with the solutions of CPLEX solver and the best-known method in the literature under different time limits. Statistical analysis proves that the proposed algorithm is able to obtain better solutions.     

On single-path network routing subject to max-min fair flow allocation

Fair allocation of flows in multicommodity networks has been attracting a growing attention. In Max-Min Fair (MMF) flow allocation, not only the flow of the commodity with the smallest allocation is maximized but also, in turn, the second smallest, the third smallest, and so on. Since the MMF paradigm allows to approximate the TCP flow allocation when the routing paths are given and the flows are elastic, we address the network routing problem where, given a graph with arc capacities and a set of origin-destination pairs with unknown demands, we must route each commodity over a single path so as to maximize the throughput, subject to the constraint that the flows are allocated according to the MMF principle. After discussing two properties of the problem, we describe a column generation based heuristic and report some computational results.     

A stabilized structured Dantzig–Wolfe decomposition method

We discuss an algorithmic scheme, which we call the stabilized structured Dantzig–Wolfe decomposition method, for solving large-scale structured linear programs. It can be applied when the subproblem of the standard Dantzig–Wolfe approach admits an alternative master model amenable to column generation, other than the standard one in which there is a variable for each of the extreme points and extreme rays of the corresponding polyhedron. Stabilization is achieved by the same techniques developed for the standard Dantzig–Wolfe approach and it is equally useful to improve the performance, as shown by computational results obtained on an application to the multicommodity capacitated network design problem.     

考虑订单合并和货物转运的多式联运路径优化研究

为了获得运输的规模经济效应,本文研究了一种考虑订单合并和货物转运的零担多式联运路径优化问题。首先,以总运输成本为目标函数,以网络中的运输工具容量、可以提供的运输工具最大数量、运输工具服务的关闭时间以及订单时间窗为约束,构建混合整数规划模型,在模型中允许多个订单进行合并运输并考虑运输过程中的转运成本。其次,由于多式联运路径优化问题是典型的NP-hard问题,为了快速求解该模型,开发了一种可以快速为该问题提供近似最优解和下界的列生成启发式算法。最后,生成并测试了大量算例,结果表明所开发的列生成启发式算法可以在较短的时间内提供高质量的近似最优解。文章所构建的模型和开发的列生成启发式算法可以为零担自营多式联运物流企业提供高效的决策支持。     

A Comparison of Heuristics for the Discrete Cost Multicommodity Network Optimization Problem

In this paper, approximate solutions algorithms for discrete cost multicommodity network optimization problems are presented and compared. Firstly, extensions of classical greedy heuristics, based on link-rerouting and flow-rerouting heuristics, are presented in details. Secondly, a new approximate solution algorithm, which basically consists of a heuristic implementation of the exact Benders-type cutting plane generation method, is proposed. All these algorithms are extensively compared on randomly generated graphs up to 50 nodes and 90 links. It clearly appears that this new Benders-type approach is very promising since it produces the best heuristic solutions.     

An interior-point Benders based branch-and-cut algorithm for mixed integer programs

We present an interior-point branch-and-cut algorithm for structured integer programs based on Benders decomposition and the analytic center cutting plane method (ACCPM). We show that the ACCPM based Benders cuts are both pareto-optimal and valid for any node of the branch-and-bound tree. The valid cuts are added to a pool of cuts that is used to warm-start the solution of the nodes after branching. The algorithm is tested on two classes of problems: the capacitated facility location problem and the multicommodity capacitated fixed charge network design problem. For the capacitated facility location problem, the proposed approach was on average 2.5 times faster than Benders-branch-and-cut and 11 times faster than classical Benders decomposition. For the multicommodity capacitated fixed charge network design problem, the proposed approach was 4 times faster than Benders-branch-and-cut while classical Benders decomposition failed to solve the majority of the tested instances.     

0-1 reformulations of the multicommodity capacitated network design problem

We study 0-1 reformulations of the multicommodity capacitated network design problem, which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. In this paper, we compare two cutting-plane algorithms to compute the same lower bound on the optimal value of the problem: one based on the generation of residual capacity inequalities within the model with general integer variables, and the other based on the addition of extended linking inequalities to the 0-1 reformulation. To further improve the computational results of the latter approach, we develop a column-and-row generation approach; the resulting algorithm is shown to be competitive with the approach relying on residual capacity inequalities.     

Heuristics for solving a capacitated multiple allocation hub location problem with application in German wagonload traffic

In this paper, we present a capacitated multiple allocation hub location problem, which arose from a network design problem in German wagonload traffic. We develop heuristic solution approaches based on local improvements. We solve the problem with the heuristics and CPLEX on test data sets provided by our partner Deutsche Bahn AG. The computational results are presented and compared.     

Path Relinking, Cycle-Based Neighbourhoods and Capacitated Multicommodity Network Design

In this paper, we propose a path relinking procedure for the fixed-charge capacitated multicommodity network design problem. Cycle-based neighbourhoods are used both to move along paths between elite solutions and to generate the elite candidate set by a tabu-like local search procedure. Several variants of the method are implemented and compared. Extensive computational experiments indicate that the path relinking procedure offers excellent results. It systematically outperforms the cycle-based tabu search method in both solution quality and computational effort and offers the best current meta-heuristic for this difficult class of problems.     

Cooperative Parallel Tabu Search for Capacitated Network Design

We present a cooperative parallel tabu search method for the fixed charge, capacitated, multicommodity network design problem. Several communication strategies are analyzed and compared. The resulting parallel procedure displays excellent performances in terms of solution quality and solution times. The experiments show that parallel implementations find better solutions than sequential ones. They also show that, when properly designed and implemented, cooperative search outperforms independent search strategies, at least on the class of problems of interest here.     

A parallel insert method for the capacitated arc routing problem

The arc routing problem involves the total distance covered in traversing a certain number of arcs in a network. In the capacitated version of this problem of a finite capacity is associated with each vehicle. In this paper we introduce a new approximate solution strategy for the capacitated arc routing problem (CARP). This strategy usesd an insertion procedure to generate many routes in parallel. The purpose is to obtain a better balance between the costs of each route. Computational results are reported.     

A Slope Scaling/Lagrangean Perturbation Heuristic with Long-Term Memory for Multicommodity Capacitated Fixed-Charge Network Design

This paper describes a slope scaling heuristic for solving the multicomodity capacitated fixed-charge network design problem. The heuristic integrates a Lagrangean perturbation scheme and intensification/diversification mechanisms based on a long-term memory. Although the impact of the Lagrangean perturbation mechanism on the performance of the method is minor, the intensification/diversification components of the algorithm are essential for the approach to achieve good performance. The computational results on a large set of randomly generated instances from the literature show that the proposed method is competitive with the best known heuristic approaches for the problem. Moreover, it generally provides better solutions on larger, more difficult, instances.     

Designing WDM Optical Networks Using Branch-and-Price

In this paper, we present an exact solution procedure for the design of two-layer wavelength division multiplexing (WDM) optical networks with wavelength changers and bifurcated flows. This design problem closely resembles the traditional multicommodity flow problem, except that in the case of WDM optical networks, we are concerned with the routing of multiple commodities in two network layers. Consequently, the corresponding optimization models have to deal with two types of multicommodity variables defined for each of the network layers. The proposed procedure represents one of the first branch-and-price algorithms for a general WDM optical network setting with no assumptions on the number of logical links that can be established between nodes in the network. We apply our procedure in a computational study with four different network configurations. Our results show that for the three tested network configurations our branch-and-price algorithm provides solutions that are on average less than 5 % from optimality. We also provide a comparison of our branch-and-price algorithm with two simple variants of the upper bounding heuristic procedure HLDA that is commonly used for WDM optical network design.     

A splitter location–allocation problem in designing fiber optic access networks

This paper deals with a physical access network design problem of fiber-to-the-home passive optical network (FTTH-PON). The design of FTTH-PON access network seeks the cost effective location of optical splitters that provide optical connectivity from central office to subscribers in a given service area. We formulate the problem as a multi-level capacitated facility location problem on a tree topology with nonlinear link cost. Dealing with the nonlinear link cost, we propose an objective function relaxation approach to obtain tight upper and lower bounds. We develop valid inequalities that enhance the lower bound and propose a local search heuristic procedure that improves the upper bound. Valid inequalities force integrality condition on the number of splitters placed at nodes. Local search heuristic improves the initial greedy solution by placing splitters on the sub-root nodes of a given tree network. Computational results demonstrate the effectiveness of the proposed solution procedures.     

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

A ring-mesh topology design problem for optical transport networks

This paper deals with a ring-mesh network design problem arising from the deployment of an optical transport network. The problem seeks to find an optimal clustering of traffic demands in the network such that the total cost of optical add-drop multiplexer (OADM) and optical cross-connect (OXC) is minimized, while satisfying the OADM ring capacity constraint, the node cardinality constraint, and the OXC capacity constraint. We formulate the problem as an integer programming model and propose several alternative modeling techniques designed to improve the mathematical representation of the problem. We then develop various classes of valid inequalities to tighten the mathematical formulation of the problem and describe an algorithmic approach that coordinates tailored routines with a commercial solver CPLEX. We also propose an effective tabu search procedure for finding a good feasible solution as well as for providing a good incumbent solution for the column generation based heuristic procedure that enhances the solvability of the problem. Computational results exhibit the viability of the proposed method.     

Scatter Search for Network Design Problem

A fixed charge capacitated multicommodity network design problem on undirected networks is addressed. At the present time, there exists no algorithm that can solve large instances, common in several applications, in a reasonable period of time. This paper presents an efficient procedure using a scatter search framework. Computational experiments on a large set of randomly generated problems show that this procedure is capable of finding good solutions to large-scale problems within a reasonable amount of time.