A tabu-search based heuristic for the hub covering problem over incomplete hub networks

Hub location problems deal with finding the location of hub facilities and with the allocation of demand nodes to these located hub facilities. In this paper, we study the single allocation hub covering problem over incomplete hub networks and propose an integer programming formulation to this end. The aim of our model is to find the location of hubs, the hub links to be established between the located hubs, and the allocation of non-hub nodes to the located hub nodes such that the travel time between any origin–destination pair is within a given time bound. We present an efficient heuristic based on tabu search and test the performance of our heuristic on the CAB data set and on the Turkish network.     

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.     

A hybridization of an evolutionary algorithm and a parallel branch and bound for solving the capacitated single allocation hub location problem

In this study, we propose a hybrid optimization method, consisting of an evolutionary algorithm (EA) and a branch-and-bound method (BnB) for solving the capacitated single allocation hub location problem (CSAHLP). The EA is designed to explore the solution space and to select promising configurations of hubs (the location part of the problem). Hub configurations produced by the EA are further passed to the BnB search, which works with fixed hubs and allocates the non-hub nodes to located hubs (the allocation part of the problem). The BnB method is implemented using parallelization techniques, which results in short running times. The proposed hybrid algorithm, named EA-BnB, has been tested on the standard Australia Post (AP) hub data sets with up to 300 nodes. The results demonstrate the superiority of our hybrid approach over existing heuristic approaches from the existing literature. The EA-BnB method has reached all the known optimal solutions for AP hub data set and found new, significantly better, solutions on three AP instances with 100 and 200 nodes. Furthermore, the extreme efficiency of the implementation of this hybrid algorithm resulted in short running times, even for the largest AP test instances.     

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.     

A model for a reliable single allocation hub network design under massive disruption

Hub facilities may fail to operate in networks because of accidental failures such as natural disasters. In this paper, a quadratic model was presented for a reliable single allocation hub network under massive random failure of hub facilities which more than one hub may be disrupted in a route. It determines the location of the hub facilities and the primal allocation of non-hub nodes. It also determines the backup allocation in case of failure of the primal hub. First, a new lexicographic form of a bi-objective quadratic model is presented where the first objective maximizes served demands or equivalently, minimizes lost flows and the second objective minimizes total cost under a to massive disruption in the network. Then, by adding a structure-based constraint, the model is transformed to a single objective one. A linearization technique reported in the literature is applied on the quadratic model to convert it into classic linear zero–one mixed integer model while enhancing it by finding tighter bounds. The tight bounds’ technique is compared with other techniques in terms of computational time and its better performance was approved in some problem instances. Finally, due to the NP-hardness of the problem, an iterated local search algorithm was developed to solve large sized instances in a reasonable computational time and the computational results confirm the efficiency of the proposed heuristic, ILS can solve all CAB and IAD data set instances in less than 15 and 24 seconds, respectively. Moreover, the proposed model was compared with the classical hub network using a network performance measure, and the results show the increased efficiency of the model.     

Uncapacitated single allocation p-hub maximal covering problem

The hub location problem is to find a set of hub nodes on the network, where logistics transportation via the hubs is encouraged because of the cost or distance savings. Each node that has a specified amount of demands can be connected to one of p hubs. The uncapacitated single allocation p-hub maximal covering problem is to maximize the logistics covered, where the logistics of demand is said to be covered if the distance between two nodes is less than or equal to the specified range in consideration of the distance savings between hubs. The aim of our model is to locate the hub, and to allocate non-hub nodes to the located hub nodes; the hub can maximize the demand covered by deadline traveling time. It is presented an integer programming formulation for the new hub covering model, and a computational study based on several instances derived from the CAB (Civil Aeronautics Board) data set. Two heuristics, distance based allocation and volume based allocation methods, are suggested with a computational experiment on the CAB data set. Performances of heuristics are evaluated, and it is shown that good solutions are found in a relatively reasonable computation time for most of instances.     

A branch-and-cut algorithm for the hub location and routing problem

We study the hub location and routing problem where we decide on the location of hubs, the allocation of nodes to hubs, and the routing among the nodes allocated to the same hubs, with the aim of minimizing the total transportation cost. Each hub has one vehicle that visits all the nodes assigned to it on a cycle. We propose a mixed integer programming formulation for this problem and strengthen it with valid inequalities. We devise separation routines for these inequalities and develop a branch-and-cut algorithm which is tested on CAB and AP instances from the literature. The results show that the formulation is strong and the branch-and-cut algorithm is able to solve instances with up to 50 nodes.     

