Waste management is a major challenge in urban areas, including in Lhokseumawe. The main problem is that the route still needs to be optimal for operating waste transportation or Vehicle Routing Problems (VRP). Metter this is because there are still obstacles in the field, including the need for more resources, the number of waste trucks, the increase in the amount of waste produced, the lack of temporary collecting points, as well as the long distances to the landfill. The proposed solution to this problem is creating a management information system integrated with web-based waste transportation in Lhokseumawe. Through this system, waste transportation can be optimized as well as provide waste management information to the public. Algorithm Simulated Annealing (SA) is an algorithm that can solve this problem VRP problem very well. Previous research has proven this algorithm better when compared to the GA algorithm in determining the optimal route, so it is hoped that it will also produce better routes determining the optimal route for transporting waste in this research. The data used in this research were taken from the Environmental Service Lhokseumawe City, Indonesia, including total waste transportation trucks, old temporary collecting points, total daily waste generation, waste volume transported per day, current transportation routes, and landfill locations. The initial condition was there are 15 temporary collecting points, 20 large trucks, and 7 small trucks in Lhokseumawe city. The results show that, it was required 17 large and 7 small waste transportation trucks. The SA calculation is carried out using parameters that have been tested to produce optimal values. The parameters used are To = 5000, α= 0,55, and T1=1. The result is that costs and travel time can be reduced by 30%, and travel distance can be reduced by 17% if compared to initial conditions.