Volume 9 - Issue 3
A Bio-Inspired Capacitated Vehicle-Routing Problem Scheme Using Artificial Bee Colony with Crossover Optimizations
- Chatchai Punriboon
Applied Network Technology (ANT) Laboratory, Department of Computer Science, Faculty of Science, Khon Kaen University, Khon Kaen, 40002, Thailand
- Chakchai So-In
Applied Network Technology (ANT) Laboratory, Department of Computer Science, Faculty of Science, Khon Kaen University, Khon Kaen, 40002, Thailand
chakso@kku.ac.th
- Phet Aimtongkham
Applied Network Technology (ANT) Laboratory, Department of Computer Science, Faculty of Science, Khon Kaen University, Khon Kaen, 40002, Thailand
- Kanokmon Rujirakul
Business Computer, Faculty of Management Science, Nakhon Ratchasima Rajabhat University, 30000, Thailand
Keywords: Artificial Bee Colony, Bio-inspired, Capacitated Vehicle Routing Problem, Crossover
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.