The International Maritime Organization has introduced the concept of Emission Control Area to reduce sulfur emissions from coastal areas. The expensive low-sulfur fuels are required to be used in Emission Control Area, leading to increased sulfide emissions due to bypassing by ship operators. It creates new challenges for navigation and power generation scheduling of all-electric ships. This article presents a new bi-objective joint optimization scheme for ship sailing routes and energy management. It considers emission control strategies to balance the total cost of operation and sulfur dioxide emissions throughout the ship’s voyage. Unlike previous optimization problems with fixed routes and sailing time, the influence of emission policies on the operator’s navigation decisions is considered. The route options and sailing time are treated as variables embedded in the model. In addition, the optimization accuracy is improved by integrating the model into mixed integer linear programming through a modified piecewise linearization model. The results show that the total operating cost for the same route is reduced by 6.05%, and the SO2 emission is 8.36% after integrating the emission policy influencing factor in the model. The effectiveness of the proposed scheme is validated, and the model’s necessity for optimizing ship power generation and voyage within Emission Control Area is also illustrated.