Are Stacker Crane Problems easy? A statistical study

F. Jordan Srour

doi:10.1016/j.cor.2011.06.017

Return

Are Stacker Crane Problems easy? A statistical study

2013-03-01

PRE

F. Jordan Srour *

Steef van de Velde

DOI：10.1016/j.cor.2011.06.017

Original

Original request for help

Save

Abstract

En 中文

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. (c) 2011 Elsevier Ltd. All rights reserved.

Keywords:

Drayage

Intermodal freight

Asymmetric Traveling Salesman Problem

Traveling Salesman Problem

Stacker Crane Problem

Statistical analysis of algorithms

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.