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

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.