Personalized trip planning is a challenging problem given that places of interest should be selected according to user preferences and sequentially arranged while satisfying various constraints. In this study, we aimed to model various uncertain aspects that should be considered during trip planning and efficiently generate personalized plans that maximize user satisfaction based on preferences and constraints. Specifically, we propose a probabilistic itinerary evaluation model based on a hybrid temporal Bayesian network that determines suitable itineraries considering preferences, constraints, and uncertain environmental variables. The model retrieves the sum of time-weighted user satisfaction, and ant colony optimization generates the trip plan that maximizes the objective function. First, the optimization algorithm generates candidate itineraries and evaluates them using the proposed model. Then, we improve candidate itineraries based on the evaluation results of previous itineraries. To validate the proposed trip planning approach, we conducted an extensive user study by asking participants to choose their preferred trip plans from options created by a human planner and our approach. The results show that our approach provides human-like trip plans, as participants selected our generated plans in 57% of the pairs. We also evaluated the efficiency of the employed ant colony optimization algorithm for trip planning by performance comparisons with other optimization methods.