Lower and upper bounds for a capacitated plant location problem with multicommodity flow

In this paper, we introduce a capacitated plant location problem with multicommodity flow. Given a set of potential plant sites and a set of capacitated arcs linking plants, transshipment points and customers, the aim is to determine where to locate plants and how to move flows from open plants to customers through a set of transshipment points. This model extends the classical capacitated plant location problem by introducing a multicommodity flow problem in the distribution issue. The combination of the location problem and the flow distribution problem is reasonable and realistic since both of them belong to strategic planning horizons. We propose a Lagrangean-based method, including a Lagrangean relaxation, a Lagrangean heuristic and a subgradient optimization, to provide lower and upper bounds of the model. Then, we employ a Tabu search to further improve upper bounds provided by the Lagrangean procedure. The computational results demonstrate that our solution method is effective since gaps between the upper and lower bound are on average around 2%.     

Bounds for the single source modular capacitated plant location problem

In this paper, we propose a discrete location problem, which we call the Single Source Modular Capacitated Location Problem (SS-MCLP). The problem consists of finding the location and capacity of the facilities, to serve a set of customers at a minimum total cost. The demand of each customer must be satisfied by one facility only and the capacities of the open facilities must be chosen from a finite and discrete set of allowable capacities. Because the SS-MCLP is a difficult problem, a lagrangean heuristic, enhanced by tabu search or local search was developed in order to obtain good feasible solutions. When needed, the lower bounds are used in order to evaluate the quality of the feasible solutions. Our method was tested computationally on randomly generated test problems some of which are with large dimensions considering the literature related to this type of problem. The computational results obtained were compared with those provided by the commercial software Cplex.     

Dynamic location problem under uncertainty with a regret‐based measure of robustness

In this paper, we present a dynamic uncapacitated facility location problem that considers uncertainty in fixed and assignment costs as well as in the sets of potential facility locations and possible customers. Uncertainty is represented via a set of scenarios. Our aim is to minimize the expected total cost, explicitly considering regret. Regret is understood as a measure, for each scenario, of the loss incurred for not choosing that scenario's optimal solution if that scenario indeed occurred. We guarantee that the regret for each scenario is always upper bounded. We present a mixed integer programming model for the problem and we propose a solution approach based on Lagrangean relaxation integrating a local neighborhood search and a subgradient algorithm to update Lagrangean multipliers. The problem and the solutions obtained are first analyzed through the use of illustrative examples. Computational results over sets of randomly generated test problems are also provided.     

Tight bounds from a path based formulation for the tree of hub location problem

This paper considers the tree of hub location problem. We propose a four index formulation which yields much tighter LP bounds than previously proposed formulations, although at a considerable increase of the computational burden when obtained with a commercial solver. For this reason we propose a Lagrangean relaxation, based on the four index formulation, that exploits the structure of the problem by decomposing it into independent subproblems which can be solved quite efficiently. We also obtain upper bounds by means of a simple heuristic that is applied at the inner iterations of the method that solves the Lagrangean dual. As a consequence, the proposed Lagrangean relaxation produces tight upper and lower bounds and enable us to address instances up to 100 nodes, which are notably larger than the ones previously considered in the literature, with sizes up to 20 nodes. Computational experiments have been performed with benchmark instances from the literature. The obtained results are remarkable. For most of the tested instances we obtain or improve the best known solution and for all tested instances the deviation between our upper and lower bounds, never exceeds 10%.     

A Branch and Bound Algorithm for An Uncapacitated Facility Location Problem with a Side Constraint

In this paper, a branch and bound algorithm for solving an uncapacitated facility location problem (UFLP) with an aggregate capacity constraint is presented. The problem arises as a subproblem when Lagrangean relaxation of the capacity constraints is used to solve capacitated facility location problems. The algorithm is an extension of a procedure used by Christofides and Beasley (A tree search algorithm for the p-median problem. European Journal of Operational Research , Vol. 10, 1982, pp. 196–204) to solve p -median problems and is based on Lagrangean relaxation in combination with subgradient optimization for lower bounding, simple Lagrangean heuristics to produce feasible solutions, and penalties to reduce the problem size. For node selection, a jump-backtracking rule is proposed, and alternative rules for choosing the branching variable are discussed. Computational experience is reported.     

Local Search Heuristics for Capacitated p-Median Problems