A 2-phase algorithm for solving the single allocation p-hub center problem

The single allocation p-hub center problem is an NP-hard location–allocation problem which consists of locating hub facilities in a network and allocating non-hub nodes to hub nodes such that the maximum distance/cost between origin–destination pairs is minimized. In this paper we present an exact 2-phase algorithm where in the first phase we compute a set of potential optimal hub combinations using a shortest path based branch and bound. This is followed by an allocation phase using a reduced sized formulation which returns the optimal solution. In order to get a good upper bound for the branch and bound we developed a heuristic for the single allocation p-hub center problem based on an ant colony optimization approach. Numerical results on benchmark instances show that the new solution approach is superior over traditional MIP-solver like CPLEX. As a result we are able to provide new optimal solutions for larger problems than those reported previously in literature. We are able to solve problems consisting of up to 400 nodes in reasonable time. To the best of our knowledge these are the largest problems solved in the literature to date.     

Routing and scheduling decisions in the hierarchical hub location problem

Hubs are facilities that consolidate and disseminate flow in many-to-many distribution systems. The hub location problem considers decisions that include the locations of hubs in a network and the allocations of demand (non-hub) nodes to these hubs. We propose a hierarchical multimodal hub network structure, and based on this network, we define a hub covering problem with a service time bound. The hierarchical network consists of three layers in which we consider a ring-star-star (RSS) network. This multimodal network may have different types of vehicles in each layer. For the proposed problem, we present and strengthen a mathematical model with some variable fixing rules and valid inequalities. Also, we develop a heuristic solution algorithm based on the subgradient approach to solve the problem in more reasonable times. We conduct the computational analysis over the Turkish network and the CAB data sets.     

Uncapacitated single and multiple allocation p-hub center problems

The hub median problem is to locate hub facilities in a network and to allocate non-hub nodes to hub nodes such that the total transportation cost is minimized. In the hub center problem, the main objective is one of minimizing the maximum distance/cost between origin destination pairs. In this paper, we study uncapacitated hub center problems with either single or multiple allocation. Both problems are proved to be NP-hard. We even show that the problem of finding an optimal single allocation with respect to a given set of hubs is already NP-hard. We present integer programming formulations for both problems and propose a branch-and-bound approach for solving the multiple allocation case. Numerical results are reported which show that the new formulations are superior to previous ones.     

A multi-start local search heuristic for ship scheduling—a computational study

We present a multi-start local search heuristic for a typical ship scheduling problem. A large number of initial solutions are generated by an insertion heuristic with random elements. The best initial solutions are improved by a local search heuristic that is split into a quick and an extended version. The quick local search is used to improve a given number of the best initial solutions. The extended local search heuristic is then used to further improve some of the best solutions found. The multi-start local search heuristic is compared with an optimization-based solution approach with respect to computation time and solution quality. The computational study shows that the multi-start local search method consistently returns optimal or near-optimal solutions to real-life instances of the ship scheduling problem within a reasonable amount of computation time.     

求解最大割问题的多启动禁忌搜索算法

为了增强局部搜索算法在求解最大割问题上的寻优能力,提高解质量,提出了一种多启动禁忌搜索（MSTS）算法。算法主要包括两个重要组件:一是用于搜索高质量局部优化解的禁忌搜索算法;二是具有全局搜索能力的重启策略。算法首先通过禁忌搜索组件获取局部优化解;然后应用设计的重启策略重新生成初始解并重启禁忌搜索过程。重启策略基于随机贪心的思想,综合利用了“构造”和“扰动”这两种方法生成新的起始解,来逃离局部最优的陷阱从而找到更高优度的解。采用了国际文献中公认的21个算例作为本算法的测试实验集并进行实算, 并与多个先进算法进行比较,MSTS算法在18个算例上得到最好解值,高于其他对比算法。实验结果表明,MSTS算法具有更强的寻优能力和更高的解质量。     

Applying two efficient hybrid heuristics for hub location problem with fully interconnected backbone and access networks

This paper considers the design of two-layered networks with fully interconnected backbone and access networks. The problem, a specific application of hub location to network design, is known as fully interconnected network design problem (FINDP). A novel mathematical programming formulation advantageous over an earlier formulation is presented to model the problem. Two hybrid heuristics are proposed to solve the problem, namely SA_VNS and TS_VNS which incorporate a variable neighborhood search (VNS) algorithm into the framework of simulated annealing (SA) and tabu search (TS). The proposed algorithms are able to easily obtain the optimal solutions for 24 small instances existing in the literature in addition to efficiently solve new generated medium and large instances. Results indicate that the proposed algorithms generate high quality solutions in a quite short CPU 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 simple metaheuristic for minimizing the makespan in two-machine no-wait job shops

