Solving multi-objective team orienteering problem with time windows using adjustment iterated local search

Subject Areas : Mathematical Optimization

Indri Hapsari ¹ , Isti Surjandari ² , K. Komarudin ³

1 - Industrial Engineering, Universitas Indonesia, Depok, Indonesia
2 - Industrial Engineering, Universitas Indonesia, Depok, Indonesia
3 - Industrial Engineering, Universitas Indonesia, Depok, Indonesia

Received: 2020-10-08 Accepted : 2020-10-08 Published : 2019-12-01

Keywords: Multi, objective · Team orienteering problem · Time window · Iterated local search · Mixed integer linear programming,

Abstract :

One of the problems tourism faces is how to make itineraries more effective and efficient. This research has solved the routing problem with the objective of maximizing the score and minimizing the time needed for the tourist’s itinerary. Maximizing the score means collecting a maximum of various kinds of score from each destination that is visited. The profits differ according to whether those destinations are the favorite ones for the tourists or not. Minimizing time means traveling time and visiting time in the itinerary being kept to a minimum. Those are small case with 16 tourism destinations in East Java, and large case with 56 instances consists of 100 destinations each from previous research. The existing model is the Team Orienteering Problem with Time Window (TOPTW), and the development has been conducted by adding another objective, minimum time, become Flexible TOPTW. This model guarantees that an effective itinerary with efficient timing to implement will be produced. Modification of Iterated Local Search (ILS) into Adjustment ILS (AILS) has been done by replacing random construction in the early phase with heuristic construction, continue with Permutation, Reserved and Perturbation. This metaheuristic method will address this NP-hard problem faster than the heuristic method because it has better preparation and process. Contributing to this research is a multi-objective model that combines maximum score and minimum time, and a metaheuristics method to solve the problem faster and effectively. There are calibration parameter with 17 instances of 100 destinations each, small case test using Mixed Integer Linear Programming, and large case test comparing AILS with Multi-Start Simulated Annealing (MSA), Simulated Annealing (SA), Artificial Bee Colony (ABC), and Iterated Local Search. The result shows that the proposed model will provide itinerary with less number of visited destination 4.752% but has higher total score 8.774%, and 3836.877% faster, comparing with MSA, SA, and ABC. While AILS is compared with ILS, it has less visited destination 5.656%, less total score 56.291%, and faster 375.961%. Even though AILS has more efficient running time than other methods, it needs improvement in algorithm to create better result.