Skip to main content
Top

2019 | OriginalPaper | Chapter

An Efficient Algorithm Based Tabu Search for the Robust Sparse CARP Under Travel Costs Uncertainty

Authors : Sara Tfaili, Abdelkader Sbihi, Adnan Yassine, Ibrahima Diarrassouba

Published in: Operations Research and Enterprise Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We previously studied the capacitated arc routing problem over sparse underlying graphs under travel costs uncertainty. In this paper, we study the same problem by recalling the mathematical formulation of the problem given in [29]. The problem is characterized by the uncertainty of the travel costs and by the sparse network over which it is defined. In fact, a Multiple-Scenario Min-Max CARP over sparse underlying graphs is studied. More numerical instances applying the greedy heuristic algorithm developed in [29] and the adapted tabu-search algorithm are introduced in which these computational experiments show the effectiveness of these two algorithms.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Álvarez-Miranda, E., Ljubić, I., Toth, P.: Exact approaches for solving robust prize-collecting Steiner tree problems. Eur. J. Oper. Res. 229(3), 599–612 (2013)MathSciNetCrossRef Álvarez-Miranda, E., Ljubić, I., Toth, P.: Exact approaches for solving robust prize-collecting Steiner tree problems. Eur. J. Oper. Res. 229(3), 599–612 (2013)MathSciNetCrossRef
2.
go back to reference Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)CrossRef Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)CrossRef
3.
go back to reference Bertsimas, D.: Probabilistic combinatorial optimization problems. Ph.D. thesis Massachusetts Institute of Technology, Dept. of Mathematics (1988) Bertsimas, D.: Probabilistic combinatorial optimization problems. Ph.D. thesis Massachusetts Institute of Technology, Dept. of Mathematics (1988)
5.
go back to reference Bertsimas, D., Gamarnik, D., Rikun, A.A.: Performance analysis of queueing networks via robust optimization. Oper. Res. 59(2), 455–466 (2011)MathSciNetCrossRef Bertsimas, D., Gamarnik, D., Rikun, A.A.: Performance analysis of queueing networks via robust optimization. Oper. Res. 59(2), 455–466 (2011)MathSciNetCrossRef
8.
go back to reference Christiansen, C.H., Lysgaard, J.: A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. Lett. 35(6), 773–781 (2007)MathSciNetCrossRef Christiansen, C.H., Lysgaard, J.: A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. Lett. 35(6), 773–781 (2007)MathSciNetCrossRef
9.
go back to reference Christiansen, C.H., Lysgaard, J., Wøhlk, S.: A branch-and-price algorithm for the capacitated arc routing problem with stochastic demands. Oper. Res. Lett. 37(6), 392–398 (2009)MathSciNetCrossRef Christiansen, C.H., Lysgaard, J., Wøhlk, S.: A branch-and-price algorithm for the capacitated arc routing problem with stochastic demands. Oper. Res. Lett. 37(6), 392–398 (2009)MathSciNetCrossRef
10.
go back to reference Coco, A.A., Solano-Charris, E.L., Santos, A.C., Prins, C., Noronha, T.: Robust optimization criteria: state-of-the-art and new issuses. Technical report UTT-LOSI -14001. ISSN:2266–5064. Universit\(\acute{\text{e}}\) de Technologie de Troyes (2014) Coco, A.A., Solano-Charris, E.L., Santos, A.C., Prins, C., Noronha, T.: Robust optimization criteria: state-of-the-art and new issuses. Technical report UTT-LOSI -14001. ISSN:2266–5064. Universit\(\acute{\text{e}}\) de Technologie de Troyes (2014)
13.
go back to reference Han, J., Lee, C., Park, S.: A robust scenario approach for the vehicle routing problem with uncertain travel times. Transp. Sci. 48(3), 373–390 (2013)CrossRef Han, J., Lee, C., Park, S.: A robust scenario approach for the vehicle routing problem with uncertain travel times. Transp. Sci. 48(3), 373–390 (2013)CrossRef
14.
go back to reference Kasperski, A., Zieliński, P.: On the approximability of robust spanning tree problems. Theoret. Comput. Sci. 412(4–5), 365–374 (2011)MathSciNetCrossRef Kasperski, A., Zieliński, P.: On the approximability of robust spanning tree problems. Theoret. Comput. Sci. 412(4–5), 365–374 (2011)MathSciNetCrossRef
15.
go back to reference Kenyon, A.S., Morton, D.: Stochastic vehicle routing with random travel times. Transp. Sci. 37(1), 69–82 (2003)CrossRef Kenyon, A.S., Morton, D.: Stochastic vehicle routing with random travel times. Transp. Sci. 37(1), 69–82 (2003)CrossRef
16.
go back to reference Kouvelis, P., Yu, G.: Robust Discrete Optimization and its Applications. Kluwer Academic Publishers, Norwell (1997)CrossRef Kouvelis, P., Yu, G.: Robust Discrete Optimization and its Applications. Kluwer Academic Publishers, Norwell (1997)CrossRef
17.
go back to reference Laporte, G., Louveaux, F., Mercure, H.: The vehicle routing problem with stochastic travel times. Transp. Sci. 26(3), 161–170 (1992)CrossRef Laporte, G., Louveaux, F., Mercure, H.: The vehicle routing problem with stochastic travel times. Transp. Sci. 26(3), 161–170 (1992)CrossRef
18.
go back to reference Laporte, G., Louveaux, F., Hamme, L.V.: An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. 50(3), 415–423 (2002)MathSciNetCrossRef Laporte, G., Louveaux, F., Hamme, L.V.: An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. 50(3), 415–423 (2002)MathSciNetCrossRef
19.
20.
go back to reference Mei, Y., Tang, K., Yao, X.: Capacitated arc routing problem in uncertain environments. In: IEEE World Congress on Computational Intelligence, pp. 1400–1407 (2010) Mei, Y., Tang, K., Yao, X.: Capacitated arc routing problem in uncertain environments. In: IEEE World Congress on Computational Intelligence, pp. 1400–1407 (2010)
21.
go back to reference Monaci, M., Pferschy, U., Serafini, P.: Exact solution of the robust knapsack problem. Comput. Oper. Res. 40(11), 2625–2631 (2013)MathSciNetCrossRef Monaci, M., Pferschy, U., Serafini, P.: Exact solution of the robust knapsack problem. Comput. Oper. Res. 40(11), 2625–2631 (2013)MathSciNetCrossRef
22.
go back to reference Sbihi, A.: A cooperative local serach-based algorithm for the multiple-scenario max-min knapsack problem. Eur. J. Oper. Res. 202(2), 339–346 (2010)CrossRef Sbihi, A.: A cooperative local serach-based algorithm for the multiple-scenario max-min knapsack problem. Eur. J. Oper. Res. 202(2), 339–346 (2010)CrossRef
23.
go back to reference Secomandi, N.: Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands. Comput. Oper. Res. 27(11–12), 1201–1225 (2000)CrossRef Secomandi, N.: Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands. Comput. Oper. Res. 27(11–12), 1201–1225 (2000)CrossRef
24.
go back to reference Secomandi, N., Margot, F.: Reoptimization approaches for the vehicle-routing problem with stochastic demands. Oper. Res. 57(1), 214–230 (2009)CrossRef Secomandi, N., Margot, F.: Reoptimization approaches for the vehicle-routing problem with stochastic demands. Oper. Res. 57(1), 214–230 (2009)CrossRef
25.
go back to reference Shapiro, A., Dentcheva, S., Ruszczyński, A.: Lectures on Stochastic Programming: Modeling and Theory, vol. 9 (2008) Shapiro, A., Dentcheva, S., Ruszczyński, A.: Lectures on Stochastic Programming: Modeling and Theory, vol. 9 (2008)
26.
go back to reference Solano Charris, E.L.: Optimization methods for the robust vehicle routing problem. In: Ph.D. thesis, Universit\(\acute{\text{ e }}\) de Technologie de Troyes (2015) Solano Charris, E.L.: Optimization methods for the robust vehicle routing problem. In: Ph.D. thesis, Universit\(\acute{\text{ e }}\) de Technologie de Troyes (2015)
27.
go back to reference Sun, L.: A new robust optimization model for the vehicle routing problem with stochastic demands. J. Interdisc. Math. 17(3), 287–309 (2014)CrossRef Sun, L.: A new robust optimization model for the vehicle routing problem with stochastic demands. J. Interdisc. Math. 17(3), 287–309 (2014)CrossRef
28.
go back to reference Sungur, I., Ordóñez, F., Dessouky, M.: A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Trans. 40(5), 509–523 (2008)CrossRef Sungur, I., Ordóñez, F., Dessouky, M.: A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Trans. 40(5), 509–523 (2008)CrossRef
29.
go back to reference Tfaili, S., Sbihi, A., Yassine, A., Diarrassouba, I.: Capacitated arc routing problem over sparse underlying graph and under travel costs uncertainty. In: Proceedings of the 7th International Conference on Operations Research and Enterprise Systems: ICORES, vol. 1, pp. 144–151 (2018) Tfaili, S., Sbihi, A., Yassine, A., Diarrassouba, I.: Capacitated arc routing problem over sparse underlying graph and under travel costs uncertainty. In: Proceedings of the 7th International Conference on Operations Research and Enterprise Systems: ICORES, vol. 1, pp. 144–151 (2018)
30.
go back to reference Toklu, N.E., Montemanni, R., Gambardella, L.M.: An ant colony system for the capacitated vehicle routing problem with uncertain travel costs. In: IEEE Symposium on Swarm Intelligence (SIS), pp. 32–39 (2013) Toklu, N.E., Montemanni, R., Gambardella, L.M.: An ant colony system for the capacitated vehicle routing problem with uncertain travel costs. In: IEEE Symposium on Swarm Intelligence (SIS), pp. 32–39 (2013)
31.
go back to reference Toklu, N.E., Montemanni, R., Gambardella, L.M.: A robust multiple ant colony system for the capacitated vehicle routing problem. In: IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 1871–1876 (2013) Toklu, N.E., Montemanni, R., Gambardella, L.M.: A robust multiple ant colony system for the capacitated vehicle routing problem. In: IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 1871–1876 (2013)
32.
go back to reference Verweij, B., Shabbir, A., Kleywegt, A.J., Nemhauser, G., Shapiro, A.: The sample average approximation method applied to stochastic routing problems: a computational study. Comput. Optim. Appl. 24(2–3), 289–333 (2003)MathSciNetCrossRef Verweij, B., Shabbir, A., Kleywegt, A.J., Nemhauser, G., Shapiro, A.: The sample average approximation method applied to stochastic routing problems: a computational study. Comput. Optim. Appl. 24(2–3), 289–333 (2003)MathSciNetCrossRef
33.
go back to reference Waters, C.: Vehicle-scheduling problems with uncertainty and omitted customer. J. Oper. Res. Soc. 4(12), 1099–1108 (1989)CrossRef Waters, C.: Vehicle-scheduling problems with uncertainty and omitted customer. J. Oper. Res. Soc. 4(12), 1099–1108 (1989)CrossRef
35.
go back to reference Mei, Y., Tang, K., Yao, X.: Capacitated arc routing problem in uncertain environments. In: Proceedings of the 2010 IEEE Congress on Evolutionary Computation, pp. 1400–1407 (2010) Mei, Y., Tang, K., Yao, X.: Capacitated arc routing problem in uncertain environments. In: Proceedings of the 2010 IEEE Congress on Evolutionary Computation, pp. 1400–1407 (2010)
Metadata
Title
An Efficient Algorithm Based Tabu Search for the Robust Sparse CARP Under Travel Costs Uncertainty
Authors
Sara Tfaili
Abdelkader Sbihi
Adnan Yassine
Ibrahima Diarrassouba
Copyright Year
2019
DOI
https://doi.org/10.1007/978-3-030-16035-7_9

Premium Partner