nach oben

Cluster Computing

Erschienen in:

17.02.2018

Improved tabu search algorithm for the open vehicle routing problem with soft time windows and satisfaction rate

verfasst von: Yangkun Xia, Zhuo Fu

Erschienen in: Cluster Computing | Sonderheft 4/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The open vehicle routing problem (OVRP) has a wide range of applications in the field of logistics distribution. A model of OVRP with soft time windows and satisfaction rate is analyzed here in order to reduce the logistics distribution cost. The minimization of the number of vehicles required is taken as the primary objective, while the minimization of the traveling distance cost and the deviation cost of the time windows are used as secondary objectives. A corresponding mathematical model with bi-objective programming is established for the problem. Based on the coding rules of natural numbers, several strategies such as the adaptive penalty mechanism, multi-neighborhood structure and re-initialization rule are embedded in the tabu search algorithm (TSA), resulting in an improved TSA (ITSA). Computational results are provided and these are compared with other methods in the literature, demonstrating the effectiveness of the ITSA.

Vorheriger Artikel A novel energy efficient and scalable hybrid-mac protocol for massive M2M networks

Nächster Artikel RETRACTED ARTICLE: Numerical simulation of twin-barge float-over installation on AQWA software

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

Barkaoui, M., Berger, J., Boukhtouta, A.: Customer satisfaction in dynamic vehicle routing problem with time windows. Appl. Soft Comput. 35, 423–432 (2015)CrossRef

Lai, M., Tong, X.: A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. J. Ind. Manag. Optim. 8(2), 469–484 (2017)MathSciNetCrossRef

Sariklis, D., Powell, S.: A heuristic method for the open vehicle routing problem. J. Oper. Res. Soc. 51(5), 564–573 (2000)CrossRef

Fu, Z., Eglese, R., Li, L.Y.O.: A new tabu search heuristic for the open vehicle routing problem. J. Oper. Res. Soc. 56(3), 267–274 (2005)CrossRef

Tarantilis, C., Diakoulaki, D., Kiranoudis, C.T.: Combination of geographical information system and efficient routing algorithms for real life distribution operations. Eur. J. Oper. Res. 152(2), 437–453 (2004)CrossRef

Repoussis, P.P., Tarantilis, C.D., Ioannou, G.: The open vehicle routing problem with time windows. J. Oper. Res. Soc. 58(3), 355–367 (2007)CrossRef

Li, S.B., Wang, L.M.: Multi-start tabu search algorithm for solving OVRPTW. Comput. Eng. 37(6), 187–189 (2011). https://doi.org/10.3969/j.issn.1000-3428.2011.06.064 CrossRef

Xiao, T.G., Fu, Z.: A genetic algorithm for the open vehicle routing problem with soft time windows. J. Railw. Sci. Eng. 5(2), 79–83 (2008)

Duan, F.H.: OVRPSTW and its improved genetic algorithm. Advanced Technology in Teaching: Proceedings of the 2009 3rd International Conference on Teaching and Computational Science (WTCS 2009), Springer Berlin Heidelberg, 117, 249–255 (2012)

10.

Shi, Y., Boudouh, T., Grunder, O.: A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand. Expert Syst. Appl. 72, 160–176 (2017)CrossRef

11.

Fu, Z., Eglese, R., Li, L.Y.O.: A unified tabu search algorithm for vehicle routing problems with soft time windows. J. Oper. Res. Soc. 59(5), 663–673 (2008)CrossRef

12.

Belfiore, P., Yoshizaki, H.T.Y.: Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries. Comput. Ind. Eng. 64(2), 589–601 (2013)CrossRef

13.

Xia, Y.K., Fu, Z., Xie, J.Y.: Material distribution route planning for multiple automated guided vehicles with split deliveries by order. Comput. Integr. Manuf. Syst. 23(7), 1520–1528 (2017). https://doi.org/10.13196/j.cims.2017.07.017 CrossRef

14.

Nishi, T., Izuno, T.: Column generation heuristics for ship routing and scheduling problems in crude oil transportation with split deliveries. Comput. Chem. Eng. 60(2), 329–338 (2014)CrossRef

15.

Lai, M., Battarra, M., Francesco, M.D., et al.: An adaptive guidance meta-heuristic for vehicle routing problem with splits and clustered backhauls. J. Oper. Res. Soc. 66(7), 1222–1236 (2015)CrossRef

16.

Ghannadpour, S.F., Noori, S., Tavakkoli-Moghaddam, R.: Multi objective dynamic vehicle routing problem with fuzzy travel times and customers’ satisfaction in supply chain management. IEEE Trans. Eng. Manag. 60(4), 777–790 (2013)CrossRef

17.

Solomon, M.M.: Algorithms for vehicle routing problem and scheduling problem with time windows constraints. Oper. Res. 35(2), 254–265 (1987)MathSciNetCrossRef

18.

Accorsi, R., Gallo, A., Manzini, R.: A climate driven decision-support model for the distribution of perishable products. J. Clean. Prod. 165, 917–929 (2017)CrossRef

19.

Brito, J., Martinez, F.J., Moreno, J.A., et al.: An ACO hybrid metaheuristic for close-open vehicle routing problems with time windows and fuzzy constraints. Appl. Soft Comput. 32, 154–163 (2015)CrossRef

20.

Quintero-Araujo, C.L., Caballero-Villalobos, J.P., Juan, A.A., et al.: A biased-randomized metaheuristic for the capacitated location routing problem. Int. Trans. Oper. Res. 24(5), 1079–1098 (2017)MathSciNetCrossRef

21.

Bae, J., Chung, W.: A heuristic for a heterogeneous automated guided vehicle routing problem. Int. J. Precis. Eng. Manuf. 18(6), 795–801 (2017)CrossRef

22.

Fu, Z., Liu, W., Qiu, M.: A tabu search algorithm for the vehicle routing problem with soft time windows and split deliveries by order. Chin. J. Manag. Sci. 25(5), 78–86 (2017). https://doi.org/10.16381/j.cnki.issn1003-207x.2017.05.010 CrossRef

23.

Syslo, M., Deo, N., Kowalski, J.: Discrete Optimization Algorithms with Pascal Programs. Prentice Hall, New Tork (1983)MATH

24.

Wang, J.Y., Xu, H.C.: Transportation route optimization with cost object in China. Clust. Comput. 19(3), 1489–1501 (2016)CrossRef

25.

Wei, M., Sun, B.: Bi-level programming model for multi-modal regional bus timetable and vehicle dispatch with stochastic travel time. Clust. Comput. 20(1), 401–411 (2017)MathSciNetCrossRef

Titel: Improved tabu search algorithm for the open vehicle routing problem with soft time windows and satisfaction rate
verfasst von: Yangkun Xia
Zhuo Fu
Publikationsdatum: 17.02.2018
Verlag: Springer US
Erschienen in: Cluster Computing / Ausgabe Sonderheft 4/2019
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-018-1957-x

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"

Weitere Artikel der Sonderheft 4/2019

An on-line detection method for outliers of dynamic unstable measurement data

Non-contact detection of human heart rate with Kinect

Remote sensing image land type data mining based on QUEST decision tree

Mutual information of massive MIMO systems on block Rayleigh-faded channels

Development of vegetable intelligent farming device based on mobile APP

Cost-effectiveness analysis and evaluation of a ‘three-old’ reconstruction project based on smart system