Performance Analysis of Online Algorithms for Logistics Models with Online Customer Selection

In this thesis, we review and extend the results of the recent paper ”Supply Chain Management with Online Custmoer Selection” by Elmachtoub and Levi (2016). The authors study online versions of four logistics models with rejection option, where the supplier has a freedom to decide whether to serve or reject a customer request without having any prior knowledge of the future customer arrivals. In order to make the cost minimizing customer selections, they provide two unique online algorithms, CopyCat Algorithm and StablePair Algorithm, that apply the concept of repeated reoptimization of corresponding offline subproblems. They provide computational studies of both algorithms for two types of inventory control problems, Economic Lot Sizing Problem and Joint Replenishment Problem, with online customer selection (online ELSP-CS, online JRP-CS) as well as a Facility Location Problem with online customer selection (online FLP-CS). We first reproduce the computational results of the CopyCat and the StablePair for the online ELSP-CS and the online JRP-CS. Then we consider three interesting applications of the CopyCat and the Sta-blePair for (i) the online ELSP-CS and the online JRP-CS with production availability date, (ii) the online JRP-CS with a submodular cost structure, and (iii) an online version of Prize Collecting Travelling Sales-man Problem (online PCTSP). Using the well-known competitive ratio framework, we demonstrate that our experiments for the online ELSP-CS and the online JRP-CS correctly reproduce the performance of the benchmark results. Moreover, we observe that the inclusion of production availability date substan-tially decreases the computation time of the CopyCat at a cost of increased competitive ratios. Also, we show that associating the submodular cost structure to the online JRP-CS largely increases the com-plexity for both CopyCat and StablePair. Finally, the CopyCat Algorithm on the online PCTSP show a comparable strength to the J-L online algorithm provided by Jaillet and Lu (2013) for a small number of requests, but significantly worse for large instances.