Integrated optimization of inventory-distribution systems by random local search and a genetic algorithm

A new model and its solution procedure for the commodity distribution system consisting of distribution centers and consumer points are discussed. Demand is assumed to be a random variable that obeys a known, stationary probability distribution. An integrated optimization model is built where both the order-up-to-R policy, which is one of the typical inventory policies for periodic review models, and the transportation problem are considered simultaneously. The assignment of consumer points to distribution centers is not fixed. The problem is to determine the target inventory and the transportation quantity in order to minimize the expectation of the sum of inventory related costs and transportation costs. Simulation and linear programming are used to calculate the expected costs, and a random local search method is developed in order to determine the optimum target inventory. A genetic algorithm is also tested and compared with the proposed random local search method. The model and effectiveness of the proposed solution procedure are clarified by computational experiments.     

具单周期特性的短生命周期产品随机IRP及算法

为优化企业物流系统,针对单周期,短生命周期产品的特点,将库存控制与配送路径安排决策集成,考虑随机需求、缺货成本、积压贬值成本、配送成本等,建立一个具有单周期特性的短生命周期产品随机IRP离散模型,目标是合理确定各零售门店的订购数量及配送路线使得系统成本最小。该问题属于NP-hard问题。对此,采用“报童模型”和差分法求解最佳订购量,将模型予以转化,并设计了一种遗传算法进行求解。算例结果表明所提算法能在较短时间内求解出不同客户数目组合的满意解。结论是：门店订购量宜采用组合选择方式;系统成本与单位行程运价正相关;车容量增大有助于降低系统成本。     

Solving exclusionary side constrained transportation problem by using a hybrid spanning tree-based genetic algorithm

In real life applications we often have the following problem: How to find the reasonable assignment strategy to satisfy the source and destination requirement without shipping goods from any pairs of prohibited sources simultaneously to the same destination so that the total cost can be minimized. This kind of problem is known as the transportation problem with exclusionary side constraint (escTP). Since this problem is one of nonlinear programming models, it is impossible to solve this problem using a traditional linear programming software package (i.e., LINDO). In this paper, an evolutionary algorithm based on a genetic algorithm approach is proposed to solve it. We adopt a Prüfer number to represent the candidate solution to the problem and design the feasibility of the chromosome. Moreover, to handle the infeasible chromosome, here we also propose the repairing procedure. In order to improve the performance of the genetic algorithm, the fuzzy logic controller (FLC) is used to dynamically control the genetic operators. Comparisons with other conventional methods and the spanning tree-based genetic algorithm (st-GA) are presented and the results show the proposed approach to be better as a whole.     

Spanning tree-based genetic algorithm for bicriteria transportation problem

In this paper, we present a new approach which is spanning tree-based genetic algorithm for bicriteria transportation problem. The transportation problem have the special data structure in solution characterized as a spanning tree. In encoding transportation problem, we introduce one of node encoding which is adopted as it is capable of equally and uniquely representing all possible basic solutions. The crossover and mutation was designed based on this encoding. And we designed the criterion that chromosome always feasibility converted to a transportation tree. In the evolutionary process, the mixed strategy and roulette wheel selection is used. Numerical experiments will be shown the effectiveness and efficiency of the proposed algorithm.     

A note on “Nonlinear fixed charge transportation problem by spanning tree-based genetic algorithm” by Jung-Bok Jo,Yinzhen Li,Mitsuo Gen,Computers & Industrial Engineering (2007)

In 2007, a spanning tree-based genetic algorithm approach for solving nonlinear fixed charge transportation problem proposed by Jo et al. [Jo, J. B., Li, Y., Gen, M. (2007). Nonlinear fixed charge transportation problem by spanning tree-based genetic algorithm. Computers & Industrial Engineering. doi:10.1016/j.cie.2007.06.022] was published in Computers & Industrial Engineering journal. In 2008, comments like calculation of total cost, indication of problem size were given by Kannan et al. [Kannan, G., Kumar, P. S., Vinay V. P. (2008). Comments on ‘‘Nonlinear fixed charge transportation problem by spanning tree-based genetic algorithm” by Jung-Bok Jo, Yinzhen Li, Mitsuo Gen, Computers & Industrial Engineering (2007). Computers & Industrial Engineering. doi:10.1016/j.cie.2007.12.019] for the published model of [Jo, J. B., Li, Y., Gen, M. (2007). Nonlinear fixed charge transportation problem by spanning tree-based genetic algorithm. Computers & Industrial Engineering.doi:10.1016/j.cie.2007.06.022]. In this note, as a response to the comments of Kannan et al., the formula for calculating the total cost of nonlinear fixed charge transportation problem is illustrated with examples, to which the near-optimal solutions are given.     

