Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem

The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a traditional Lagrangean relaxation over q-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints that can lead to lower bounds that are superior to those given by previous methods. The resulting branch-and-cut-and-price algorithm can solve to optimality all instances from the literature with up to 135 vertices. This more than doubles the size of the instances that can be consistently solved.     

A heuristic procedure for the Capacitated m-Ring-Star problem

In this paper we propose a heuristic method to solve the Capacitated m-Ring-Star Problem which has many practical applications in communication networks. The problem consists of finding m rings (simple cycles) visiting a central depot, a subset of customers and a subset of potential (Steiner) nodes, while customers not belonging to any ring must be “allocated” to a visited (customer or Steiner) node. Moreover, the rings must be node-disjoint and the number of customers allocated or visited in a ring cannot be greater than the capacity Q given as an input parameter. The objective is to minimize the total visiting and allocation costs. The problem is a generalization of the Traveling Salesman Problem, hence it is NP-hard. In the proposed heuristic, after the construction phase, a series of different local search procedures are applied iteratively. This method incorporates some random aspects by perturbing the current solution through a “shaking” procedure which is applied whenever the algorithm remains in a local optimum for a given number of iterations. Computational experiments on the benchmark instances of the literature show that the proposed heuristic is able to obtain, within a short computing time, most of the optimal solutions and can improve some of the best known results.     

Branch-and-Cut-and-Price for Capacitated Connected Facility Location

We consider a generalization of the Connected Facility Location Problem (ConFL), suitable to model real world network extension scenarios such as fiber-to-the-curb. In addition to choosing a set of facilities and connecting them by a Steiner tree as in ConFL, we aim to maximize the resulting profit by potentially supplying only a subset of all customers. Furthermore, capacity constraints on potential facilities need to be considered. We present two mixed integer programming based approaches which are solved using branch-and-cut and branch-and-cut-and-price, respectively. By studying the corresponding polyhedra we analyze both approaches theoretically and show their advantages over previously presented models. Furthermore, using a computational study we are able to additionally show significant advantages of our models over previously presented ones from a practical point of view.     

An Integer Linear Programming Formulation and Branch-and-Cut Algorithm for the Capacitated m-Ring-Star Problem

We study the capacitated m-ring-star problem (CmRSP) that faces the design of minimum cost network structure that connects customers with m rings using a set of ring connections that share a distinguished node (depot), and optionally star connections that connect customers to ring nodes. Ring and star connections have some associated costs. Also, rings can include transit nodes, named Steiner nodes, to reduce the total network cost if possible. The number of customers in each ring-star (ringʼs customers and customer connected to it through star connections) have an upper bound (capacity).These kind of networks are appropriate in optical fiber urban environments. CmRSP is know to be NP-Hard. In this paper we propose an integer linear programming formulation and a branch-and-cut algorithm.     

A Bionomic Approach to the Capacitated p-Median Problem

This paper advocates the use of the bionomic algorithm, a recently proposed metaheuristic technique, as an effective method to solve capacitated p-median problems (CPMP). Bionomic algorithms already proved to be an effective framework for finding good solutions to combinatorial optimization problems, when good local optimization algorithms are available. The paper also presents an effective local search technique for the CPMP. Computational results show the effectiveness of the proposed approach, when compared to the best performing heuristics so far presented in the literature.     

A branch-and-cut algorithm for solving the Non-Preemptive Capacitated Swapping Problem

This paper models and solves a capacitated version of the Non-Preemptive Swapping Problem. This problem is defined on a complete digraph G=(V,A), at every vertex of which there may be one unit of supply of an item, one unit of demand, or both. The objective is to determine a minimum cost capacitated vehicle route for transporting the items in such a way that all demands are satisfied. The vehicle can carry more than one item at a time. Three mathematical programming formulations of the problem are provided. Several classes of valid inequalities are derived and incorporated within a branch-and-cut algorithm, and extensive computational experiments are performed on instances adapted from TSPLIB.     

