Back
1-s2.0-s0377221723008962-main
Journal article

A capacitated multi-vehicle covering tour problem on a road network and its application to waste collection

BP2-STS

Show more…
  • 29.11.2023
Published in:
  • European Journal of Operational Research. - Elsevier BV. - 2023, p. 1-16
Combinatorial optimization
Waste collection
Multi-vehicle covering tour problem
Mixed-integer linear programming
Road network
English In most Swiss municipalities, a curbside system consisting of heavy trucks stopping at almost each household is used for non-recoverable waste collection. Due to the many stops of the trucks, this strategy causes high fuel consumption, emissions and noise. These effects can be alleviated by reducing the number of stops performed by the collection vehicles. One possibility consists of selecting a subset of candidate locations that are scattered throughout the municipality to place collection points which are used by residents to bring their waste. Provided that the underlying road network is available and that the collection vehicle has a known capacity, we refer to this problem as the capacitated multi-vehicle covering tour problem on a road network (C𝑚-CTP-R). We propose a road-network-based mixed-integer linear programming (MILP) formulation that exploits the sparsity of the network. We compare it against the MILP formulation that results from assuming a customer-based graph, which is typically used in vehicle routing problems (VRP). To solve large instances, we develop a two-phased heuristic approach that addresses the two subproblems the C𝑚-CTP-R is built on: a set covering problem to select the locations and a split-delivery VRP to determine the tours. Computational experiments on instances derived from real-life data show that the road-network-based formulation is better suited. Furthermore, the proposed heuristic provides good solutions with optimality gaps below 1.7% and finds better solutions for most of the instances that the exact method is not able to solve within a given time limit.
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/327035
Statistics
Document views: 10 File downloads:
  • 1-s2.0-s0377221723008962-main.pdf: 13