The search for p-median vertices on a network (graph) is a classical location problem. The p facilities (medians) must be located so as to minimize the sum of the distances from each demand vertex to its nearest facility. The Capacitated p-Median Problem (CPMP) considers capacities for the service to be given by each median. The total service demanded by vertices identified by p-median clusters cannot exceed their service capacity. Primal-dual based heuristics are very competitive and provide simultaneously upper and lower bounds to optimal solutions. The Lagrangean/surrogate relaxation has been used recently to accelerate subgradient like methods. The dual lower bound have the same quality of the usual Lagrangean relaxation dual but is obtained using modest computational times. This paper explores improvements on upper bounds applying local search heuristics to solutions made feasible by the Lagrangean/surrogate optimization process. These heuristics are based on location-allocation procedures that swap medians and vertices inside the clusters, reallocate vertices, and iterate until no improvements occur. Computational results consider instances from the literature and real data obtained using a geographical information system.     

The multiple disposal facilities and multiple inventory locations rollon–rolloff vehicle routing problem

In the Multiple disposal facilities and multiple inventory locations rollon–rolloff vehicle routing problem (M-RRVRP), one of the very important pickup and disposal problems in the sanitation industry, tractors move large trailers, one at a time, between customer locations such as construction sites and shopping centers, disposal facilities and inventory locations. In this paper, we model the M-RRVRP as a time constrained vehicle routing problem on a multigraph (TVRP-MG). We then formulate the TVRP-MG as a set partitioning problem with an additional constraint and describe an exact method for solving the TVRP-MG. This exact method is based on a bounding procedure that combines three lower bounds derived from different relaxations of the formulation of the problem. Further, we obtain a valid upper bound and show how this bounding procedure can transform the solution of a Lagrangean lower bound into a feasible solution.     

An aggregation heuristic for large scale p-median problem

The p-median problem (PMP) consists of locating p facilities (medians) in order to minimize the sum of distances from each client to the nearest facility. The interest in the large-scale PMP arises from applications in cluster analysis, where a set of patterns has to be partitioned into subsets (clusters) on the base of similarity.In this paper we introduce a new heuristic for large-scale PMP instances, based on Lagrangean relaxation. It consists of three main components: subgradient column generation, combining subgradient optimization with column generation; a “core” heuristic, which computes an upper bound by solving a reduced problem defined by a subset of the original variables chosen on a base of Lagrangean reduced costs; and an aggregation procedure that defines reduced size instances by aggregating together clients with the facilities. Computational results show that the proposed heuristic is able to compute good quality lower and upper bounds for instances up to 90,000 clients and potential facilities.     

A heuristic algorithm for optimal location of flow‐refueling capacitated stations

Constructing refueling stations in the transportation network is one of the most important steps toward the promotion of alternative‐fuel vehicles. The capacity of these stations is usually limited. In this paper, a new capacitated refueling station location model and a solution algorithm are proposed. The algorithm is divided into two main steps. At first step, a restricted capacitated problem on core sets is constructed. Then, a modified Lagrangean iterative method is used for obtaining solutions. The Lagrangean method decomposes the restricted problem into two subproblems that are easy to solve. Information from subproblems is used to generate valid inequalities for tightening the upper and lower bounds. The approach is evaluated by considering a set of networks and randomly generated instances. The obtained results indicate that the large problems are efficiently tractable by the proposed algorithm in a reasonable time.     

Heuristic approaches to the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problem arising from work related to aircraft routing. This paper describes the problem and presents heuristic approaches for solving the RATSP. We use simulated annealing to obtain feasible solutions, and hence, upper bounds on the optimum value, and solve a Lagrangean dual problem using a subgradient optimization method to obtain lower bounds. While previous methods failed to obtain optimal solutions to some problem classes after 2 h of computation time, with average gaps ranging from 15% to 30%, our heuristic approaches take only 15–20 min to obtain feasible solutions, with gaps of less than 3%. We give computational results comparing these approaches.     

GRASP and hybrid GRASP-Tabu heuristics to solve a maximal covering location problem with customer preference ordering

