Stochastic optimization for airport inventory management

Abstract

Effective supply chain management is currently recognized as a key determinant of competitiveness and success in manufacturing and services, because the implementation of supply chain management has significant impact on cost, service and quality. Numerous strategies for achieving these targets have been proposed. The improvements in information technology coupled with the substantial reduction in the cost of processing, storing and analyzing data have made new strategies more attractive. On such strategy allows movements of stock between locations at the same echelon level via lateral transshipment. Despite the above technology improvements, the implementation of such transshipment strategy requires still great efficiency especially in real life problems, because it suffers from computer memory limits and long computation times when the number of warehouses gets large, or when the number of parallel items to ba analyzed following an item approach gets large, too.In fact, a drawback of the policy of interest is the state dependent nature of the re-forwardings in the systems. Therefore an effective tactical planning requires joint contribution from various disciplines in order to be implemented efficiently, such as engineering, mathematics, economics and computer science. New solution methods have to be explored in order to effectively implementing new management strategies. This thesis uses operations research techniques in order to study a single echelon, one-for-one ordering policy with complete pooling, with a deterministic rule for lateral transshipments. Specifically we propose new evaluation and optimization methods thus handling real life problems within a reasonable amount of computation time. In fact, we test all the proposed methods on the practical case study motivated by the practical needs of an Italian logistics, supporting the activity of 38 civil airports spread over the Italian territory. The company handles 17 warehouses and manages the overall process of purchasing, holding, ensuring that the overall reliability of safety equipments is always within contractual limits. The aim of the company is therefore to grant the prescribed quality of service at minimum cost.

The items to be managed in such a context are typically expensive ones and with low demand, but we clearly recognize that there are many different types of service parts and that they perform many different functions. Therefore, in such a context also parts with a lower ratio between holding and transshipment costs may be encountered and managed. Thus with all the uncertainties that exist, a tactical plan should be created that will provide the flexibility needed to meet a wide range of scenarios, pointing the attention on the characteristics of the majority of items. Common techniques models the management policy with a Markov chain approach, thus evaluating such a policy given a spare parts allocation. The optimal stock allocation problem is formulated as an integer program with non linear objective function and non linear constraints. Therefore total enumeration methods or approximation algorithms can be employed for optimally solve it. Based on the needs summarized above, the following research objectives have been achieved in this dissertation. We have focused on a single echelon one-forone ordering policy with complete pooling, with a deterministic rule for lateral transshipments. We have formalized mathematically the Spares Allocation Problem (SAP) and have understood its mathematical structure for building an exact algorithm for optimally allocating the spares. In fact, in literature to the best of our knowledge no exact algorithm has been proposed for allocating optimally the spares in a continuous review setting rather than a total enumerative algorithm. By exploiting the above algorithm it is interesting – Making insight in the SAP and underline which factors influence inventories in such a context. – Evaluating fast and accurate heuristics for SAP. Efficient and accurate models for assessing the performance of a single echelon replenishment policy have been proposed and evaluated especially for large numbers of locations. A drawback of the policy of interest is the state dependent nature of the re-forwardings in the systems, it has been therefore interesting. – understanding the properties of the Markov chain associated to the chosen policy. – exploring, despite its state dependent nature, the possibility of expressing the state probabilities of the associated Markov chain model exactly in product form – developing fast and accurate approximate models for evaluating the performance and costs in the system, since computing the state probabilities is not practical as the number of states in the Markov chain increases. The achievement of the first objective clearly required a strong connection with the resolution of the second objective. In fact, the development of an exact algorithm for allocating the spares may require in contexts with a large number of warehouses and high rates approximate models for assessing the performance and evaluating the costs. Specifically, n this thesis by using a suitable optimization model we have shown that the Markov chain cannot be decomposed exactly in product form. In fact, the best product form approximation returns a positive accuracy error, which implies that an exact product form does not exist. Hence, we have adapted four approximation techniques to our model and evaluate their performance in terms of computational effort, memory requirement and error with respect to the exact value. Three techniques approximate state probabilities with others that can be expressed in product form, so that the Markov chain can be decomposed. Specifically, we adapt a method by Alfredsson and Verrijdt, the Equivalent Random Traffic (ERT) method and the Interrupted Poisson Process (IPP) method. The last two techniques have been proposed for exploring the influence of peakedness in approximation models with respect to the accuracy of performance estimation due to the state dependent nature of the re-forwardings in the system. The fourth technique is based on the multi-dimensional scaling down approach, which studies an equivalent reduced Markov chain rather than decomposing the original one. The scaling down method outperforms the decomposition techniques for small OA values (OA < 0.997), while the percentage error is similar for larger OA values. Besides the better performance shown in figure, in our experiments the scaling down method provides OA values smaller than the exact ones in more than 80% of the experiments while the decomposition methods find OA values always larger than the exact ones. The scaling down method is therefore more conservative than the decomposition methods, and this is an important feature when the method has to be used within an optimization

The formulation and solution of the Spares Allocation Problem (SAP) is one of the main achievements of this thesis. The mathematical structure of the problem has been investigated to build an efficient exact algorithm for optimally allocating the spares. Two assumption on the cost structure of the problem leads to prove properties of the cost function that in turns allow to design a new efficient branch and bound procedure. The lower bound is obtained by solving a reduced problem with convex objective function, solvable at optimally very efficiently. A new fast heuristic algorithm is also developed to find a feasible allocation within small computation time. Computational experiments demonstrate that the branch and bound technique is able to optimally solve almost all tested instances within reasonable computation time. The heuristic algorithm finds quite good solutions within very limited computation time, thus being a promising approach for finding feasible solutions to difficult instances. Moreover we have analyzed several cost structure scenarios and we have observed that the transshipment cost is often comparable with the holding cost and therefore it cannot be neglected in the solution of the problem.