Optimization Online


Complexity of Routing Problems with Release Dates and Deadlines

Alan Erera(alan.erera***at***isye.gatech.edu)
Damian Reyes(ldrr3***at***gatech.edu)
Martin Savelsbergh(martin.savelsbergh***at***isye.gatech.edu)

Abstract: 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).

Keywords: dynamic delivery, vehicle routing, complexity

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 06/01/2016
Entry Accepted: 06/01/2016
Entry Last Modified: 06/01/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society