جستجوی محله ای متغیر ابتکاری برای مسئله مسیریابی موجودی در تحویل سوخت

In this paper we observe the extension of the vehicle routing problem (VRP) in fuel delivery that includes petrol stations inventory management and which can be classified as the Inventory Routing Problem (IRP) in fuel delivery. The objective of the IRP is to minimize the total cost of vehicle routing and inventory management. We developed a Variable Neighborhood Search (VNS) heuristic for solving a multi-product multi-period IRP in fuel delivery with multi-compartment homogeneous vehicles, and deterministic consumption that varies with each petrol station and each fuel type. The stochastic VNS heuristic is compared to a Mixed Integer Linear Programming (MILP) model and the deterministic “compartment transfer” (CT) heuristic. For three different scale problems, with different vehicle types, the developed VNS heuristic outperforms the deterministic CT heuristic. Also, for the smallest scale problem instances, the developed VNS was capable of obtaining the near optimal and optimal solutions (the MILP model was able to solve only the smallest scale problem instances).

The transportation and inventories management have a decisive influence on the effectiveness of the distribution process. Although this fact is well known, modeling approaches to distribution process optimization usually consider inventory control and transportation independently, neglecting their mutual impact. However, the inter-relationship between the inventory allocation and vehicle routing has recently motivated some authors to model these two activities simultaneously by solving the Inventory Routing Problem (IRP). The objective of the IRP is to minimize the total cost of vehicle routing and inventory management. Regardless of the type and characteristics of the IRP an optimal solution for real life problems is so far unreachable due to the problem complexity which is related to simultaneous resolution of the routing problem and the allocation of deliveries over an observed planning horizon. The IRP assumes application of the VMI concept where suppliers determine an order quantity and the time of delivery. The VMI concept enables the supplier to better utilize the vehicles, but on the other hand it shifts the responsibility of inventory management from clients to the supplier. There are many industries, including the petrochemical industry where the VMI concept is applied, and that can draw benefit from the integrated approach to the IRP (Campbell & Savelsbergh, 2004). Recently, Bersani, Minciardi, and Sacile (2010) discussed the VMI concept in distribution of petrol products to service stations. The vehicle routing problem (VRP) in fuel delivery is a well known research area (Avella et al., 2004, Boctor et al., 2011, Brown et al., 1987, Brown and Graves, 1981, Bruggen et al., 1995, Cornillier et al., 2007, Cornillier et al., 2008, Fallahi et al., 2008, Mendoza et al., 2010 and Uzar and Catay, 2012) where the main objective is to minimize the transportation costs incurred by the delivery of petroleum products to a set of clients, usually trough the use of multi-compartment vehicles. In this paper we observe the extension of the VRP in fuel delivery that includes petrol stations inventory management. Hence, this problem can be classified as the IRP in fuel delivery. More precisely, we observe secondary distribution of different fuel types from one depot location to a set of petrol stations by a designated fleet of multi-compartment vehicles, and for which a single oil company has control over all of the managerial decisions over all of the resources. This enables the VMI concept, and therefore, the application of the IRP. Bell et al. (1983) were among the first authors to observe the IRP. They considered distribution of liquefied industrial gases and used the linear programming model and Lagrangian relaxation to obtain the delivery plan for short-term planning horizon. Recently research efforts on the IRP topic have been intensified (Coehlo et al., 2012, Li et al., 2010, Li et al., 2011, Liu and Chen, 2011, Liu and Chung, 2009, Moin et al., 2011, Shen et al., 2011, Stalhane et al., 2011, Yu et al., 2008, Yu et al., 2010 and Zachariadis et al., 2009) where in all of them different heuristic approaches were developed for the purpose of solving the larger scale problems. However, there seems to be a lack of papers that considered the IRP with multi-compartment vehicles, with the exception of papers from the marine transport, for instance Siswanto, Essam, and Sarker (2011). Oppen, Lokketangen, and Desrosiers (2010) solved a multi-compartment vehicle routing and inventory problem in the Livestock Collection Problem (LCP) and Popovic, Bjelic, and Radivojevic (2011) presented a simulation approach to the analysis of the applicability of a deterministic IRP solution to real life stochastic fuel consumption with fuel distribution by multi-compartment vehicles. There are several papers from the IRP research area that have considered Variable Neighborhood Search (VNS) heuristic (Hemmelmayr et al., 2009, Hemmelmayr et al., 2010, Liu and Chen, 2012, Liu and Lee, 2011 and Zao et al., 2008), which was originally developed by Mladenovic and Hansen (1997). For an insight in methods and application of VNS we recommend the paper by Hansen, Mladenovic, and Perez (2010). For a detailed review on the IRP we refer the reader to the papers of Moin and Salhi (2007) and Andersson, Hoff, Christiansen, Hasle, and Lokketangen (2010). Also, case studies from the Netherlands (Bruggen et al. 1995) and Hong Kong (Ng, Leung, Lam, & Pan, 2008) can give a detailed insight into the practical issues of the IRP in fuel delivery. In this paper we developed a Variable Neighborhood Search (VNS) heuristic for solving a multi-product multi-period IRP in fuel delivery with multi-compartment homogeneous vehicles, and deterministic consumption that varies over each petrol station and each fuel type. The local search and the shaking procedure (as two central procedures of the VNS) are based on three neighborhoods that are derived by the following changes of the delivery plan: relocation of individual compartments; relocation of all compartments for the observed station’s fuel type; and relocation of all compartments for the observed station. The VNS heuristic is compared to a Mixed Integer Linear Programming (MILP) model and the deterministic “compartment transfer” (CT) heuristic; both models were developed by Vidovic, Popovic, and Ratkovic (2011). This paper is organized as follows: The mathematical formulation is given in Section 2. Section 3 presents a description of the VNS heuristic. The computational results are presented in Section 4. Finally, conclusions are given in Section 5, together with directions for further research.

In this paper we developed the VNS heuristic model for solving the multi-period multi-product IRP in fuel delivery with multi-compartment homogenous vehicles. This stochastic VNS heuristic is compared to deterministic CT heuristic and to the optimal MILP model. For the P1 problem instances, VNS heuristic was able to find optimal solution for 27 out of 30 instances. The stochastic VNS heuristic showed better results than the deterministic CT heuristic in 87 out of 90 instances for all three problem sets (for only three instances of P1 problem set both VNS and CT heuristics found optimal solution). Future research should be focused on the heterogeneous vehicle fleet and stochastic nature of the IRP. The model extensions by considering these factors can enrich and bring the IRP model closer to the real life conditions.