The desire of companies to offer same-day delivery leads to interesting new routing problems. We study the complexity of a setting in which a delivery to a customer is guaranteed to take place within a pre-specified time after the customer places the order. Thus, an order has a release date (when the order is placed) and a deadline (when the order needs to be delivered). A vehicle delivering an order cannot depart the depot before the order is released and has to arrive at the customer at or before the order’s deadline. We show that the variant with a single delivery vehicle and customer locations on a half-line can be solved in polynomial time. This setting as well as our results generalize those found in Archetti et al. (2015).