A Bio-Inspired Capacitated Vehicle-Routing Problem Scheme Using Artificial Bee Colony with Crossover Optimizations

Chatchai Punriboon¹, Chakchai So-In¹⁺, Phet Aimtongkham¹, and Kanokmon Rujirakul²

¹Applied Network Technology (ANT) Laboratory, Department of Computer Science, Faculty of Science, Khon Kaen University, Khon Kaen, 40002, Thailand

²Business Computer, Faculty of Management Science, Nakhon Ratchasima Rajabhat University, 30000, Thailand

Abstract

The capacitated vehicle-routing problem (CVRP) is considered one of the descendants of the traditional vehicle-routing problem (VRP) based on the consideration of capital gains in logistics and supply chains. Similar to VRP, CVRP is an NP-Hard problem; finding the optimal solution is difficult, especially with large amounts of data. In other words, the problem cannot be solved using a traditional approach because of the high cost of such an approach, i.e., high computational time. Thus, this research considers the possibility of integrating a variety of crossover methodologies into an artificial bee colony (ABC) as a heuristic approach to identifying a candidate for a CVRP solver. The research also optimizes ABC to obtain a better solution, rapidly, given time constraint, considering the effectiveness of randomness and precision enhancements related to both the crossover route and path diversity. The practicality of the proposal was evaluated by pitting fourteen well-known datasets against a traditional method, including other state-of-the-art CVRP heuristic solutions, and the performance improvement was confirmed in terms of both accuracy (i.e., finding the best solution) and the computational time as tradeoff.

Keywords: Artificial Bee Colony, Bio-inspired, Capacitated Vehicle Routing Problem, Crossover.

+: Corresponding author: Chakchai So-In

Applied Network Technology (ANT) Laboratory, Department of Computer Science, Faculty of Science, Khon Kaen University, Khon Kaen, 40002, Thailand, Email: chakso@kku.ac.th, Tel: +66-430-09700

Journal of Internet Services and Information Security (JISIS), 9(3): 21-40, August 2019

DOI: 10.22667/JISIS.2019.08.31.021 [pdf]