Tactical and Dynamic Technician Routing and Scheduling

Weconsider the tactical planning aspect of a dynamic technician routing and scheduling problem with a time horizon of several days. In this problem study, some tasks are known beforehand, while others arrive dynamically. The tactical planning is to schedule the known tasks, such that we minimise the overall driving distance while ensuring short service times of the dynamic tasks. Without tactical planning, the known tasks would be spread throughout the whole area as they are scheduled based on a first-come-first-serve principle. In this study, we partition the area into some disjoint areas covering the full plane. Every day we schedule the known tasks corresponding to one area in a round-robin fashion. The partitioning of the areas will be constructed with a balanced sweep algorithm using two approaches: The first is based on a sweep-line following a given angle, while the second is based on a rotating sweep-line around a given origin. To guide the partitioning, we aim to minimise the degree of dynamism, which in our case is def ined by the number of dynamic tasks, the distance from known tasks to dynamic tasks, and the tightness of the time windows. The tactical planning is evaluated using dynamic instances based on the Solomon test instances, where some of the tasks are known, and some are dynamic. We benchmark the two partitioning approaches against the default strategy of just serving all known tasks on a first-come-first-serve basis. Computational results are reported.