This paper proposes a multi-objective two-depot traveling salesman problem with uncertain fleet size (MTTSP), which determines optimal distribution route for hazardous materials (hazmat). It actually aims to identify nondominated paths from two given depots to some given destinations under the premise of minimizing the number of mix trucks, that is, deploy as few resources as possible to meet the need effectively and efficiently. An effective genetic algorithm based on ranking is then developed. In addition, a case study is carried out to demonstrate the methodology proposed in this paper.