GRASP-based heuristic algorithm for the multi-product multi-vehicle inventory routing problem

In this paper, we introduce an improved Greedy Randomized Adaptive Search Procedure (GRASP) based heuristic for the multi-product multi-vehicle inventory routing problem (MMIRP). The inventory routing problem, which combines the vehicle-routing problem and the inventory control decisions, is one of the most important problems in combinatorial optimization field. To deal with the MMIRP, we develop a GRASP-based heuristic (GBH). Each GBH iteration consists of two sequential phases; the first phase is a Greedy Randomized Procedure, in which, the best tradeoff between the inventory holding cost and routing cost is looked. Then, in the second phase, as local search for the GRASP, we use the Tabu search (TS) meta-heuristic to improve the solution found in the first phase. The GBH two phases are repeated until some stopped criterion is met. Our proposed method is evaluated on two benchmark data sets, and successfully compared with two state-of-the-art algorithms.     

Routing and scheduling in a liquefied natural gas shipping problem with inventory and berth constraints

Liquefied natural gas (LNG) is natural gas that has been transformed to liquid form for the purpose of transportation, which is mainly done by specially built LNG vessels travelling from the production site to the consumers. We describe a real-life ship routing and scheduling problem from the LNG business, with both inventory and berth capacity constraints at the liquefaction port. We propose a solution method where the routing and scheduling decisions are decomposed. The routing decisions consist of deciding which vessels should service which cargoes and in what sequence. The scheduling decisions are then to decide when to start servicing the cargoes while satisfying inventory and berth capacity constraints. The proposed solution method has been tested on several problem instances based on the real-life problem. The results show that the proposed solution method is well suited to solve this LNG shipping problem.     

An adaptive large neighborhood search algorithm for a selective and periodic inventory routing problem

We study a selective and periodic inventory routing problem (SPIRP) and develop an Adaptive Large Neighborhood Search (ALNS) algorithm for its solution. The problem concerns a biodiesel production facility collecting used vegetable oil from sources, such as restaurants, catering companies and hotels that produce waste vegetable oil in considerable amounts. The facility reuses the collected waste oil as raw material to produce biodiesel. It has to meet certain raw material requirements either from daily collection, or from its inventory, or by purchasing virgin oil. SPIRP involves decisions about which of the present source nodes to include in the collection program, and which periodic (weekly) routing schedule to repeat over an infinite planning horizon. The objective is to minimize the total collection, inventory and purchasing costs while meeting the raw material requirements and operational constraints. A single-commodity flow-based mixed integer linear programming (MILP) model was proposed for this problem in an earlier study. The model was solved with 25 source nodes on a 7-day cyclic planning horizon. In order to tackle larger instances, we develop an ALNS algorithm that is based on a rich neighborhood structure with 11 distinct moves tailored to this problem. We demonstrate the performance of the ALNS, and compare it with the MILP model on test instances containing up to 100 source nodes.     

A new model and hybrid approach for large scale inventory routing problems

This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.     

Large scale stochastic inventory routing problems with?split delivery and service level constraints

A stochastic inventory routing problem (SIRP) is typically the combination of stochastic inventory control problems and NP-hard vehicle routing problems, which determines delivery volumes to the customers that the depot serves in each period, and vehicle routes to deliver the volumes. This paper aims to solve a large scale multi-period SIRP with split delivery (SIRPSD) where a customer??s delivery in each period can be split and satisfied by multiple vehicle routes if necessary. This paper considers SIRPSD under the multi-criteria of the total inventory and transportation costs, and the service levels of customers. The total inventory and transportation cost is considered as the objective of the problem to minimize, while the service levels of the warehouses and the customers are satisfied by some imposed constraints and can be adjusted according to practical requests. In order to tackle the SIRPSD with notorious computational complexity, we first propose an approximate model, which significantly reduces the number of decision variables compared to its corresponding exact model. We then develop a hybrid approach that combines the linearization of nonlinear constraints, the decomposition of the model into sub-models with Lagrangian relaxation, and a partial linearization approach for a sub model. A near optimal solution of the model found by the approach is used to construct a near optimal solution of the SIRPSD. Randomly generated instances of the problem with up to 200 customers and 5 periods and about 400 thousands decision variables where half of them are integer are examined by numerical experiments. Our approach can obtain high quality near optimal solutions within a reasonable amount of computation time on an ordinary PC.     

