Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

A facility neighborhood search heuristic for capacitated facility location with single-source constraints and flexible demand

We consider a generalization of the well-known capacitated facility location problem with single source constraints in which customer demand contains a flexible dimension. This work focuses on providing fast and practically implementable optimization-based heuristic solution methods for very large scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems.     

On the resolution of the single product capacitated machine siting problem

The single product capacitated machine siting problem (SPCMSP) is an extension of the simple plant location problem, in which plant production depends on installing capacitated machines. In this paper we compare, both theoretically and computationally, three heuristic algorithms for the SPCMSP based upon Lagrangean relaxation and reduction tests of a mixed-integer formulation of the problem, which is NP-hard. We test the performance of the algorithms with examples involving up to 100 potential plants, 1000 customers and six potential machines per plant, which we obtain encouraging results.     

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.     

An integrated approach to dynamic plant location and capacity planning

We consider a dynamic capacitated plant location problem in which capacities of opened plants are determined by acquisition and/or disposal of multiple types of facilities. We determine the opening schedule of plants, allocations of customers' demands and plans for acquisition and/or disposal of plant capacities that minimise the sum of discounted fixed costs for opening plants, delivery costs of products, and acquisition and operation costs of facilities. The dynamic capacitated plant location problem is formulated as a mixed integer linear program and solved by a heuristic algorithm based on Lagrangian relaxation and a cut and branch algorithm which uses Gomory cuts. Several solution properties of the relaxed problem are found and used to develop efficient solution procedures for the relaxed problem. A subgradient optimisation method is employed to obtain better lower bounds. The heuristic algorithm is tested on randomly generated test problems and results show that the algorithm finds good solutions in a reasonable amount of computation time.     

An artificial bee colony algorithm for the capacitated vehicle routing problem

This paper introduces an artificial bee colony heuristic for solving the capacitated vehicle routing problem. The artificial bee colony heuristic is a swarm-based heuristic, which mimics the foraging behavior of a honey bee swarm. An enhanced version of the artificial bee colony heuristic is also proposed to improve the solution quality of the original version. The performance of the enhanced heuristic is evaluated on two sets of standard benchmark instances, and compared with the original artificial bee colony heuristic. The computational results show that the enhanced heuristic outperforms the original one, and can produce good solutions when compared with the existing heuristics. These results seem to indicate that the enhanced heuristic is an alternative to solve the capacitated vehicle routing problem.     

Solving the capacitated location-routing problem

This is a summary of the main results presented in the author’s Ph.D thesis, available at http://prodhonc.free.fr/homepage. This thesis, written in French, was supervised by Christian Prins and Roberto Wolfler-Calvo, and defended on 16 October 2006 at the Université de Technologie de Troyes. Several new approaches are proposed to solve the capacitated location-routing problem (CLRP): heuristic, cooperative and exact methods. Their performances are tested on various kinds of instances with capacitated vehicles and capacitated or uncapacitated depots.      

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.     

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.     

A heuristic lagrangean algorithm for the capacitated plant location problem

Lagrangean techniques have been widely applied to the uncapacitated plant location problem, and in some cases they have proven to be successfull even when capacitated problems with additional constraints are taken into account. In our paper we study the application of these techniques to the capacitated plant location problem when the model considered is a pure integer one. Several lagrangean decompositions are considered and for some of them heuristic algorithms have been designed to solve the resulting lagrangean subproblems, the heuristics consisting of a two phase procedure. The first (location phase) defines a set of multipliers from the analysis of the dual LP relaxation, and makes a choice of the plants considering the resulting subproblems as a particular case of the general assignment problems. Several heuristics have been studied for this second phase, based either on a decomposition of knapsack type subproblems through a definition of a set of penalties, or of looking into the duality gap and trying to reduce it. Computational experience is reported.     

一种带时间窗和容量约束的车辆路线问题及其Tabu Search算法

本文提出一种带时间窗和容量约束的车辆路线问题（CVRPTW），并利用Tabu Search快速启式算法，针对Solomon提出的几个标准问题，快捷地得到了优良的数值结果。     

Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type

This paper presents exact and heuristic solution procedures for a multiproduct capacitated facility location (MPCFL) problem in which the demand for a number of different product families must be supplied from a set of facility sites, and each site offers a choice of facility types exhibiting different capacities. MPCFL generalizes both the uncapacitated (or simple) facility location (UFL) problem and the pure-integer capacitated facility location problem. We define a branch-and-bound algorithm for MPCFL that utilizes bounds formed by a Lagrangian relaxation of MPCFL which decomposes the problem into UFL subproblems and easily solvable 0-1 knapsack subproblems. The UFL subproblems are solved by the dual-based procedure of Erlenkotter. We also present a subgradient optimization-Lagrangian relaxation-based heuristic for MPCFL. Computational experience with the algorithm and heuristic are reported. The MPCFL heuristic is seen to be extremely effective, generating solutions to the test problems that are on average within 2% of optimality, and the branch-and-bound algorithm is successful in solving all of the test problems to optimality.     

GRASP-ASP: An algorithm for the CVRP with route balancing

