مدل‌سازی ریاضی و ارایه یک الگوریتم فراابتکاری مبتنی بر جمعیت برای مسأله مسیریابی- موجودی چندمحصولی، چندوسیله‌ای همراه با جریان معکوس

نوع مقاله: مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری، دانشکده فنی و مهندسی، دانشگاه یزد، یزد، ایران

2 استادیار، دانشکده فنی و مهندسی، دانشگاه یزد، یزد، ایران

3 استاد، دانشکده فنی و مهندسی، دانشگاه یزد، یزد، ایران

چکیده

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

کلیدواژه‌ها


عنوان مقاله [English]

Mathematical Modeling and the Presentation of A Population-Based Meta- Heuristic Algorithm for Multi-Product, Multi-Vehicle Inventory- Routing Problem, With Backhauls

نویسندگان [English]

  • M. Forghani 1
  • M. A. Vahdat-Zad 2
  • A. Sadegheih 3
1 Ph.D., Student ,Department of Industrial Engineering, Faculty of Engineering, Yazd University, Yazd, Iran
2 Assistant Professor, Department of Industrial Engineering, Faculty of Engineering, Yazd University, Yazd, Iran
3 Professor, Department of Industrial Engineering, Faculty of Engineering, Yazd University, Yazd, Iran
چکیده [English]

One of the key issues in the operational management of the supply chain is the inventory routing problem, which is a combination of inventory management and transportation planning. According to the literature review, this paper combines one of the practical features of routing problem named as "backhauls" with the multi-product, multi-period, multi-Vehicle inventory- routing problem. The stock out and backlogging is not allowed in this model. The Strategy of routing is Multiple Delivery Strategy. This problem is non-deterministic polynomial-time hard (NP-hard) and the solution time, using the exact methods, increase exponentially with the increase in the dimensionality of the problem. Therefore, after introducing the research background, a new mathematical model is proposed in the form of the mixed integer programming for the problem defined in this paper. As follows, an efficient meta-heuristic genetic algorithm is provided to solve it. At the end, the numerical results obtained by this algorithm are analyzed using the randomized testing problems.
 
 

کلیدواژه‌ها [English]

  • Genetic Algorithm
  • Multi-Product
  • Backhauls
  • Inventory-Routing
  • Heterogeneous Fleet

-Abdelmaguid, T.F., Dessouky, M. M., Ordóñez, F., (2009), "Heuristic approaches for the inventory-routing problem with backlogging." Computers & Industrial Engineering, Vol.56, No.4, pp. 1519-1534.

 

-Adelman, D., (2004), "Price-directed approaches to stochastic inventory/routing". Operations Research, Vol.52, No.4,
pp. 499–514.

 

-Adulyasak, Y., Cordeau, J.-F., Jans, R., (2014), "Formulations and Branch-and-Cut Algorithms for Multivehicle Production and Inventory Routing Problems." INFORMS Journal on Computing Vol. 26, No.1,
pp. 103-120.

 

-Andersson H, Christiansen M, Fagerholt K., (2010). "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. pp. 427-439.

 

-Anily, S. and A. Federgruen (1990), "One Warehouse Multiple Retailer Systems with Vehicle Routing Costs." Management Science Vol. 36, No.1, pp. 92-114.

 

-Archetti, C., Bertazzi, L., Hertz, L., Speranza, M. G., (2012), "A Hybrid Heuristic for an Inventory Routing Problem." INFORMS Journal on Computing, Vol. 24, No.1, pp. 101-116.

 

-Archetti, C., Bertazzi, L., Hertz, L., Speranza, M. G., (2014), "Formulations for an inventory routing problem." International Transactions in Operational Research, Vol. 21, No.3, pp. 353-374.

 

-Azadeh, A., Elahi, S., Farahani, M. H., Nasirian, B., (2017), "A genetic algorithm-Taguchi based approach to inventory routing problem of a single perishable product with transshipment." Computers & Industrial Engineering, Vol. 104,
pp. 124-133.

 

-Bard, J. F. and N. Nananukul (2009), "Heuristics for a multi period inventory routing problem with production decisions." Computers & Industrial Engineering, Vol. 57, No. 3, pp. 713-723.

 

-Bassok, Y. and R. Ernst (1995), "Dynamic Allocations for Multi-Product Distribution." Transportation Science, Vol. 29, No. 3,
pp. 256-266.

 

-Bell, W. J., Dalberto, L. M., Fisher, M.
L., Greenfield, A. J., Jaikumar, R., Kedia, P., Mack, R. G., Prutzman, P. J., (1983), "Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer". Interfaces, Vol. 13, No. 6, pp. 4–23.

 

-Benoist, T., Gardi, F., Jeanjean, A., Estellon, B., (2011) "Randomized local search for real-life inventory routing". Transportation Science, Vol. 45, No. 3, pp. 381–398.

 

