This problem is called Chinese Postman Problem and can be solved in polynomial time using matching algorithms:

https://en.m.wikipedia.org/wiki/Route_inspection_problem