A page from the OpenDepot.org service

Jump to the start of the main contents

Cornillier, Fabien and Boctor, Fayez and Renaud, Jacques (2012) Heuristics for the multi-depot petrol station replenishment problem with time windows. European Journal of Operational Research, 220 (2). pp. 361-369. ISSN 03772217

Full text not available from this repository.


In the multi-depot petrol station replenishment problem with time windows (MPSRPTW), the delivery of petroleum products stored in a number of different petroleum depots to a set of petrol distribution stations has to be optimized. Each depot has its own fleet of heterogeneous and compartmented tank trucks. Stations specify their demand by indicating the minimum and maximum quantities to be delivered for each ordered product and require the delivery within a predetermined time window. Several inter-related decisions must be made simultaneously in order to solve the problem. For this problem, the set of feasible routes to deliver all the demands, the departure depot for each route, the quantities of each product to be delivered, the assignment of these routes to trucks, the time schedule for each trip, and the loading of the ordered products to different tanks of the trucks used need to be determined. In this paper, we propose a mathematical model that selects, among a set of feasible trips, the subset that allows the delivery of all the demands while maximizing the overall daily net revenue. If this model is provided with all possible feasible trips, it determines the optimal solution for the corresponding MPSRPTW. However, since the number of such trips is often huge, we developed a procedure to generate a restricted set of promising feasible trips. Using this restricted set, the model produces a good but not necessarily optimal solution. Thus the proposed solution process can be seen as a heuristic. We report the results of the extensive numerical tests carried out to assess the performance of the proposed heuristic. In addition, we show that, for the special case of only one depot, the proposed heuristic outperforms a previously published solution method.

Item Type: Article
Uncontrolled Keywords: Petrol station replenishment; Truck-fleet management; Vehicle routing and scheduling
Subjects: Mathematical and Computer Sciences > Operational Research
Depositing User: Fabien Cornillier
Date Deposited: 22 Mar 2012 23:10
Last Modified: 22 Mar 2012 23:10
URI: http://opendepot.org/id/eprint/951

Actions (login required)

View Item