Selective and periodic inventory routing problem for waste vegetable oil collection

We consider a biodiesel production company that collects waste vegetable oil from source points that generate waste in large amounts. The company uses the collected waste as raw material for biodiesel production. The manager of this company needs to decide which of the present source points to include in the collection program, which of them to visit on each day, which periodic routing schedule to repeat over an infinite horizon and how many vehicles to operate such that the total collection, inventory and purchasing costs are minimized while the production requirements and operational constraints are met. For this selective and periodic inventory routing problem, we propose two different formulations, compare them and apply the better performing one on a real-world problem with 36 scenarios. We generate lower bounds using a partial linear relaxation model, and observe that the solutions obtained through our model are within 3.28% of optimality on the average. Several insights regarding the customer selection, routing and purchasing decisions are acquired with sensitivity analysis.     

A hybrid tabu search based heuristic for the periodic distribution inventory problem with perishable goods

Most of the research on integrated inventory and routing problems ignores the case when products are perishable. However, considering the integrated problem with perishable goods is crucial since any discrepancy between the routing and inventory cost can double down the risk of higher obsolescence costs due to the limited shelf-life of the products. In this paper, we consider a distribution problem involving a depot, a set of customers and a homogeneous fleet of capacitated vehicles. Perishable goods are transported from the depot to customers in such a way that out-of-stock situations never occur. The objective is to simultaneously determine the inventory and routing decisions over a given time horizon such that total transportation cost is minimized. We present a new “arc-based formulation” for the problem which is deemed more suitable for our new tabu search based approach for solving the problem. We perform a thorough sensitivity analysis for each of the tabu search parameters individually and use the obtained gaps to fine-tune the parameter values that are used in solving larger sized instances of the problem. We solve different sizes of randomly generated instances and compare the results obtained using the tabu search algorithm to those obtained by solving the problem using CPLEX and a recently published column generation algorithm. Our computational experiments demonstrate that the tabu search algorithm is capable of obtaining a near-optimal solution in less computational time than the time required to solve the problem to optimality using CPLEX, and outperforms the column generation algorithm for solving the “path flow formulation” of the problem in terms of solution quality in almost all of the considered instances.     

A computational comparison of algorithms for the inventory routing problem

The inventory routing problem is a distribution problem in which each customer maintains a local inventory of a product such as heating oil and consumes a certain amount of that product each day. Each day a fleet of trucks is dispatched over a set of routes to resupply a subset of the customers. In this paper, we describe and compare algorithms for this problem defined over a short planning period, e.g. one week. These algorithms define the set of customers to be serviced each day and produce routes for a fleet of vehicles to service those customers. Two algorithms are compared in detail, one which first allocates deliveries to days and then solves a vehicle routing problem and a second which treats the multi-day problem as a modified vehicle routing problem. The comparison is based on a set of real data obtained from a propane distribution firm in Pennsylvania. The solutions obtained by both procedures compare quite favorably with those in use by the firm.Part of this work was performed while this author was visiting the University of Waterloo.     

Hybrid heuristics for a short sea inventory routing problem

We consider a short sea fuel oil distribution problem where an oil company is responsible for the routing and scheduling of ships between ports such that the demand for various fuel oil products is satisfied during the planning horizon. The inventory management has to be considered at the demand side only, and the consumption rates are given and assumed to be constant within the planning horizon. The objective is to determine distribution policies that minimize the routing and operating costs, while the inventory levels are maintained within their limits. We propose an arc-load flow formulation for the problem which is tightened with valid inequalities. In order to obtain good feasible solutions for planning horizons of several months, we compare different hybridization strategies. Computational results are reported for real small-size instances.     

A practical solution approach for the cyclic inventory routing problem