A class of multi-objective supply chain networks optimal model under random fuzzy environment and its application to the industry of Chinese liquor

An important issue, when shipping cost and customers demand are random fuzzy variables in supply chain network (SCN) design problem, is to find the network strategy that can simultaneously achieve the objectives of minimization total cost comprised of fixed costs of plants and distribution centers (DCs), inbound and outbound distribution costs, and maximization customer services that can be rendered to customers in terms of acceptable delivery time. In this paper, we propose a random fuzzy multi-objective mixed-integer non-linear programming model for the SCN design problem of Luzhou Co., Ltd. which is representative in the industry of Chinese liquor. By the expected value operator and chance constraint operator, the model has been transformed into a deterministic multi-objective mixed-integer non-linear programming model. Then, we use spanning tree-based genetic algorithms (st-GA) by the Prüfer number representation to find the SCN to satisfy the demand imposed by customers with minimum total cost and maximum customer services for multi-objective SCN design problem of this company under condition of random fuzzy customers demand and transportation cost between facilities. Furthermore, the efficacy and the efficiency of this method are demonstrated by the comparison between its numerical experiment results and those of tradition matrix-based genetic algorithm.     

A genetic algorithm using priority-based encoding with new operators for fixed charge transportation problems

In this paper, we propose a genetic algorithm using priority-based encoding (pb-GA) for linear and nonlinear fixed charge transportation problems (fcTP) in which new operators for more exploration are proposed. We modify a priority-based decoding procedure proposed by Gen et al. [1] to adapt with the fcTP structure. After comparing well-known representation methods for a transportation problem, we explain our proposed pb-GA. We compare the performance of the pb-GA with the recently used spanning tree-based genetic algorithm (st-GA) using numerous examples of linear and nonlinear fcTPs. Finally, computational results show that the proposed pb-GA gives better results than the st-GA both in terms of the solution quality and computation time, especially for medium- and large-sized problems. Numerical experiments show that the proposed pb-GA better absorbs the characteristics of the nonlinear fcTPs.     

面向无线内容分发网络的树形拓扑生成算法

在无线内容分发网络中,为减轻骨干网络的传输压力,可将网络拓扑结构构建为以基站和Wi Fi接入点为根的若干棵最小生成树,并对生成树的深度和每个节点的度数进行约束。这种深度和度数约束的最小生成树问题是一个NP完全问题。针对该问题,首先提出能够生成优质近似解的启发式算法,该算法在不违反深度以及度数约束的情况下构建生成树,算法思想为在服务性节点相连的边中选择与当前生成树相连且权值最小的边加入生成树。然后在生成初始近似解的基础上采用定制的禁忌搜索算法和模拟退火算法对该近似解实施进一步优化。实验结果表明,在给定的约束条件下,禁忌搜索算法求得的解优于现有的遗传算法,在深度约束为4以及度数约束为10的条件下,解的改进幅度可达18.5%,所提算法的运行速度比遗传算法提高了10倍。     

集成整车物流系统的网络规划问题研究

综合考虑运输、库存、设施、服务质量等决策因素,建立了整车物流网络规划集成优化模型,针对由工厂、集货中心和分销中心构成的基本物流网络,提出了用于运输路径优化的流预测算法,并嵌入到遗传算法,解决了适应值的计算难点,给出了基于流预测的遗传算法求解框架．通过实例分析了运输规模效应、库存控制策略、服务质量指标等因素对物流网络结构设计方案的影响。     

Hierarchical spanning tree network design with Nash genetic algorithm

In this paper, we will propose a Nash genetic algorithm (Nash GA) for solving a hierarchical spanning tree network design problem, formulated as a bi-level programming problem. The proposed algorithm can be employed in designing the backbone topology in a hierarchical link-state (LS) routing domain. Because the well-designed backbone topology structure has a great impact on the overall routing performance in a hierarchical LS domain, the importance of this research is evident. The proposed algorithm is to find an optimal configuration of backbone network for backbone provider (BP) and distribution network for internet service provider (ISP), properly meeting two-aspect engineering goals: i.e., average message delay and connection costs. Also, it is assumed that there are the decision makers for BP and the decision makers for ISP join in the decision making process in order to non-cooperatively optimize the own objective function. From the experiment results, we can see clearly that our proposed algorithm can be employed in effectively designing the spanning tree network of hierarchical LS routing domain considering not only engineering aspects but also specific benefits from systematical layout of backbone network.     

An integrated replenishment model with quantity discounts, reentry and downward substitution for control wafers

