| In this thesis, we introduce a capacitated arc routing problem with time dependent service costs. This problem is motivated from winter gritting applications, where the timing of each intervention is crucial. The cost function on each required arc is thus a piecewise linear function with an optimal time interval for service. That is, the service cost is minimum within that interval.Keywords. Arc routing problem, variable service costs, column generation, variable neighborhood descent, dynamic problems.To solve the problem, we first propose an exact column generation approach based on a transformation of the original problem into a node routing problem. We also directly solve the arc routing problem with a variable neighborhood descent heuristic. The latter is based on neighborhood structures that move arcs or sequences of arcs. Finally, we introduce a dynamic arc routing problem with time dependent service costs. The dynamic aspect comes from possible changes in the optimal service time intervals when new weather forecasts are received in real time. The dynamic problem is addressed by solving a series of smaller static problems, where a new static problem is defined each time an updated weather forecast is received. |
