Back
1-s2.0-s0305054823002575-main_0
Journal article

A logic-based Benders decomposition solution approach for two covering problems that consider the underlying transportation

BP2-STS

  • 22.08.2023
Published in:
  • Computers & Operations Research. - Elsevier BV. - 2023, vol. 160, p. 1-13
Logic-based Benders decomposition
Maximal covering location problem
Transportation
Perfect matching
Waste collection
English We investigate two maximal covering location problems with capacity restrictions, minimum workload, and transportation. The problems are inspired by a waste collection problem in which large waste containers are scattered throughout the municipality, and the residents bring their waste to these containers. We take the residents’ preferences into account when allocating them to locations. When a container is full, a vehicle transports an empty container from the disposal facility (depot) to that location and replaces it. We propose a mixed-integer linear programming formulation for the problems in which vehicles can carry one or two containers, and apply a logic-based Benders decomposition approach for the latter. Here, the sub problem is a multi-period minimum weight perfect matching problem. We show that our logic-based Benders decomposition approach outperforms the direct formulation in terms of solution quality and speed. We further show that transportation of two containers at a time reduces the distance to be driven by 29.5% on average, without compromising the covering level. Furthermore, we analyze the effect of imposing a minimum workload as well as the effect of changing the focus between transportation and covering.
Faculty
Faculté des sciences économiques et sociales et du management
Department
Département d'informatique
Language
  • English
Classification
Computer science and technology
License
CC BY
Open access status
hybrid
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/326102
Statistics
Document views: 48 File downloads:
  • 1-s2.0-s0305054823002575-main_0.pdf: 68