An integer programming approach for the Chinese postman problem with time-dependent travel time

Jinghao Sun (), Yakun Meng and Guozhen Tan
Additional contact information
Jinghao Sun: Northeastern University
Yakun Meng: Northeastern University
Guozhen Tan: Dalian University of Technology

Journal of Combinatorial Optimization, 2015, vol. 29, issue 3, No 4, 565-588

Abstract: Abstract 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.

Keywords: Time-dependent; Chinese postman problem; Polyhedral combinatorics; Valid inequalities; Cycle-path formulation (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9755-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:3:d:10.1007_s10878-014-9755-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9755-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().