EXACT SOLUTION APPROACHES FOR THE DIRECTED BI-OBJECTIVE CHINESE POSTMAN PROBLEM

In this study, we consider a directed bi-objective Chinese Postman Problem with two additive objectives (like total cost and total distance) and propose two solution approaches to generate all non-dominated objective vectors.  The first approach, namely classical approach, uses the optimal solutions of the mixed integer linear programs and generates the non-dominated objective vectors’ set sequentially. The second approach, namely branch and bound algorithm takes its spirit from the optimal solutions of the linear programming relaxations and generates the non-dominated objective vectors’ set simultaneously. The results of our extensive computational study show that our approaches are capable of solving large-sized problem instances in reasonable times.