Energy efficient multi-place robot rendezvous problem with campaign time restrictions

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Bilimleri Enstitüsü, Yöneylem Araştırması Anabilim Dalı, Türkiye

Tezin Onay Tarihi: 2020

Tezin Dili: İngilizce

Öğrenci: NAZLI DOLU HASTÜRK

Danışman: Mustafa Kemal Tural

Özet:

We study the energy efficient multi-place robot rendezvous problem. In this problem, we aim to find a set of rendezvous places where a tanker robot meets with mobile worker robots for a recharging task by preserving a meeting order. The problem is examined under two different objective functions. The first objective function is to minimize the total time spent, i.e., campaign time to recharge all the robots. The second objective function is to minimize the total energy consumption of all the robots by taking a predetermined campaign time as a restriction. The energy consumption functions of both the mobile worker robots and the tanker robot used in this study are nonlinear and distances between locations are calculated by the Euclidean distances. This problem is NP-hard when we aim to find the optimal rendezvous places and the optimal meeting order simultaneously. In our solution approach, we first fix the meeting order and determine the optimal rendezvous places based on a given meeting order. To do so, we provide a second order cone programming formulation. Then, we utilize improvement heuristics to find a better meeting order to improve the objective function value. Mainly we work on 2-opt and 3-opt edge exchange improvement heuristics as well as their combination to search for a better meeting order. Furtherv more, we implement speed-up techniques to decrease the solution times of the improvement heuristics. Finally, extensive computational experiments are conducted to compare the suggested improvement heuristic algorithms and speed-up techniques.