This paper examines the problem of scheduling two-machine no-wait job shops to minimize makespan. The problem is known to be strongly NP-hard. A two-phase heuristic is developed to solve the problem. Phase 1 of the heuristic transforms the problem into a no-wait flow shop problem and solves it using the well known Gilmore and Gomory algorithm. Phase 2 of the heuristic improves the solution obtained in phase 1 using a simple tabu search algorithm. Computational results show that the proposed heuristic performs extremely well in terms of both solution quality and computation time. It finds an optimal solution to about 90% of the problem instances and the average deviation from the lower bond for the other problem instances is infinitesimal.     

Spatial Analysis of Single Allocation Hub Location Problems

Hubs are special facilities that serve as switching, transshipment and sorting nodes in many-to-many distribution systems. Flow is consolidated at hubs to exploit economies of scale and to reduce transportation costs between hubs. In this article, we first identify general features of optimal hub locations for single allocation hub location problems based on only the fundamental problem data (demand for travel and spatial locations). We then exploit this knowledge to develop a straightforward heuristic methodology based on spatial proximity of nodes, dispersion and measures of node importance to delineate subsets of nodes likely to contain optimal hubs. We then develop constraints for these subsets for use in mathematical programming formulations to solve hub location problems. Our methodology can also help narrow an organization’s focus to concentrate on more detailed and qualitative analyses of promising potential hub locations. Results document the value of including both demand magnitude and centrality in measuring node importance and the relevant tradeoffs in solution quality and time.     

A Heuristic Algorithm for Hierarchical Hub-and-spoke Network of Time-definite Common Carrier Operation Planning Problem

Designing a heuristic approach to solve time-definite common carrier operation planning problem is the purpose of this research. The time-definite common carrier operation planning is implemented using the arcs and nodes of a hierarchical hub-and-spoke network. In light of the complexity involved in determining the types of the vehicles, as well as their associated routing and scheduling simultaneously, we design an algorithm, which employs the concept of tabu search to solve the network structure problem. The testing data are obtained from the second largest time-definite common carrier in Taiwan. When applied to the data of this test case company, the designed tabu search algorithm can obtain final solutions in a relatively short time regardless of the level of service required. Carriers can plan their operations according to the solutions on the operation networks. Although it is possible that the designed heuristic algorithm may converge to a local optimal solution, it can be a meaningful approach for the industrial application that emphasizes the value of time and can be satisfied with a near-optimal solution.     

Heuristics for the capacitated modular hub location problem

In this paper we study the hub location problem, where the goal is to identify an optimal subset of facilities (hubs) to minimize the transportation cost while satisfying certain capacity constraints. In particular, we target the single assignment version, in which each node in the transportation network is assigned to only one hub to route its traffic. We consider here a realistic variant introduced previously, in which the capacity of edges between hubs is increased in a modular way. This reflects the practical situation in air traffic where the number of flights between two locations implies a capacity in terms of number of passengers. Then, the capacity can be increased in a modular way, as a factor of the number of flights. We propose heuristic methods to obtain high-quality solutions in short computing times. Specifically, we implement memory structures to create advanced search methods and compare them with previous heuristics on a set of benchmark instances. Memory structures have been widely implemented in the context of the tabu search methodology, usually embedded in local search algorithms. In this paper we explore an alternative design in which the constructive method is enhanced with frequency information and the local search is coupled with a path relinking post-processing. Statistical tests confirm the superiority of our proposal with respect to previous developments.     

An efficient heuristic to dimension large-scale hybrid optoelectronic networks

This paper presents a new heuristic to solve efficiently the problem of dimensioning large-size hybrid optoelectronic networks with grooming. It is modeled as a large mixed integer program which cannot be solved to optimality in a reasonable amount of time for networks larger than 10 nodes. The heuristic is based on concepts borrowed from genetic algorithm, tabu search and simulated annealing. The definition of the populations and neighborhoods are discussed in depth along with the intensification and diversification procedures. An application of this heuristic to networks of up to 50 nodes has shown excellent results: The computational time is low and the average optimality gap is generally under 7%.     

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.