A Lagrangean Heuristic for a Modular Capacitated Location Problem

This paper considers the Modular Capacitated Location Problem (MCLP) which consists of finding the location and capacity of the facilities, to serve a set of customers at a minimum total cost. Each customer has an associated demand and the capacity of each potential location must be chosen from a finite and discrete set of available capacities. Practical applications of this problem can be found in the location of warehouses, schools, health care services or other types of public services. For the MCLP different mixed integer linear programming models are proposed. The authors develop upper and lower bounds on the problem's optimal value and present computational results with randomly generated tests problems.     

A Genetic Algorithm for Solving a Capacitated p-Median Problem

Facility-location problems have several applications, such as telecommunications, industrial transportation and distribution. One of the most well-known facility-location problems is the p-median problem. This work addresses an application of the capacitated p-median problem to a real-world problem. We propose a genetic algorithm (GA) to solve the capacitated p-median problem. The proposed GA uses not only conventional genetic operators, but also a new heuristic “hypermutation” operator suggested in this work. The proposed GA is compared with a tabu search algorithm.     

A cutting plane algorithm for the Capacitated Connected Facility Location Problem

We consider a network design problem that arises in the cost-optimal design of last mile telecommunication networks. It extends the Connected Facility Location problem by introducing capacities on the facilities and links of the networks. It combines aspects of the capacitated network design problem and the single-source capacitated facility location problem. We refer to it as the Capacitated Connected Facility Location Problem. We develop a basic integer programming model based on single-commodity flows. Based on valid inequalities for the capacitated network design problem and the single-source capacitated facility location problem we derive several (new) classes of valid inequalities for the Capacitated Connected Facility Location Problem including cut set inequalities, cover inequalities and combinations thereof. We use them in a branch-and-cut framework and show their applicability and efficacy on a set of real-world instances.     

A Branch-and-Price algorithm for the Single Source Capacitated Plant Location Problem

This paper considers the Single Source Capacitated Plant Location Problem (SSCPLP). We propose an exact algorithm in which a column generation procedure for finding upper and lower bounds is incorporated within a Branch-and-Price framework. The bounding procedure exploits the structure of the problem by means of an iterative approach. At each iteration, a two-level optimization problem is considered. The two levels correspond with the two decisions to be taken: first, the selection of a subset of plants to be opened and then, the allocation of clients within the subset of open plants. The second level subproblem is solved using column generation. The algorithm has been tested with different sets of test problems and the obtained results are satisfactory.     

Dominance Criteria for the Capacitated Warehouse Location Problem

The paper examines the capacitated warehouse location problem where fixed costs, generally relating to the installation of warehouses and variable costs, consisting mainly of transportation costs, are minimized. The minimization of each kind of cost drives the solution towards opposite directions with respect to the number of warehouses to be opened/closed. Therefore, dominance criteria between fixed and variable costs are examined. This leads to exact tests as well as greedy heuristics, the latter known in the literature as ADD/DROP techniques.     

Heuristic Procedures for the Capacitated Vehicle Routing Problem

In this paper we present two new heuristic procedures for the Capacitated Vehicle Routing Problem (CVRP). The first one solves the problem from scratch, while the second one uses the information provided by a strong linear relaxation of the original problem. This second algorithm is designed to be used in a branch and cut approach to solve to optimality CVRP instances. In both heuristics, the initial solution is improved using tabu search techniques. Computational results over a set of known instances, most of them with a proved optimal solution, are given.     

A solvble case of the Capacitated Chinese Postman Problem

<正> The Capacitated Chinese Postman Problem(CCPP)is NP—hard.However,there aresome solvable cases.In this paper we show that a CCPP is solvable provided all arcs'de-mands are larger than one third of the vehicle's capacity.     

Density Based Problem Space Search for the Capacitated Clustering p-Median Problem

