DELTA - Route Optimization and Stay Time Prediction

Abstract

"Route optimization is a long-standing research challenge due to its complexity and computational inefficiency. While numerous optimization methods exist, their effective adaptation for real-world usage remains a subject of ongoing research. This challenge extends to simple activities like trip planning, where poor planning can lead to time and budget constraints. Travelers may overstay or under-stay at locations, potentially missing key destinations. Therefore, factoring in the stay time for each location becomes crucial, especially for single-day trips.

This paper tackles the problem in two components. The first component predicts the stay time at each location, considering factors like the time of day, location type, and individual preferences. An artificial neural network regression model was trained using a dataset combining crowdsourced information and reviews from platforms like TripAdvisor and TripHobo. The predicted stay times are scaled to fit the user’s specified time window.

The second component optimizes the travel route using a Genetic Algorithm (GA). The GA reorders user-provided locations based on distances retrieved from the Google Maps API and stay times obtained from the neural network. This optimization produces a detailed travel itinerary specifying the order of locations and recommended stay durations.

The inclusion of stay time as a heuristic in the GA enhances its computational efficiency, making the solution novel. The paper also compares parameters such as cross-selection probability, mutation probability, and selection methods within the GA. The results identify optimal parameter combinations for faster convergence and reduced routing time, offering a practical and efficient solution for personalized route optimization."