Augmented Simultaneous Perturbation Stochastic Approximation (ASPSA) for Discrete Supply Chain Inventory Optimization Problems

Open Access
Wang, Liya
Graduate Program:
Industrial Engineering
Doctor of Philosophy
Document Type:
Date of Defense:
September 22, 2006
Committee Members:
  • Vittaldas V Prabhu, Committee Member
  • Arunachalam Ravindran, Committee Member
  • Ling Rothrock, Committee Member
  • Hong Xu, Committee Member
  • Simulation based optimization
  • supply chain optimization
In recent years, simulation optimization has attracted a lot of attention because simulation can model the real systems in fidelity and capture the dynamics of the systems. Simultaneous Perturbation Stochastic Approximation (SPSA) is a simulation optimization algorithm that has attracted considerable attention because of its simplicity and efficiency. SPSA performs well for many problems but does not converge for some. This research proposes Augmented Spontaneous Perturbation Stochastic Approximation (ASPSA) algorithm in which SPSA is extended to include presearch, ordinal optimization, non-uniform gain, and line search. Extensive tests show that ASPSA achieves speedup and improves solution quality. ASPSA is also shown to converge. For unconstrained problems ASPSA uses random presearch whereas for constrained problems presearch search is used to find a feasible solution, thereby extending the gradient based approach. Performance of ASPSA is tested for supply chain inventory optimization problems including serial and fork-join supply chain without constraints and fork-join supply chain network with customer service level constraints. To evaluated performance of ASPSA, a naïve implementation of Genetic Algorithm is used to primarily test solution quality and indicate computation effort. Experiments show that ASPSA is comparable to Genetic Algorithms (GAs) in solution quality (worst case 16.67%) but is much more efficient computationally (12x faster).