Robust Optimization Approach in Chinese Postman Problem

Chinese postman problem is one of the most known arc routing problems with multiple uses in real application. It is similar to well-known Traveling salesman problem, but unlike it, the goal is to visit all edges, not nodes. This paper deals with using Chinese postman problem and it shows how to deal with a situation when travel times on given edges are not exactly known. In real life problems, it is very common that not every part of the model is precisely known. This can be caused by traffic complications or other uncertain circumstances and mathematical programming allows us to handle uncertainty in multiple ways. One of the frequently used methods is stochastic optimization, or there is robust optimization approach, that is used in this paper. The robust approach allows one to identify deviations of deterministic values, find robust-optimal solution and keeps the optimization model relatively simple. This paper describes robust optimization approach towards Chinese postman problem in detail with example in the end.