In a previous paper, we proposed two heuristic algorithms for the euclidean 2-period Balanced Travelling Salesman Problem (2B-TSP). In this problem, which arises from a similar one introduced by Butler et al., a certain number of customers must be visited at minimum total cost over a period of two days: some customers must be visited daily, and the others on alternate days (even or odd days). Moreover, the number of customers visited in every tour must be ‘balanced’, i.e. it must be the same or, alternatively, the difference between the maximum and the minimum number of visited customers must be less than a given threshold: this kind of constraint does not appear explicitly in the paper by Butler. In this paper a third algorithm is presented which overcomes some inadequacy of the algorithm A2 we proposed in the previous paper. The new algorithm’s performance is then analyzed, with respect particularly with the first proposed algorithm.

A new algorithm for the 2-period Balanced Traveling Salesman Problem in Euclidean Graphs.

MASON, Francesco;
2008

Abstract

In a previous paper, we proposed two heuristic algorithms for the euclidean 2-period Balanced Travelling Salesman Problem (2B-TSP). In this problem, which arises from a similar one introduced by Butler et al., a certain number of customers must be visited at minimum total cost over a period of two days: some customers must be visited daily, and the others on alternate days (even or odd days). Moreover, the number of customers visited in every tour must be ‘balanced’, i.e. it must be the same or, alternatively, the difference between the maximum and the minimum number of visited customers must be less than a given threshold: this kind of constraint does not appear explicitly in the paper by Butler. In this paper a third algorithm is presented which overcomes some inadequacy of the algorithm A2 we proposed in the previous paper. The new algorithm’s performance is then analyzed, with respect particularly with the first proposed algorithm.
File in questo prodotto:
File Dimensione Formato  
2008wp173.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Accesso libero (no vincoli)
Dimensione 625.69 kB
Formato Adobe PDF
625.69 kB Adobe PDF Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10278/24271
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact