Complexity of routing problems with release dates and deadlines

The desire of companies to offer same-day delivery leads to interesting new routing optimization problems. We study the complexity of single depot dispatching problems in which a delivery to a customer must occur within a pre-specified time after the customer places the order. Thus, each order has a release date (when the order can be dispatched from the depot) and a service guarantee that implies a deadline (when the order needs to be delivered). A vehicle delivering an order cannot depart the depot before the order is released, and must arrive at the customer at or before the order's deadline. We show that single and multiple vehicle variants where customers are located on a half-line can be solved to optimality in polynomial time. This setting, as well as our results, generalize those found in Archetti, Feillet, and Speranza (2015).