The application of a stationary ultra-capacitor energy storage system (ESS) in urban rail transit allows for the recuperation of vehicle braking energy for increasing energy savings as well as for a better vehicle voltage profile. This paper aims to obtain the best energy savings and voltage profile by optimizing the location and size of ultra-capacitors. This paper firstly raises the optimization objective functions from the perspectives of energy savings, regenerative braking cancellation and installation cost, respectively. Then, proper mathematical models of the DC (direct current) traction power supply system are established to simulate the electrical load-flow of the traction supply network, and the optimization objections are evaluated in the example of a Chinese metro line. Ultimately, a methodology for optimal ultra-capacitor energy storage system locating and sizing is put forward based on the improved genetic algorithm. The optimized result shows that certain preferable and compromised schemes of ESSs’ location and size can be obtained, acting as a compromise between satisfying better energy savings, voltage profile and lower installation cost.