Models and Algorithms for the Integrated Planning of Bin Allocation and Vehicle Routing in Solid Waste Management

V.C. Hemmelmayr, K.F. Doerner, R.F. Hartl, D. Vigo

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

The efficient organization of waste collection systems based on bins located along the streets involves the solution of several tactical optimization problems. In particular, the bin configuration and sizing at each collection site as well as the service frequency over a given planning horizon have to be decided. In this context, a higher service frequency leads to higher routing costs, but at the same time less or smaller bins are required, which leads to lower bin allocation investment costs. The bins used have different types and different costs and there is a limit on the space at each collection site as well as a limit on the total number of bins of each type that can be used. In this paper we consider the problem of designing a collection system consisting of the combination of a vehicle routing and a bin allocation problem in which the trade-off between the associated costs has to be considered. The solution approach combines an effective variable neighborhood search metaheuristic for the routing part with a mixed integer linear programming-based exact method for the solution of the bin allocation part. We propose hierarchical solution procedures where the two decision problems are solved in sequence, as well as an integrated approach where the two problems are considered simultaneously. Extensive computational testing on synthetic and real-world instances with hundreds of collection sites shows the benefit of the integrated approaches with respect to the hierarchical ones. © 2014 INFORMS.
Original languageEnglish
Pages (from-to)103-120
JournalTransportation Science
Volume48
Issue number1
DOIs
Publication statusPublished - 2014

Fingerprint

integrated planning
Vehicle routing
waste management
Bins
Solid wastes
Waste management
Planning
costs
Costs
programming
organization
planning
Linear programming
Testing

Cite this

@article{ef3553165dbd4905be7977879b87dcfb,
title = "Models and Algorithms for the Integrated Planning of Bin Allocation and Vehicle Routing in Solid Waste Management",
abstract = "The efficient organization of waste collection systems based on bins located along the streets involves the solution of several tactical optimization problems. In particular, the bin configuration and sizing at each collection site as well as the service frequency over a given planning horizon have to be decided. In this context, a higher service frequency leads to higher routing costs, but at the same time less or smaller bins are required, which leads to lower bin allocation investment costs. The bins used have different types and different costs and there is a limit on the space at each collection site as well as a limit on the total number of bins of each type that can be used. In this paper we consider the problem of designing a collection system consisting of the combination of a vehicle routing and a bin allocation problem in which the trade-off between the associated costs has to be considered. The solution approach combines an effective variable neighborhood search metaheuristic for the routing part with a mixed integer linear programming-based exact method for the solution of the bin allocation part. We propose hierarchical solution procedures where the two decision problems are solved in sequence, as well as an integrated approach where the two problems are considered simultaneously. Extensive computational testing on synthetic and real-world instances with hundreds of collection sites shows the benefit of the integrated approaches with respect to the hierarchical ones. {\circledC} 2014 INFORMS.",
author = "V.C. Hemmelmayr and K.F. Doerner and R.F. Hartl and D. Vigo",
year = "2014",
doi = "10.1287/trsc.2013.0459",
language = "English",
volume = "48",
pages = "103--120",
journal = "Transportation Science",
issn = "0041-1655",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "1",

}

Models and Algorithms for the Integrated Planning of Bin Allocation and Vehicle Routing in Solid Waste Management. / Hemmelmayr, V.C.; Doerner, K.F.; Hartl, R.F.; Vigo, D.

In: Transportation Science, Vol. 48, No. 1, 2014, p. 103-120.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Models and Algorithms for the Integrated Planning of Bin Allocation and Vehicle Routing in Solid Waste Management

AU - Hemmelmayr, V.C.

AU - Doerner, K.F.

AU - Hartl, R.F.

AU - Vigo, D.

PY - 2014

Y1 - 2014

N2 - The efficient organization of waste collection systems based on bins located along the streets involves the solution of several tactical optimization problems. In particular, the bin configuration and sizing at each collection site as well as the service frequency over a given planning horizon have to be decided. In this context, a higher service frequency leads to higher routing costs, but at the same time less or smaller bins are required, which leads to lower bin allocation investment costs. The bins used have different types and different costs and there is a limit on the space at each collection site as well as a limit on the total number of bins of each type that can be used. In this paper we consider the problem of designing a collection system consisting of the combination of a vehicle routing and a bin allocation problem in which the trade-off between the associated costs has to be considered. The solution approach combines an effective variable neighborhood search metaheuristic for the routing part with a mixed integer linear programming-based exact method for the solution of the bin allocation part. We propose hierarchical solution procedures where the two decision problems are solved in sequence, as well as an integrated approach where the two problems are considered simultaneously. Extensive computational testing on synthetic and real-world instances with hundreds of collection sites shows the benefit of the integrated approaches with respect to the hierarchical ones. © 2014 INFORMS.

AB - The efficient organization of waste collection systems based on bins located along the streets involves the solution of several tactical optimization problems. In particular, the bin configuration and sizing at each collection site as well as the service frequency over a given planning horizon have to be decided. In this context, a higher service frequency leads to higher routing costs, but at the same time less or smaller bins are required, which leads to lower bin allocation investment costs. The bins used have different types and different costs and there is a limit on the space at each collection site as well as a limit on the total number of bins of each type that can be used. In this paper we consider the problem of designing a collection system consisting of the combination of a vehicle routing and a bin allocation problem in which the trade-off between the associated costs has to be considered. The solution approach combines an effective variable neighborhood search metaheuristic for the routing part with a mixed integer linear programming-based exact method for the solution of the bin allocation part. We propose hierarchical solution procedures where the two decision problems are solved in sequence, as well as an integrated approach where the two problems are considered simultaneously. Extensive computational testing on synthetic and real-world instances with hundreds of collection sites shows the benefit of the integrated approaches with respect to the hierarchical ones. © 2014 INFORMS.

U2 - 10.1287/trsc.2013.0459

DO - 10.1287/trsc.2013.0459

M3 - Article

VL - 48

SP - 103

EP - 120

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 1

ER -