It is the primary responsibility of a gas pipeline company to satisfy the gas demand of customers and ensure the economical operation of its pipelines. This paper presents a stochastic multi-objective transient peak shaving optimization model that considers uncertainty in gas demand while optimizing operational schemes of compressors and peak shaving measures of underground gas storages. The model is a rigorous multi-objective non-linear program (NLP) constrained by governing gas flow equations, operating envelopes of centrifugal compressors, and thermodynamic equations that model natural gas properties. The proposed multi-objective model aims to minimize the operational costs (the sum of the electricity cost of compressor stations and the gas withdrawal cost of underground gas storage) and maximize the line pack at the end of the time horizon subject to multiple legal and physical constraints. The model was tested on a real gas pipeline system, and a set of Pareto optimal solutions are obtained. The optimal operational schemes and peak shaving measures under three typical Pareto optimal solutions are analyzed in detail, and numerical results are presented following stochastic and robust optimization approaches.