This paper considers control wafers replenishment problem in wafer fabrication factories. A dynamic lot-sizing replenishment problem with reentry and downward substitution is examined in a pulling control production environment. The objective is to set the inventory level so as to minimize the total cost of control wafers, where the costs include order cost, purchase cost, setup cost, production cost and holding cost, while maintaining the same level of production throughput. In addition, purchase quantity discounts and precise inventory level are considered in the replenishment model. The control wafers replenishment problem is first constructed as a network, and is then transformed into a mixed integer programming model. Lastly, an efficient heuristic algorithm is proposed for solving large-scale problems. A numerical example is given to illustrate the practicality for empirical investigation. The results demonstrate that the proposed mixed integer programming model and the heuristic algorithm are effective tools for determining the inventory level of control wafers for multi-grades in multi-periods.     

A supplier-selection model with classification and joint replenishment of inventory items

Since inventory costs are closely related to suppliers, many models in the literature have selected the suppliers and also allocated orders, simultaneously. Such models usually consider either a single inventory item or multiple inventory items which have independent holding and ordering costs. However, in practice, ordering multiple items from the same supplier leads to a reduction in ordering costs. This paper presents a model in capacity-constrained supplier-selection and order-allocation problem, which considers the joint replenishment of inventory items with a direct grouping approach. In such supplier-selection problems, the following items are considered: a fixed major ordering cost to each supplier, which is independent from the items in the order; a minor ordering cost for each item ordered to each supplier; and the inventory holding and purchasing costs. To solve the developed NP-hard problem, a simulated annealing algorithm was proposed and then compared to a modified genetic algorithm of the literature. The numerical example represented that the number of groups and selected suppliers were reduced when the major ordering cost increased in comparison to other costs. There were also more savings when the number of groups was determined by the model in comparison to predetermined number of groups or no grouping scenarios.     

A tabu search procedure for coordinating production,inventory and distribution routing problems

This paper addresses the problem of optimally coordinating a production‐distribution system over a multi‐period finite horizon, where a facility production produces several items that are distributed to a set of customers by a fleet of homogeneous vehicles. The demand for each item at each customer is known over the horizon. The production planning determines how much to produce of each item in every period, while the distribution planning defines when customers should be visited, the amount of each item that should be delivered to customers and the vehicle routes. The objective is to minimize the sum of production and inventory costs at the facility, inventory costs at the customers and distribution costs. We also consider a related problem of inventory routing, where a supplier receives or produces known quantities of items in each period and has to solve the distribution problem. We propose a tabu search procedure for solving such problems, and this approach is compared with vendor managed policies proposed in the literature, in which the facility knows the inventory levels of the customers and determines the replenishment policies.     

A Joint Replenishment Inventory-Location Model

We introduce a distribution center location model that incorporates joint replenishment inventory costs at the distribution centers. The model is formulated as a Fixed Charge Location Problem (FCLP) which objectively considers not only location specific costs but also inventory replenishment costs. In the joint replenishment problem we consider a single item and several distribution centers in different locations and apply a similar algorithm to the one used to solve the multi-item problem. We propose a Greedy Randomized Adaptive Search Procedure (GRASP) to solve the problem.     

An arc flow formulation to the multitrip production,inventory, distribution,and routing problem with time windows

The multitrip production, inventory, distribution, and routing problem with time windows (MPIDRPTW) is an integrated problem that combines a production and distribution problem, a multitrip vehicle routing problem, and an inventory routing problem. In the MPIDRPTW, a set of customers, which have a time-varying demand during a finite planning horizon, is served by a single production facility. The distribution is accomplished by a fleet of homogeneous vehicles that deliver the customer orders within their specific time windows. Production management has to be done according to the inventories at the facility and at the customers. An exact arc flow model based on a graph is proposed to solve the MPIDRPTW, where the nodes represent instants of time. The main goal of the problem is to minimize the costs associated with the entire system. The proposed approach was implemented and a set of experimental tests were conducted based on a set of adapted instances from the literature.     

Developing a multi-objective,multi-item inventory model and three algorithms for its solution

We develop a multi-objective model in a multi-product inventory system.The proposed model is a joint replenishment problem(JRP) that has two objective functions.The first one is minimization of total ordering and inventory holding costs,which is the same objective function as the classic JRP.To increase the applicability of the proposed model,we suppose that transportation cost is independent of time,is not a part of holding cost,and is calculated based on the maximum of stored inventory,as is the case in many real inventory problems.Thus,the second objective function is minimization of total transportation cost.To solve this problem three efficient algorithms are proposed.First,the RAND algorithm,called the best heuristic algorithm for solving the JRP,is modified to be applicable for the proposed problem.A multi-objective genetic algorithm(MOGA) is developed as the second algorithm to solve the problem.Finally,the model is solved by a new algorithm that is a combination of the RAND algorithm and MOGA.The performances of these algorithms are then compared with those of the previous approaches and with each other,and the findings imply their ability in finding Pareto optimal solutions to 3200 randomly produced problems.     

