The Daily Drayage Problem with Time Windows can be seen as a generalization of the Pickup and Delivery Problem with Time Windows (PDPTW). In our problem, in addition to traditional PDP constraints for picking and delivering containers, we should satisfy a precedence constraint between two interrelated requests by introducing a minimum time-lag constraint between some pairs of pickup and delivery requests. Our problem is formulated as a PDPTW with precedence constraints between requests and heterogeneous fleet of vehicles and containers. In order to solve the problem efficiently, we develop a Large Neighborhood Search (LNS) heuristic. LNS heuristics are mainly based on destroy and repair operators that consist in removing and inserting a set of requests in an iterative schema. In our problem, routes are strongly interdependent due to interrelated requests. It is import to check quickly if inserting a request into a partial solution is feasible or not. In this work, we present an approach to check the feasibility of request insertion in constant time.