A Max-Min Ant System Applied to The Vehicle Routing Problems

บทคัดย่อ

Abstract

This work introduces a modified MAX-MIN Ant System (MMAS) algorithm to solve the Vehicle Routing problem (VRP), in which customers of known demand are supplied from a single depot. Vehicle Routing Problem is an NP-complete optimization problem and has usually been solved to nearly optimum by heuristics. The objective of VRP is to use a fleet of vehicles with specified capacity to serve a number of customers with dissimilar demands at minimum cost, without violating the capacity and route length constraints. Many meta-heuristic approaches like Simulated Annealing (ร A), Genetic Algorithm (GA), Tabu Search (TS) and An Improved Ant Colony System (IACS) algorithm. In this research, we proposed a Max-Min Ant System algorithm with local search approaches. Experiments on various aspects of 14 problem benchmark problems are other meta-heuristic and show that our results are competitive.

Keywords : Vehicle routing problem; Combinatorial optimization; Meta-heuristic; Ant Colony Optimization; Max-Min Ant System