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.     

Two-echelon, multi-commodity supply chain network design with mode selection, lead-times and inventory costs

Designing distribution networks - as one of the most important strategic issues in supply chain management - has become the focus of research attention in recent years. This paper deals with a two-echelon supply chain network design problem in deterministic, single-period, multi-commodity contexts. The problem involves both strategic and tactical levels of supply chain planning including locating and sizing manufacturing plants and distribution warehouses, assigning the retailers' demands to the warehouses, and the warehouses to the plants, as well as selecting transportation modes.We have formulated the problem as a mixed integer programming model, which integrates the above mentioned decisions and intends to minimize total costs of the network including transportation, lead-times, and inventory holding costs for products, as well as opening and operating costs for facilities. Moreover, we have developed an efficient Lagrangian based heuristic solution algorithm for solving the real-sized problems in reasonable computational time.     

A location–inventory supply chain problem: Reformulation and piecewise linearization

In this paper, we study a two-echelon inventory management problem with multiple warehouses and retailers. The problem is a natural extension to the well-known one-warehouse multi-retailer inventory problem. The problem is formulated as a mixed integer non-linear program such that its continuous relaxation is non-convex. We propose an equivalent formulation with fewer non-linear terms in the objective function so that the continuous relaxation of the new model is a convex optimization problem. We use piecewise linearization to transform the resulting MINLP to a mixed integer program and we solve it using CPLEX. Through numerical experiments, we compare the solutions obtained by solving the new formulation using CPLEX with two previously published Lagrangian relaxation based heuristics to solve the original mixed integer non-linear program. We demonstrate that the new approach is capable of providing almost the same solutions without the need of using specialized algorithms. This important contribution further implies that additional variants of the problem, such as multiple products, capacitated warehouses and routing, can be added to result in a problem that will again be solvable by commercial optimization software, while the respective Lagrangian heuristics will fail to solve such variants or extended problems.     

Local search heuristics for the mobile facility location problem

In the mobile facility location problem (MFLP), one seeks to relocate (or move) a set of existing facilities and assign clients to these facilities so that the sum of facility movement costs and the client travel costs (each to its assigned facility) is minimized. This paper studies formulations and develops local search heuristics for the MFLP. First, we develop an integer programming (IP) formulation for the MFLP by observing that for a given set of facility destinations the problem may be decomposed into two polynomially solvable subproblems. This IP formulation is quite compact in terms of the number of nonzero coefficients in the constraint matrix and the number of integer variables; and allows for the solution of large-scale MFLP instances. Using the decomposition observation, we propose two local search neighborhoods for the MFLP. We report on extensive computational tests of the new IP formulation and local search heuristics on a large range of instances. These tests demonstrate that the proposed formulation and local search heuristics significantly outperform the existing formulation and a previously developed local search heuristic for the problem.     

考虑供应商选择的选址一库存一路径的联合优化

针对装配型制造企业供应链集成优化问题,建立了随机需求情形下整合供应商选择和各层级之间运输方式选择的多层级选址—库存模型。该模型通过对供应商的选择,装配厂和分销中心的选址,相邻两层级之间的分配服务关系及运输方式的确定,实现整体供应链网络成本最小化。为求解此混合整数非线性规划模型,设计了一种矩阵编码的改进自适应遗传算法。仿真实验表明,该算法的解的寻优能力明显优于标准遗传算法,得出了供应链总成本与装配厂的最大提前期存在一定规律性的结论。     

A comparison of formulations and solution methods for the minimum-envy location problem

We consider a discrete facility location problem with a new form of equity criterion. The model discussed in the paper analyzes the case where demand points only have strict preference order on the sites where the plants can be located. The goal is to find the location of the facilities minimizing the total envy felt by the entire set of demand points. We define this new total envy criterion and provide several integer linear programming formulations that reflect and model this approach. The formulations are illustrated by examples. Extensive computational tests are reported, showing the potentials and limits of each formulation on several types of instances. Finally, some improvements for all the formulations previously presented are developed, obtaining in some cases much better resolution times.     

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.     

Facility location and scale decision problem with customer preference

