Multi-type facility location in printing and parcel delivery services

Abstract

We examine a novel variant of multitype capacitated facility location, motivated by two contemporary applications in parcel delivery and in managed printing services. Our setting is characterized by nonlinear functions for the setup cost of multiple facilities in a location and the service cost of multiple clients by a facility, capacities on both locations and facilities and unsplittable demand per client. The total cost includes also the standard fixed opening costs of the locations and the connection costs per client and location. We propose a compact integer programming formulation that uses only two-index variables, plus its linearisation, which is then strengthened by a set of valid inequalities that yield near-optimal lower bounds. To speed up an exact solver, we propose construction heuristics and variable neighborhood descent (VND) metaheuristics. The former include a combinatorial heuristic that efficiently tackles nonlinearity and an LP-rounding approach handling hard capacities on locations and facilities. The VND strategy is guided by local improvement stages where multiple locations or facilities might be exchanged under various improvement strategies and a neighborhood reduction mechanism. We establish the computational competence of our approach by solving exactly large-scale real instances, thus showing also its practical relevance and impact. Further experimentation on benchmark instances shows that our approach computes almost optimal solutions in a few minutes, which in turn speed up considerably the execution of a commercial solver when used as upper bounds. Our data and code are made available.