A Budget Aware Travel Planning & Route Optimization Approach

Authors:

1. Sai Kumari¹, D. Prem Sagar², G. Mounika³, K. Manoj Kumar⁴, K. Daiva Keerthana⁵, G. Anil Reddy⁶

¹²³⁴⁵⁶Department of Information Technology
Dhanekula Institute of Engineering and Technology

Abstract - Modern travellers face difficulties in creating personalized, budget-friendly, and logically ordered trip itineraries especially for diverse, and wide areas such as India. This paper is a fully-end-to-end machine learning system for Budget-Aware Travel Planning Route Optimization (Trip Planner) that combines dynamic, real-time geocoding APIs and combinatorial optimization to automatically create day-by-day, budget-limited trip schedules. Given the origin and destination, the type of group (solo, couple, friends, family), duration and a maximum budget limit from the user, the system automatically creates the itinerary, which involves identifying attractions, choosing a tour route and then sequencing day-wise itineraries with minimum cost without any manual interference. This work uses a hybrid recommendation engine using collaborative filtering, content-based filtering and context-ranking for shortening the candidate list. A 0/1 Knapsack dynamic programming algorithm finds the optimal budget allocation for each day, and an A* with Haversine heuristic is used for optimal routing, while Dijkstra with OpenRouteServiceAPI is used for calculation and the travelling salesman problem heuristics (Nearest Neighbor + 2-opt, GA,ACO) is employed to find the optimal visiting order on each day. DB clustering partitions days geographically. The cost of the trip is predicted using linear regression, and the recommendations are improved over time by using a Q-Learning based approach. The deployment stack includes FastAPI, React 19, Vite 7, Leaflet.js, Firebase, Geoapify, and LocationIQ. Our system shows improvement compared to existing travel tools for metropolian, heritage, coastal, and hill-station based travel destinations in terms of efficient route, cost constraint and user experience based.

Keywords: Budget-Constrained Itinerary, Route Optimisation, Knapsack Dynamic Programming, Travelling Salesman Problem, Reinforcement Learning, Hybrid Recommendation System, Indian Tourism, Geoapify, FastAPI, React.