This paper addresses the facility location problem that aims to optimize the location and scale of a new facility in consideration of customer restrictions, including customer preference and the minimum number of customers required to open the facility. In a classic covering problem, the customer is assumed to be covered if he/she is located within the critical distance zone around the facility and is otherwise not covered. This problem is caused by customer facility selection, which differs from the classic covering problem in which services are determined only by proximity. This paper proposes a mixed integer programming formulation based on customer restrictions and also develops a heuristic solution procedure using Lagrangian relaxation. The suggested solution procedure is shown to yield acceptable results in a reasonable computation time.     

The optimization of warehouse location and resources distribution for emergency rescue under uncertainty

China is one of the countries that suffer the most natural disasters in the world. The situation of emergency response and rescue is extremely tough. Establishing the emergency warehouse is one of the important ways to cope with rapid-onset disasters. In this paper, a mixed integer programming (MIP) model based on time cost under uncertainty is proposed, which help solve the emergency warehouse location and distribution problem. Comprehensive consideration of factors such as time cost, penalty cost for lack of resources, alternative origins of resources from both suppliers and emergency warehouses, different means of transportation and multiple resources types are involved in our study. We also introduce uncertain scenarios to describe the severity of the disaster. Particle swarm optimization (PSO) and variable neighborhood search (VNS) are designed to solve the MIP model of different scales of instances. Numerous examples have been tested to compare two heuristics with commercial solver (CPLEX). Both of two algorithms can obtain the exact solution same as CPLEX in small-scale instances while show great performance on larger instances with 10 candidate warehouses, 25 disasters and 50 scenarios.     

Optimizing a location allocation-inventory problem in a two-echelon supply chain network: A modified fruit fly optimization algorithm

In this paper, a design of the supply chain distributer–retailer network for a seasonal multiple-product location allocation-inventory control problem in a planning horizon consisting of multiple periods is modeled. The distance between the distributers and retailers are assumed to be Euclidean and square Euclidean while retailers purchase the products from the distributers under all-unit and incremental quantity discount policies. Furthermore, the products are delivered in packets of known size of items and in case of shortage, a fraction of demand is considered backorder and a fraction lost sale. Besides, the distributers store the manufactured products in their warehouses before delivering them to the retailers since the total warehouse spaces and the total available budget are limited. Capacity constraints are also taken into account when planning inventory levels. It is considered that the distributers manufacture the products under some production limitations. The aim of the problem is to find the optimal number of packets of the products purchased by the retailers from the distributers in different periods and determine the coordinates of the distributers’ locations to minimize the total inventory cost. As the mixed integer nonlinear model of the problem is complicated to solve using exact methods, a modified fruit fly optimization algorithm (MFOA) is proposed to find the optimal solution. Due to the nonlinear nature of the original formulation and noticing that there is no benchmark available in the literature to justify and validate the results, particle swarm optimization (PSO) and simulated annealing (SA) algorithms are represented as well. Some numerical examples are generated to show the performance and application of the algorithms for both Euclidean and square Euclidean distances where the MFOA has a better performance than the PSO and SA.     

An adaptive genetic algorithm for the time dependent inventory routing problem

In this paper we propose an adaptive genetic algorithm that produces good quality solutions to the time dependent inventory routing problem (TDIRP) in which inventory control and time dependent vehicle routing decisions for a set of retailers are made simultaneously over a specific planning horizon. This work is motivated by the effect of dynamic traffic conditions in an urban context and the resulting inventory and transportation costs. We provide a mixed integer programming formulation for TDIRP. Since finding the optimal solutions for TDIRP is a NP-hard problem, an adaptive genetic algorithm is applied. We develop new genetic representation and design suitable crossover and mutation operators for the improvement phase. We use adaptive genetic operator proposed by Yun and Gen (Fuzzy Optim Decis Mak 2(2):161–175, 2003) for the automatic setting of the genetic parameter values. The comparison of results shows the significance of the designed AGA and demonstrates the capability of reaching solutions within 0.5 % of the optimum on sets of test problems.     

Regression approximation for a partially centralized inventory system considering transportation costs

Inventory centralization for multiple stores with stochastic demands reduces costs by establishing and maintaining a central ordering/distribution point. However the inventory centralization may increase the transportation costs since either the customer must travel more to reach the product, or the central warehouse must ship the product over longer distance to reach the customer. In this paper, we study a partially centralized inventory system where multiple central warehouses exist and a central warehouse fulfills the aggregated demand of stores. We want to determine the number, the location of central warehouses and an assignment of central warehouses and a set of stores. The objective is the minimization of the sum of warehouse costs and transportation cost. With the help of the regression approximation of cost function, we transform the original problem to more manageable facility location problems. Regression analysis shows that the approximated cost function is close to the original one for normally distributed demands.     

Decomposition heuristic to minimize total cost in a multi-level supply chain network

In this paper, the distribution planning model for the multi-level supply chain network is studied. Products which are manufactured at factory are delivered to customers through warehouses and distribution centers for the given customer demands. The objective function of suggested model is to minimize logistic costs such as replenishment cost, inventory holding cost and transportation cost. A mixed integer programming formulation and heuristics for practical use are suggested. Heuristics are composed of two steps: decomposition and post improving process. In the decomposition heuristics, the problems are solved optimally only considering the transportation route first by the minimum cost flow problem, and the replenishment plan is generated by applying the cost-saving heuristic which was originally suggested in the manufacturing assembly line operation, and integrating with the transportation plan. Another heuristic, in which the original model is segmented due to the time periods, and run on a rolling horizon based method, is suggested. With the post-improving process using tabu search method, the performances are evaluated, and it was shown that solutions can be computed within a reasonable computation time by the gap of about 10% in average from the lower bound of the optimal solutions.     

Incorporating lateral transfers of vehicles and inventory into an integrated replenishment and routing plan for a three-echelon supply chain

This paper focuses on developing an integrated replenishment and routing plan that takes into account lateral transfers of both vehicles and inventory for a three-echelon supply chain system including a single plant, multiple distribution centers and multiple retailers. A mixed integer programming model to the overall system is formulated first, and then an optimization-based heuristic consisting of three major components is proposed. The purpose of the first component is to assign retailers to distribution centers, and determine routing schedules for each distribution center. And the remaining two components are corresponding to two smaller optimization models – a variant of the classical transportation problem modeled for determining vehicle transfer between distribution centers, and a variant of the conventional minimum cost network flow problem modeled for determining inventory replenishment and transfer. Experimental results reveal that the proposed algorithm is rather computational effectiveness, and the pooling strategy that considers both vehicles and inventory transfers is a worthy option in designing supply chain operations.     

Heuristics for a continuous multi-facility location problem with demand regions

We consider a continuous multi-facility location allocation problem where the demanding entities are regions in the plane instead of points. The problem can be stated as follows: given m (closed, convex) polygonal demand regions in the plane, find the locations of q facilities and allocate each region to exactly one facility so as to minimize a weighted sum of squares of the maximum Euclidean distances between the demand regions and the facilities they are assigned to.We propose mathematical programming formulations of the single and multiple facility versions of the problem considered. The single facility location problem is formulated as a second order cone programming (SOCP) problem, and hence is solvable in polynomial time. The multiple facility location problem is NP-hard in general and can be formulated as a mixed integer SOCP problem. This formulation is weak and does not even solve medium-size instances. To solve larger instances of the problem we propose three heuristics. When all the demand regions are rectangular regions with their sides parallel to the standard coordinate axes, a faster special heuristic is developed. We compare our heuristics in terms of both solution quality and computational time.     

Supply chain system design integrated with risk pooling

This paper considers the location, production–distribution and inventory system design model for supply chain for determining facility locations and their capacity. Risk pooling effect, for both safety stock and running inventory (RI), have been incorporated in the system to minimize the supply chain cost along with determining facility location and capacity. In order to study the benefit of risk pooling for safety stock and RI two cases have been considered, first when retailers act independently and second when DCs-retailers work jointly. The model is formulated as mixed integer nonlinear problem and divided into two stages. The first stage determines the optimal locations for plants and flow relation between plants-DCs and DCs-retailers. At this stage the problem has been linearized using piece-wise linear function. Second stage enumerates the required capacity of opened plants and DCs. The first stage problem is further divided in two sub-problems using Lagrangean relaxation. First sub-problem determines the flow relation between plants and DCs whereas; second sub-problem determines the DCs- retailers flow. Solution of the sub-problems provides the lower bound for the main problem. Computational results reveal that main problem is within the 8.25% of the lower bound and significant amount of cost reduction can be achieved for safety stock and RI costs when DC-Retailer acts jointly.     

