In energy markets, regulators are often tempted to use price schedules to improve economic efficiency and promote a reasonable resource allocation. Time-of-use pricing is very popular with economists, and many researchers have been written estimating and exploring the optimal time-of-use pricing for electricity markets. Yet, such pricing has rarely been used in the natural gas sector. In this paper, we propose an optimal time-of-use pricing in urban gas market based on an evolutionary game-theoretic perspective. As the urban gas market is a nonlinear complex economic system with several interacting agents, we use a multi-agent system comprising a government agent, a local gas distribution operator agent, and different types of end-user agents. A power structure demand response program is employed to simulate the user demand response. A mixed-integer linear programming is formulated to determine the time-of-use price-signal delivering maximum gas operator profit and the optimal load pattern for end-users. In an illustrative example, we simulate and compare the time-of-use block prices and time of-use hourly prices with traditional fixed pricing using real-world data of Wuhan in China. The numerical results indicate that time-of-use pricing schedules have significant potential for peak-shaving and load-shifting for urban gas pipeline network systems and would thus lower operating costs. Furthermore, different gas users exhibit different demand responsiveness intensity. Finally, we evaluate the impact on total social welfare of regulation scenarios and find that welfare decreases with deregulation, implying that the urban gas market is immature and reasonable regulation is still necessary. (C) 2015 Elsevier Ltd. All rights reserved.