Abstract:

Scheduling, routing, and layout tasks are examples of hard operations-research problems that have broad application in industry. Typical algorithms for these problems combine some form of gradient descent to find local minima with some strategy for escaping nonoptimal local minima. Our idea is to divide these two subtasks cleanly between human and computer: in our paradigm of human-guided simple search the computer is responsible only for finding local minima using a simple hill-climbing search; using visualization and interaction techniques, the human user identifies promising regions of the search space for the computer to explore, and intervenes to help it escape nonoptimal local minima. We have applied our approach to the problem of capacitated vehicle routing with time windows, a commercially important problem with a rich research history. Despite its simplicity, our prototype system is competitive with the majority of previously reported systems on benchmark academic problems, and has the advantage of keeping a human tightly in the loop to handle the complexities of real-world applications.