Alternative fuel vehicle (AFV) fleet adoption is an attractive mitigative measure to reduce environmental externalities from transportation activities of logistics. However, adequate economic and environmental attractions should be in place to encourage organisations to invest in AFVs. This paper introduces the alternative fuel vehicle routing problem (AFVRP), which is proposed to assist companies with an AFV fleet through both reducing the consumption level and optimising the utilisation of the alternative fuel. Distinguishing two dominant categories of AFVs as dedicated AFVs and bi-fuel vehicles, another extension of the problem as bi-fuel vehicle routing problem (BFVRP) is also studied. Experiments were run and the results indicated that for urban logistics networks a reduction by up to 35% in CO2 emissions and by up to 16% in costs is possible by using an AFV fleet and the proposed methodology instead of gasoline vehicles and the conventional VRP with a simple distance minimisation objective.