On prize-collecting tours and the asymmetric travelling salesman problem.

*(English)*Zbl 0860.90121Summary: We consider a variant of the travelling salesman problem which is to determine a tour visiting each vertex in the graph at most at one time; if a vertex is left unrouted a given penalty has to be paid. The objective function is to find a balance between these penalities and the cost of the tour. We call this problem the Profitable Tour Problem (PTP). If, in addition, each vertex is associated with a prize and there is a knapsack constraint which guarantees that a sufficiently large prize is collected, we have the well-known Prize-collecting Travelling Salesman Problem (PCTSP). In this paper, we summarize the main results presented in the literature, then we give lower bounds for the asymmetric version of PTP and PCTSP. Moreover, we show, through computational experiments, that large size instances of the asymmetric PTP can be solved exactly.

##### MSC:

90C35 | Programming involving graphs or networks |

##### Keywords:

Lagrangean relaxation; profitable tour problem; prize-collecting; travelling salesman; lower bounds; asymmetric version
PDF
BibTeX
Cite

\textit{M. Dell'Amico} et al., Int. Trans. Oper. Res. 2, No. 3, 297--308 (1995; Zbl 0860.90121)

Full Text:
DOI

##### References:

[1] | Balas E., Networks 19 pp 621– (1989) |

[2] | E. Balas (1993 ). The prize collecting traveling salesman problem: II. Polyhedral results . Technical report MSRR-591, Carnegie Mellon University, Pittsburgh, PA15213 -3890 . |

[3] | E. Balas, and G. Martin (1985 ). ROLL-A-ROUND: Software package for scheduling the rounds of a rolling mill. Copyright Balas and Martin Associates, 104 Maple Heights Road, Pittsburgh, PA. |

[4] | DOI: 10.1007/BF01581256 · Zbl 0793.90089 |

[5] | Carpaneto G., Exact solution of large-scale asymmetric travelling salesman problems (1990) |

[6] | Christofides N., Worst-case analysis of a new heuristic for the travelling salesman problem (1976) |

[7] | Dell’Amico M., The linear assignment problem: an annotated bibliography (1994) |

[8] | Fischetti M., Vehicle Routing: Methods and Studies pp 319– (1988) |

[9] | Fischetti M., Operations Research 37 pp 313– (1989) |

[10] | Fischetti M., ORSA Journal on Computing 5 (1993) · Zbl 0789.90082 |

[11] | Gensch D. H., AIIE Transactions 10 pp 362– (1978) |

[12] | M. X. Goemans, and D. P. Williamson (1992 ). A general approximation technique for constrained forest problems. InProc. 3rd SODA Symposium, Chapter 37, pp. 307 -316 . · Zbl 0818.90124 |

[13] | Golden B. L., Naval Research Logistics Quarterly 34 pp 307– (1987) |

[14] | Golden B. L., Naval Research Logistics Quarterly 35 pp 359– (1988) |

[15] | DOI: 10.1007/BF01580223 · Zbl 0284.90057 |

[16] | Ibaraki T., Electronics and Communications in Japan 53 pp 10– (1970) |

[17] | DOI: 10.1007/BF02278710 · Zbl 0607.90056 |

[18] | DOI: 10.1016/0166-218X(90)90100-Q · Zbl 0695.90098 |

[19] | DOI: 10.2307/2582629 |

[20] | DOI: 10.2307/2582232 · Zbl 0628.90086 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.