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

Article Sidebar

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

Main Article Content

Suphan Sodsoon
1Industrial Technology Rajamangala University of Technology Isan., Kasetsomboon Rd. Muang Kalasin, Thailand 46000 Tel: 0-4381-1128 Fax: 0-4381-3170 Email: suphan_sodsoon@hotmail.com
Sombut Sindhuchao
ndustrial Engineering, Ubonratchathani University., 85 Sathollmark Rd. Warinchamrap Ubonratchathani, Thailand 34190 Tel: 0-4528-8400-3 Fax: 0-4528-8378 Email: somsin@rocketmail.com

Abstract

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

Article Details

How to Cite
[1]
S. Sodsoon and S. Sindhuchao, “A Max-Min Ant System Applied to The Vehicle Routing Problems”, RMUTI Journal, vol. 2, no. 1, pp. 39–47, Jan. 2014.
Issue
Vol. 2 No. 1 (2009): January-June
Section
Research article