The street sweeping problem

The Problem considered in this paper is designing the routing of street sweeper vehicles under the multifarious constraints that are involved in municipal street sweeping operations. Interesting graph theoretic and combinatiorial problems are involved in the process of developing efficient solutions. The general problem is showed to be NP-complete. A approximate algorithm is presented for routing in the case of a mixed graph.