This paper addresses the optimization of Launch and Deployment (L&D) strategies for Low Earth Orbit (LEO) satellite constellations using Orbital Transfer Vehicles (OTVs). The problem is formulated as a bi-objective combinatorial optimization model that simultaneously minimizes the number of launches and the average fuel consumption, thereby reducing launch costs and improving mission reliability. To enhance solution diversity, the ϵ-constraint method is employed to decompose the original problem into a series of constrained single-objective subproblems. A Cluster and Nearest Sorting initialized Genetic Algorithm with Local Search (CNS-LSGA) is developed to efficiently solve these subproblems. The CNS initialization mechanism is specifically designed to avoid infeasible solutions caused by limited OTV fuel and the high fuel requirements of LEO orbital maneuvers, while two local search operators are incorporated to improve local exploitation. Comparative evaluations across three LEO constellation architectures demonstrate that the proposed framework is both effective and robust, and can consistently obtain greater solution diversity and higher-quality results than the established population-based multi-objective algorithms.