Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem

In this paper new MILP formulations for the multiple allocation p-hub median problem are presented. These require fewer variables and constraints than those traditionally used in the literature. An efficient heuristic algorithm, based on shortest paths, is described. LP based solution methods as well as an explicit enumeration algorithm are developed to obtain exact solutions. Computational results are presented for well known problems from the literature which show that exact solutions can be found in a reasonable amount of computational time. Our algorithms are also benchmarked on a different data set. This data set, which includes problems that are larger than those used in the literature, is based on a postal delivery network and has been treated by the authors in an earlier paper.     

On formulations of the stochastic uncapacitated lot-sizing problem

We consider two formulations of a stochastic uncapacitated lot-sizing problem. We show that by adding (?,S) inequalities to the one with the smaller number of variables, both formulations give the same LP bound. Then we show that for two-period problems, adding another class of inequalities gives the convex hull of integral solutions.     

Optimizing fuzzy p-hub center problem with generalized value-at-risk criterion

In this study, we reduce the uncertainty embedded in secondary possibility distribution of a type-2 fuzzy variable by fuzzy integral, and apply the proposed reduction method to p-hub center problem, which is a nonlinear optimization problem due to the existence of integer decision variables. In order to optimize p-hub center problem, this paper develops a robust optimization method to describe travel times by employing parametric possibility distributions. We first derive the parametric possibility distributions of reduced fuzzy variables. After that, we apply the reduction methods to p-hub center problem and develop a new generalized value-at-risk (VaR) p-hub center problem, in which the travel times are characterized by parametric possibility distributions. Under mild assumptions, we turn the original fuzzy p-hub center problem into its equivalent parametric mixed-integer programming problems. So, we can solve the equivalent parametric mixed-integer programming problems by general-purpose optimization software. Finally, some numerical experiments are performed to demonstrate the new modeling idea and the efficiency of the proposed solution methods.     

Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem

This paper deals with the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP). Two genetic algorithm (GA) approaches are proposed for solving this NP-hard problem. New encoding schemes are implemented with appropriate objective functions. Both approaches keep the feasibility of individuals by using specific representation and modified genetic operators. The numerical experiments were carried out on the standard ORLIB hub data set. Both methods proved to be robust and efficient in solving USApHMP with up to 200 nodes and 20 hubs. The second GA approach achieves all previously known optimal solutions and achieves the best-known solutions on large-scale instances.     

