Optimally solving a versatile Traveling Salesman Problem on tree networks with soft due dates and multiple congestion scenarios

Stefan Bock ()

European Journal of Operational Research, 2020, vol. 283, issue 3, 863-882

Abstract: This paper considers a versatile Traveling Salesman Problem (TSP) on tree networks with soft due date restrictions. Data unreliability is handled by introducing multiple congestion scenarios. The objective function sums up customizable monotonous cost assessments of the scenario-dependent total tardiness. Due to its generality, this covers a versatile application of different concepts including several robustness issues. Various complexity results are derived for the minimization of total tardiness: While the problem is proven to be at least binary NP-hard in all cases, strongly NP-hardness is shown if either the number of congestion scenarios or the number of roads are allowed to increase linearly with the number of requests. The same applies if non-zero unloading times occur. In order to efficiently solve the problem, a best-first Branch&Bound approach is proposed that attains a pseudo-polynomial running time if none of the three aforementioned cases applies. The Branch&Bound approach is evaluated by a computational study.

Keywords: Scheduling; Versatile TSP approach; Multiple scenarios; Complexity analysis; Branch&Bound (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719309701
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:283:y:2020:i:3:p:863-882

DOI: 10.1016/j.ejor.2019.11.058

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 ().