Planning of Garbage Collection Service: An Arc-Routing Problem with Time-Dependent Penalty Cost

Xin Jin, Hu Qin, Zizhen Zhang, Mengchu Zhou, Jiahai Wang

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


This paper presents an arc-routing problem with time-dependent penalty cost (ARPTPC), which arises from a practical application in garbage collection service. ARPTPC considers the minimization of service cost, traveling cost and penalty cost. While the first two parts are known as the traditional objectives of arc-routing problems, the third part is determined by the parking pattern and service period on each arc. We formulate the problem by using a mixed integer linear model. To solve it, we design a dynamic programming to determine the optimal service beginning time on each edge when a routing sequence is given. We then propose a problem-specific intelligent heuristic search approach involving six neighborhood operators, a priority maintenance mechanism and a perturbation process. Through numerical experiments, we demonstrate that the proposed approach is able to produce satisfactory solutions of ARPTPC. Additional experiments are also carried out to analyze the effects of operators and parameters on solution quality.

Original languageEnglish (US)
Article number9003511
Pages (from-to)2692-2705
Number of pages14
JournalIEEE Transactions on Intelligent Transportation Systems
Issue number5
StatePublished - May 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Automotive Engineering
  • Mechanical Engineering
  • Computer Science Applications


  • Garbage collection
  • arc-routing problem
  • street parking
  • time-dependent


Dive into the research topics of 'Planning of Garbage Collection Service: An Arc-Routing Problem with Time-Dependent Penalty Cost'. Together they form a unique fingerprint.

Cite this