In addition to the increasing population and rapid urbanization, the amount and variety of medical waste are rapidly increasing due to the coronavirus disease (COVID-19) pandemic affecting the whole world. COVID-19 does not only increase the amount of medical waste produced, medical wastes generated in the care of COVID-19 carries a high risk of transmission as well. In this regard, the safe and effective management of medical wastes has become a serious health and safety issue. This research aims to determine the safest and shortest transportation routes for medical waste vehicles. The safety scores used in this study were obtained in our previous study. The resulting safety scores were used in a multi-objective traveling salesman problem for deriving two objective functions, which are based on safety scores and total transportation distance. A conciliating solution was obtained by solving this linear programming model. The proposed model faced by health institutions in Istanbul has been applied for a specific district. According to the obtained results, suggestions for the direction of medical waste vehicles have been proposed.