A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (ℓ,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (ℓ,S) inequalities to a general class of valid inequalities, called the inequalities, and we establish necessary and sufficient conditions which guarantee that the inequalities are facet-defining. A separation heuristic for inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the inequalities as cuts. This research has been supported in part by the National Science Foundation under Award number DMII-0121495.     

A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.     

Solving large single allocation p-hub problems with two or three hubs

In this paper we present an efficient approach for solving single allocation p-hub problems with two or three hubs. Two different variants of the problem are considered: the uncapacitated single allocation p-hub median problem and the p-hub allocation problem. We solve these problems using new mixed integer linear programming formulations that require fewer variables than those formerly used in the literature. The problems that we solve here are the largest single allocation problems ever solved. The numerical results presented here will demonstrate the superior performance of our mixed integer linear programs over traditional approaches for large problems. Finally we present the first mixed integer linear program for solving single allocation hub location problems that requires only O(n²) variables and O(n²) constraints that is valid for any number of hubs.     

New formulations for the uncapacitated multiple allocation hub location problem

In this paper we review the integer linear formulations of the uncapacitated multiple allocation hub location problem, we study the scope of validity of these formulations and give new ones that generalize the older formulations. Our formulations allow one or two visits to hubs and include a more general cost structure that needs not satisfy the triangle inequality. We prove that the constraints defined by cliques of a related (intersection) graph are tighter constraints than the classical ones. We also discuss a pre-processing of the problem, which is very useful for reducing its size. Finally, we check the strength of the new formulations and compare them with others in the literature by solving instances of two commonly used data sets: the CAB (Civil Aeronautics Board) and AP (Australian Post), and also randomly generated instances. Our computational results clearly show that our formulations outperform all others previously used for small and medium problems.     

Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic

The uncapacitated facility location problem (UFLP) is a popular combinatorial optimization problem with practical applications in different areas, from logistics to telecommunication networks. While most of the existing work in the literature focuses on minimizing total cost for the deterministic version of the problem, some degree of uncertainty (e.g., in the customers’ demands or in the service costs) should be expected in real-life applications. Accordingly, this paper proposes a simheuristic algorithm for solving the stochastic UFLP (SUFLP), where optimization goals other than the minimum expected cost can be considered. The development of this simheuristic is structured in three stages: (i) first, an extremely fast savings-based heuristic is introduced; (ii) next, the heuristic is integrated into a metaheuristic framework, and the resulting algorithm is tested against the optimal values for the UFLP; and (iii) finally, the algorithm is extended by integrating it with simulation techniques, and the resulting simheuristic is employed to solve the SUFLP. Some numerical experiments contribute to illustrate the potential uses of each of these solving methods, depending on the version of the problem (deterministic or stochastic) as well as on whether or not a real-time solution is required.     

General variable neighborhood search for the uncapacitated single allocation <Emphasis Type="Italic">p</Emphasis>-hub center problem

In this paper we propose a general variable neighborhood search heuristic for solving the uncapacitated single allocation p-hub center problem (USApHCP). For the local search step we develop a nested variable neighborhood descent strategy. The proposed approach is tested on benchmark instances from the literature and found to outperform the state-of-the-art heuristic based on ant colony optimization. We also test our heuristic on large scale instances that were not previously considered as test instances for the USApHCP. Moreover, exact solutions were reached by our GVNS for all instances where optimal solutions are known.     

Revenue management approach to stochastic capacity allocation problem

To formulate stochastic capacity allocation problems in a manufacturing system, the concept and techniques of revenue management is applied in this research. It is assumed the production capacity is stochastic and hence its exact size cannot be forecasted in advance, at the time of planning. There are two classes of “frequent” and “occasional” customers demanding this capacity. The price rate as well as the penalty for order cancellation caused by overbooking is different for each class. The model is developed mathematically and we propose an analytical solution method. The properties of the optimal solution as well as the behavior of objective function are also analyzed. The objective function is not concave, in general. However, we prove it is a unimodal function and by taking advantage of this property, the optimal solution is determined.     

Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique

This paper deals with the uncapacitated multiple allocation hub location problem. The dual problem of a four-indexed formulation is considered and a heuristic method, based on a dual-ascent technique, is designed. This heuristic, which is reinforced with several specifical subroutines and does not require any external linear problem solver, is the core tool embedded in an exact branch-and-bound framework. Besides, the heuristic provides the branch-and-bound algorithm with good lower bounds for the nodes of the branching tree. The results of the computational experience (with the classical CAB and AP data sets) are included, showing the great effectiveness of this approach: instances with up to 120 nodes are solved.     

On the stochastic uncapacitated dynamic single-item lotsizing problem with service level constraints

In this paper, we consider the uncapacitated single-item dynamic lotsizing problem with stochastic period demands and backordering. We present a model formulation that minimizes the setup and holding costs with respect to a constraint on the probability that the inventory at the end of any period does not become negative (α service level) and, alternatively, to a fill rate constraint (β service level). In contrast to earlier model formulations which consider the cycle α service level (α_c) and which approximate the on hand inventory by the net inventory, we include the exact on hand inventory into the model formulation. Therefore, the models are also applicable in situations with very low service levels.     

Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation

Hub and spoke type networks are often designed to solve problems that require the transfer of large quantities of commodities. This can be an extremely difficult problem to solve for constructive approaches such as ant colony optimisation due to the multiple optimisation components and the fact that the quadratic nature of the objective function makes it difficult to determine the effect of adding a particular solution component. Additionally, the amount of traffic that can be routed through each hub is constrained and the number of hubs is not known a-priori. Four variations of the ant colony optimisation meta-heuristic that explore different construction modelling choices are developed. The effects of solution component assignment order and the form of local search heuristics are also investigated. The results reveal that each of the approaches can return optimal solution costs in a reasonable amount of computational time. This may be largely attributed to the combination of integer linear preprocessing, powerful multiple neighbourhood local search heuristic and the good starting solutions provided by the ant colonies.     

The p-hub center allocation problem

The p-hub center problem is to locate p hubs and to allocate non-hub nodes to hub nodes such that the maximum travel time (or distance) between any origin–destination pair is minimized. We address the p-hub center allocation problem, a subproblem of the location problem, where hub locations are given. We present complexity results and IP formulations for several versions of the problem. We establish that some special cases are polynomially solvable.     

The uncapacitated facility location problem with demand-dependent setup and service costs and customer-choice allocation

We consider a generalization of the uncapacitated facility location problem, where the setup cost for a facility and the price charged for service may depend on the number of customers patronizing the facility. Customers are represented by the nodes of the transportation network, and facilities can be located only at nodes; a customer selects a facility to patronize so as to minimize his (her) expenses (price for service + the part of transportation costs paid by the customer). We assume that transportation costs are paid partially by the service company and partially by customers. The objective is to choose locations for facilities and balanced prices so as to either minimize the expenses of the service company (the sum of the total setup cost and the total part of transportation costs paid by the company), or to maximize the total profit. A polynomial-time dynamic programming algorithm for the problem on a tree network is developed.     

A heuristic approach to a single stage assembly problem with transportation allocation

Determining assembly scheduling and transportation allocation are two practical problems that industries face, such as the electronics and health products industries. Problems associated with assembly scheduling mainly focus on how to determine the orders’ processing sequence on the assembly line in order to minimize the waiting times before they are flown to their destinations. Problems associated with transportation allocation arise in the system of assigning processed orders to transport modes with the purpose of minimizing penalties from earliness and tardiness. To minimize overall delivery costs, businesses should decide on assembly scheduling and transportation allocation decision simultaneously. However, since simultaneously making these two decisions is not an easy task, most of the works done on them usually deal with these two problems separately. Apart from previous works, this paper establishes a mixed integer programming model that deals with these problems simultaneously. Due to the computational complexity of the problem, this paper develops a hybrid heuristic algorithm to solve this problem, and we evaluate the performance of the presented heuristic algorithm with the well-known GAMS/BARON and Lingo commercial software, which tests the heuristic algorithm on randomly-generated problems. The presented heuristic algorithm is shown to perform well compared with well-known commercial software.     

Modeling a stochastic multi-objective supplier quota allocation problem with price-dependent ordering

One of the interesting subjects in supply chain management is supply management, which generally relates to the activities regarding suppliers such as empowerment, evaluation, partnerships and so on. A major objective of supplier evaluation involves buyers determining the optimal quota allocated to each supplier when placing an order. In this paper, we propose a multi-objective model in which purchasing cost, rejected units, and late delivered units are minimized, while the obtained total score from the supplier evaluation process is maximized. We assume that the buyer obtains multiple products from a number of predetermined suppliers. The buyer faces a stochastic demand with a probability distribution of Poisson regarding each product type. A major assumption is that the supplier prices are linearly dependent on the order size of each product. Since demand is stochastic, the buyer may incur holding and stockout costs in addition to the regular purchasing cost. We use the well-known L-1 metric method to solve the supplier evaluation problem by utilizing two meta-heuristic algorithms to solve the corresponding mathematical problems.