Vendor managed inventory (VMI) is an example of effective cooperation and partnering practices between up- and downstream stages in a supply chain. In VMI, the supplier takes the responsibility for replenishing his customers’ inventories based on their consumption data, with the aim of optimizing the over all distribution and inventory costs throughout the supply chain. This paper discusses the challenging optimization problem that arises in this context, known as the inventory routing problem (IRP). The objective of this IRP problem is to determine a distribution plan that minimizes average distribution and inventory costs without causing any stock-out at the customers. Deterministic constant customer demand rates are assumed and therefore, a long-term cyclical approach is adopted, integrating fleet sizing, vehicle routing, and inventory management. Further, realistic side-constraints such as limited storage capacities, driving time restrictions and constant replenishment intervals are taken into account. A heuristic solution approach is proposed, analyzed and evaluated against a comparable state-of-the-art heuristic.     

A solution approach to the inventory routing problem in a three-level distribution system

We consider the infinite horizon inventory routing problem in a three-level distribution system with a vendor, a warehouse and multiple geographically dispersed retailers. In this problem, each retailer faces a demand at a deterministic, retailer-specific rate for a single product. The demand of each retailer is replenished either from the vendor through the warehouse or directly from the vendor. Inventories are kept at both the retailers and the warehouse. The objective is to determine a combined transportation (routing) and inventory strategy minimizing a long-run average system-wide cost while meeting the demand of each retailer without shortage. We present a decomposition solution approach based on a fixed partition policy where the retailers are partitioned into disjoint and collectively exhaustive sets and each set of retailers is served on a separate route. Given a fixed partition, the original problem is decomposed into three sub-problems. Efficient algorithms are developed for the sub-problems by exploring important properties of their optimal solutions. A genetic algorithm is proposed to find a near-optimal fixed partition for the problem. Computational results show the performance of the solution approach.     

第三方库存-路线问题的模型及混合遗传算法设计

根据第三方库存-路线问题的特点,以车辆租赁费用和运行费用之和为目标函数,不限制客户每次的配送量小于车辆容量,建立了满载运输和非满载运输混合的整数规划模型.针对第三方库存-路线问题的复杂性,本文设计嵌入禁忌搜索的遗传算法来同时决策库存和路线问题.首先对配送间隔进行编码,然后用禁忌搜索法计算每天需要配送的车辆路线问题.最后与其下界值进行比较,结果表明该算法是一个有效的算法,不但第三方能取得较低的运营总成本和较高的车辆利用率,而且也能为客户节约库存空间.     

Fleet routing position-based model for inventory pickup under production shutdown

This paper addresses the problem of collecting inventory of production at various plants having limited storage capacity, violation of which forces plant shutdowns. The production at plants is continuous (with known rates) and a fleet of vehicles need to be scheduled to transport the commodity from plants to a central storage or depot, possibly making multiple pickups at a given plant to avoid shutdown. One operational objective is to achieve the highest possible rate of product retrieval at the depot, relative to the total travel time of the fleet. This problem is a variant (and generalization) of the inventory routing problem. The motivating application for this paper is barge scheduling for oil pickup from off-shore oil-producing platforms with limited holding capacity, where shutdowns are prohibitively expensive. We develop a new model that is fundamentally different from standard node-arc or path formulations in the literature. The proposed model is based on assigning a unique position to each vehicle visit at a node in a chronological sequence of vehicle-nodal visits. This approach leads to substantial flexibility in modeling multiple visits to a node using multiple vehicles, while controlling the number of binary decision variables. Consequently, our position-based model solves larger model instances significantly more efficiently than the node-arc counterpart. Computational experience of the proposed model with the off-shore barge scheduling application is reported.     

随机的库存-路径问题的机会约束规划模型与算法

随机需求下的库存-路径问题是一类复杂的组合优化问题.本文讨论了VMI背景下的库存-路径联合优化问题,构建了问题的机会约束规划模型,并将随机模拟、人工神经网络和遗传算法结合在一起,设计了求解问题的混合智能算法.实验表明算法性能良好.     

考虑横向整合战略的库存路径动态区域定价

