点击次数：

论文类型：期刊论文

发表时间：2015-04-01

发表刊物：JOURNAL OF COMBINATORIAL OPTIMIZATION

收录刊物：SCIE、EI、Scopus

卷号：29

期号：3,SI

页面范围：565-588

ISSN号：1382-6905

关键字：Time-dependent; Chinese postman problem; Polyhedral combinatorics; Valid inequalities; Cycle-path formulation

摘要：The Chinese postman problem with time-dependent travel time (CPPTDT) is a generalization of the classical Chinese postman problem (CPP), where the travel time on an arc depends on the time of beginning of travel along it. While CPP and its almost static variants can be solved by integer program successfully, there are very challenging time varying CPP variants, such as CPPTDT, which are difficult to be formulated directly. The first and the only integer programming formulation modeling the time varying CPP directly was presented in the pioneering work of Wang and Wen (Comput Math Appl 44:375-387, 2002), which was unfortunately based on a strong assumption that each basic cycle in the graph must visit the depot. In this work, we propose a new integer programming formulation for the CPPTDT without any unrealistic assumptions, namely, the arc-cycle formulation, which can be viewed as an extended version of the formulation given by Wang and Wen. The constraint set of this formulation can be divided into two parts. The first part has a strong combinatorial structure, which is linear and used to define the polytope of cycle-path alternation sequence (CPAS). We determine the dimension of the CPAS polytope and identify the facet defining inequalities which may be helpful to tighten the integer programming formulation. The second part is closely related to time-dependent travel time and is nonlinear. The linearization is provided to the case when all the travel times are piecewise functions of beginning time, and several strong, valid inequalities are also proposed. The computation results with a cutting plane algorithm using the new cuts are reported on several randomly generated instances.