New complexity results for the p-hub median problem

Abstract

Using transportation mode and flow dependent cost structures on the classical p-hub median problems affects the shape of its linear cost function. While there is a vast literature about the classical problem, the studies with cost structures different than linear functions are rare. In this study, several cost structures such as all unit discount model, modified all unit discount model, car load discount model and container cost structures, which are especially useful in freight transportation, are considered. It is shown that some easy classical problems become NP-hard when the linearity of the cost functions is lost.