روش جستجوی محلی یکپارچه برای تصمیمات موجودی و مسیریابی

The present article studies an inventory routing model which integrates two important components of the supply chain: transportation logistics and inventory control. The distribution system examined consists of customers that face product demand at a deterministic and constant rate. Customer demand is satisfied by a fixed vehicle fleet located at the central depot. The aim of the problem is to determine the timing and size of the replenishment services together with the vehicle routes, so that the total transportation and inventory holding cost of the system is minimized. In methodological terms, we propose a solution approach applying two innovative local search operators for jointly dealing with the inventory and routing aspects of the examined problem, and Tabu Search for further reducing the transportation costs. The proposed algorithmic framework was tested on a set of new benchmark instances of various scales. It produced satisfactory results both in terms of effectiveness and robustness.

The Inventory Routing Problem (IRP) is an important integration of two key elements of the supply chain management, namely the distribution process and the inventory control. Both transportation and inventory issues have been mostly examined as independent operations without their interplay being thoroughly investigated. However, it has been well realized that effectively dealing with their integration can result into significant benefits for the overall supply chain system. The IRP finds commercial applicability in the Vendor Managed Inventory (VMI) business model. Following the VMI strategy, the vendor has the freedom to decide the timing and the size of the deliveries to the customers, and the obligation to ensure that customers do not face any stock-outs. In the present paper, we study a practical IRP model over a finite periodic planning horizon of T time units (t = 1, 2, …, T); consisting of n customers (retailers) and a central warehouse (depot). With each customer i (i = 1, 2, …, n) is associated a constant demand of di product units per time period, and a unit inventory holding cost equal to hi. The customer demand is satisfied by a fixed-size fleet of vehicles based at the depot without any stock-out occurrences throughout the planning horizon. Implementing a transition between two locations i and j of the problem (either customer pair or the depot and a customer) incurs a fixed cost equal to cij. The goal of this combinatorial optimization problem is to determine the schedule, so as to minimize the total inventory and routing costs faced by the overall system. This schedule is composed by the route set, as well as the delivered quantities, for each time unit. Regarding previously published IRP models and solution approaches, the research stream has been focused on three distinct problem categories according to the time horizon considered: (i) single-period, (ii) multi-period, and (iii) infinite horizon. Since the problem we examine belongs to the latter category of models, we provide an analytic review for the infinite horizon category, for which several distribution systems and solution methodologies have been published. To reduce the computational complexity of the problem many researchers have proposed fixed partition (FP) inventory policies for replenishing the customer population. Under an FP policy, whenever a customer in a given partition is visited by a vehicle, this vehicle also serves all other customers in the partition. Anily and Federgruen (1990) have considered a distribution system composed by multiple customers served by a central depot (warehouse). Each customer faces a constant deterministic product demand rate, while inventory is held only at the customer locations. The aim of their paper is to determine the inventory strategies and routing patterns that minimize the total long-term cost of the system. The inventory aspects are dealt by employing an FP policy. In detail, a collection of regions is specified. With each of these regions is associated a customer set. If a customer is assigned to more than one region, each of the regions takes responsibility for a fraction of the customer demand. In this way, a customer may be replenished before its stock has been exhausted at the expense of higher inventory cost. The same authors (Anily & Federgruen, 1993) also employ an FP policy to minimize the total running cost of a distribution system in which inventory can be held both at the customers, and the central warehouse. Furthermore, fixed ordering cost is taken into consideration. Another FP policy is employed by Bramel and Simichi-Levi (1995) for a similar IRP model with transportation, inventory and fixed ordering costs. To partition the customers into disjoint sets, they transform the problem into a Capacitated Concentrator Location Problem (CCLP). The generated customer sets are then heuristically improved in terms of their routing cost. Archetti, Bertazzi, Laporte, and Speranza (2007) consider an IRP system, over a given horizon, in which replenishments are dictated by a deterministic order-up-to policy. To solve the examined model they propose a branch-and-cut algorithm. Other solution approaches commonly adopt the power-of-two (POT), stationary and nested inventory policies: under a POT policy, replenishments occur every T time units, where T is a power-of-two multiple of some base planning period TB, a stationary policy is characterized by constant time intervals between replenishments of a given customer, while nested is a policy for which if a replenishment interval of a customer is greater than that of another, the former must be a multiple of the latter. Herer and Roundy (1997) study a system facing inventory, ordering, and routing costs. They adopt a power-of-two (POT) policy for replenishing customers. In their work, vehicles are assumed to have unlimited capacity. Viswanathan and Mathur (1997) investigate a multi-echelon and multi-product system for which the customer demand rate is constant and known, while inventory is held only at the customer locations. Their solution approach consists of a heuristic methodology using a nested stationary POT policy. Two solution methodologies combining both the FP, and the POT policies come from Jung and Mathur, 2007 and Zhao et al., 2007. These works examine a distribution system in which customers face a constant demand rate. Inventory can be held both at the central depot, and customer locations, while fixed ordering costs are also taken into consideration. Zhao, Wang, and Lai (2007) adopt the FP policy, so that customers are partitioned into disjoint sets. Each of these sets is served independently of each other according to the POT policy that minimizes the total ordering and inventory cost. To obtain the final solution, the authors apply a Tabu Search procedure in order to optimally partition the customer population. Jung and Mathur (2007) propose an effective solution approach following an FP, POT stationary inventory policy. Customers are partitioned into disjoint clusters, the replenishment interval of which must be a POT multiple of some base period. Adapting this POT policy, the authors can easily implement stationary nested policies for the reorder of customers belonging to the same cluster. Following these policies, whenever a customer in a cluster is replenished, all customers having lower reorder interval and belonging to this cluster are replenished simultaneously. The reorder intervals for the warehouse and the customers are obtained by a heuristic procedure that minimizes the long-run inventory, ordering and routing costs of the studied distribution system. The purpose of this paper is to propose an integrated local search methodology designed for the investigated IRP model. Our solution approach is not limited to several limitations concerning the adopted inventory policies. As presented in the literature review, to keep the IRP tractable, most of the solution approaches restrict themselves to some inventory strategy which heavily dictates the structure of the solution produced: following a partition policy, customer subgroups are bounded to be visited independently of each other. Under POT and nested strategies, customers are forced to be replenished at stationary intervals. Furthermore, the majority of the solution strategies do not treat the replenishment quantities as mere decision variables: the size of the deliveries is determined by the customer replenishment intervals, so that all customers are replenished when their inventory level reaches zero. Avoiding these restrictive policies, our algorithm treats the routing and inventory aspects in an integrated manner, solely controlled towards the minimization of the objective function. To do so, we have designed innovative local search operators that effectively deal with the IRP joint characteristics. In cooperation with these methods, our approach uses Tabu Search (TS) (Glover, 1986) for further improving the routing quality of the overall system. Our model is a new IRP variant, differentiated in terms of how replenishment timing is dealt with: instead of determining the frequencies of the replenishment services, we aim to construct replenishment schedules over a finite planning horizon of T time units, during which all customers must be visited and serviced. Therefore, the algorithmic performance is evaluated on 10 new problem instances, of various sizes, that were specially designed for the proposed IRP system, and not on previously introduced benchmark problems. The remainder of the article is outlined as follows: Section 2 provides an analytic description, together with a mathematical formulation of the examined system. The adopted solution approach is presented in detail in Section 3, followed by its computational results in Section 4. Finally, Section 5 concludes the paper, giving possible future research directions.

