Heuristic algorithms for dynamic capacitated arc routing

This thesis concerns the capacitated arc routing problem (CARP), which can be used as a model of various real-life scenarios such as rubbish collection, snow ploughing, and other situations where an emphasis is placed on providing a certain service along streets. The goal of the CARP is to find a minimum-cost set of routes such that (i) each route starts and ends at the depot, (ii) each task is serviced in one of the routes, and (iii) the total demand in each route does not exceed the capacity. Until recently, the study of the CARP is concentrated on its "static" version, that is, it is assumed that the problem remains unchanged after vehicles start their journeys. However, with today's communication technology, a route planner and drivers can communicate with each other in real time, hence the possibility of amending vehicle routes if deemed necessary or appropriate for changes that may occur in the problem. This motivates the study of a dynamic CARP. This thesis focusses on one type of change in the dynamic CARP, namely the appearance of new tasks. To ensure that a service can be performed smoothly, the ability to update a solution quickly is often preferable to achieving optimality with an excessive amount of computational effort. For this reason, we opt to develop a dynamic CARP solver based on heuristic algorithms. An investigation is conducted to gain more insights about what makes an algorithm improve a solution quickly. Furthermore, factors in the dynamic CARP beyond a solution-seeking algorithm are investigated. This includes the frequency of updating the solution and the idea of instructing vehicles to wait for additional tasks at certain locations. Efforts are focussed on reducing the total distance at the end of the service while ensuring that the service completion time is not excessive