Trade-offs between the stepwise cost function and its linear approximation for the modular hub location problem. (April 2019)

• Record Type: Journal Article
• Authors: Keshvari Fard, Milad; Alfandari, Laurent
• Is Part Of: Computers & operations research. Volume 104(2019)
• Page Start: 358
• Page End: 374
• Publication Date: 2019-04
• Subjects: Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.11.014
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We study the Modular Hub Location Problem (p-median with single assignment). We propose to replace the stepwise transportation cost function by its best linear approximation. Various intercepts of the linear approximation, depending on problem data, are compared. The best linear approximation provides very low gaps to optimality for the MHLP, with reduced computational time. We analyze the savings induced by the possibility of direct shipments, and the impact of shipment frequency. Abstract: There exist situations where the transportation cost is better estimated as a function of the number of vehicles required for transporting a load, rather than a linear function of the load. This provides a stepwise cost function, which defines the so-called Modular Hub Location Problem (MHLP, or HLP with modular capacities) that has received increasing attention in the last decade. In this paper, we consider formulations to be solved by exact methods. We show that by choosing a specific generalized linear cost function with slope and intercept depending on problem data, one minimizes the measurement deviation between the two cost functions and obtains solutions close to those found with the stepwise cost function, while avoiding the higher computational complexity of the latter. As a side contribution, we look at the savings induced by using direct shipments in a hub and spoke network, given the better ability of a stepwise cost function to incorporate direct transportation. Numerical experiments are conducted over benchmark HLP instances of the OR-library.