In response to growing environmental concerns and regulatory pressures, reducing carbon emissions in maritime transport has become a priority. Shipping companies face the challenge of balancing profitability objectives with the imperative to minimize their environmental footprint. This study addresses the tramp ship routing and scheduling problem by incorporating the carbon intensity indicator (CII) into the optimization framework. A bi-objective optimization model is developed, with two objective functions aimed at maximizing fleet profit and improving CII ratings. The Gale–Shapley algorithm is employed to achieve stable vessel–cargo matching, and the genetic algorithm is adopted for iterative optimization. This computational study, based on real historical data, verifies the effectiveness of the proposed model and algorithm. The results demonstrate notable improvements in fleet efficiency and environmental performance, increasing profitability by 4.38% while maintaining favorable CII ratings. The findings provide valuable theoretical guidance for shipping companies navigating increasingly stringent CII regulations.