Nowadays, trajectory data is widely accessible and can be beneficial for various practical applications, such as location-based services, personalized recommendation, and traffic management. Despite the immense benefits in these scenarios, trajectories can reveal highly sensitive information about individuals, such as personal characteristics, movement patterns, visited locations, and social connections. Consequently, it is imperative to prioritize protecting privacy when conducting trajectory analyses. Existing privacy-preserving techniques focus on optimizing data utility but often overlook the diverse requirements for privacy preservation. To address this limitation, this paper aims to maximize both privacy and utility as a multi-objective optimization problem for Privacy-Preserving Trajectory Data Publishing (PPTDP). We propose a novel algorithm called Dynamic-Parameter Genetic Algorithm (DPGA) that utilizes the non-dominated sorting multi-objective optimization approach and genetic algorithm (GA). This algorithm designs the mutation and crossover strategies to dynamically adjust the mutation and crossover parameters and improve the solution’s quality. It also adopts a scramble mutation strategy that helps to achieve better population diversity. Extensive experiments demonstrate the efficiency of the proposed algorithm in terms of solution accuracy and convergence result.