nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

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

verfasst von : Sara Tfaili, Abdelkader Sbihi, Adnan Yassine, Ibrahima Diarrassouba

Erschienen in: Operations Research and Enterprise Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel An Efficient Application of Goal Programming to Tackle Multiobjective Problems with Recurring Fitness Landscapes

Nächstes Kapitel Optimal Air-Cargo Allotment Contract with Multiple Freight Forwarders

Á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

Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)CrossRef

Bertsimas, D.: Probabilistic combinatorial optimization problems. Ph.D. thesis Massachusetts Institute of Technology, Dept. of Mathematics (1988)

Bertsimas, D.: A vehicle routing problem with stochastic demand. Oper. Res. 40(3), 574–585 (1992)MathSciNetCrossRef

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., Sim, M.: Robust discrete optimization and network flows. Math. Program. 98, 49–71 (2003)MathSciNetCrossRef

National Center for Biotechnology Information. http://www.ncbi.nlm.nih.gov

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

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)

11.

Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6(1), 80–91 (1959)MathSciNetCrossRef

12.

Fleury, G., Lacomme, P., Prins, C.: Evolutionary algorithms for stochastic arc routing problems. In: Raidl, G.R., et al. (eds.) EvoWorkshops 2004. LNCS, vol. 3005, pp. 501–512. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24653-4_51CrossRef

13.

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.

Kasperski, A., Zieliński, P.: On the approximability of robust spanning tree problems. Theoret. Comput. Sci. 412(4–5), 365–374 (2011)MathSciNetCrossRef

15.

Kenyon, A.S., Morton, D.: Stochastic vehicle routing with random travel times. Transp. Sci. 37(1), 69–82 (2003)CrossRef

16.

Kouvelis, P., Yu, G.: Robust Discrete Optimization and its Applications. Kluwer Academic Publishers, Norwell (1997)CrossRef

17.

Laporte, G., Louveaux, F., Mercure, H.: The vehicle routing problem with stochastic travel times. Transp. Sci. 26(3), 161–170 (1992)CrossRef

18.

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.

Mattia, S.: The robust network loading problem with dynamic routing. Comput. Optim. Appl. 54(3), 619–643 (2013)MathSciNetCrossRef

20.

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.

Monaci, M., Pferschy, U., Serafini, P.: Exact solution of the robust knapsack problem. Comput. Oper. Res. 40(11), 2625–2631 (2013)MathSciNetCrossRef

22.

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.

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.

Secomandi, N., Margot, F.: Reoptimization approaches for the vehicle-routing problem with stochastic demands. Oper. Res. 57(1), 214–230 (2009)CrossRef

25.

Shapiro, A., Dentcheva, S., Ruszczyński, A.: Lectures on Stochastic Programming: Modeling and Theory, vol. 9 (2008)

26.

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.

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.

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.

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.

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.

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.

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.

Waters, C.: Vehicle-scheduling problems with uncertainty and omitted customer. J. Oper. Res. Soc. 4(12), 1099–1108 (1989)CrossRef

34.

Wets, R.J.B.: Stochastic programming models: wait-and-see versus here-and-now. In: Greengard, C., Ruszczynski, A. (eds.) Decision Making Under Uncertainty. The IMA Volumes in Mathematics and its Applications, vol. 128, pp. 1–15. Springer, New York (2002). https://doi.org/10.1007/978-1-4684-9256-9_1CrossRef

35.

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)

Titel: An Efficient Algorithm Based Tabu Search for the Robust Sparse CARP Under Travel Costs Uncertainty
verfasst von: Sara Tfaili
Abdelkader Sbihi
Adnan Yassine
Ibrahima Diarrassouba
Verlag: Springer International Publishing
Buch: Operations Research and Enterprise Systems
Print ISBN: 978-3-030-16034-0

Electronic ISBN: 978-3-030-16035-7

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-16035-7_9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner