Planning routes between two points over road networks is a common yet time-consuming task. Although both travel time and utility (e.g., beauty, safety/risky or happiness) on arcs are time-dependent concurrently in real cases, they are overlooked in most prior work. In this work, targeting a personalized route planning, we allow both travel time and utility on the arc to vary from time to time. Over such two-fold time dependent road network, we aim to discover the routes with the objectives of maximizing the utility and minimizing the travel time. Due to its strong NP-hard nature, a fast new ε-constraint-based heuristic algorithm is proposed. The main idea is to transform the bi-objective problem into a series of single-objective problems which can be solved to obtain an approximate Pareto front. We evaluate the proposed algorithm based on two real-world road networks. The results show that the proposed algorithm is able to find high-quality Pareto solutions for large-scale problem efficiently.