Paper Info
Title
Are Stacker Crane Problems easy? A statistical study
Abstract
Many full truckload pick-up and delivery problems in the intermodal freight container transport industry can be modeled as Asymmetric Traveling Salesman Problems (ATSPs). Several authors have noted that while ATSPs are NP-hard, some instances are readily solved to optimality in only a short amount of time. Furthermore, the literature contains several references to the Stacker Crane Problem (SCP) as an ''easy'' problem amidst the ATSPs. We put this hypothesis to test by using statistical methods to build a model relating measurable distance matrix structures to the amount of time required by two existing exact solvers in finding solutions to over 500 ATSP instances. From this analysis we conclude that SCPs are not necessarily easier than other ATSPs, but a special subset of SCPs, termed drayage problems, are more readily solved. We speculate that drayage problems are ''easy'' because of a comparatively high number of zeros in symmetric locations within the distance matrix. In real-world drayage problems (i.e. the movement of containers a short distance to/from a port or rail terminal), these zeros correspond to the prevalence of jobs originating at or destined to a fixed number of freight terminals.
Year
DOI
Venue
2013
10.1016/j.cor.2011.06.017
Computers & OR
Keywords
DocType
Volume
measurable distance matrix structure,Traveling Salesman Problem,drayage problem,Stacker Crane Problem,short distance,fixed number,real-world drayage problem,freight terminal,statistical study,Stacker Crane,Drayage,high number,Intermodal Freight,distance matrix,intermodal freight container transport,Asymmetric Traveling Salesman Problem,Statistical Analysis of Algorithms,short amount
Journal
40
Issue
ISSN
Citations 
3
Computers and Operations Research
4
PageRank 
References 
Authors
0.48
11
2
Name
Order
Citations
PageRank
F. Jordan Srour1164.11
Steef van de Velde2213.31