Complexity of routing problems with release dates

Claudia Archetti, Dominique Feillet and M. Grazia Speranza

European Journal of Operational Research, 2015, vol. 247, issue 3, 797-803

Abstract: In this paper we consider a routing problem where uncapacitated vehicles are loaded with goods, requested by the customers, that arrive at the depot over time. The arrival time of a product at the depot is called its release date. We consider two variants of the problem. In the first one a deadline to complete the distribution is given and the total distance traveled is minimized. In the second variant no deadline is given and the total time needed to complete the distribution is minimized. While both variants are in general NP-hard, we show that they can be solved in polynomial time if the underlying graph has a special structure.

Keywords: Vehicle routing; Release dates; Computational complexity (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715005901
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:247:y:2015:i:3:p:797-803

DOI: 10.1016/j.ejor.2015.06.057

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
Bibliographic data for series maintained by Catherine Liu ().