Collision Free Vehicle Routing

Monday, February 23, 2015 - 10:30am - 11:30am
Keller 3-180
Stephen Wright (University of Wisconsin, Madison)
*Stephen Wright filling in for Ruta Mehta

Since formulation of the traveling salesman problem in 1930's, there has been immense amount of work on vehicle routing problems within TCS, spanning a genre of problems from k-server to packet routing on internet to selfish routing. One such problem that has come to prominence, relatively recently due to demand for automated warehouses and assembly lines, is of {\em collision free vehicle routing}, where a collection of robots (vehicles) have to be scheduled so that they finish a list of tasks as soon as possible without colliding with each other.

The primary difficulty is to handle congestion created due to collision
avoidance. In this talk I will discuss what is known and what is not, possible approaches to solve both online and offline versions of the problem, and their short comings. I will conclude with a variety of open questions in the area.

(Based on an upcoming survey with Junho Lee, George Nemhauser, Prasad Tetali.)