Are Stacker Crane problems easy? A statistical study

F Jordan Srour, Steef van de Velde

Research output: Contribution to journalArticleAcademicpeer-review

13 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)674-690
Number of pages17
JournalComputers and Operations Research
Issue number3
Publication statusPublished - 1 Jul 2011

Research programs



Dive into the research topics of 'Are Stacker Crane problems easy? A statistical study'. Together they form a unique fingerprint.

Cite this