The optimal itinerary offers higher efficiency and is very crucial, especially for an individual with a restricted amount of time to visit their point of interest. The Miller-Tucker-Zemlin Traveling Salesman Problem (MTZ-TSP) is an approach that finds the shortest path that visits multiple vertices using integer linear programming technique. Utilizing the MTZ-TSP in the context of travel itinerary creation could improve travel experience in an area, especially for solo traveler. Islamic landmarks refer to places, sites, or landmarks that hold significance within the Islamic faith or culture. However, the study that used MTZ-TSP to develop travel itineraries for solo travelers with limited time, focusing on enhancing the travel experience associated with Islamic landmarks in urban area, is still lacking. Hence, this paper presents an optimized travel itinerary for visiting seven Islamic landmarks in the selected urban area, namely, Kuala Lumpur, Malaysia, using the MTZ-TSP approach. Three initial start points were selected to provide a diverse range of travel itineraries for tourists. As a result, it was found that the total travel time to traverse all of the selected Islamic landmarks would be 98 min.