الگوریتم بهینه سازی اصلاح شده کلونی مورچه ها برای مشکلات مسیریابی موجودی چند آیتمی با عدم اطمینان تقاضا

This paper addresses an integrated model that schedules multi-item replenishment with uncertain demand to determine delivery routes and truck loads, where the actual replenishment quantity only becomes known upon arrival at a demand location. This paper departs from the conventional ant colony optimization (ACO) algorithm, which minimizes total travel length, and incorporates the attraction of pheromone values that indicate the stockout costs on nodes. The contributions of the paper to the literature are made both in terms of modeling this combined multi-item inventory management with the vehicle-routing problem and in introducing a modified ACO for the inventory routing problem.

Inventory routing problems (IRPs) address the coordination of inventory management and transportation (Kleywegt et al., 2002), which is usually necessitated by consumers relying on a central supplier to provide a given commodity on a repeated basis (Jaillet et al., 2002). IRPs are used to determine shipping policies that optimize the trade-off between inventory costs and transportation costs (Burns et al., 1985). The IRP is one of the core problems that must be solved when implementing vendor-managed inventory (VMI) replenishment (Kleywegt et al., 2002), an emerging trend in logistics that refers to a situation in which the supplier manages inventory replenishment on behalf of the customers. Disney et al. (2003) investigates the impact of a VMI strategy upon transportation and shows that transport cost savings are possible in both the short and long term operations in a supply chain. The reason that vendor-managed resupply does not occur on a large scale is the complexity of developing a distribution strategy that minimizes the number of stockouts while simultaneously realizing potential savings in distribution costs (Campbell et al., 1998). The problem of integrating inventory control and vehicle routing into a cost-effective strategy for a distribution system consisting of one depot and many geographically dispersed retailers, has been approached in different ways. The approach chosen depends on factors such as customer inventory policies, service level restrictions and the time horizon under consideration (Adelman, 2004, Anily and Federgruen, 1990, Anily and Federgruen, 1993, Archetti et al., 2007, Bertazzi, 2008, Burns et al., 1985, Campbell and Savelsbergh, 2004, Gallego and Simchi-Levi, 1990, Haughton and Stenger, 1999, Jaillet et al., 2002 and Savelsbergh and Song, 2008). The aforementioned distribution systems may face external demands occurring at constant, deterministic and retailer-specific rates (Anily and Federgruen, 1990). In research conducted by Archetti et al. (2007), the supplier monitors the inventory of each retailer and determines a joint replenishment policy for multi-item inventory management, in a stochastic setting where stockout is not permitted. Yang et al. (2000) developed heuristic algorithms and an optimal restocking policy with single commodity for a stochastic vehicle-routing problem. Qu et al. (1999) proposed a heuristic decomposition method to solve the stochastic multi-item joint replenishment problem: this involved simultaneous decisions being made on inventory and transportation policies. Among the research reports in the area of IRPs, given the indeterminacy of the delivery volume when routes are designed, we found that provision must be made for recourse actions in case a delivery vehicle lacks sufficient capacity to fulfill the delivery completely in one trip. There is a paucity of research into this area of inquiry. Moreover, in dealing with this NP-hard problem, some researchers adopted the mathematical programming approach, which merely constructs a lower bound of computational experience (Sindhuchao et al., 2005 and Qu et al., 1999). Therefore, this study creates replenishment route plans for multi-item inventories allowing for consumption uncertainty, stockout costs, and transportation costs. Effectively, suppliers will be able to deliver the optimal volume of inventory to customers, with reduced total costs. The IRP is a variation of the vehicle-routing problem (VRP): it arises in situations in which a vendor has the ability to make decisions about the timing and size of deliveries, as well as the routing (Campbell and Savelsbergh, 2004). Unlike classic VRPs, which have received considerable attention from researchers, IRPs still represent a relatively new class of problem (Archetti et al., 2007). The classic, or deterministic, capacitated VRP involves dispatching vehicles from the depot to service a set of geographically dispersed customers with known demand (Clarke and Wright, 1964). The objective is to find a route that involves minimal travel costs, with the caveat that each customer is served exactly once. In light of Christiansen and Lysgaard’s (2007) research regarding capacitated VRP with stochastic demands for single-item inventory replenishment, this study formulates a fixed-fleet VRP with stochastic demands and multi-items (VRPSDMI) to find a route that carries minimal expected total costs. Since inventories are observable only at delivery points, actual demand is only known upon arrival at the customer location. Accordingly, problems may arise if the actual demand on a route exceeds vehicle capacity; recourse action is then required and the vehicle must return to the depot to replenish. Our problem is similar to the IRP presented by Bard et al. (1998) and Jaillet et al. (2002), in which a central supplier must restock a subset of customers on an intermittent basis with unknown customer demand, and complete the deliveries on a day within a given number of hours. However, our problem differs from that of Bard et al. (1998) and Jaillet et al.’s (2002) in two respects. Firstly, we dealt with scheduling of replenishments by route and truck for multiple items using a fleet of vehicles based on a single depot; whereas, by comparison; Bard et al. (1998) and Jaillet et al. (2002) considered the problem of delivering a single commodity to customers based on the depot and several satellite facilities holding an unlimited supply of the given commodity. Secondly, our problem minimizes the total costs by simultaneously determining which customers to replenish and the feasible daily routing plans. Contrastingly, Bard et al. (1998) and Jaillet et al. (2002) investigates the trade-off between distance and annual costs by adopting the decomposition scheme, which first involves clustering customers by identifying those customers whose optimal delivery day falls within the timeframe and then specifies the routing plan. In this study, we examine the VRPSDMI for determining the optimal inventory policy and replenishment routes for circumstances in which everyday visits to each customer are not feasible, due to fleet limitations. Furthermore, this study investigates the performance of an evolutionary computing approach that is based on the ant colony optimization (ACO) algorithm. The ACO was initially proposed by Dorigo and coworkers (Dorigo, 1992, Dorigo and Blum, 2005, Dorigo et al., 1996 and Dorigo et al., 2000), and was inspired by the food-foraging behavior of ant colonies. The ACO algorithm has been advocated for use in solving VRPs with time windows (Gambardella et al., 1999 and Reimann et al., 2004). Lau et al. (2003) derives the hybrid ants system and tabu search to solve the IRP with time windows (IRPTW) and discovers the solution quality and time performances of the hybridized scheme by decomposing the IRPTW into two single-objective sub-problems. In contrast to the conventional ACO meta-heuristic developed for combinatorial optimization problems, the ACO framework considered in this paper not only calculates the pheromone values along the trail, but also computes the set of feasible neighbors making use of the attraction on nodes. Section 2 of this paper provides detailed formulations of the cost model, including stockout costs and transportation costs. Section 3 discusses the modified AOC algorithm used to solve the integrated problem, and Section 4 presents the results. These results demonstrate the benefits of incorporating consideration of the attraction on nodes in AOC, as compared to limiting consideration to the pheromone values along the trail, as in the classic ACO algorithm. The final section summarizes findings, discusses their implications, and lastly, suggests avenues for further research.

This paper has outlines how a minimum cost model was formulated for the multi-item replenishment problem in conditions of uncertain demand, and the development of a modified ACO algorithm, which minimizes the total cost and stockout costs indicated by the attraction of pheromone values on nodes. This study included an extensive comparison of the conventional ACO and the modified ACO, to confirm the superior performance of this adapted algorithm in the fixed fleet VRPSDMI. The results of our simulations and optimizations reveal that the modified ACO algorithm achieves highly significant improvements compared to the conventional ACO. Future studies could expand the exploration of the present problem into a multiple-item IRP with demand uncertainty and multiple failures, and thus address potential recourse strategies for determining a route that incurs minimum total costs. Another potential topic for further research is to set up the multiple-item IRP with several satellite facilities (Bard et al., 1998 and Jaillet et al., 2002) to permit drivers to refill their vehicles, and check whether the modified ACO algorithm still strikes a good balance between solution quality and running time.