The time-dependent rural postman problem: polyhedral results. (English) Zbl 1283.90035
Summary: 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 the 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.
Keywords:
time-dependent; rural postman problem; polyhedral combinatorics; valid inequalities; arc-path formulationReferences:
| [1] | Aldaeeb W., J. Oper. Res. Soc. 50 pp 711– (1999) · Zbl 1054.90542 · doi:10.1057/palgrave.jors.2600740 |
| [2] | DOI: 10.1109/26.111442 · doi:10.1109/26.111442 |
| [3] | Bang J., Digraphs: Theory, Algorithms and Applications (2001) · Zbl 0958.05002 |
| [4] | DOI: 10.1016/j.comnet.2006.08.015 · Zbl 1119.68018 · doi:10.1016/j.comnet.2006.08.015 |
| [5] | DOI: 10.1007/s10107-003-0391-9 · Zbl 1023.90072 · doi:10.1007/s10107-003-0391-9 |
| [6] | DOI: 10.1287/opre.1040.0168 · Zbl 1165.90534 · doi:10.1287/opre.1040.0168 |
| [7] | DOI: 10.1007/978-1-4615-4495-1 · doi:10.1007/978-1-4615-4495-1 |
| [8] | DOI: 10.1007/BF01580113 · Zbl 0281.90073 · doi:10.1007/BF01580113 |
| [9] | DOI: 10.1287/opre.43.2.231 · Zbl 0837.90037 · doi:10.1287/opre.43.2.231 |
| [10] | DOI: 10.1287/opre.43.3.399 · Zbl 0853.90042 · doi:10.1287/opre.43.3.399 |
| [11] | DOI: 10.1007/s101070050007 · Zbl 0987.90091 · doi:10.1007/s101070050007 |
| [12] | Grotschel M., The Traveling Salesman Problem pp 251– (1985) |
| [13] | DOI: 10.1007/BF01581206 · Zbl 0761.90082 · doi:10.1007/BF01581206 |
| [14] | Guan M. G., Chinese Math. 1 pp 273– (1962) |
| [15] | DOI: 10.1016/j.disopt.2007.05.004 · Zbl 1169.90326 · doi:10.1016/j.disopt.2007.05.004 |
| [16] | DOI: 10.1016/S0164-1212(01)00132-7 · doi:10.1016/S0164-1212(01)00132-7 |
| [17] | DOI: 10.1016/S0305-0548(97)00013-0 · Zbl 0889.90146 · doi:10.1016/S0305-0548(97)00013-0 |
| [18] | DOI: 10.1016/j.cor.2004.11.020 · Zbl 1087.90054 · doi:10.1016/j.cor.2004.11.020 |
| [19] | DOI: 10.1287/trsc.26.3.185 · Zbl 0758.90029 · doi:10.1287/trsc.26.3.185 |
| [20] | Mullaseril, P. A. 1996. ”Capacitated rural postman problem with time windows and split delivery”. University of Arizona. Ph.D. thesis |
| [21] | DOI: 10.1002/(SICI)1097-0037(199603)27:2<97::AID-NET1>3.0.CO;2-8 · Zbl 0851.90128 · doi:10.1002/(SICI)1097-0037(199603)27:2<97::AID-NET1>3.0.CO;2-8 |
| [22] | DOI: 10.1145/79147.214078 · Zbl 0699.68074 · doi:10.1145/79147.214078 |
| [23] | DOI: 10.1016/0305-0548(87)90065-7 · Zbl 0614.90060 · doi:10.1016/0305-0548(87)90065-7 |
| [24] | DOI: 10.1016/0377-2217(94)90048-5 · Zbl 0816.90088 · doi:10.1016/0377-2217(94)90048-5 |
| [25] | DOI: 10.1016/j.ejor.2006.06.028 · Zbl 1121.90031 · doi:10.1016/j.ejor.2006.06.028 |
| [26] | Yannakakis, M. Testing, optimization, and games. Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science. Vol. 1, pp.78–88. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
