Vehicle refueling problem with limited resources
Murat Firat

In our vehicle refueling problem, there is a fixed route on which a series of 
fuel stations are located. Various amounts of fuel are needed between 
successive stations. At the stations, limited amounts of fuel can be bought 
with varying prices. The capacity of the fuel tank may also vary between 
adjacent fuel stations. The main goal is to reach the final destination with 
cheapest cost of fuel. The vehicle refueling problem corresponds to an 
inventory-capacitated lot-sizing problem with zero setup costs, zero inventory 
holding costs, linear cost functions for production, and non-stationery 
inventory capacity. The movements of the vehicle between adjacent stations 
correspond to stages in time and the fuel is the commodity in demand for each 
stage. The fuel available at stations corresponds to production capacities and 
the fuel carried in the tank corresponds to keeping some commodity stock for 
later demands. In the talk an O(n log n) time algorithm for this vehicle 
refueling problem will be presented.