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

Document Type : Original Article

Authors

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

Abstract

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.
 
 

Keywords


-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.