In this paper, optimum routing was developed based on the travel salesman method and integrated in ArcInfo GIS using linear programming. The results of the optimized travel distances and times for residential waste collection and routing to disposal site were used to calculate the number and type of required track collection, labour requirement, costing of waste collection and to determine the overall solid waste management efficiency through waste management operation research methods. The objective of the study was to optimize residential collection and hauling to disposal site through operation cost minimization for Petaling Jaya Municipality in the state of Selangor, Malaysia. The study determined that with optimized routes and recycling possibilities, the total cost of waste collections could be reduced from RM90,372 to RM20,967, with a reduction of 76.8%. It was also revealed that optimum routes might not necessarily be the shortest distance from point A to point B as travel time maybe high on short distances due to traffic congestion and the presence of many traffic lights. Techniques and methods developed using general GIS have proven effective in route optimization and allowed management of data to suit local conditions and limitations of waste management for the studied area. Thus, scenarios of travel distances, time and waste quantity value generated from the GIS enabled appropriate determination of the number of waste trucks and labour requirements for the operation and the overall calculation of costs of waste management based on the operation research methods used in the study.