Multiproduct multiple-buyer single-vendor supply chain problem with stochastic demand, variable lead-time, and multi-chance constraint

In this paper, a multi-product multi-chance constraint joint single-vendor multi-buyers inventory problem is considered in which the demand follows a uniform distribution, the lead-time is assumed to vary linearly with respect to the lot size, and the shortage in combination of backorder and lost-sale is assumed. Furthermore, the orders are placed in multiple of packets, there is a limited space available for the vendor, there are chance constraints on the vendor service rate to supply the products, and there is a limited budget for each buyer to purchase the products. While the elements of the buyers’ cost function are holding, shortage, order and transportation costs, the set up and holding costs are assumed for the vendor. The goal is to determine the re-order point and the order quantity of each product for each buyer such that the chain total cost is minimized. We show the model of this problem to be a mixed integer nonlinear programming type and in order to solve it a particle swarm optimization (PSO) approach is used. To justify the results of the proposed PSO algorithm, a genetic algorithm (GA) is applied as well to solve the problem. Then, the quality of the results and the CPU times of reaching the solution are compared through three numerical examples that are given to demonstrate the applicability of the proposed methodology in real world inventory control problems. The comparison results show the PSO approach has better performances than the GA method.     

A multi-machine multi-product EPQ problem for an imperfect manufacturing system considering utilization and allocation decisions

This paper considers a multi-product problem with non-identical machines. This manufacturing system consists of various machine types with different production capacities, production costs, setup times, production rates and failure rates. One of the major issues in the planning phase of a manufacturing system is to take the best decision about which machines must be utilized to manufacture which items. As a result, the decision makers face three critical questions: what machines must be purchased, which items should be allocated to each machine, and what is the optimal cycle length. These decisions must be made to minimize system costs including utilization, setup, production, holding and scrap costs. The multi-machine multi-product economic production quantity (EPQ) problem for an imperfect manufacturing system is formulated as a mixed integer non-linear programming (MINLP), where the convexity property of multi-product single machine EPQ model is used to convert the problem into a bi-level decision-making problem. In the first level, decisions about machine utilization and items allocation are made. After, in the second level the optimal cycle length for each machine is determined. To solve the problem at hand, a hybrid genetic algorithm (HGA) is proposed integrating genetic algorithm and derivatives method. In the proposed HGA, the solutions of the first level are obtained randomly and then, for the second level, the derivatives method is applied to obtain optimal cycle length based on solutions of the first level. Finally, the results of HGA method are compared to the results of general algebraic modeling system (GAMS) and it is found that HGA method has better and more efficient results. Also, a numerical experimentation and a sensitivity analysis of the model are done.     

Tabu search with path relinking for an integrated production–distribution problem

This paper deals with the problem of integrating production and distribution planning over periods of a finite horizon. We consider a capacity-constrained plant that produces a number of items distributed by a fleet of homogenous vehicles to customers with known demand for each item in each period. The production planning defines the amount of each item produced in every period, while the distribution planning defines when customers should be visited, the amount of each item that should be delivered to customers, and the vehicle routes. The objective is to minimize production and inventory costs at the plant, inventory costs at the customers and distribution costs. We propose two tabu search variants for this problem, one that involves construction and a short-term memory, and one that incorporates a longer term memory used to integrate a path relinking procedure to the first variant. The proposed tabu search variants are tested on generated instances with up to ten items and on instances from the literature involving a single item.     

A learning automata-based heuristic algorithm for solving the minimum spanning tree problem in stochastic graphs

During the last decades, a host of efficient algorithms have been developed for solving the minimum spanning tree problem in deterministic graphs, where the weight associated with the graph edges is assumed to be fixed. Though it is clear that the edge weight varies with time in realistic applications and such an assumption is wrong, finding the minimum spanning tree of a stochastic graph has not received the attention it merits. This is due to the fact that the minimum spanning tree problem becomes incredibly hard to solve when the edge weight is assumed to be a random variable. This becomes more difficult if we assume that the probability distribution function of the edge weight is unknown. In this paper, we propose a learning automata-based heuristic algorithm to solve the minimum spanning tree problem in stochastic graphs wherein the probability distribution function of the edge weight is unknown. The proposed algorithm taking advantage of learning automata determines the edges that must be sampled at each stage. As the presented algorithm proceeds, the sampling process is concentrated on the edges that constitute the spanning tree with the minimum expected weight. The proposed learning automata-based sampling method decreases the number of samples that need to be taken from the graph by reducing the rate of unnecessary samples. Experimental results show the superiority of the proposed algorithm over the well-known existing methods both in terms of the number of samples and the running time of algorithm.