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

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.

Authors:

• Abdolsalam Ghaderi

Keywords:

• Location-routing problem
• robust optimization
• Stochastic Programming
• variable neighborhood search.

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.