In the Capacitated Clustering Problem (CCP), a given set of n weighted points is to be partitioned into p clusters such that, the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centers that minimises total scatter of points allocated to them. In this paper a new constructive method, a general framework to improve the performance of greedy constructive heuristics, and a problem space search procedure for the CCP are proposed. The constructive heuristic finds patterns of natural subgrouping in the input data using concept of density of points. Elements of adaptive computation and periodic construction–deconstruction concepts are implemented within the constructive heuristic to develop a general framework for building efficient heuristics. The problem-space search procedure is based on perturbations of input data for which a controlled perturbation strategy, intensification and diversification strategies are developed. The implemented algorithms are compared with existing methods on a standard set of bench-marks and on new sets of large-sized instances. The results illustrate the strengths of our algorithms in terms of solution quality and computational efficiency.     

A Lagrangian Heuristic for the Capacitated Plant Location Problem with Side Constraints

In this paper we present a Lagrangian relaxation-based heuristic for solving the capacitated plantlocation problem with side constraints. The side constraints are upper-bound constraints on disjoint subsets of the (0-1) variables. Computational results are reported for some problems, having been obtained both on a mainframe computer and on a personal computer.     

A Branch-and-Price Algorithm for the Capacitated Arc Routing Problem with Stochastic Demands

We address the Capacitated Arc Routing Problem with Stochastic Demands (CARPSD), which we formulate as a Set Partitioning Problem. The CARPSD is solved by a Branch-and-Price algorithm, which we apply without graph transformation. The demand’s stochastic nature is incorporated into the pricing problem. Computational results are reported.     

Bounds and Heuristics for the Shortest Capacitated Paths Problem

Given a graph G, the Shortest Capacitated Paths Problem (SCPP) consists of determining a set of paths of least total length, linking given pairs of vertices in G, and satisfying capacity constraints on the arcs of G.We formulate the SCPP as a 0-1 linear program and study two Lagrangian relaxations for getting lower bounds on the optimal value. We then propose two heuristic methods. The first one is based on a greedy approach, while the second one is an adaptation of the tabu search meta-heuristic.     

Branch-and-price algorithms for the Two-Echelon Capacitated Vehicle Routing Problem

In this paper, we propose an Integer Programming formulation and two branch-and-price implementations for the Two-Echelon Capacitated Vehicle Routing Problem. One algorithm considers routes that satisfy the elementarity condition, while the other relaxes such constraint when pricing routes. For instances that could not be solved to proven optimality within a given time limit, our computational experience suggests that the former provides sharper upper bounds while the latter offers tighter lower bounds. As a by-product, ten new best upper bounds and two new optimality certificates are provided here.     

An Improved Algorithm for the Capacitated Facility Location Problem

In this paper we consider the classical capacitated facility location problem. A branch and bound algorithm is presented which measurably improves upon the recent results of Akinc and Khumawala. The use of a specialized Lagrangean relaxation results in significantly tighter bounds than those for the traditional continuous relaxation. These bounds, when combined with penalties derived from the Lagrangean relaxation, enable many integer variables to be fixed at specific values. This results in fewer branches, and indeed for certain test problems taken from the literature, branching is not required. Average computation time for a battery of test problems from the literature has been reduced (conservatively) by a factor of 3.     

有容量限制的可靠性固定费用选址问题

设施网络可能面临各种失灵风险,而设施选址属于战略决策问题,短期内难以改变,因而在选址设计时需要充分考虑设施的非完全可靠性。本文针对无容量限制的可靠性固定费用选址问题进行扩展,进一步考虑设施的容量约束,基于非线性混合整数规划方法建立了一个有容量限制的可靠性固定费用选址问题优化模型。针对该模型的特点,应用线性化技术进行模型转化,并设计了一种拉格朗日松弛算法予以求解。通过多组算例分析,验证了算法的性能。算例分析结果表明设施失灵风险和设施容量对于选址决策有显著影响,因而在实际的选址决策过程中有必要充分考虑设施的失灵风险及容量约束。