Abstract




 
   

IJE TRANSACTIONS C: Aspects Vol. 31, No. 6 (June 2018) 626-635   

downloaded Downloaded: 0   viewed Viewed: 228

  DEVELOPING THE INVENTORY ROUTING PROBLEM CONSIDERING THE MULTIPLE DELIVERY STRATEGY WITH BACKHAULS AND SPLIT SERVICE: SOLVED WITH THE GENETIC ALGORITHM
 
M. Forghani, M. A. Vahdat Zad and A. Sadegheih
 
( Received: July 30, 2017 – Accepted: February 15, 2018 )
 
 

Abstract    One of the most important points in a supply chain is customer-driven modeling, which reduces the bullwhip effect in the supply Chain, as well as the costs of investment on the inventory and efficient transshipment of the products. The homogeneity of them is reflected in the Inventory Routing Problem, which is a combination of distribution and inventory management. In this paper, with regard to the literature, the classical Inventory Routing Problem has been expanded based on the Multiple Delivery Strategy along with one of the functionalities of routing problem, namely, "backhauls", with a priority consideration for linehaul customers. Then it has been modeled in the form of a problem with Multi-period, multi-product, and multi- vehicle planning horizons that stock out is not allowed. Moreover, for an optimal use of the vehicle capacity to serve the linehaul and backhaul customers, the problem of “split service” has been added to the model, which also increases the complexity of the problem. First, considering the above-mentioned assumptions, a new mathematical model is proposed in the form of mixed integer programming for the problem defined in this paper. Then, since the stated problem can be considered among the non-deterministic polynomial-time hard, an efficient meta-heuristic genetic algorithm is provided for solving it. At the end, the numerical results obtained by this algorithm are analyzed using the randomized testing problems.

 

Keywords    Inventory-routing, backhauls, Logistics, heterogeneous fleet, split delivery, Genetic algorithm, multi product.

 

چکیده    یکی از نکات بسیار مهم در یک زنجیره تأمین، مدلسازي بر مبناي میزان مصرف مشتریان که منجر به کاهش اثر شلاقی زنجیره و نیز هزینه­ هاي حاصل از سرمایه­ گذاري بر موجودي و حمل ونقل کارآمد محصولات می­ شود، است. بطوریکه یکپارچگی آن­ها در مسأله مسیریابی-موجودی که ترکیبی از مدیریت توزیع و موجودی می­ باشد، نمود پیدا می­ کند. در این مقاله با توجه به ادبیات موضوع مسأله کلاسیک مسیریابی- موجودی را تحت استراتژی توزیع ارسال در طی مسیر به همراه یکی از ویژگی­های کاربردی مسایل مسیریابی یعنی «حمل در بازگشت» با اولویت مشتریان خط رفت، بسط داده و در قالب یک مسأله با افق برنامه ­ریزی چنددوره­ ای، چند محصولی و چندوسیله­ ای که کمبود مجاز نمی ­باشد، مدلسازی شده است. همچنین برای استفاده بهینه از ظرفیت وسایل نقلیه جهت خدمت ­رسانی به مشتریان خط رفت و برگشت موضوع «تقسیم تقاضا» به مدل اضافه شده که این موضوع پیچیدگی مسأله را نیز افزایش می­ دهد. با توجه به مفروضات فوق، ابتدا یک مدل ریاضی جدید در قالب برنامه ­ریزی عددصحیح مختلط برای مسأله تعریف شده در این مقاله ارایه شده و به دلیل اینکه مسأله مذکور در زمره مسایل چند جمله ­اي نامعین سخت قرار دارد، در ادامه یک الگوریتم متاهیوریستیک «ژنتیک کارا» برای حل آن تشریح و در پایان به تحلیل نتایج عددي حاصل از این الگوریتم با استفاده از مسایل نمونه تصادفی طراحی شده، پرداخته می­ شود.

