This paper considers a generalized version of the trip packing problem that we encountered as a sub-problem of the petrol stations replenishment problem. In this version we have to assign a number of trips to a fleet composed of a limited number of non-identical tank-trucks. Each trip has a specific duration, working time of vehicles is limited and the net revenue of each trip depends on the truck used. The paper provides a mathematical formulation of the problem and proposes some construction, improvement and neighbourhood search solution heuristics. A set of benchmark problem instances is created in a way that reflects real-life situations and used to analyse the performance of the proposed heuristics. A real-life case is also used to further assess the proposed heuristics. © 2010 Elsevier Ltd.