A Cutting Plane Heuristic Algorithm for the Time Dependent Chinese Postman Problem

摘要

In this paper we describe a cutting plane heuristic algorithm for the Time Dependent Chinese Postman Problem. This algorithm is based on the facial structure of the time dependent postman polyhedron and on the simplex method. The facial structure investigated here provides cutting planes that can be separated polynomially using a maximum flow algorithm, and the simplex method exhibits the linear programming relaxation solutions, based on which two upper bound heuristics are designed. Computational results show that the cutting planes can improve the lower bound of the formulation substantially, and that the best upper bound obtained by the two stage heuristic is always very close to the lower bound in most cases.