The Green Vehicle Routing and Scheduling Problem (GVRSP) has drawn considerable research attention, due to its capability to address the trade-off between traditional business and environmental objectives. Most of the existing models consider the problem on a complete graph composed of the depot and the customers. However, time and load dependent problems are not always possible to be modelled over a complete graph, since the departure times and carried loads between nodes are not known in advance. This paper formulates
the GVRSP as a bi-objective time-and-load-dependent optimisation model and proposes an algorithm for solving it on a real road network. A network reduction technique to reduce the number of eligible paths between the network nodes, and an algorithm for departure time optimisation that can be embedded into different local search-based meta-heuristics are proposed. We are presenting results of computational experiments to demonstrate the efficiency of the proposed methodology.