A type of decision of major importance that directly affects the performance of a distribution system is the routing and scheduling of delivery trucks. The determination of hazardous materials distribution routes can be defined as a bi-objective vehicle routing problem with time windows since risk minimization accompanies the cost minimization in the objective function. The objective of this paper is to present a new heuristic algorithm for solving the bi-objective vehicle routing and scheduling problem. The proposed algorithm has been applied to several benchmark problems. The results of these applications seem to be quite encouraging. Furthermore, the proposed algorithm has been integrated within a GIS based decision support system for hazardous materials logistics operations providing valid preliminary results on a set of case studies.