点击次数：

论文类型：期刊论文

发表时间：2013-08-01

发表刊物：OPTIMIZATION METHODS & SOFTWARE

收录刊物：SCIE、EI

卷号：28

期号：4,SI

页面范围：855-870

ISSN号：1055-6788

关键字：time-dependent; rural postman problem; polyhedral combinatorics; valid inequalities; arc-path formulation

摘要：The Chinese postman problem is a famous and classical problem in graph theory. This paper introduces a new variant of this problem, namely, the time-dependent rural postman problem, which is motivated by applications, involving scheduling with time-dependent processing time. We present an arc-path formulation for the problem with a constraint set that is divided into two parts. The first part is linear and has a strong combinatorial structure, which defines the polytope of the arc-path alternation sequence (APAS), while the second part is nonlinear and is closely related to time-dependent travel time. First, we investigate the facial structure of the APAS polytope and present several facet inequalities. Second, considering the travel and service time functions as piecewise functions, we linearize the nonlinear inequalities and propose several strong, valid inequalities. Finally, we propose a cutting plane algorithm and report numerical results on several randomly generated instances.