راه حل های بهبود یافته برای مشکلات مسیریابی موجودی از طریق نابرابری های معتبر و ورودی سفارش

Inventory-routing problems (IRP) combine inventory control and vehicle routing, effectively optimizing inventory and replenishment decisions over several periods at a centralized level. In this paper we provide an exact formulation which includes several well-known valid inequalities for some classes of IRPs. We then propose three new valid inequalities based on the relation between demand and available capacities. Then, following an idea proposed for the binary clustering and for the job scheduling problems, we also show how the order of the input data can have a major effect on the linear relaxation of the proposed model for the IRP. Extensive computational experiments confirm the success of our algorithm. We have used two available datasets with new solutions identified as recently as 2013. On one set of benchmark instances with 249 open instances, we have improved 98 lower bounds, we have computed 96 new best known solutions, and we have proved optimality for 11 instances. On the other dataset composed of larger instances, of which were 63 open, we have improved 32 lower bounds, we have obtained 20 new best known solutions, and we proved optimality for three instances.

Inventory control is one of the pillars of production economics. Its underlying theoretical basis is rooted in the ground breaking paper of Harris (1913). This seminal article formalizes the well-known Economic Order Quantity (EOQ) model which computes the quantity that minimizes total inventory holding and ordering costs in a constant demand environment. Several extensions and variations of this model have emerged over the years. For the case of non-constant demands, the classical reference is the paper of Wagner and Whitin (1958) which generalizes the EOQ model to the dynamic lot sizing problem. This problem was solved exactly by dynamic programming by Wagner and Whitin (1958), and heuristically by the well-known Silver-Meal algorithm (Silver and Meal, 1973). The multi-product case was studied for more than 50 years, as was the problem of determining the lot size for the manufacturing of several products on the same machine. This problem, known as the Economic Lot Scheduling Problem, was introduced by Rogers (1958) and was later extended by Elmaghraby (1978). Recently, the research community has focused its attention on joint decision making problems arising in several areas, thus removing some of the boundaries between some logistics activities. This joint decision planning arises when information from different areas are combined to make more general decisions, which take into account a broader view of the production process. These include inventory problems arising in green and reverse logistics (Gou et al., 2008) in that it seeks a trade-off between transportation costs, emissions and environmental aspects; robustness and resilience of inventory planning and control (Klibi and Martel, 2012) which combines location and transportation analysis coupled with unknown demands; inventory optimization with side constraints (van Donselaar and Broekmeulen, 2013 and van Horenbeek et al., 2013); as well as demand dynamism and stochasticity (Tarim and Kingsman, 2004). These problems cover different aspects of the supply chain, such as production set up costs, synchronized inventory and transportation (Adulyasak et al., forthcoming and Cárdenas-Barrón et al., 2012), inventory management, facility location and transportation (Guerrero et al., 2013), and joint transportation and inventory management (Andersson et al., 2010 and Coelho et al., forthcoming). Inventory-Routing Problems (IRP), which are the focus of this paper, combine inventory management and vehicle routing decisions by jointly optimizing inventory levels and replenishment for several products over several periods with several vehicles. The optimization process takes place at a centralized entity which is responsible for making all the decisions for the network. Usually this centralized element is the supplier. This is the case of vendor-managed inventory (VMI) applications in which the supplier is responsible for deciding when and how much to deliver to each of its customers. The integration of inventory management and vehicle routing decisions dates back to the 1980s and is rooted in the seminal paper of Bell et al. (1983). Since then, several technical contributions and applications have emerged. The survey paper of Andersson et al. (2010) concentrates on the applications of the IRP, whereas that of Coelho et al. (forthcoming) focuses on the methodological aspects of the problem. In what follows, we review some of the most relevant recent algorithmic literature on the IRP. The first exact algorithm for the IRP is due to Archetti et al. (2007) who solved the single-vehicle case. The proposed model and algorithm yielded optimal solutions for instances with up to 30 customers and six periods, and with up to 50 customers and three periods. The authors also introduced the first testbed which contains benchmark instances now used by most authors. Archetti et al. (2012) have later developed a powerful matheuristic algorithm based on tabu search and on the solution of mixed-integer problems which was able to compute solutions with very small optimality gaps on the testbed instances, within a very short running time. These authors also introduced a second and larger set of instances, still considering a single vehicle. At the same time, Coelho et al. (2012a) proposed an ALNS heuristic in which subproblems were solved as minimum-cost network flow problems. This algorithm also provides solutions with very low optimality gap. The algorithm of Coelho et al. (2012a) was later extended by Coelho et al. (2012b) to solve multi-vehicle instances. Finally, two similar exact algorithms, by Adulyasak et al. (forthcoming) and by Coelho and Laporte (2013), were recently developed for multi-vehicle problems. The first solves the IRP by branch-and-cut as a special case of the production-routing problem, and was tested on the first set of instances. The second applies a branch-and-cut scheme enhanced by the exact solution of smaller mixed-integer linear programs, which constitutes a powerful upper bounding procedure and provides all best known solutions on the two sets of benchmark instances. With respect to the existing literature, this paper makes three main contributions. First, we introduce new valid inequalities in the context of the multi-vehicle IRP, which are based on the demand and on the capacities of the customers and of the vehicles. Second, we analyze the impact of changing the order of the input on the value of the linear relaxation, and thus, on the best lower bound value obtained after a given computing time. Third, we show how these first two contributions yield improved lower bounds and provide new best known solutions for large open benchmark instances of the IRP. The remainder of the paper is organized as follows. In Section 2 we provide a formal statement of the problem as well as an exact mixed-integer linear formulation for it. Existing and new valid inequalities are presented in detail in Section 3, which also introduces the notion of input ordering for the IRP. The exact branch-and-cut algorithm is briefly described in Section 4, followed by computational experiments in Section 5. Conclusions are presented in Section 6.

We have developed new valid inequalities which hold for several classes of IRPs, and we have tested the effect of changing the order of the input data on the quality of the bounds obtained and on the running time. We have generated new best known solutions for several large instances of the multi-vehicle IRP. We have also obtained improved lower bounds for several instances when compared with previous best known solutions, besides identifying new optimal solutions. We have increased the size of instances which we are now capable of solving exactly within short computational times.