We study the Pickup and Delivery Problem with Time Windows and Last-in-First-out Loading (PDPTWL), a decision-making problem that aims at minimizing the cost to serve a set of customers (consisting of pickup and delivery locations) within their time windows, using a fleet of capacitated vehicles and handling their loads with a Last-in-First-out policy. We propose a bounding procedure based on column generation to find tight dual bounds to the PDPTWL by solving the linear relaxation of a set partitioning formulation, where variables correspond to (non-necessarily elementary) routes. We consider a set of benchmark instances from the literature to show that these dual bounds are tight and can be computed in a few seconds. Therefore, the bounding procedure can be a building block of an exact method for the PDPTWL.