Time-constrained Chinese postman problems

The Chinese postman problem was first proposed by the Chinese mathematician Meigu Guan. It says that a postman picks up mails at the post office, delivers it along a set of streets, and returns to the post office. In practice, apart from the requirement of travelling all streets, we consider the street direction, number of postmen, and the capacity of postman, etc. But in the present environment of ‘time is money’, consideration of a time window constraint is necessary. In this paper, we investigate a Chinese postman problem with time window constraint such that this problem can simulate the real situations. Finally, when time constraints are not certain, we employ the concept of fuzzy set theory to cope with a directed Chinese postman problem with fuzzy time windows.