An extension of the capacitated vehicle routing problem is studied in this paper. In this version the difference between the individual route lengths is minimized simultaneously with the total length. The drivers’ workload and perhaps, income, may be affected by the route lengths; so adding this objective makes the problem closer to real-life than the original, single-objective problem. A heuristic based on GRASP is used to obtain an approximation of the Pareto set. The proposed heuristic is tested on instances from the literature, obtaining good approximations of the Pareto set.     

A covering tour approach to the location of satellite distribution centers to supply humanitarian aid

This article concerns the location of satellite distribution centers (SDCs) to supply humanitarian aid to the affected people throughout a disaster area. In such situations, it is not possible for the relief teams to visit every single home. Instead, the people are required to go to a satellite distribution center in order to obtain survival goods, provided that these centers are not too far from their homes. The SDCs are usually within walking distance. However, these SDCs need to be supplied from a central depot, using a heterogeneous and capacitated fleet of vehicles. We model this situation as a generalization of the covering tour problem, introduce the idea of split delivery, and propose an efficient heuristic approach to solve it. Numerical experiments on randomly-generated data show that, first, only very small instances can be solved efficiently using the mathematical model and, second, our heuristic produces high-quality solutions and solves real-size instances in a reasonable computing time.     

A heuristic Lagrangean algorithm for the capacitated plant location problem — A comment

This is a comment on the paper “A heuristic Lagrangean relaxation algorithm for the capacitated plant location problem” by J. Barcelo and J. Casanovas. The authors have a single source version of the problem where they provide a necessary and sufficient condition for the feasibility of the problem. We show that the condition as shown by the authors is only a necessary condition and not a sufficient condition using an example.     

A Lagrangian Relaxation Heuristic for Capacitated Facility Location with Single-Source Constraints

Facility location models are applicable to problems in many diverse areas, such as distribution systems and communication networks. In capacitated facility location problems, a number of facilities with given capacities must be chosen from among a set of possible facility locations and then customers assigned to them. We describe a Lagrangian relaxation heuristic algorithm for capacitated problems in which each customer is served by a single facility. By relaxing the capacity constraints, the uncapacitated facility location problem is obtained as a subproblem and solved by the well-known dual ascent algorithm. The Lagrangian relaxations are complemented by an add heuristic, which is used to obtain an initial feasible solution. Further, a final adjustment heuristic is used to attempt to improve the best solution generated by the relaxations. Computational results are reported on examples generated from the Kuehn and Hamburger test problems.     

A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times

This paper presents a hybrid of a general heuristic framework and a general purpose mixed-integer programming (MIP) solver. The framework is based on local search and an adaptive procedure which chooses between a set of large neighborhoods to be searched. A mixed integer programming solver and its built-in feasibility heuristics is used to search a neighborhood for improving solutions. The general reoptimization approach used for repairing solutions is specifically suited for combinatorial problems where it may be hard to otherwise design suitable repair neighborhoods. The hybrid heuristic framework is applied to the multi-item capacitated lot sizing problem with setup times, where experiments have been conducted on a series of instances from the literature and a newly generated extension of these. On average the presented heuristic outperforms the best heuristics from the literature, and the upper bounds found by the commercial MIP solver ILOG CPLEX using state-of-the-art MIP formulations. Furthermore, we improve the best known solutions on 60 out of 100 and improve the lower bound on all 100 instances from the literature.     

一类带单源约束的选址运输问题算法研究

带单源约束的选址运输问题是在经典的选址运输问题基础上考虑每个顾客需求的产品仅由一家工厂供应的情况。所建立的模型是整数规划，是NP难的。本文先考虑了开办费用为零的带单源约束的选址运输问题，即带单源约束的运输问题。松弛其中一种变量约束，借鉴求解运输问题的表上作业法，给出了一种修正的表上作业法，然后将算法推广。最后给出了将算法应用在Excel随机生成的测试问题上所得到的结果，与LINDO求得的最优解相比，差距很小。由此得出结论：对规模较小的带单源约束的选址运输问题，本文提出的算法是简便且行之有效的。     

Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem

In this paper, we consider the capacitated multi-facility Weber problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the rectilinear distance separating them. We first give a new mixed integer linear programming formulation of the problem by making use of a well-known necessary condition for the optimal facility locations. We then propose new heuristic solution methods based on this formulation. Computational results on benchmark instances indicate that the new methods can provide very good solutions within a reasonable amount of computation time.     

Lower and upper bounds for a two-stage capacitated facility location problem with handling costs

We study in this paper multi-product facility location problem in a two-stage supply chain in which plants have production limitation, potential depots have limited storage capacity and customer demands must be satisfied by plants via depots. In the paper, handling cost for batch process in depots is considered in a realistic way by a set of capacitated handling modules. Each module can be regards as alliance of equipment and manpower. The problem is to locate depots, choose appropriate handling modules and to determine the product flows from the plants, opened depots to customers with the objective to minimize total location, handling and transportation costs. For the problem, we developed a hybrid method. The initial lower and upper bounds are provided by applying a Lagrangean based on local search heuristic. Then a weighted Dantzig–Wolfe decomposition and path-relinking combined method are proposed to improve obtained bounds. Numerical experiments on 350 randomly generated instances demonstrate our method can provide high quality solution with gaps below 2%.