库存路径和定价是供货商管理库存(Vendor Management Inventory, VMI)中三个互相制约和影响的决策问题,是降低供货商成本,提高其利润的关键。针对VMI拉式供应链中多供货商、多商品和多区域的库存路径定价问题,提出了对不同区域客户、在不同时段进行商品差异化定价策略,并设计一种共同配送车辆司机成本和燃油成本分摊方案,据此构建基于横向整合战略的库存路径动态区域定价模型。算例结果显示,在横向整合战略下,供货商商品定价会有所降低,配送车辆行驶距离显著缩短,各时段配货量更为均衡,期末库存数量显著降低。研究表明,无论供货商之间供货规模比例差异多大,开展库存路径动态区域定价,供货商联盟成员的利润均能得到显著提高,实现合作共赢的目标。     

求解硬时间窗约束下随机需求库存-路径问题的优化算法

随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem, SDIRP)即考虑随机需求环境下供应链中库存与配送的协调优化问题,是实施供应商管理库存策略过程中的关键所在,也是典型的NP难题之一。文章以具有硬时间窗约束的随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem with Hard Time Windows, SDIRPHTW)为研究对象,将SDIRPHTW分解为直接配送的随机库存-路径问题和具有硬时间窗约束的路径优化问题两个子问题,并以最小化系统运行成本和用车数量为目标,设计了一个基于(s,S)库存策略和修正C-W节约法的启发式算法。最后,通过相应的数值算例验证了算法的有效性。     

Managing inventory and service levels in a safety stock‐based inventory routing system with stochastic retailer demands

The inherent uncertainty in supply chain systems compels managers to be more perceptive to the stochastic nature of the systems' major parameters, such as suppliers' reliability, retailers' demands, and facility production capacities. To deal with the uncertainty inherent to the parameters of the stochastic supply chain optimization problems and to determine optimal or close to optimal policies, many approximate deterministic equivalent models are proposed. In this paper, we consider the stochastic periodic inventory routing problem modeled as chance‐constrained optimization problem. We then propose a safety stock‐based deterministic optimization model to determine near‐optimal solutions to this chance‐constrained optimization problem. We investigate the issue of adequately setting safety stocks at the supplier's warehouse and at the retailers so that the promised service levels to the retailers are guaranteed, while distribution costs as well as inventory throughout the system are optimized. The proposed deterministic models strive to optimize the safety stock levels in line with the planned service levels at the retailers. Different safety stock models are investigated and analyzed, and the results are illustrated on two comprehensively worked out cases. We conclude this analysis with some insights on how safety stocks are to be determined, allocated, and coordinated in stochastic periodic inventory routing problem. Copyright © 2017 John Wiley & Sons, Ltd.     

An integrated inventory–transportation system with modified periodic policy for multiple products

Efficient management of a distribution system requires an integrated approach towards various logistical functions. In particular, the fundamental areas of inventory control and transportation planning need to be closely coordinated. Our model deals with an inbound material-collection problem. An integrated inventory–transportation system is developed with a modified periodic-review inventory policy and a travelling-salesman component. This is a multi-item joint replenishment problem, in a stochastic setting, with simultaneous decisions made on inventory and transportation policies. We propose a heuristic decomposition method to solve the problem, minimizing the long-run total average costs (major- and minor-ordering, holding, backlogging, stopover and travel). The decomposition algorithm works by using separate calculations for inventory and routing decisions, and then coordinating them appropriately. A lower bound is constructed and computational experience is reported.     

Model and algorithm for inventory/routing decision in a three-echelon logistics system

This paper addresses an integrated inventory and routing problem in a three-echelon logistics system, which consists of a supplier, a central warehouse and a group of retailers. The inventory decision of each member and the routing decision among members of the system are made simultaneously, with the objective of minimizing the overall average cost of the system. A strategy named fixed partition and power-of-two (FP–POT) is proposed for the considered problem and a variable large neighborhood search (VLNS) algorithm, which is a special case of variable neighborhood search (VNS) algorithm, is developed. The efficiency of the strategy as well as the algorithm is illustrated by comparing computational results with a lower bound. The advantage of the proposed VLNS algorithm is further shown by getting better results for the problems in a two-echelon logistics system, which have been solved by a Tabu Search algorithm recently.