Route optimization is an extensively studied NP-hard graph search problem. Many researchers applied numerous techniques to find the optimum or semi optimum solution (the one with least cost). There are many practical extensions and modifications of this problem applied using deterministic methods. However, traveling between nodes (locations) might encounter additional fuzzy cost (time) on the overall trip, whether they are traveled during the rush hour periods or if they crossed traffic regions (the city centers). Since, those factors are non-deterministic; it would be closer to reality to represent them using fuzzy numbers. In this paper, we propose a novel route optimization under road uncertainties using Interval-Valued Fuzzy Soft Sets. We use scoring technique to help determining the optimum route amongst all alternatives. Our novel approach can be looked at as a practical and closer to reality estimation for non-deterministic factors of the original abstract route optimization problem.