Аннотация:

The paper addresses a new single-depot multi-trip petrol station replenishment problem originating from a Russian petroleum company. We assume that each underground reservoir at each petrol station can be serviced in only one trip, and the service time of the station depends on the number of hoses on the truck. The truck's compartment closest to its cabin must be emptied last. The goal is to minimize the total size of the heterogeneous truck fleet required to service all the stations. We develop a linear 0-1 formulation for an exact approach and a heuristic based on the column generation method to obtain lower and upper bounds on the optimum. The approach is tested on a semi-synthetic dataset, and the bounds differ by at most two trucks in most cases.