Nearly-Eulerian Tours
For total cost, see http://en.wikipedia.org/wiki/Route_inspection_problem (also called the Chinese postman problem). The optimal solutions to this problem visit each edge at most twice, so they also optimize your width cost.