-Berman, O. and R. C. Larson (2001), "Deliveries in an Inventory/Routing Problem Using Stochastic Dynamic Programming." Transportation Science, Vol. 35, No. 2, pp. 192-213.

 

-Bertazzi, L., Paletta, G., Speranza, M.G., (2008), "Inventory Routing. The Vehicle Routing Problem", Latest Advances and New Challenges. B. Golden, S. Raghavan and E. Wasil. Boston, MA, Springer US,
pp. 49-72.

 

-Blumenfeld, D.E., Burns, L.D., Diltz, J.D., Daganzo, C.F., (1985), "Analyzing trade-offs between transportation, inventory and production costs on freight networks". Transportation Research, Part B: Methodological, Vol. 19, No.5,
pp. 361–380.

 

-Brandão, J., (2016), "A deterministic iterated local search algorithm for the vehicle routing problem with backhauls." TOP, Vol. 24, No.2, pp. 445-465.

 

-Cáceres-Cruz, J., Juan, A.A., Bektas, T., Grasman, S.E., Faulin, J., (2012), Combining Monte Carlo simulation with heuristics for solving the inventory routing problem with stochastic demands. In: Laroque, C., Himmelspach, J., Pasupathy, R., Rose, O., Uhrmacher, A. (Eds.), Proceedings of the 2012 Winter Simulation Conference. IEEE Press, Piscataway, NJ, USA.

 

-Campbell, A. M. and M. W. P. Savelsbergh (2004b), "Decomposition Approach for the Inventory-Routing Problem." Transportation Science, Vol.38, No.4,
pp. 488-502.

 

-Chien, T. W., Balakrishnan, A., Wong, R.T., (1989), "An integrated inventory allocation and vehicle routing problem". Transportation Science, Vol. 23, No. 2,
pp. 67–76.

 

-Coelho, L.C., Cordeau, J-F., Laporte, G., (2012a) "Consistency in multivehicle inventory-routing". Transportation Research Part C: Emerging Tech. Vol. 24, No. 1,
pp. 270–287.

 

-Coelho, L.C., Cordeau, J-F., Laporte, G., (2012b), "Dynamic and stochastic inventory-routing". Technical report, CIRRELT-201237, Montreal, Canada.

 

-Coelho, L. C., and G. Laporte, (2013a), "A branch-and-cut algorithm for the
multi-product multi-vehicle inventory-routing problem." International Journal of Production Research. Vol. 51, No. 23-24, pp. 7156-7169.

 

-Coelho, L. C., and G. Laporte, (2013b) "The exact solution of several classes of inventory-routing problems". Computers & Operations Research, Vol. 40, No.2,
pp. 558–565.

-Coelho, L. C. and G. Laporte (2014). "Optimal joint replenishment, delivery and inventory management policies for perishable products." Computer & Operation Research Vol. 47, pp. 42-52.

 

-Coelho, L. C., Cordeau, J-F., Laporte, G., (2014), "Thirty Years of Inventory Routing." Transportation Science, Vol. 48, No.1, pp. 1-19.

 

-Cordeau, J.-F., Laganà, D., Roberto, M., Francesca, V., (2015), "A decomposition-based heuristic for the multiple-product inventory-routing problem." Computers & Operations Research, Vol. 55, pp. 153-166.

 

-Desaulniers, G., Rakke, J. G., Coelho, L. C., (2016), "A Branch-Price-and-Cut Algorithm for the Inventory-Routing Problem." Transportation Science, Vol. 50, No.3, pp. 1060-1076.

 

-Dror, M., and Trudeau, P., (1996), "Cash flow optimization in delivery scheduling". European Journal of Operational Research, Vol. 88, No. 5, pp. 04–15.

 

-Federgruen, A., and Zipkin, P. H., (1984), "A combined vehicle routing and inventory allocation problem". Operations Research, Vol. 32, No. 10, pp. 19–37.

 

-Gallego, G. and D. Simchi-Levi (1990), "On the Effectiveness of Direct Shipping Strategy for the One-Warehouse Multi-Retailer R-Systems." Management Science, Vol. 36, No. 2, pp. 240-243.

 

-Guemri, O., Bekrar, A., Bouziane, B., Damien, T., (2016), "GRASP-based heuristic algorithm for the multi-product multi-vehicle inventory routing problem." 4OR, Vol. 14, No. 4, pp. 377-404.

 

-Herer, Y.T. and Levy, R. (1997) The Metered Inventory Routing Problem, an Integrative Heuristic Algorithm. International Journal of Production Economics, Vol. 51, pp. 69-81.

 

