Consideration of risk as a criterion for selecting hazardous materials distribution routes contributes substantially to the reduction of accident probability and the severity of accident impacts. Moreover, optimum deployment of emergency response units ensures an immediate response to a hazardous materials accident and consequently contributes significantly to the reduction of accident impacts. Vehicle routing and emergency response facility location are two of the most frequently faced logistical decisions in hazardous materials distribution management and emergency response planning, respectively. In particular, hazardous materials transportation can be defined as a bi-objective vehicle routing problem with time windows since risk minimization accompanies cost minimization in the objective function. Furthermore, the emergency response unit location problem aims at locating a set of response units to minimize the total response time and distribute the emergency response workload equally among them. The complexity of these two problems causes a heavy computational burden for their solution, especially in cases of large-scale distribution networks. Two new heuristic algorithms are presented for solution of the bi-objective vehicle routing and scheduling problem and the emergency response facility location problem. The algorithm for the hazardous materials routing problem was applied to several benchmark problems and provided results superior to those of other competing algorithms. The algorithm for the emergency response problem was applied to several case studies and provided near-optimal solutions.