A petrol station replenishment problem: new variant and formulation
- PDF / 839,280 Bytes
- 18 Pages / 595.276 x 790.866 pts Page_size
- 79 Downloads / 206 Views
ORIGINAL PAPER
A petrol station replenishment problem: new variant and formulation Abdelaziz Benantar1 • Rachid Ouafi1 • Jaouad Boukachour2
Received: 20 October 2015 / Accepted: 19 March 2016 The Author(s) 2016. This article is published with open access at Springerlink.com
Abstract One of the most important problems in the petroleum industry is the well-known petrol station replenishment problem with time windows, which calls for the determination of optimal routes by using a fleet of tank trucks to serve a set of petrol stations over a given planning horizon. In this paper, we introduce a model and solve a specific problem that originates from a real-life application arising in the fuel distribution where specific attention is paid to tank trucks with compartments and customers with different types of products and time windows. Literally, we call the resulting problem the multi-compartment vehicle routing problem with time windows (MCVRPTW). To solve the MCVRPTW, we begin by describing the problem, providing its mathematical formulation and discussing the sense of its constraints. As the problem is NP-hard, we propose an efficient tabu search algorithm for its solution. We introduce the Kolmogorov–Smirnov statistic into the framework of the tabu search to manage the neighbourhood size. We evaluate the performance of the algorithm on a set of vehicle routing problems with time windows instances as well as other realistic instances. Our results are compared to CPLEX, to the heuristics reported in the literature and also to those extracted from the company plans. & Abdelaziz Benantar [email protected] Rachid Ouafi [email protected] Jaouad Boukachour [email protected] 1
Department of Operational Research, USTHB University, P.O. Box 32, 16111 Bab-Ezzouar, Algeria
2
LMAH, Normandie University, ULH, 76600, Le Havre, France
Keywords Petrol station replenishment Vehicle routing Compartments Time windows Tabu search
1 Introduction The specific problem, which will be discussed in this paper, is a variant of the capacitated vehicle routing problem and occurs in the context of fuel distribution. More precisely, the paper deals with the daily replenishment-planning problem that the biggest Algerian petroleum company is facing. The company is faced with a particular problem which is demonstrated by the following procedures in operations. (a) The company has to deliver different fuel types ordered by a set of petrol stations during the next working day. (b) These stations order one or more fuel types each time and specify the quantity to be delivered for each product ordered. (c) The products are incompatible and must be transported in independent vehicle compartments. In addition, petrol stations specify time windows during which they must be served. The company delivers products from one or more depots. (d) Each depot is responsible for the demand of stations located in the same district as the depot. The company assigns a fleet of vehicles to each depot. (e) These vehicles are compartmentaliz
Data Loading...
