Skip to main content
Top

2020 | OriginalPaper | Chapter

Modified DFA Minimization with Artificial Bee Colony Optimization in Vehicular Routing Problem with Time Windows

Authors : G. Niranjani, K. Umamaheswari

Published in: Data Management, Analytics and Innovation

Publisher: Springer Singapore

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

search-config
loading …

Abstract

A NP-hard problem, vehicular routing is a combinatorial optimization problem. Vehicular routing problem with time windows indicates vehicular routing with specified start and end time. There will be “n” number of vehicles starting from the depot to cater to the needs of “m” customers. In this paper, Gehring and Homberger benchmark problems are considered wherein the size of customers is taken to be 1000. Artificial Bee Colony Optimization algorithm is executed on these 60 datasets and the number of vehicles along with total distance covered is recorded. The modified version of Deterministic Finite Automata is applied along with the Artificial Bee Colony Optimization and the results produce 25.55% efficient routes and 15.42% efficient distance compared to simple Artificial Bee Colony Optimization algorithm.

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 Toth, P., Vigo, D.: The vehicle routing problem. In: Toth, P., Vigo, D. (eds.) SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (2001) Toth, P., Vigo, D.: The vehicle routing problem. In: Toth, P., Vigo, D. (eds.) SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (2001)
2.
go back to reference Golden, B.L., Assad, A.A., Wasil, E.A.: Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, pp. 245–286. SIAM, Philadelphia (2002)CrossRef Golden, B.L., Assad, A.A., Wasil, E.A.: Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, pp. 245–286. SIAM, Philadelphia (2002)CrossRef
3.
go back to reference Karaboga, D.: An idea based honey bee swarm for numerical optimization. Technical Report-TR06, October (2005) Karaboga, D.: An idea based honey bee swarm for numerical optimization. Technical Report-TR06, October (2005)
4.
go back to reference Karaboga, D., Basturk, B.: A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J. Global Optim. 39(3), 459–471 (2007)MathSciNetCrossRef Karaboga, D., Basturk, B.: A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J. Global Optim. 39(3), 459–471 (2007)MathSciNetCrossRef
5.
go back to reference Singh, A.: An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem. Appl. Soft Comput. 9(2), 625–631 (2009)CrossRef Singh, A.: An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem. Appl. Soft Comput. 9(2), 625–631 (2009)CrossRef
6.
go back to reference Umamaheswari, K., Sarathambekai, S.: Task scheduling in distributed systems using discrete particle swarm optimization. Int. J. Adv. Res. Comput. Sci. Softw. Eng. 4(2):510–522 (2014/2) Umamaheswari, K., Sarathambekai, S.: Task scheduling in distributed systems using discrete particle swarm optimization. Int. J. Adv. Res. Comput. Sci. Softw. Eng. 4(2):510–522 (2014/2)
7.
go back to reference Sarathambekai, S., Umamaheswari, K.: Task scheduling in distributed systems using heap intelligent discrete particle swarm optimization. J. Comput. Intell. 33(4):737–770 (2017/11)MathSciNetCrossRef Sarathambekai, S., Umamaheswari, K.: Task scheduling in distributed systems using heap intelligent discrete particle swarm optimization. J. Comput. Intell. 33(4):737–770 (2017/11)MathSciNetCrossRef
8.
go back to reference Bonabeau, E., Dorigo, M., Theraulaz, G.: Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York (1999)MATH Bonabeau, E., Dorigo, M., Theraulaz, G.: Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York (1999)MATH
10.
go back to reference Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. J. Oper. Res. Soc. Am. 12(4), 568–581 (1964) Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. J. Oper. Res. Soc. Am. 12(4), 568–581 (1964)
12.
go back to reference Bhagade, A.S., Puranik, P.V.: Artificial bee colony (abc) algorithm for vehicle routing optimization problem. Int. J. Soft Comput. Eng. (IJSCE) 2(2), 2231–2307 (2012) Bhagade, A.S., Puranik, P.V.: Artificial bee colony (abc) algorithm for vehicle routing optimization problem. Int. J. Soft Comput. Eng. (IJSCE) 2(2), 2231–2307 (2012)
14.
go back to reference Watson, B.W.: A taxonomy of finite automata minimization algorithms. Computing Science Report 93/44 Eindhoven, January 1995 (1995) Watson, B.W.: A taxonomy of finite automata minimization algorithms. Computing Science Report 93/44 Eindhoven, January 1995 (1995)
15.
go back to reference Perrin, D.: CHAPTER 1—Finite Automata Formal Models and Semantics, Handbook of Theoretical Computer Science, pp. 1–57. Elsevier, Amsterdam (1990) Perrin, D.: CHAPTER 1—Finite Automata Formal Models and Semantics, Handbook of Theoretical Computer Science, pp. 1–57. Elsevier, Amsterdam (1990)
16.
go back to reference Bulhões, S.R., Uchoa, E.: A branch-and-price algorithm for the minimum latency problem. Comput. Oper. Res. 93, 66–78 (2017)MathSciNetCrossRef Bulhões, S.R., Uchoa, E.: A branch-and-price algorithm for the minimum latency problem. Comput. Oper. Res. 93, 66–78 (2017)MathSciNetCrossRef
19.
go back to reference Matthopoulos, P.-P., Sofianopoulou, S.: A firefly algorithm for the heterogeneous fixed fleet VRP. Int. J. Ind. Syst. Eng. 33(1) (2018)CrossRef Matthopoulos, P.-P., Sofianopoulou, S.: A firefly algorithm for the heterogeneous fixed fleet VRP. Int. J. Ind. Syst. Eng. 33(1) (2018)CrossRef
20.
go back to reference Shi, Y.-J., Meng, F.-W., Shen, G.-J.: A modified artificial bee colony algorithm for vehicle routing problems with time windows. Inf. Technol. J. 11(10), 1490–1495 (2012)CrossRef Shi, Y.-J., Meng, F.-W., Shen, G.-J.: A modified artificial bee colony algorithm for vehicle routing problems with time windows. Inf. Technol. J. 11(10), 1490–1495 (2012)CrossRef
21.
go back to reference Nahum, O.E., Hadas, Y., Spiegel, U.: Multi-objective vehicle routing problems with time windows: a vector evaluated artificial bee colony approach. Int. J. Comput. Inf. Technol. 3(1), 41–47 (2014) Nahum, O.E., Hadas, Y., Spiegel, U.: Multi-objective vehicle routing problems with time windows: a vector evaluated artificial bee colony approach. Int. J. Comput. Inf. Technol. 3(1), 41–47 (2014)
22.
go back to reference Alzaqebah, M., Abdullah, S., Jawarneh, S.: Modified artificial bee colony for the vehicle routing problems with time windows. SpringerPlus 5(1), 1298 (2016)CrossRef Alzaqebah, M., Abdullah, S., Jawarneh, S.: Modified artificial bee colony for the vehicle routing problems with time windows. SpringerPlus 5(1), 1298 (2016)CrossRef
Metadata
Title
Modified DFA Minimization with Artificial Bee Colony Optimization in Vehicular Routing Problem with Time Windows
Authors
G. Niranjani
K. Umamaheswari
Copyright Year
2020
Publisher
Springer Singapore
DOI
https://doi.org/10.1007/978-981-32-9949-8_45