عدد صحیح مختلط و مدل اکتشافی برای مشکل مسیریابی موجودی در تحویل سوخت

This paper presents solution approaches for the multi-product multi-period Inventory Routing Problem (IRP) in fuel delivery. A homogeneous fleet of vehicles with compartments is used for fuel distribution from one depot to a set of petrol stations that have deterministic fuel consumption. The IRP consists of two mutually dependent sub-problems, those of inventory and routing, in a Vendor Management Inventory (VMI) environment in which suppliers determine the quantities and time periods of the deliveries. For solving the IRP, we propose a Mixed Integer Programming (MIP) model and a heuristic approach with and without fleet size costs, to observe the impact of these costs on the solutions that are obtained. The heuristics model is based on constructive heuristics with two Variable Neighborhood Descent (VND) search types: a local intra-period search and a large inter-period neighborhood search. Both of these approaches were tested on numerical examples for which the results, together with the performances of the proposed models, are presented. A combination of good computational time and good quality solutions suggests the use of the proposed heuristics on problems with realistic dimensions where the MIP model cannot find an optimal solution in a reasonable amount of time.

Transportation and inventory costs are the two main components of the supply chain; these factors have the most significant impact on its performance. Although this fact is well known, modeling approaches for supply chain optimization usually consider inventory control and transportation independently, ignoring their interrelationships. However, the interrelationship between the inventory allocation and vehicle routing has recently motivated some authors to model these two activities simultaneously. This practical and challenging logistical problem is known as the integrated Inventory Routing Problem (IRP) (see Moin and Salhi, 2007). The idea of the IRP is to simultaneously solve the problems of choosing the optimal quantity of the goods and the time of delivery as well as the problem of optimal vehicle routing. Therefore, the objective of an IRP is finding a balance between the inventory and routing costs to minimize the total costs that are incurred by these two segments in the supply chain. The IRP assumes the application of the Vendor Management Inventory (VMI) concept, in which suppliers determine the order quantity and the time of delivery. There are many industries using the VMI concept that can benefit from the integrated approach of the IRP, including suppliers and supermarkets, store chains, clothing industries, and automotive industries (Campbell and Savelsbergh, 2004), as well as the petrochemical industry that is studied in this paper. Yu et al. (2012b) presented the most recent paper that describes the VMI concept with deteriorating raw materials and products. These authors developed a model to calculate the total inventory and the deteriorating costs. On the basis of those costs, the replenishment cycle and frequency were obtained. Inspiration for our paper was found in the practical problem of secondary distribution, for which different fuel types are transported from one depot location to a set of petrol stations by a designated fleet of vehicles, and for which a single oil company has control over all of the managerial decisions over all of the resources. As a consequence, the full VMI concept can be applied, and therefore, the IRP model can be formulated. The IRP studied in this paper can be described as a multi-product multi-period deterministic IRP in fuel delivery. To solve this problem, we propose a Mixed Integer Programming (MIP) model and heuristics for two cases, with and without fleet size costs, to observe the impact of these costs on the solutions that are obtained. A heuristics model is based on constructive heuristics with two improvement techniques: a local intra-period search and a large inter-period neighborhood search. The results of the proposed heuristics are compared with solutions that are obtained from the MIP model on the set of small-size test examples, which are used later as benchmarks to estimate the heuristics solution performance. In addition, we have solved moderate-size problems by a heuristic model only, and we have compared the results that were obtained by the models with and without considering the fleet size. This paper is concerned with the problem of solving IRPs in fuel delivery, which is a well-known research area; however, the proposed approaches offer some innovations in this field. First, the proposed MIP formulation differs from previous models in the formulation of the routing part of the model, which is considered to be the problem of making an optimal assignment of the petrol stations. Second, there are certain advantages to solving this class of problems with the proposed heuristics approach, which includes a relaxed MIP model for obtaining the initial solution, ideas for transferring deliveries over one or more time periods earlier, assigning petrol stations to the vehicle in the same route (represented through the utilities calculation), and a Variable Neighborhood Descent (VND) search. This paper is organized in the following way. A literature review is presented in Section 2. The model formulation is given in Section 3. Section 4 presents a description of the proposed MIP formulation. A description of the proposed heuristic is given in Section 5, and computational results are presented in Section 6. Finally, Section 7 presents some concluding remarks and directions for further research.

This paper presents two solution approaches for the multi-product multi-period IRP in fuel delivery, the MIP model and the heuristics approach. The MIP model is formulated as the problem of petrol stations assignment to individual routes with consideration of the daily inventory costs. The proposed heuristics includes a relaxed MIP model for obtaining the initial solution, ideas for transferring deliveries over one or more time periods earlier, assigning petrol stations to the vehicle in the same route (represented through the utilities calculation), and a Variable Neighborhood Descent (VND) search. An interesting conclusion can be drawn from the computational time that is needed for obtaining the solution in the case of the MIP models. As we can see from Table 3, the average computational time for the IRP model is approximately 2 min, and for the Routing model, the time is more than 10 times longer; for the Inventory model, it is less than 1 s. This scenario implies that the inventory segment in the objective function reduces the entire solution space. The heuristic approach in average gives less than 4% higher total costs for the IRP and in average less than 7% higher total costs for the IRPF compared with the optimal solution, whereas the heuristics computational time is significantly lower. A combination of the computational time and the good quality of the solutions suggests the use of the proposed heuristics on problems of real dimensions (more than 20 petrol stations with intensive deliveries) for which the MIP model cannot find the optimal solution in a reasonable amount of time. It can be concluded that the proposed solution approaches can be considered very promising for optimizing the fuel delivery process. However, its implementation needs further adjustments to the requirements and limitations that exist in real systems. Therefore, the directions for future research are related to the application of other solution approaches and to further problem analysis, especially in the context of the length of the planning horizon because fuel consumption in real systems is more uncertain than deterministic. In addition to introducing additional requirements and limitations from real systems, an important area for future research is related to the compartments' size optimization as well as to analyzing the effects of a continuous supply based on the vehicles equipped with the fuel flow meters.