A location-or-routing problem with partial and decaying coverage

Maryam Haghi, Okan Arslan, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

Abstract

This paper studies a generalized location-or-routing problem by considering partial coverage of the users according to a distance-decaying coverage function. In this problem, there is a set of candidate locations where to open facilities, and a set of locations with given number of users that must be covered by the open facilities. Users may travel directly to an open facility if they are within the coverage range of it, or they may be transported to facilities by capacitated vehicles. A distance-decaying function for the facility coverage is considered and the vehicles are allowed to partially cover the users located at the same location. Two mixed integer programming models are presented that minimize the number of uncovered users subject to a restricted budget, and an adaptive large neighborhood search metaheuristic is developed as the solution methodology. Through several computational experiments, the efficiency of the proposed formulations and the solution algorithm are evaluated, and the ALNS algorithm is shown to perform well in terms of solution quality and computing time. Computational results indicate that considering the partial coverage of users reduces the number of uncovered ones as the vehicle capacity decreases, and this reduction is more significant under a distance-decaying facility coverage function. It is also observed that considering distance-decaying coverage increases both the number of uncovered users and the spent budget, especially with a continuous function such as an exponential decay function.

Original languageEnglish
Article number106041
JournalComputers and Operations Research
Volume149
Early online date29 Sep 2022
DOIs
Publication statusE-pub ahead of print - 29 Sep 2022

Keywords

  • Adaptive large neighborhood search
  • Decaying coverage
  • Location
  • Routing

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'A location-or-routing problem with partial and decaying coverage'. Together they form a unique fingerprint.

Cite this