A new, simple and effective heuristic algorithm has been developed for the period traveling salesman problem. Computational results obtained from the test problems taken from the literature indicate that the algorithm compares well in terms of accuracy with other existing algorithms, finding a larger number of best solutions. Moreover, its average percentage error and its worst ratio of solution to the best-known solution are smaller than those of the other existing algorithms. In the period traveling salesman problem, a traveling salesman must visit each city a fixed number of times over a given m-day planning period. Each city specifies a set of sequences of visit days and the visit days are assigned to the city by selecting one of these sequences. Moreover, for each day of the planning period, a not empty tour must be generated by connecting the salesman home city and the cities that must be visited on that day. The salesman objective is to minimize the total distance traveled over the entire m-day period. For this problem, arising in various situations such as mail delivery or lawn-care services, the paper proposes a simple and effective heuristic algorithm where an improvement procedure is embedded within a tour construction type procedure.

### The period traveling salesman problem: a new heuristic algorithm

#### Abstract

A new, simple and effective heuristic algorithm has been developed for the period traveling salesman problem. Computational results obtained from the test problems taken from the literature indicate that the algorithm compares well in terms of accuracy with other existing algorithms, finding a larger number of best solutions. Moreover, its average percentage error and its worst ratio of solution to the best-known solution are smaller than those of the other existing algorithms. In the period traveling salesman problem, a traveling salesman must visit each city a fixed number of times over a given m-day planning period. Each city specifies a set of sequences of visit days and the visit days are assigned to the city by selecting one of these sequences. Moreover, for each day of the planning period, a not empty tour must be generated by connecting the salesman home city and the cities that must be visited on that day. The salesman objective is to minimize the total distance traveled over the entire m-day period. For this problem, arising in various situations such as mail delivery or lawn-care services, the paper proposes a simple and effective heuristic algorithm where an improvement procedure is embedded within a tour construction type procedure.
##### Scheda breve Scheda completa Scheda completa (DC)
2002
Computation results; Heuristic algorithms; Period traveling salesman problem
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS 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: `https://hdl.handle.net/20.500.11770/126089`
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• 35
• 24