This paper addresses a rollon–rolloff waste collection vehicle routing problem which involves large containers that collect huge amounts of waste from construction sites and shopping malls. In this problem, vehicles could only move one container at a time between customers’ locations, a depot, a disposal center, and a recycling center site. Other than a disposal center, a recycling center site is also added to the collection network based on which 10 trip types are defined. The problem aims to determine the optimal routes for minimizing the total distance traveled by vehicles resulting in a decrease in service time and cost. An initial solution is first generated by a heuristic algorithm and then, a hybrid meta-heuristic solution involving simulated annealing (SA) algorithm and hybrid SA and local search algorithm is proposed to tackle the problem. The data of the problem which is categorized into 12 classes are first generated randomly. Then, a straightforward solution representation is presented to encode the problem. The final generated results, the degree of their improvement and their computation time are compared with each other. Finally, conclusion remarks and future research directions are provided