Abstract:
This work addresses a family of green vehicle routing problems. Three key operational characteristics distinguish alternative-fuel vehicles (AFVs) from gasoline or diesel vehicles (GDVs): (i) limited driving range before refueling is needed, (ii) scarce refueling infrastructure, and (iii) lengthy refueling times. The operational challenges in daily routing decisions faced by fleet managers and several key modeling aspects such as mixed fleets, refueling at customer and non-customer locations, and refueling policies are incorporated into the GVRP models. The first study compares two competing GVRP formulations, namely node- and arc-duplicating. Both formulations are strengthened via (i) two label setting algorithms to tighten the bounds, and (ii) improved lower bound on the number of routes. Through computational experiments based on two testbeds from the literature, the study concludes that the less common arc-duplicating formulation outperforms the more common node-duplicating formulation. The second study introduces an efficient solution framework by exploiting the route optimization outcome of the GDVs. We investigate the benefits of utilizing GDV optimal routes by quantifying the differences between AFV and GDV optimal routes and the solution times. Based on the results, three route optimization frameworks are proposed and implemented in a column generation algorithm. Based on data analysis, a solution methodology that potentially shortens the expected solution time is proposed. Finally, the third study introduces a novel profit-maximizing fleet mix and sizing with customer selection in green vehicle routing problem (GVRP). In addition to addressing operational challenges presented in the previous chapters, this study considers environmentally conscious customers who prefer receiving service with AFVs to reduce their supply chain carbon footprint and may have willingness-to-pay a green premium for it.