References    [1]- Fumero, F., Vercellis, C., Integrating distribution, machine assignment and lot-sizing via lagrangian relaxation. International Journal of Production Economics, Vol. 49, No. 1, (1997), 45–54. [2]- Li, j., Chu, f., Chen, H., "A solution approach to the inventory routing problem in a three-level distribution system". European Journal of Operational Research, Vol. 210, (2011), 736–744. [3]- Aghezzaf, E., Raa, B., Van Landeghem, H., "Modeling inventory routing problems in supply chains of high consumption products". European Journal of Operational Research, Vol. 169, (2006), 1048–1063. [4]- Karp, R. M., "Reducibility among combinatorial problems", in Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Eds., Plenum Press, New York, (1972), 85-104. [5]- Bell, W. J., Dalberto, L. M., Fisher, M. L., Greenfield, A. J., Jaikumar, R., Kedia, P., Mack, R. G., Prutzman, P. J., "Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer". Interfaces, Vol. 13, No. 6, (1983), 4–23. [6]- Federgruen, A., Zipkin, PH., A combined vehicle routing and inventory allocation problem. Operations Research, Vol. 32, No. 10, (1984), 19–37. [7]- Blumenfeld DE, Burns LD, Diltz JD, Daganzo CF., "Analyzing trade-offs between transportation, inventory and production costs on freight networks". Transportation Res. Part B: Methodological, Vol. 19, No. 5, (1985), 361–380. [8]- Anily, S. and A. Federgruen "One warehouse multiple retailer systems with vehicle Routing costs." Management Science, Vol.  36, No. 1, (1990), 92-114. [9]- Kleywegt, A.J., Nori, V.S., Savelsbergh, M. W. P., "The stochastic inventory routing problem with direct deliveries". Transportation Science. Vol. 36, No. 1, (2002), 94–118. [10]- Andersson. H., Christiansen. M., Fagerholt. K., "Transportation planning and inventory management in the LNG supply chain". In: Bjørndal E, Bjørndal M, Pardalos PM, Ronnqvist M, editors. Energy, natural resources and environmental economics. New York: Springer. (2010), 223–248. [11]- Coelho, L.C., Cordeau, J-F., Laporte, G., "Thirty years of inventory routing." Transportation Science, Vol. 48, No. 1, (2014). 1-19. [12]- Bertazzi, L., G. Paletta, M. G. Speranza., "Deterministic order-up-to level policies in an inventory routing problem." Transportation Science. Vol. 36, No. 1, (2002), 119-132. [13]- Li, K., Chen, B., Sivakumar, A. L., Wu, Y., "An inventory–routing problem with the objective of travel time minimization." European Journal of Operational Research, Vol. 236, No. 3, (2014), 936-945. [14]- Archetti. C., Bertazzi L, Laporte. G., Speranza M. G., "A branch and cut algorithm for a vendor-managed inventory-routing problem". Transportation Science. Vol. 41, No.3, (2007), 382–391. [15]- Solyali, O., Süral, H., A branch-and-cut algorithm using a strong formulation and an a priori tour-based heuristic for an inventory-routing problem. Transportation Sci. Vol.45, No.3, (2011), 335–345. [16]- Desaulniers, G., J. G. Rakke, L. C. Coelho, "A branch-price-and-cut algorithm for the inventory-routing problem." Transportation Science. Vol.50, No.3, (2016), 1060-1076. [17]- Archetti, C., L. Bertazzi, L. Hertz., M. G. Speranza., "A hybrid heuristic for an inventory routing problem." INFORMS Journal on Computing, Vol.24, No.1, (2012), 101-116. [18]- Coelho, L.C., Cordeau, J-F., Laporte, G., "Consistency in multivehicle inventory-routing". Transportation Resreach. Part C: Emerging Tech. Vol. 24, No.1, (2012a), 270–287. [19]- Archetti C, Bianchessi N, Irnich S, Speranza MG "Formulations for an inventory routing problem." International Transactions in Operational Research, Vol. 21, No.3, (2014), 353-374. [20]- Coelho, L. C., and G. Laporte, "A branch-and-cut algorithm for the multi-product multi-vehicle inventory-routing problem." International Journal of Production Research. Vol.51, No.23-24, (2013a), 7156-7169. [21]- Adulyasak, Y., J.-F. Cordeau, R. Jans., "Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems." INFORMS Journal on Computing, Vol.26, No.1, (2014), 103-120. [22]- Coelho, L.C., Cordeau, J-F., Laporte, G., "Dynamic and stochastic inventory-routing". Technical report, CIRRELT-201237, Montreal, Canada, (2012b). [23]- Abdelmaguid T.F., "Heuristic approaches for the integrated inventory distribution problem". PhD thesis, University of Southern California, Los Angeles, USA, (2004). [24]- Abdelmaguid, T. F. and M. M. Dessouky "A genetic algorithm approach to the integrated inventory-distribution problem." International Journal of Production Research, Vol. 44, No. 21, (2006), 4445-4464.  [25]- Santos, E., Ochi, L. S., Simonetti, L., González, P. H., "A hybrid heuristic based on iterated local search for multivehicle inventory routing problem." Electronic Notes in Discrete Mathematics, Vol. 52, (2016), 197-204. [26]- Moin, N. H., S. Salhi, Aziz, N. A. B. "An efficient hybrid genetic algorithm for the multi-product multi-period inventory routing problem." International Journal of Production Economics, Vol. 133, No. 1, (2011), 334-343. [27]- Mjirda, A., Jarboui, B., Rita, M., Saïd, H., Nenad, M., "A two phase variable neighborhood search for the multi-product inventory routing problem." Computers & Operations Research, Vol. 52, (2014), 291-299. [28]- Sindhuchao, S., Romeijn, H. E., Elif, A., Rein, B., "An integrated inventory-routing system for multi-item joint replenishment with limited vehicle capacity." Journal of Global Optimization. Vol. 32, No. 1, (2005), 93-118. [29]- Popović, D., Vidović, M., Gordana, R., "Variable neighborhood search heuristic for the inventory routing problem in fuel delivery." Expert Systems with Applications. Vol. 39, No.18, (2012), 13390-13398. [30]- Coelho, L. C., and G. Laporte, "The exact solution of several classes of inventory-routing problems". Computers and Operations Research. Vol. 40, No. 2, (2013b), 558–565. [31]- Cordeau, J.-F., Laganà, D., Roberto, M., Francesca, V., "A decomposition-based heuristic for the multiple-product inventory-routing problem." Computers & Operations Research, Vol. 55, (2015), 153-166. [32]- Guemri, O., Bekrar, A., Bouziane, B., Damien, T., "GRASP-based heuristic algorithm for the multi-product multi-vehicle inventory routing problem." 4OR, Vol. 14, No.4, (2016), 377-404. [33]- Rabbani, M., Baghersad, M., Jafari, R., "A new hybrid GA-PSO method for solving multi-period inventory routing problem with considering financial decisions." Journal of Industrial Engineering and Management. Vol. 6, No. 4, (2013), 909-929. [34]- Mirzaei, S. and A. Seifi,"Considering lost sale in inventory routing problems for perishable goods." Computers & Industrial Engineering, Vol. 87, (2015), 213-227. [35]- Azadeh, A., S. Elahi, M. H. Farahani., B. Nasirian., "A genetic algorithm-Taguchi based approach to inventory routing problem of a single perishable product with transshipment." Computers and Industrial Engineering, Vol. 104, (2017), 124-133. [36]- Liu, S.-C., Lu, M.-C., Chung, C.-H., "A hybrid heuristic method for the periodic inventory routing problem." The International Journal of Advanced Manufacturing Technology, Vol. 85, No. 9, (2016), 2345-2352. [37]- Dror, M., & Trudeau, P. "Split delivery routing". Naval Research Logistics, Vol. 37, (1990), 383–402. [38]- Archetti, C. and M. G. Speranza "The split delivery vehicle routing problem: A Survey". The Vehicle Routing Problem: Latest Advances and New Challenges. B. Golden, S. Raghavan and E. Wasil. Boston, MA, Springer US, (2008), 103-122. [39]- Yu, Y., Chen, H., and Chu, F., "Large scale inventory routing problem with split delivery: a new model and Lagrangian relaxation approach". In: IEEE international conference on service operations and logistics, and informatics, Beijing, China, (2005). [40]- Yu, Y., Chen, H., Chu, F., "A new model and hybrid approach for large scale inventory routing problems." European Journal of Operational Research, Vol.189, No.3, (2008), 1022-1040 [41]- Yu, Y., Chu, C., Chen, H., Chu, F., "Large scale stochastic inventory routing problems with split delivery and service level constraints." Annals of Operations Research, Vol.197, No.1, (2012), 135-158. [42]- Koza, J. R., "Genetic Programming: On the Programming of Computers by Means of Natural Selection" Cambridge, Mass., MIT Press, (1992).





International Journal of Engineering
E-mail: office@ije.ir
Web Site: http://www.ije.ir