The reason for minimizing fuel consumption is presumably to minimize fuel cost. If you can come up with a cost rate for travel time, then you can combine the two objectives into an overall cost function and minimize that. No normalization is required.
More generally, if you cannot put the criteria in common units (such as dollars of cost), then one option is to ask the decision maker something along the lines of "how many additional gallons of fuel would you be willing to expend to cut travel time by one day?" and use that to generate weights. Again, no normalization is required; if fuel consumption is in gallons, travel time is in days and the decision maker equates one day of travel with 100 gallons of fuel, just multiply fuel consumption by 1 and travel time by 100 (putting the combined function in terms of gallons of fuel).
Where I have seen normalization used, the units of the various criteria are not directly commensurable and decision makers can only give vague guidance like "saving fuel is twice as important as saving travel time". You can guesstimate the range of values for each criterion function, subtract the min and divide by the range to put the criterion on a [0, 1] scale, and then apply weights. Whether this produces meaningful results is in my opinion a tad dubious.