In this paper we investigate theoretical properties of the Double Traveling Salesman Problem with Multiple Stacks. In particular, we provide polynomial time algorithms for different subproblems when the stack size limit is relaxed. Since these algorithms can represent building blocks for more complex methods, we also include them in a simple heuristic which we test experimentally. We finally analyze the impact of handling the stack size limit, and we propose repair procedures. The theoretical investigation highlights interesting structural properties of the problem, and our computational results show that the single components of the heuristic can be successfully incorporated in more complex algorithms or bounding techniques.
Efficient algorithms for the double travelling salesman problem with multiple stacks / M. Casazza, A. Ceselli, M. Nunkesser. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 39:5(2012 May), pp. 1044-1053. [10.1016/j.cor.2011.06.008]
Efficient algorithms for the double travelling salesman problem with multiple stacks
M. Casazza;A. Ceselli;
2012
Abstract
In this paper we investigate theoretical properties of the Double Traveling Salesman Problem with Multiple Stacks. In particular, we provide polynomial time algorithms for different subproblems when the stack size limit is relaxed. Since these algorithms can represent building blocks for more complex methods, we also include them in a simple heuristic which we test experimentally. We finally analyze the impact of handling the stack size limit, and we propose repair procedures. The theoretical investigation highlights interesting structural properties of the problem, and our computational results show that the single components of the heuristic can be successfully incorporated in more complex algorithms or bounding techniques.File | Dimensione | Formato | |
---|---|---|---|
2012_COR_DTSPMS_Casazza_Ceselli.pdf
accesso riservato
Descrizione: Articolo principale, versione finale
Tipologia:
Publisher's version/PDF
Dimensione
500.65 kB
Formato
Adobe PDF
|
500.65 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.