Residential parcel lockers (RPLs), unlike their public counterparts, facilitate secure parcel delivery to occupants of private apartment and condominium buildings in urban areas. In this work, we consider the perspective of a last-mile parcel carrier that has access to an RPL in the lobby of a high-rise residential building. Motivated by growing e-commerce demand, we assume that the number of parcels to be delivered on a particular day exceeds the number of RPL compartments allocated to the carrier; parcels that cannot be delivered to the RPL must be delivered directly to residents’ doorsteps on upper floors of the building. Using information about the building’s floor layouts and expected elevator waiting times, we seek to optimally group the parcels into batches, determine which parcels to deliver to the RPL, and route the driver through the building to directly deliver the remaining parcels. Under mild assumptions, we first derive a polynomial-time algorithm for determining the optimal sequence of floor visits given a set of parcels designated for direct delivery. We then leverage this algorithm to develop a branch-and-price solution approach capable of solving realistically sized instances of the full problem to optimality. Additionally, we propose and analyze two intuitive heuristics that provide greater transparency and operational simplicity. Our computational experiments suggest that intelligent use of an RPL — whether via exact optimization or heuristics — can entail significant time savings both relative to myopic use of an RPL and relative to the absence of an RPL.