Dynamic (Time Dependent) Green Vehicle Routing Problem

Abstract

This research summarizes recent studies on two versions of the Vehicle Routing Problem, i.e., the time-dependent vehicle routing problem (TD-VRP) and the green vehicle routing problem (G-VRP), for which a time-dependent version is also developed. A new formulation of TD-VRP is proposed that can deal with the time-dependent vehicle routing problem with dynamic demand information and provide the minimum cost routing plan. We also introduce a special case of G-VRP with a mixed fleet of heterogeneous electric and internal combustion engine commercial vehicles. Two different formulations are proposed to solve two different variants of the problem. A constructive heuristic is defined to generate initial feasible solution to the problem. The initial solution is further improved by deconstructing a large part of it and then, rebuilding it with the constructive heuristic. This algorithm is preferred over the local search algorithms as it provides better solutions due to the diversification effect embedded in it by deconstructing a large part of the solution. The results of the implementation of the proposed modes in a number of test problems and a large case study are also presented.