Skip to main content
Top
Published in: Wireless Personal Communications 1/2018

05-02-2018

An Adaptive Tabu Search Algorithm for the Open Vehicle Routing Problem with Split Deliveries by Order

Authors: Yangkun Xia, Zhuo Fu

Published in: Wireless Personal Communications | Issue 1/2018

Log in

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

search-config
loading …

Abstract

In order to reduce the cost of logistics distribution, a capacitated open vehicle routing problem with split deliveries by order is studied. According to the actual situation of split deliveries by order in the practice of logistics distribution, the condition of non-split in the traditional open vehicle routing problem is relaxed, and a new form of discrete split deliveries by order is designed. Based on the classical model of open vehicle routing problem, a corresponding double objective mathematical model with split deliveries by order is established, and an adaptive tabu search algorithm is designed to solve the problem. In order to improve the optimization performance, an adaptive penalty mechanism is designed, a multiple neighborhood structure is constructed, and the tabu list is reinitialized. The comparison with other methods in the literature shows the effectiveness of the algorithm.

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

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+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 "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
2.
go back to reference Pu, E., Wang, F., Yang, Z. L., et al. (2017). Hybrid differential evolution optimization for the vehicle routing problem with time windows and driver-specific times. Wireless Personal Communications, 95(3), 2345–2357.CrossRef Pu, E., Wang, F., Yang, Z. L., et al. (2017). Hybrid differential evolution optimization for the vehicle routing problem with time windows and driver-specific times. Wireless Personal Communications, 95(3), 2345–2357.CrossRef
3.
go back to reference Han, F. W., & Chu, Y. C. (2016). A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts. Transportation Research Part E Logistics & Transportation Review., 88, 11–31.CrossRef Han, F. W., & Chu, Y. C. (2016). A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts. Transportation Research Part E Logistics & Transportation Review., 88, 11–31.CrossRef
4.
go back to reference Fu, Z., Eglese, R., & Li, L. Y. O. (2005). A new tabu search heuristic for the open vehicle routing problem. Journal of the Operational Research Society, 56(3), 267–274.CrossRef Fu, Z., Eglese, R., & Li, L. Y. O. (2005). A new tabu search heuristic for the open vehicle routing problem. Journal of the Operational Research Society, 56(3), 267–274.CrossRef
6.
go back to reference Dror, M., & Trudeau, P. (2006). Savings by split delivery routing. Transportation Science, 23(2), 141–145.CrossRef Dror, M., & Trudeau, P. (2006). Savings by split delivery routing. Transportation Science, 23(2), 141–145.CrossRef
7.
go back to reference Archetti, C., Hertz, A., & Speranza, M. G. (2006). A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science, 40(1), 64–73.CrossRef Archetti, C., Hertz, A., & Speranza, M. G. (2006). A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science, 40(1), 64–73.CrossRef
8.
go back to reference Fu, Z., Eglese, R., & Li, L. Y. O. (2008). A unified tabu search algorithm for vehicle routing problems with soft time windows. Journal of the Operational Research Society, 59(5), 663–673.CrossRef Fu, Z., Eglese, R., & Li, L. Y. O. (2008). A unified tabu search algorithm for vehicle routing problems with soft time windows. Journal of the Operational Research Society, 59(5), 663–673.CrossRef
9.
go back to reference Archetti, C., Bianchessi, N., & Speranza, M. G. (2014). Branch-and-cut algorithms for the split delivery vehicle routing problem. European Journal of Operational Research, 238(3), 685–698.MathSciNetCrossRef Archetti, C., Bianchessi, N., & Speranza, M. G. (2014). Branch-and-cut algorithms for the split delivery vehicle routing problem. European Journal of Operational Research, 238(3), 685–698.MathSciNetCrossRef
10.
go back to reference Sariklis, D., & Powell, S. A. (2000). A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society, 51(5), 564–573.CrossRef Sariklis, D., & Powell, S. A. (2000). A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society, 51(5), 564–573.CrossRef
11.
go back to reference Tarantilis, C. D., Diakoulaki, D., & Kiranoudis, C. T. (2004). Combination of geographical information system and efficient routing algorithms for real life distribution operations. European Journal of Operational Research, 152(2), 437–453.CrossRef Tarantilis, C. D., Diakoulaki, D., & Kiranoudis, C. T. (2004). Combination of geographical information system and efficient routing algorithms for real life distribution operations. European Journal of Operational Research, 152(2), 437–453.CrossRef
12.
go back to reference Tarantilis, C. D., Ioannou, G., Kiranoudis, C. T., et al. (2004). A threshold accepting approach to the open vehicle routing problem. Rairo Operations Research., 38(4), 345–360.MathSciNetCrossRef Tarantilis, C. D., Ioannou, G., Kiranoudis, C. T., et al. (2004). A threshold accepting approach to the open vehicle routing problem. Rairo Operations Research., 38(4), 345–360.MathSciNetCrossRef
13.
go back to reference Tarantilis, C. D., Ioannou, G., Kiranoudis, C. T., et al. (2005). Solving the open vehicle routing problem via a single parameter metaheuristic algorithm. The Journal of Operational Research Society, 56(5), 588–596.CrossRef Tarantilis, C. D., Ioannou, G., Kiranoudis, C. T., et al. (2005). Solving the open vehicle routing problem via a single parameter metaheuristic algorithm. The Journal of Operational Research Society, 56(5), 588–596.CrossRef
14.
go back to reference Joseph, I. V., & Cavalier, T. M. (2012). A Genetic algorithm for the split delivery vehicle routing problem. American Journal of Operations Research, 2(2), 207–216.CrossRef Joseph, I. V., & Cavalier, T. M. (2012). A Genetic algorithm for the split delivery vehicle routing problem. American Journal of Operations Research, 2(2), 207–216.CrossRef
15.
go back to reference Berbotto, L., Garcia, S., & Nogales, F. J. (2014). A randomized granular tabu search heuristic for the split delivery vehicle routing problem. Annals of Operations Research, 222(1), 153–173.MathSciNetCrossRef Berbotto, L., Garcia, S., & Nogales, F. J. (2014). A randomized granular tabu search heuristic for the split delivery vehicle routing problem. Annals of Operations Research, 222(1), 153–173.MathSciNetCrossRef
18.
go back to reference Salani, M., & Vacca, I. (2011). Branch and price for the vehicle routing problem with discrete split deliveries and time windows. European Journal of Operational Research, 213(3), 470–477.MathSciNetCrossRef Salani, M., & Vacca, I. (2011). Branch and price for the vehicle routing problem with discrete split deliveries and time windows. European Journal of Operational Research, 213(3), 470–477.MathSciNetCrossRef
19.
go back to reference Syslo, M., Deo, N., & Kowalski, J. S. (1983). Discrete optimization algorithms with pascal programs. New Jersey: Prentice Hall Inc.MATH Syslo, M., Deo, N., & Kowalski, J. S. (1983). Discrete optimization algorithms with pascal programs. New Jersey: Prentice Hall Inc.MATH
20.
go back to reference Btandao, J. (2004). A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research, 157(3), 552–564.MathSciNetCrossRef Btandao, J. (2004). A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research, 157(3), 552–564.MathSciNetCrossRef
21.
go back to reference Wang, X., Golden, B., & Gulczynski, D. (2014). A worst-case analysis for the split delivery capacitated team orienteering problem with minimum delivery amounts. Optimization Letters, 8(8), 2349–2356.MathSciNetCrossRef Wang, X., Golden, B., & Gulczynski, D. (2014). A worst-case analysis for the split delivery capacitated team orienteering problem with minimum delivery amounts. Optimization Letters, 8(8), 2349–2356.MathSciNetCrossRef
22.
go back to reference Lai, M., Battarra, M., Francesco, M. D., et al. (2015). An adaptive guidance meta-heuristic for vehicle routing problem with splits and clustered backhauls. Journal of the Operational Research Society, 66(7), 1222–1236.CrossRef Lai, M., Battarra, M., Francesco, M. D., et al. (2015). An adaptive guidance meta-heuristic for vehicle routing problem with splits and clustered backhauls. Journal of the Operational Research Society, 66(7), 1222–1236.CrossRef
23.
go back to reference Yao, B., Yu, B., Hu, P., et al. (2016). An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot. Annals of Operations Research, 242(2), 1–18.MathSciNetCrossRef Yao, B., Yu, B., Hu, P., et al. (2016). An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot. Annals of Operations Research, 242(2), 1–18.MathSciNetCrossRef
25.
go back to reference Brito, J., Martinez, F. J., Moreno, J. A., et al. (2015). An ACO hybrid metaheuristic for close-open vehicle routing problems with time windows and fuzzy constraints. Applied Soft Computing, 32, 154–163.CrossRef Brito, J., Martinez, F. J., Moreno, J. A., et al. (2015). An ACO hybrid metaheuristic for close-open vehicle routing problems with time windows and fuzzy constraints. Applied Soft Computing, 32, 154–163.CrossRef
26.
go back to reference Wang, Y., Ma, X. L., Lao, Y. T., et al. (2014). A fuzzy-based customer clustering approach with hierarchical structure for logistics network optimization. Expert Systems with Applications, 41(2), 521–534.CrossRef Wang, Y., Ma, X. L., Lao, Y. T., et al. (2014). A fuzzy-based customer clustering approach with hierarchical structure for logistics network optimization. Expert Systems with Applications, 41(2), 521–534.CrossRef
27.
go back to reference Wang, Y., Ma, X. L., Xu, M. Z., et al. (2015). Two-echelon logistics distribution region partitioning problem based on a hybrid particle swarm optimization-genetic algorithm. Expert Systems with Applications, 42(12), 5019–5031.CrossRef Wang, Y., Ma, X. L., Xu, M. Z., et al. (2015). Two-echelon logistics distribution region partitioning problem based on a hybrid particle swarm optimization-genetic algorithm. Expert Systems with Applications, 42(12), 5019–5031.CrossRef
28.
go back to reference Alemayehu, T. S., & Kim, J. H. (2017). Efficient nearest neighbor heuristic TSP algorithms for reducing data acquisition latency of UAV relay WSN. Wireless Personal Communications, 95(3), 3271–3285.CrossRef Alemayehu, T. S., & Kim, J. H. (2017). Efficient nearest neighbor heuristic TSP algorithms for reducing data acquisition latency of UAV relay WSN. Wireless Personal Communications, 95(3), 3271–3285.CrossRef
29.
go back to reference Rabik, M. M., & Balasubada, K. (2017). Distributive aware probabilistic back propagation (DAPBP) routing scheme for vehicular networks. Wireless Personal Communications, 97(1), 483–493.CrossRef Rabik, M. M., & Balasubada, K. (2017). Distributive aware probabilistic back propagation (DAPBP) routing scheme for vehicular networks. Wireless Personal Communications, 97(1), 483–493.CrossRef
Metadata
Title
An Adaptive Tabu Search Algorithm for the Open Vehicle Routing Problem with Split Deliveries by Order
Authors
Yangkun Xia
Zhuo Fu
Publication date
05-02-2018
Publisher
Springer US
Published in
Wireless Personal Communications / Issue 1/2018
Print ISSN: 0929-6212
Electronic ISSN: 1572-834X
DOI
https://doi.org/10.1007/s11277-018-5464-4

Other articles of this Issue 1/2018

Wireless Personal Communications 1/2018 Go to the issue