In this study, a maximal covering location problem is investigated. In this problem, we want to maximize the demand of a set of customers covered by a set of p facilities located among a set of potential sites. It is assumed that a set of facilities that belong to other firms exists and that customers freely choose allocation to the facilities within a coverage radius. The problem can be formulated as a bilevel mathematical programming problem, in which the leader locates facilities in order to maximize the demand covered and the follower allocates customers to the most preferred facility among those selected by the leader and facilities from other firms. We propose a greedy randomized adaptive search procedure (GRASP) heuristic and a hybrid GRASP-Tabu heuristic to find near optimal solutions. Results of the heuristic approaches are compared to solutions obtained with a single-level reformulation of the problem. Computational experiments demonstrate that the proposed algorithms can find very good quality solutions with a small computational burden. The most important feature of the proposed heuristics is that, despite their simplicity, optimal or near-optimal solutions can be determined very efficiently.     

Lagrangean-based solution approaches for the generalized problem of locating capacitated warehouses

The traditional capacitated warehouse location problem consists of determining the number and the location of capacitated warehouses on a predefined set of potential sites such that the demands of a set of customers are met. A very common assumption made in modeling this problem in almost all of the existing research is that the total capacity of all potential warehouses is sufficient to meet the total demand. Whereas this assumption facilitates to define a well‐structured problem from the mathematical modeling perspective, it is in fact restrictive, not realistic, and hence rarely held in practice. The modeling approach presented in this paper breaks away from the existing research in relaxing this very restrictive assumption. This paper therefore investigates the generalized problem of locating warehouses in a supply chain setting with multiple commodities with no restriction on the total capacity and the demand. A new integer programming formulation for this problem is presented, and an algorithm based on Lagrangean relaxation and decomposition is described for its solution. Three Lagrangean heuristics are proposed. Computational results indicate that reasonably good solutions can be obtained with the proposed algorithms, without having to use a general purpose optimizer.     

Heuristics for the single source capacitated multi-facility Weber problem

The Single Source Capacitated Multi-facility Weber Problem (SSCMWP) is concerned with locating I capacitated facilities in the plane to satisfy the demand of J customers with the minimum total transportation cost of a single commodity such that each customer satisfies all its demand from exactly one facility. The SSCMWP is a non-convex optimization problem and difficult to solve. In the SSCMWP, customer locations, customer demands and facility capacities are known a priori. The transportation costs are proportional to the distance between customers and facilities. We consider both the Euclidean and rectilinear distance cases of the SSCMWP. We first present an Alternate Location and Allocation type heuristic and its extension by embedding a Very Large Scale Neighborhood search procedure. Then we apply a Discrete Approximation approach and propose both lower and upper bounding procedures for the SSCWMP using a Lagrangean Relaxation scheme. The proposed heuristics are compared with the solution approaches from the literature. According to extensive computational experiments on standard and randomly generated test sets, we can say that they yield promising performance.     

A hybrid Lagrangean heuristic with GRASP and path-relinking for set k-covering

The set multicovering or set k-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least k times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set k-covering problem, as well as the template of a family of Lagrangean heuristics. The hybrid GRASP Lagrangean heuristic employs the GRASP with path-relinking heuristic using modified costs to obtain approximate solutions for the original problem. Computational experiments carried out on 135 test instances show experimentally that the Lagrangean heuristics performed consistently better than GRASP as well as GRASP with path-relinking. By properly tuning the parameters of the GRASP Lagrangean heuristic, it is possible to obtain a good trade-off between solution quality and running times. Furthermore, the GRASP Lagrangean heuristic makes better use of the dual information provided by subgradient optimization and is able to discover better solutions and to escape from locally optimal solutions even after the stabilization of the lower bounds, when other Lagrangean strategies fail to find new improving solutions.     

An exact solution for vehicle routing problems with semi-hard resource constraints

This paper presents an exact solution procedure for a vehicle routing problem with semi-hard resource constraints where each resource requirement can be relaxed to a pre-fixed extent at a predefined cost. This model is particularly useful for a supply chain coordination when a given number of vehicles cannot feasibly serve all the customers without relaxing some constraints.It is different from VRP with soft time windows in that the violation is restricted to a certain upper bound, the penalty cost is flat, and the number of relaxations allowed has an upper bound.We develop an exact approach to solve the problem. We use the branch cut and price procedure to solve the problem modeling the pricing problem as an elementary shortest path problem with semi hard resource constraints. The modeling of the subproblem provides a tight lower bound to reduce the computation time. We solve this subproblem using a label setting algorithm, in which we form the labels in a compact way to facilitate incorporation of the resources requirement relaxation information into it, develop extension rules that generate labels with possible relaxations, and develop dominance criteria that reduce the computation time. The lower bound is improved by applying the subset-row inequalities.     

