Mobile ad hoc network (MANET) is a decentralized, multi-hop, and dynamic network with least infrastructure. Therefore, it is necessary that they should be self organizing, self healing, self configuring and adaptable to frequent changes in network. Ant Colony Optimization presents a problem-solving paradigm that suits the dynamicity and mobility of mobile ad hoc networks. In this paper we propose a new routing algorithm AntHocNet-LS(equipped with Location Service) inspired from AntHocNet which rely on simple mobile agents and their collective intelligence for the task of routing. The algorithm performs better in major performance parameters such as packet delivery ratio and control overhead.