 Complexity of routing problems with release dates and deadlinesDamián Reyes, Alan L. Erera and Martin W.P. Savelsbergh European Journal of Operational Research, 2018, vol. 266, issue 1, 29-34 Abstract: 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). Keywords: Routing; Dynamic delivery; Release dates and deadlines; Computational complexity; Dynamic programming (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:266:y:2018:i:1:p:29-34 DOI: 10.1016/j.ejor.2017.09.020 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.