Liquefied natural gas (LNG) is estimated to account for a growing portion of the world natural gas trade. For profitable operation of a capital intensive LNG project, it is necessary to optimally design various aspects of the supply chain associated with it. Of particular interest is optimization of ship schedules and the inventories on the production and re-gasification terminals. This can be achieved by modelling the LNG supply chain as a LNG inventory routing problem (LNG-IRP). In spite of significant recent developments in algorithms and heuristics for the LNG-IRP, large problems of practical significance still take a large amount of time to solve. In this paper, we address this issue by proposing several deterministic and non-deterministic parallel large neighborhood search algorithms for solving large LNG-IRPs. We characterize the performance of these algorithms using metrics that describe accuracy, speed-up, and processor utilization. Computational investigation on a test-suite of 11 large LNG-IRPs indicate that these algorithms can obtain solutions of comparable accuracy to state-of-the art serial benchmark solution techniques with appreciable speed-up.