-Huang, S.-H., and P.-C. Lin (2010). "A modified ant colony optimization algorithm for multi-item inventory routing problems with demand uncertainty." Transportation Research Part E: Logistics and Transportation Review, Vol. 46, No. 5,
pp. 598-611.

 

-Kleywegt, A.J., Nori, V.S., Savelsbergh, M. W. P., (2002). "The stochastic inventory routing problem with direct deliveries". Transportation Science. Vol. 36, No. 1, pp. 94–118.

 

-Letchford, A. N. and A. Oukil (2009), "Exploiting sparsity in pricing routines for the capacitated arc routing problem." Computers & Operations Research, Vol. 36, No. 7, pp. 2320-2327.

 

-Li, K., Chen, B., Sivakumar, A. L., Wu, Y., (2014), "An inventory–routing problem with the objective of travel time minimization." European Journal of Operational Research, Vol. 236, No. 3, pp. 936-945.

 

-Liu S-C., Lee W-T., (2011), "A heuristic method for the inventory routing problem with time windows". Expert Systems Application. Vol. 38, No. 10,
pp. 13223–13231.

 

-Liu, S.-C., Lu, M.-C., Chung, C.-H., (2016), "A hybrid heuristic method for the periodic inventory routing problem." The International Journal of Advanced Manufacturing Technology, Vol. 85, No. 9, pp. 2345-2352.

 

-Mes, M., Schutten, M., Rivera, A.P., (2014), "Inventory routing for dynamic waste collection." Waste Management, Vol. 34, No. 9, pp. 1564-1576.

 

-Mirzaei, S. and A. Seifi (2015), "Considering lost sale in inventory routing problems for perishable goods." Computers & Industrial Engineering, Vol. 87,
pp. 213-227.

 

-Moin, N. H. and S. Salhi (2007), "Inventory Routing Problems: A Logistical Overview." The Journal of the Operational Research Society, Vol.  58, No. 9, pp. 1185-1194.

 

-Oesterle, J. and T. Bauernhansl (2016), "Exact Method for the Vehicle Routing Problem with Mixed Linehaul and Backhaul Customers, Heterogeneous Fleet, time Window and Manufacturing Capacity." Procedia CIRP, Vol. 41, pp. 573-578.

 

-Park, Y.-B., Yoo, J.-S., Park, H.-S., (2016), "A genetic algorithm for the
vendor-managed inventory routing problem with lost sales." Expert Systems with Applications, Vol. 53, pp. 149-159.

 

-Raa, B. and E.-H. Aghezzaf (2008), "Designing distribution patterns for long-term inventory routing with constant demand rates." International Journal of Production Economics, Vol. 112, No. 1,
pp. 255-263.

-Raa, B. and E.-H. Aghezzaf (2009), "A practical solution approach for the cyclic inventory routing problem." European Journal of Operational Research, Vol. 192, No. 2, pp. 429-441.

 

-Rabbani, M., Baghersad, M., Jafari, R., (2013), "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,
pp. 909-929.

 

-Rahimi, M., Baboli, A., Rekik, Y., (2017), Inventory Routing Problem for Perishable Products by Considering Customer Satisfaction and Green Criteria. Dynamics in Logistics: Proceedings of the 5th International Conference LDIC, 2016 Bremen, Germany. M. Freitag, H. Kotzab and J. Pannek. Cham, Springer International Publishing, pp. 445-455.

 

-Reiman, M. I., R. Rubio and L. M. Wein (1999), “Heavy traffic analysis of the dynamic stochastic inventory-routing problem”. Transportation Science, Vol. 33, No. 4, pp. 361-380.

 

-Santos, E., Ochi, L. S., Simonetti, L., González, P. H., (2016), "A Hybrid Heuristic based on Iterated Local Search for Multivehicle Inventory Routing Problem." Electronic Notes in Discrete Mathematics, Vol. 52, pp. 197-204.

 

-Singh, T., Arbogast, J. E., Neagu, N., (2015). "An incremental approach using local-search heuristic for inventory routing problem in industrial gases." Computers & Chemical Engineering, Vol.  80,
pp. 199-210.

 

Solyali, O., Süral, H., (2011), "A branch-and-cut algorithm using a strong formulation and an a priori tour-based heuristic for an inventory-routing problem." Transportation Science. Vol. 45, No. 3, pp. 335–345.

 

-Stålhane, M., J. G. Rakke, C. R. Moe, H. Andersson, M. Christiansen and K. Fagerholt (2012), "A construction and improvement heuristic for a liquefied natural gas inventory routing problem." Computers & Industrial Engineering, Vol. 62, No. 1, pp. 245-255.

 

 

-Zhao, Q.-H., Chen, S., Zang, C.-X., (2008), "Model and algorithm for inventory/routing decision in a three-echelon logistics system." European Journal of Operational Research, Vol. 191, No. 3, pp. 623-635.