<p>Personalized itinerary recommendations become critical as more people select travel as a primary leisure activity. Although online search engines and model-based recommendation systems can predict the points of interest (POIs) users are interested in, they are hard to generate an appropriate itinerary satisfying users’ preferences and specific temporal or spatial constraints. In this study, a novel optimization method enhanced by user interests and POI characteristics is proposed. The proposed method incorporates an interest value prediction model considering the interaction feature deriving from the user’s historical visiting sequence and visual feature from user-taken photo images. Aside from users’ interest in POIs, the POI characteristic is included in itinerary planning to increase the chance of visiting popular and nearby sites. Then, travel itinerary planning is formulated as a variant orienteering problem that aims to find the optimal itinerary that maximizes user interest and POI characteristics under user-specified constraints. Finally, an Iterated Local Search with Adaptive Perturbation (ILSAP) algorithm is proposed to escape the local optimum efficiently and explore other feasible solution regions. A real-life dataset from geo-tagged social media is implemented to demonstrate the benefits of the proposed personalized itinerary planning framework. The experiments show that the proposed method generates superior recommendations than popular baseline methods. In addition, the proposed ILSAP algorithm shows significant improvement compared to ILS algorithms with other perturbation strategies.</p>