Heuristics to Schedule Service Engineers within Time Windows

Abstract

This paper describes the development of a set of heuristics for tackling vehicle routeing problems with time windows (VRPTW) subject to uncertain demand where schedules are prepared interactively. Many public utility companies, e.g. gas, water, electricity, are now having to quote very specific times for visits to customers, both for regular service and emergency call-outs. The heuristics developed produce good tours by sequencing visits on the basis of closeness to existing visits. Tours are developed as and when demand occurs so that the customer is given an immediate appointment time, rather than waiting for a number of requests for service to be received. Simple methods to construct time windows will also be discussed.

Keywords:

• heuristics
• travelling salesman problem
• vehicle routeing