Post box collection constitutes a complex and costly operation in most postal services. The authors recently undertook a study aimed at improving this operation at the Canada Post Corporation. This paper describes an improvement to the clustering and routing algorithm currently in use. It is based on the exact solution of a generalized version of the travelling salesman problem in the last phase of the routing algorithm. The results obtained so far indicate that significant savings can be achieved.