A Robust Optimization Model for the Single-Depot Capacitated Location-Routing Problem

Authors: Abdolsalam Ghaderi

Abstract:

In this paper, the single-depot capacitated location-routing problem under uncertainty is presented. The problem aims to find the optimal location of a single depot and the routing of vehicles to serve the customers when the parameters may change under different circumstances. This problem has many applications, especially in the area of supply chain management and distribution systems. To get closer to real-world situations, travel time of vehicles, the fixed cost of vehicles usage and customers’ demand are considered as a source of uncertainty. A combined approach including robust optimization and stochastic programming was presented to deal with the uncertainty in the problem at hand. For this purpose, a mixed integer programming model is developed and a heuristic algorithm based on Variable Neighborhood Search(VNS) is presented to solve the model. Finally, the computational results are presented and future research directions are discussed.

Keywords: Location-routing problem, robust optimization, Stochastic Programming, variable neighborhood search.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1317206

References:

[1] Adulyasak, Y. and Jaillet, P. (2015), ‘Models and algorithms for stochastic and robust vehicle routing with deadlines’, Transportation Science 50(2), 608–626.
[2] Braaten, S., Gjønnes, O., Hvattum, L. M. and Tirado, G. (2017), ‘Heuristics for the robust vehicle routing problem with time windows’, Expert Systems with Applications 77, 136–147.
[3] Drexl, M. and Schneider, M. (2015), ‘A survey of variants and extensions of the location-routing problem’, European Journal of Operational Research 241(2), 283–308.
[4] Ghaderi, A., Boland, N. and JabalAmeli, M. S. (2012), ‘Exact and heuristic approaches to the budget-constrained dynamic uncapacitated facility location-network design problem’, Centre for Optimal Planning and Operations, The University of Newcastle .
[5] Ghaderi, A. and Rahmaniani, R. (2016), ‘Meta-heuristic solution approaches for robust single allocation p-hub median problem with stochastic demands and travel times’, The International Journal of Advanced Manufacturing Technology 82(9-12), 1627–1647.
[6] Ghaffari-Nasab, N., Jabalameli, M. S., Aryanezhad, M. B. and Makui, A. (2013), ‘Modeling and solving the bi-objective capacitated location-routing problem with probabilistic travel times’, The International Journal of Advanced Manufacturing Technology pp. 1–13.
[7] Harrison, H. (1979), ‘A planning system for facilities and resources in distribution networks’, Interfaces 9(2-part-2), 6–22.
[8] Jabalameli, M. S. and Ghaderi, A. (2008), ‘Hybrid algorithms for the uncapacitated continuous location-allocation problem’, The International Journal of Advanced Manufacturing Technology 37(1), 202–209.
[9] Jacobsen, S. K. and Madsen, O. B. (1980), ‘A comparative study of heuristics for a two-level routing-location problem’, European Journal of Operational Research 5(6), 378–387.
[10] Jacobsen, S. and Madsen, O. (1978), On the location of transfer points in a two-level newspaper delivery system–a case study, in ‘international symposium on locational decisions’, pp. 24–28.
[11] Jarboui, B., Derbel, H., Hanafi, S. and Mladenovi´c, N. (2013), ‘Variable neighborhood search for location routing’, Computers & Operations Research 40(1), 47–57.
[12] Keyvanshokooh, E., Ryan, S. M. and Kabir, E. (2016), ‘Hybrid robust and stochastic optimization for closed-loop supply chain network design using accelerated benders decomposition’, European Journal of Operational Research 249(1), 76–92.
[13] Klibi, W., Lasalle, F., Martel, A. and Ichoua, S. (2010), ‘The stochastic multiperiod location transportation problem’, Transportation Science 44(2), 221–237.
[14] Laporte, G., Louveaux, F. and Mercure, H. (1989), ‘Models and exact solutions for a class of stochastic location-routing problems’, European Journal of Operational Research 39(1), 71–78.
[15] Laporte, G. and Nobert, Y. (1981), ‘An exact algorithm for minimizing routing and operating costs in depot location’, European Journal of Operational Research 6(2), 224–226.
[16] Madsen, O. B. (1983), ‘Methods for solving combined two level location-routing problems of realistic dimensions’, European Journal of Operational Research 12(3), 295–301.
[17] Mladenovi´c, N. and Hansen, P. (1997), ‘Variable neighborhood search’, Computers & operations research 24(11), 1097–1100.
[18] Nambiar, J. M., Gelders, L. F. and Van Wassenhove, L. N. (1981), ‘A large scale location-allocation problem in the natural rubber industry’, European Journal of Operational Research 6(2), 183–189.
[19] Or, I. and Pierskalla, W. P. (1979), ‘A transportation location-allocation model for regional blood banking’, AIIE transactions 11(2), 86–95.
[20] Prodhon, C. (2006), Le Problme de Localisation-Routage(Location-routing problem, PhD thesis, Universit de Technologie de Troyes, Troyes, France. An optional note.
[21] Prodhon, C. and Prins, C. (2014), ‘A survey of recent research on location-routing problems’, European Journal of Operational Research 238(1), 1–17.
[22] Salhi, S., Imran, A. and Wassan, N. A. (2014), ‘The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation’, Computers & Operations Research 52, 315–325.
[23] Salhi, S. and Rand, G. K. (1989), ‘The effect of ignoring routes when locating depots’, European Journal of Operational Research 39(2), 150 – 156.
[24] Schneider, M. and Drexl, M. (2017), ‘A survey of the standard location-routing problem’, Annals of Operations Research pp. 1–26.
[25] Snyder, L. V. and Daskin, M. S. (2006), ‘Stochastic p-robust location problems’, IIE Transactions 38(11), 971–985.
[26] Sungur, I., Ord´onez, F. and Dessouky, M. (2008), ‘A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty’, IIE Transactions 40(5), 509–523.
[27] Wei, L., Zhang, Z., Zhang, D. and Lim, A. (2015), ‘A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints’, European Journal of Operational Research 243(3), 798–814.