Multi-type facility location in printing and parcel delivery services

Ioannis Avgerinos (), Ioannis Mourtos () and Georgios Zois ()
Additional contact information
Ioannis Avgerinos: Athens University of Economics and Business
Ioannis Mourtos: Athens University of Economics and Business
Georgios Zois: Athens University of Economics and Business

Annals of Operations Research, 2022, vol. 309, issue 1, No 17, 365-393

Abstract: 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.

Keywords: Facility location problem; Nonlinear cost function; Managed printing services; Parcel delivery services; Metaheuristics; Computational experiments (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-021-04469-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:309:y:2022:i:1:d:10.1007_s10479-021-04469-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-021-04469-3

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().