Green Vehicle Routing problem (GVRP) is a variant of standard Vehicle Routing Problem in which the environmental externalities of routing operations are minimized as a part of the routing cost. Early studies on GVRP were focused on minimizing energy consumption and pollution of internal combustion engine commercial vehicles. With the introduction of electric commercial vehicles and the increasing trend in their adoption in green logistics and last mile delivery operations a new strand of GVRP is introduced called “Alternative Fuel Vehicle Routing Problem (AFVRP).” The objective in AFVRP is to find optimal routes with minimum energy, time or money requirements for a fleet of alternative fuel vehicles while accounting for their operation limitations such as limited driving autonomy.

The goal of this dissertation is to develop a model for a Time-Dependent GVRP (TDGVRP) with a mixed fleet of electric and internal combustion engine commercial vehicles that finds the optimal fleet design for last mile delivery operations of a company and allocates minimum cost routes to each of these vehicles in order to satisfy the customer demands in a typical operation day. The routing cost includes vehicle purchase cost, energy consumption cost, early or late service penalty cost, labor cost, emission trading cost and Electric Commercial Vehicle (ECV) battery degradation cost. An extensive model is used to estimate the energy consumption of vehicles that accounts for not only the travel distance, but also speed, acceleration, and cargo load as contributing factors to energy consumption of vehicles. Moreover, by considering the time dependency of travel times along the network, the effect of congestion on the vehicle energy requirements is accounted for. This is very important in the context of ECVs where the energy consumption of the vehicle determines the remaining battery and driving range of the vehicle. While previous studies on GVRP focus only on the limitations of ECVs, the GVRP model proposed in this dissertation takes into account the limitations of both ECVs and Internal Combustion Commercial Vehicles (ICCVs). These limitations are in terms of limited range and higher purchase cost for electric commercial vehicles, and carbon emission limitations imposed by government regulations (e.g., Cap and Trade project) and Low Emission Zone (LEZ) penalties for ICCVs. Emission trading or LEZs are government-mandated regulations to control pollution by providing economic incentives for reducing emission of pollutants and electrifying distribution operations. This is a unique and complex model and no study in the literature has addressed this problem sufficiently. The results of the proposed model in this study can be used to illustrate the changes in the fleet design and routing of a delivery company as a result of these regulations.

A mathematical formulation is developed for the proposed Time-Dependent GVRP and numerical experiments are designed to demonstrate its capabilities. Commercial solvers like Xpress can be used to solve the proposed model on small-size problems but for large-size and real-world problems an appropriate heuristic is needed. A heuristic method that can find good solutions in reasonable time for this problem is developed and tested on several cases. Also, the model is applied to a large size case study to test its performance. At last a set of sensitivity analysis is performed on the problem characteristics to evaluate the heuristic’s potential outcome in different situations. The results show that the proposed heuristic is performing very well and efficient and it can be used to identify the changes in fleet size and routing of last mile delivery operations as a result of green logistics policies.