Although the Traveling Salesman Problem with Profits (TSP with profits) has been explored quite broadly as a field of study and practice, only very attention has been paid to multi-attribute TSP with profits, despite its large applicability. In this paper, we introduce a rich variant [1] of the TSP with profits dealing with a large class of temporal and physical incompatibility characteristics. This problem is too hard to be solved by exact methods. We therefore introduce a general multi-purpose hybrid math-heuristic based on routing heuristics and exact loading neighborhoods. To build and improve the customers' sequences, we propose a multi start-construction heuristic, a portfolio of removal and insertion heuristics and a broad range of local search procedures. A special attention has been paid to the loading aspect of the problem which was barely considered in previous works by solving the resulting loading problem exactly. Several data sets with instances of up to 288 customers were used to evaluate the unified math-heuristic from the Orienteering Problem [2,3] and the Orienteering Problem with Time Window literature [4,5]. Experimental results demonstrate that the proposed math-heuristic may compete with the best known state-of-the-art methods proposed for these problems. Expanded computational experiments on more complex generated instances substantiate the effectiveness of the proposed approach. Sensitivity analysis follows and reveals the importance of some algorithmic setups and loading neighborhoods components for reaching high quality solutions.

[1] Lahyani R, Khemakehm M, Semet F, (2013) Rich vehicle routing problems: From a taxonomy to a definition. submitted for publication.

[2] Campos V, Marti R, Sanchez O, Duarte A (2012) Grasp with path relinking for the orienteering problem. Submitted to Journal of Operational Research Society.

[3] Chao I, Golden B, Wasil E (1996) A fast and effective heuristic for the orienteering problem. European Journal of Operational Research 88:475-489.

[4] Labadie N, Mansini R, Melechovsk J, Calvo R (2012) The team orienteering problem with time windows: An lp-based granular variable neighborhood search. European Journal of Operational Research 220:15-27.

[5] Righini G, Salani M (2009) Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers & Operations Research 36:1191-1203.