New simple and efficient heuristics for the uncapacitated single allocation hub location problem

Hub-and-spoke networks are widely studied in the area of location theory. They arise in several contexts, including passenger airlines, postal and parcel delivery, and computer and telecommunication networks. Hub location problems usually involve three simultaneous decisions to be made: the optimal number of hub nodes, their locations and the allocation of the non-hub nodes to the hubs. In the uncapacitated single allocation hub location problem (USAHLP) hub nodes have no capacity constraints and non-hub nodes must be assigned to only one hub. In this paper, we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve this problem. With multi-start heuristics, several different initial solutions are constructed and then improved by tabu search, while in the two-stage integrated heuristic tabu search is applied to improve both the locational and allocational part of the problem. Computational experiments using typical benchmark problems (Civil Aeronautics Board (CAB) and Australian Post (AP) data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. We also report the integer optimal solutions for all 80 CAB data set instances and the 12 AP instances up to 100 nodes, as well as for the corresponding new generated AP instances with reduced fixed costs.     

Multiple allocation hub-and-spoke network design under hub congestion

The multiple allocation hub-and-spoke network design under hub congestion problem is addressed in this paper. A non-linear mixed integer programming formulation is proposed, modeling the congestion as a convex cost function. A generalized Benders decomposition algorithm has been deployed and has successfully solved standard data set instances up to 81 nodes. The proposed algorithm has also outperformed a commercial leading edge non-linear integer programming package. The main contribution of this work is to establish a compromise between the transportation cost savings induced by the economies of scale exploitation and the costs associated with the congestion effects.     

A Combinatorial Benders׳ decomposition for the lock scheduling problem

The Lock Scheduling Problem (LSP) is a combinatorial optimization problem that represents a real challenge for many harbours and waterway operators. The LSP consists of three strongly interconnected subproblems: scheduling lockages, assigning ships to chambers, and positioning the ships inside the chambers. These should be interpreted respectively as a scheduling, an assignment, and a packing problem. By combining the first two problems into a master problem and using the packing problem as a subproblem, a decomposition is achieved that can be solved efficiently by a Combinatorial Benders׳ approach. The master problem is solved first, thereby sequencing the ships into a number of lockages. Next, for each lockage, a packing subproblem is checked for feasibility, possibly returning a number of combinatorial inequalities (cuts) to the master problem. The result is an exact approach to the LSP. Experiments are conducted on a set of instances that were generated in correspondence with real world data. The results indicate that the decomposition approach significantly outperforms other exact approaches presented in the literature, in terms of solution quality and computation time.     

A genetic algorithm for the uncapacitated single allocation planar hub location problem

Given a set of n interacting points in a network, the hub location problem determines location of the hubs (transfer points) and assigns spokes (origin and destination points) to hubs so as to minimize the total transportation cost. In this study, we deal with the uncapacitated single allocation planar hub location problem (PHLP). In this problem, all flow between pairs of spokes goes through hubs, capacities of hubs are infinite, they can be located anywhere on the plane and are fully connected, and each spoke must be assigned to only one hub. We propose a mathematical formulation and a genetic algorithm (PHLGA) to solve PHLP in reasonable time. We test PHLGA on simulated and real life data sets. We compare our results with optimal solution and analyze results for special cases of PHLP for which the solution behavior can be predicted. Moreover, PHLGA results for the AP and CAB data set are compared with other heuristics.     

An efficient memetic algorithm for the uncapacitated single allocation hub location problem

In this paper, we present a memetic algorithm (MA) for solving the uncapacitated single allocation hub location problem (USAHLP). Two efficient local search heuristics are designed and implemented in the frame of an evolutionary algorithm in order to improve both the location and allocation part of the problem. Computational experiments, conducted on standard CAB/AP hub data sets (Beasley in J Global Optim 8:429–433, 1996) and modified AP data set with reduced fixed costs (Silva and Cunha in Computer Oper Res 36:3152–3165, 2009), show that the MA approach is superior over existing heuristic approaches for the USAHLP. For several large-scale AP instances up to 200 nodes, the MA improved the best-known solutions from the literature until now. Numerical results on instances with 300 and 400 nodes introduced in Silva and Cunha (Computer Oper Res 36:3152–3165, 2009) show significant improvements in the sense of both solution quality and CPU time. The robustness of the MA was additionally tested on a challenging set of newly generated large-scale instances with 520–900 nodes. To the best of our knowledge, these are the largest USAHLP problem dimensions solved in the literature until now. In addition, in this paper, we report for the first time optimal solutions for 30 AP and modified AP instances.     

Solving a reverse supply chain design problem by improved Benders decomposition schemes

In this paper we propose improved Benders decomposition schemes for solving a remanufacturing supply chain design problem (RSCP). We introduce a set of valid inequalities in order to improve the quality of the lower bound and also to accelerate the convergence of the classical Benders algorithm. We also derive quasi Pareto-optimal cuts for improving convergence and propose a Benders decomposition scheme to solve our RSCP problem. Computational experiments for randomly generated networks of up to 700 sourcing sites, 100 candidate sites for locating reprocessing facilities, and 50 reclamation facilities are presented. In general, according to our computational results, the Benders decomposition scheme based on the quasi Pareto-optimal cuts outperforms the classical algorithm with valid inequalities.     

An electromagnetism-like metaheuristic for the uncapacitated multiple allocation p-hub median problem

This paper deals with the uncapacitated multiple allocation p-hub median problem (UMApHMP). An electromagnetism-like (EM) method is proposed for solving this NP-hard problem. Our new scaling technique, combined with the movement based on the attraction–repulsion mechanism, directs the EM towards promising search regions. Numerical results on a battery of benchmark instances known from the literature are reported. They show that the EM reaches all previously known optimal solutions, and gives excellent results on large-scale instances. The present approach is also extended to solve the capacitated version of the problem. As it was the case in the uncapacitated version, EM also reached all previously known optimal solutions.     

Solving the uncapacitated hub location problem using genetic algorithms

Hub location problems are widely studied in the area of location theory, where they involve locating the hub facilities and designing the hub networks. In this paper, we present a new and robust solution based on a genetic search framework for the uncapacitated single allocation hub location problem (USAHLP). To present its effectiveness, we compare the solutions of our GA-based method with the best solutions presented in the literature by considering various problem sizes of the CAB data set and the AP data set. The experimental work demonstrates that even for larger problems the results of our method significantly surpass those of the related work with respect to both solution quality and the CPU time to obtain a solution. Specifically, the results from our method match the optimal solutions found in the literature for all test cases generated from the CAB data set with significantly less running time than the related work. For the AP data set, our solutions match the best solutions of the reference study with an average of 8 times less running time than the reference study. Its performance, robustness and substantially low computational effort justify the potential of our method for solving larger problem sizes.     

Distributed joint dynamic maintenance and production scheduling in manufacturing systems: Framework based on model predictive control and Benders decomposition

Scheduling the maintenance based on the condition, respectively the degradation level of the system leads to improved system's reliability while minimizing the maintenance cost. Since the degradation level changes dynamically during the system's operation, we face a dynamic maintenance scheduling problem. In this paper, we address the dynamic maintenance scheduling of manufacturing systems based on their degradation level. The manufacturing system consists of several units with a defined capacity and an individual dynamic degradation model, seeking to optimize their reward. The units sell their production capacity, while maintaining the systems based on the degradation state to prevent failures. The manufacturing units are jointly responsible for fulfilling the demand of the system. This induces a coupling constraint among the agents. Hence, we face a large-scale mixed-integer dynamic maintenance scheduling problem. In order to handle the dynamic model of the system and large-scale optimization, we propose a distributed algorithm using model predictive control (MPC) and Benders decomposition method. In the proposed algorithm, first, the master problem obtains the maintenance scheduling for all the agents, and then based on this data, the agents obtain their optimal production using the distributed MPC method which employs the dual decomposition approach to tackle the coupling constraints among the agents. The effectiveness of the proposed method is investigated on two case studies.     

HubLocator: an exact solution method for the multiple allocation hub location problem

HubLocator is a new branch-and-bound procedure for the uncapacitated multiple allocation hub location problem. An existing optimal method developed by Klincewicz (Location Sci. 4 (1996) 173) is based on dual ascent and dual adjustment techniques applied to a disaggregated model formulation. These techniques have already successfully been used to solve the closely related simple plant location problem. However, due to the specific structure of the problem at hand, the success of these techniques in reducing the computational effort is rather restricted. Therefore, HubLocator additionally considers an aggregated model formulation enabling us to significantly tighten the lower bounds. Upper bounds which satisfy complementary slackness conditions for some constraints are constructed and improved by means of a simple heuristic procedure. Computational experiments demonstrate that optimal solutions for problems with up to 40 nodes can be found in a reasonable amount of time.Scope and purposeGround and air transportation networks, postal delivery networks, and computer networks are often configured as hub-and-spoke systems. Traffic between two locations is not transported directly between these locations, but routed via particular switching or consolidation points called hubs. Due to increased traffic on linkages between hubs, larger vehicles can be used or the capacity of existing vehicles can be utilized more efficiently, resulting in smaller per unit transportation costs. The exploitation of scale economies as a result of the reduced number of linkages, which have to be operated in a hub-and-spoke system, compared to a fully interconnected network is an important advantage of this type of system.Designing hub-and-spoke networks deals with the selection of hubs from a given set of potential locations and the routing of traffic. We consider a special type of such a hub location problem and adapt a successful technique developed to find an optimal solution for the well-known simple plant location problem.     

The uncapacitated hub location problem in networks under decentralized management

We propose a new hub location model defined by the minimization of costs. The main contribution of this work is to permit the analysis of a hub-and-spoke network operated under “decentralized management”. In this type of network, various transport companies act independently, and each makes its route choices according to its own criteria, which can include cost, time, frequency, security and other factors, including subjective ones. Therefore, due to the diversity of the various companies’ criteria, one can expect that between each origin–destination pair, a fraction of the flow will be carried through hubs and a fraction will be carried by the direct route. to resolve this problem, it becomes necessary to determine the probability that any network user will choose the hub route for each trip to be made (or for each load to be carried). We present an integer programming formulation, subject the new model to experiments with an intermodal general cargo network in Brazil and address questions regarding the solution of the problem in practice.     

Accelerating Benders stochastic decomposition for the optimization under uncertainty of the petroleum product supply chain

This paper addresses the solution of a two-stage stochastic programming model for an investment planning problem applied to the petroleum products supply chain. In this context, we present the development of acceleration techniques for the stochastic Benders decomposition that aim to strengthen the cuts generated, as well as to improve the quality of the solutions obtained during the execution of the algorithm. Computational experiments are presented for assessing the efficiency of the proposed framework. We compare the performance of the proposed algorithm with two other acceleration techniques. Results suggest that the proposed approach is able to efficiently solve the problem under consideration, achieving better performance in terms of computational times when compared to other two techniques.     

Models and solution methods for the uncapacitated r‐allocation p‐hub equitable center problem

Hub networks are commonly used in telecommunications and logistics to connect origins to destinations in situations where a direct connection between each origin–destination (o‐d) pair is impractical or too costly. Hubs serve as switching points to consolidate and route traffic in order to realize economies of scale. The main decisions associated with hub‐network problems include (1) determining the number of hubs (p), (2) selecting the p‐nodes in the network that will serve as hubs, (3) allocating non‐hub nodes (terminals) to up to r‐hubs, and (4) routing the pairwise o‐d traffic. Typically, hub location problems include all four decisions while hub allocation problems assume that the value of p is given. In the hub median problem, the objective is to minimize total cost, while in the hub center problem the objective is to minimize the maximum cost between origin–destination pairs. We study the uncapacitated (i.e., links with unlimited capacity) r‐allocation p‐hub equitable center problem (with) and explore alternative models and solution procedures.     

Parking buses in a depot using block patterns: A Benders decomposition approach for minimizing type mismatches

In a transit authority bus depot, buses of different types arrive in the evening to be parked in the depot for the night, and then dispatched in the morning to a set of routes, each of which requests a specific bus type. A type mismatch occurs when the requested type is not assigned to a morning route. We consider the problem of assigning the buses to the depot parking slots such that the number of mismatches is minimized, under the constraint that the buses cannot be repositioned overnight. As in Hamdouni et al. [Dispatching buses in a depot using block patterns. Technical Report, Les Cahiers du GERAD G-2004-51, HEC Montreal, Montreal, Canada, 2004, Transportation Science, to appear], we seek robust solutions by assigning a block pattern to each depot. This pattern partitions the lane into at most two blocks, each block containing buses of a given type. Since it may not be possible to respect the selected block patterns, the problem also involves a second objective which is to minimize the discrepancy between the bus type assignment to the parking slots and the block patterns. In this paper, we first study the simplified case where only the second objective is taken into account. We model this simplified problem as an integer linear program and show that practical instances of it can easily be solved using a commercial MIP solver. Then we formulate the general case as an extension of the simplified model and propose to solve it with a Benders decomposition approach embedded in a branch-and-bound procedure. This procedure is required because the Benders decomposition yields a subproblem with integrality constraints. Of particular interests, we develop strong pruning criteria and an innovative branching strategy that imposes decisions on the master problem variables which already take integer values. Computational results for the general case are also reported.     

Exact approaches for static data segment allocation problem in an information network

In a large distributed database, data are geographically distributed across several separate servers (or data centers). This helps in distributing load in the access network. It also helps to serve data locally where it is required. There are various approaches based on the granularity of data for efficient data distribution in a communication network. The file allocation problem (FAP) locates files to servers, the segment allocation problem (SAP) locates database segments, and the mirror location problem (MLP) locates replicas of the entire database. The placement of such data to multiple servers can be modeled as an optimization problem. The major decisions influencing optimization involves the location of servers, allocation of content and assignment of users. In this paper, we study the segment allocation problem (SAP), which is also known as the partial mirroring problem. This approach is more tractable than the file allocation problem in realistic cases and also eliminates the overhead of (constant) update costs that is incurred in the mirror location problem. Our contribution is two-fold: Firstly, earlier works on SAP assume pre-defined segments. We build a data partitioning method using well-known facility location models. We quantify the performance of the partitioning method. We show that the method partitions the database within a reasonable limit of error. Secondly, we introduce a new model for the segment allocation problem in which the segments are completely connected to each other by high-bandwidth links and contains a cost benefit for inter-segment traffic flows. We formulate this problem as an MILP and build exact solution approaches to solve large scale problems. We demonstrate some structural properties of the problem that make it solvable, using a Benders decomposition algorithm. Computational results validate the superiority of the decomposition approach.     

Path relinking approach for multiple allocation hub maximal covering problem

We consider the multiple allocation hub maximal covering problem (MAHMCP): Considering a serviced O–D flow was required to reach the destination optionally passing through one or two hubs in a limited time, cost or distance, what is the optimal way to locate p hubs to maximize the serviced flows? By designing a new model for the MAHMCP, we provide an evolutionary approach based on path relinking. The Computational experience of an AP data set was presented. And a special application on hub airports location of Chinese aerial freight flows between 82 cities in 2002 was introduced.     

A decomposition based solution algorithm for U-type assembly line balancing with interval data

Balancing U-type assembly lines under uncertainty is addressed in this paper by formulating a robust problem and developing its optimization model and algorithm. U-type assembly layouts are shown to be more efficient than conventional straight lines. A great majority of studies on U-lines assume deterministic environments and ignore uncertainty in operation times. We aim to fill this research gap and, to the best of our knowledge, this study will be the first application of robust optimization to U-type assembly planning.We assume that the operation times are not fixed but they can vary. We employ robust optimization that considers worst case situations. To avoid over-pessimism, we consider that only a subset of operation times take their worst case values. To solve this problem, we suggest an iterative approximate solution algorithm. The efficiency of the algorithm is evaluated with some computational tests.     

Formulating and solving splittable capacitated multiple allocation hub location problems

It is only recently that good formulations and properties for the basic versions of the hub location problem have become available. Now, versions closer to reality can be tackled with greater guarantees of success. This article deals with the case in which the capacity of the hubs is limited. The focus is on the following interpretation of this capacity: there is, for each hub, an upper bound on the total flow coming directly from the origins. Our problem has the so-called multiple allocation possibility, i.e., there is no hub associated to each node; on the contrary, flows with, say, the same origin but different destinations, can be sent through different routes. Moreover, it is assumed that the flow between a given origin–destination pair can be split into several routes; if this is not the case, the problem becomes quite different and cannot be approached by means of the techniques used in this paper.Tight integer linear programming formulations for the problem are presented, along with some useful properties of the optimal solutions which can be used to speed up the resolution.The computational experience shows that instances of medium size can be solved very efficiently using the new method, which outperforms other methods given in the literature.     

A hub location problem with fully interconnected backbone and access networks

This paper considers the design of two-layered fully interconnected networks. A two-layered network consists of clusters of nodes, each defining an access network and a backbone network. We consider the integrated problem of determining the access networks and the backbone network simultaneously. A mathematical formulation is presented, but as the linear programming relaxation of the mathematical formulation is weak, a formulation based on the set partitioning model and column generation approach is also developed. The column generation subproblems are solved by solving a series of quadratic knapsack problems. We obtain superior bounds using the column generation approach than with the linear programming relaxation. The column generation method is therefore developed into an exact approach using the branch-and-price framework. With this approach we are able to solve problems consisting of up to 25 nodes in reasonable time. Given the difficulty of the problem, the results are encouraging.     

Combinatorial Benders cuts for decomposing IMRT fluence maps using rectangular apertures

We consider the problem of decomposing Intensity Modulated Radiation Therapy (IMRT) fluence maps using rectangular apertures. A fluence map can be represented as an integer matrix, which denotes the intensity profile to be delivered to a patient through a given beam angle. We consider IMRT treatment machinery that can form rectangular apertures using conventional jaws, and hence, do not need sophisticated multi-leaf collimator (MLC) devices. The number of apertures used to deliver the fluence map needs to be minimized in order to treat the patient efficiently. From a mathematical point of view, the problem is equivalent to a minimum cardinality matrix decomposition problem. We propose a combinatorial Benders decomposition approach to solve this problem to optimality. We demonstrate the efficacy of our approach on a set of test instances derived from actual clinical data. We also compare our results with the literature and solutions obtained by solving a mixed-integer programming formulation of the problem.