A virtual pegging approach to the max–min optimization of the bi-criteria knapsack problem

We are concerned with a variation of the knapsack problem, the bi-objective max–min knapsack problem (BKP), where the values of items differ under two possible scenarios. We have given a heuristic algorithm and an exact algorithm to solve this problem. In particular, we introduce a surrogate relaxation to derive upper and lower bounds very quickly, and apply the pegging test to reduce the size of BKP. We also exploit this relaxation to obtain an upper bound in the branch-and-bound algorithm to solve the reduced problem. To further reduce the problem size, we propose a ‘virtual pegging’ algorithm and solve BKP to optimality. As a result, for problems with up to 16,000 items, we obtain a very accurate approximate solution in less than a few seconds. Except for some instances, exact solutions can also be obtained in less than a few minutes on ordinary computers. However, the proposed algorithm is less effective for strongly correlated instances.     

An exact algorithm for the modular hub location problem with single assignments

A key feature of hub-and-spoke networks is the consolidation of flows at hub facilities. The bundling of flows allows reduction in the transportation costs, which is frequently modeled using a constant discount factor that is applied to the flow cost associated with all interhub links. In this paper, we study the modular hub location problem, which explicitly models the flow-dependent transportation costs using modular arc costs. It neither assumes a full interconnection between hub nodes nor a particular topological structure, instead it considers link activation decisions as part of the design. We propose a branch-and-bound algorithm that uses a Lagrangean relaxation to obtain lower and upper bounds at the nodes of the enumeration tree. Numerical results are reported for benchmark instances with up to 75 nodes.     

Lower and upper bounds for the two-echelon capacitated location-routing problem

In this paper, we introduce two algorithms to address the two-echelon capacitated location-routing problem (2E-CLRP). We introduce a branch-and-cut algorithm based on the solution of a new two-index vehicle-flow formulation, which is strengthened with several families of valid inequalities. We also propose an adaptive large-neighbourhood search (ALNS) meta-heuristic with the objective of finding good-quality solutions quickly. The computational results on a large set of instances from the literature show that the ALNS outperforms existing heuristics. Furthermore, the branch-and-cut method provides tight lower bounds and is able to solve small- and medium-size instances to optimality within reasonable computing times.     

Lagrangean relaxation heuristics for the p-cable-trench problem

We address the p-cable-trench problem. In this problem, p facilities are located, a trench network is dug and cables are laid in the trenches, so that every customer - or demand - in the region is connected to a facility through a cable. The digging cost of the trenches, as well as the sum of the cable lengths between the customers and their assigned facilities, are minimized. We formulate an integer programming model of the problem using multicommodity flows that allows finding the solution for instances of up to 200 nodes. We also propose two Lagrangean Relaxation-based heuristics to solve larger instances of the problem. Computational experience is provided for instances of up to 300 nodes.     

Solution method for the location planning problem of logistics park with variable capacity

In this paper we study a logistics park location planning problem in which the capacity of the logistics park is determined by the sectors used to establish it in an open site. Since the size of each sector is not necessarily the same in every potential site, the capacity of the logistics park is thus variable, which makes this problem different from the traditional location problems in which the capacity of each facility is fixed. The task of this problem is to determine the location of the logistics parks, the sectors to be used to establish the logistics park in each open site, and the allocation of customers to the established logistics parks so as to minimize the total costs for establishing the logistics parks and supplying the demands of customers. The size mode is introduced to deal with the nonlinear establishment cost function and consequently this problem is formulated as an integer linear programming (ILP) model. Since CPLEX can only solve the ILP model with small-size problems, a tabu search (TS) hybrid with filter and fan (F&F) is presented to obtain near optimal solutions. In the hybrid algorithm, the TS is used to improve the solution by changing the allocation of customers to open sites while the F&F is used to further improve the solution by adjusting the status of sites (i.e., open or closed). In addition, an elite solution pool is constructed to store good solutions found in the searching history. Whenever the hybrid algorithm is trapped in local minima, a new start solution will be generated from the elite pool so as to improve the search diversity. To evaluate the performance of the proposed hybrid TS method, the column generation (CG) method with an acceleration strategy is developed to provide tight lower bounds. Computational results showed that the proposed hybrid algorithm can obtain optimal solutions for most of the small size problems and satisfactory near-optimal solutions with comparison to lower bounds for large size problems.