The p-median problem with upgrading of transportation costs and minimum travel time allocation

Abstract

In this paper, we analyse the upgrading of arcs in the p-median problem on a bi-network. Both travel times and transportation costs are associated with each arc. Our goal consists of simultaneously finding p medians, allocating each node to the median of minimum travel time and distributing a known budget among the arcs of the network to reduce their transportation cost, in order to minimise the total transportation cost of the system. The problem is motivated by the warehouse-to-locker structure of the distribution networks of many ecommerce businesses. We formulate it in two different ways as an integer programming problem, derive some properties of any optimal solution, develop valid inequalities and present computational results.