Finding optimal tour schedules on transportation paths under extended time window constraints

Stefan Bock ()

Journal of Scheduling, 2016, vol. 19, issue 5, No 2, 527-546

Abstract: Abstract This paper addresses time-critical routing on a given path under release dates and deadline restrictions, while the minimization of the total weighted completion time is pursued. Since there may be destinations with flexible picking area resources that enable a delivery of goods before the defined release date at no additional costs, the well-known Line-Traveling Repairman problem (Line-TRPTW) is extended into the Line-TRPeTW. The Line-TRPeTW has various practical applications, such as, for example, the tour planning of an inland container ship along a river or that of a vehicle along a coastline. Although the feasibility variant of the Line-TRPTW/Line-TRPeTW is known to be strongly $${\mathcal {NP}}$$ NP -hard, a first practically applicable Branch&Bound procedure is generated. By making use of different dominance rules and lower bounds, a comprehensive computational study proves that instances comprising up to 200 requests and locations are solved to optimality in reasonable time. Moreover, the paper analyzes the complexity of the simpler variant with relaxed release dates at all customer locations. This relaxed variant provides tight lower bounds. Furthermore, the complexity analysis shows that the relaxed problem variant is binary $${\mathcal {NP}}$$ NP -hard even if deadlines are ignored, but can be efficiently solved by a specific Dynamic Programming approach that runs in pseudo-polynomial time.

Keywords: Optimal tours on given transportation paths; Extended release date restrictions; Line-TRP with extended time windows; Complexity analysis; Branch&Bound (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-016-0481-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:19:y:2016:i:5:d:10.1007_s10951-016-0481-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-016-0481-1

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().