In this paper, we study an IRP model which jointly deals with two crucial elements of the supply chain: inventory holding and transportation. The examined IRP consists of a single central depot and many customers over a finite periodic planning horizon. Each customer faces a deterministic constant demand rate. This demand is satisfied by replenishment services executed by a fixed-size fleet of capacitated vehicles. Inventory is held only at customer locations, at the expense of a linear inventory holding cost. Aim of the problem is to determine the size and timing of the replenishment services, as well as the vehicle routes, so that the total inventory and transportation cost of the distribution system is minimized. As seen from the provided problem formulation, optimally solving medium- and large-scale instances of the examined IRP model would require impractical computational effort. Therefore, our interest was focused on metaheuristic methods which can produce high quality solutions in acceptable computational times. We propose a solution approach which employs two innovative local search operators for jointly tackling the inventory and transportation aspects of the problem. The routing quality of the distribution system is further improved by a Tabu Search procedure. To tune the parameters of the algorithmic framework, and evaluate its performance, we applied it on a set of new benchmark instances of various scales introduced in the present article. In terms of future research directions, the problem formulation could be extended to allow inventory holding at the depot, synchronization issues for transferring inventory from the depot to the customers, as well as fixed ordering costs. In terms of the product demand, the model could be extended for covering multi-item and time-dependent customer demand.