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

Vera Fischer; Sanne Wøhlk

doi:10.1016/j.cor.2023.106393

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

^*Corresponding author for this work

Department of Economics and Business Economics

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

2 Citations (Scopus)

55 Downloads (Pure)

Abstract

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.

Original language	English
Article number	106393
Journal	Computers and Operations Research
Volume	160
Number of pages	13
ISSN	0305-0548
DOIs	https://doi.org/10.1016/j.cor.2023.106393
Publication status	Published - Dec 2023

Keywords

Logic-based Benders decomposition
Maximal covering location problem
Perfect matching
Transportation
Waste collection

Access to Document

10.1016/j.cor.2023.106393Licence: CC BY

1-s2.0-S0305054823002575-mainFinal published version, 1.45 MBLicence: CC BY

Cite this

@article{e71120833c12412aa94297207fe703e0,

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

abstract = "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{\textquoteright} 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.",

keywords = "Logic-based Benders decomposition, Maximal covering location problem, Perfect matching, Transportation, Waste collection",

author = "Vera Fischer and Sanne W{\o}hlk",

year = "2023",

month = dec,

doi = "10.1016/j.cor.2023.106393",

language = "English",

volume = "160",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

}

A logic-based Benders decomposition solution approach for two covering problems that consider the underlying transportation. / Fischer, Vera; Wøhlk, Sanne.
In: Computers and Operations Research, Vol. 160, 106393, 12.2023.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

TY - JOUR

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

AU - Fischer, Vera

AU - Wøhlk, Sanne

PY - 2023/12

Y1 - 2023/12

N2 - 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.

AB - 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.

KW - Logic-based Benders decomposition

KW - Maximal covering location problem

KW - Perfect matching

KW - Transportation

KW - Waste collection

UR - http://www.scopus.com/inward/record.url?scp=85169834301&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2023.106393

DO - 10.1016/j.cor.2023.106393

M3 - Journal article

AN - SCOPUS:85169834301

SN - 0305-0548

VL - 160

JO - Computers and Operations Research

JF - Computers and Operations Research

M1 - 106393

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this