Strategic level three-stage production distribution planning with capacity expansion

In this paper, we address a strategic planning problem for a three-stage production–distribution network. The problem under consideration is a single-item, multi-supplier, multi-producer, and multi-distributor production–distribution network with deterministic demand. The objective is to minimize the costs associated with production, transportation, and inventory as well as capacity expansion costs over a given time horizon. The limitations are the production capacities of the suppliers and producers, and transportation capacities of the corresponding transportation network. On the other hand, all capacities may be increased at a fixed cost. The problem is formulated as a 0-1 mixed integer programming model. Since the problem is intractable for real life cases efficient relaxation-based heuristics are considered to obtain a good feasible solution.     

A holonic approach based integration methodology for transportation and warehousing functions of the supply network

The supply chain (SC) is often defined as a network that is composed of different functions, including suppliers, manufacturing plants, warehouses/distribution centers, retailers and customers. A supply network (SN) is a sequence of different and multiple numbers of functions and individual functional units that must satisfy all capacities and demand requirements imposed by customers with minimum cost to the network. The most important functions of a SN are warehousing and transportation functions. This paper addresses the warehousing and transportation network design problem that involves determining the best strategy for distributing the sub-products from the suppliers to the warehouse and from the warehouse to the manufacturers. Considering some similarities between holonic systems and SN systems, a holonic approach based modeling methodology is proposed in this study. A multiple supplier, single warehouse and multiple manufacturer system are considered to be an integrated warehousing and transportation network. Consequently, a linear programming model is presented to maximize the profit of both of the overall SN and the individual functional units of the SN functions.     

A Simultaneous Inventory Control and Facility Location Model with Stochastic Capacity Constraints

Traditionally, logistics analysts divide decisions levels into strategic, tactical and operational. Often these levels are considered separately for modeling purposes. The latter may conduce to make non-optimal decisions, since in reality there is interaction between the different levels. In this research, a cross-level model is derived to analyze decisions about inventory control and facility location, specially suited to urban settings, where the storage space is scarce and the vehicles’ capacity is usually restricted. Both conditions, on the one hand make the problem difficult to solve optimally but on the other hand make it more realistic and useful in practice. This paper presents a simultaneous nonlinear-mixed-integer model of inventory control and facility location decisions, which considers two novel capacity constraints. The first constraint states a maximum lot size for the incoming orders to each warehouse, and the second constraint is a stochastic bound to inventory capacity. This model is NP-Hard and presents nonlinear terms in the objective function and a nonlinear constraint. A heuristic solution approach is introduced, based on Lagrangian relaxation and the subgradient method. Numerical experiments were designed and applied. The solution procedure presented good performance in terms of the objective function. One of the key conclusions of the proposed modeling approach is the fact that a reduction of the inventory capacity does not necessarily imply an increase in the number of installed warehouses. In fact, reducing the order size allows the optimal allocation of customers (those with higher variances) into different warehouses, reducing the total system’s cost.     

Effective reformulations for task allocation in distributed systems with a large number of communicating tasks

In any distributed processing environment, decisions need to be made concerning the assignment of computational task modules to various processors. Many versions of the task allocation problem have appeared in the literature. Intertask communication makes the assignment decision difficult; capacity limitations at the processors increase the difficulty. This problem is naturally formulated as a nonlinear integer program, but can be linearized to take advantage of commercial integer programming solvers. While traditional approaches to linearizing the problem perform well when only a few tasks communicate, they have considerable difficulty solving problems involving a large number of intercommunicating tasks. This paper introduces new mixed integer formulations for three variations of the task allocation problem. Results from extensive computational tests conducted over real and generated data indicate that the reformulations are particularly efficient when a large number of tasks communicate, solving reasonablylarge problems faster than other exact approaches available.