Abstract—Photographing a large area in an instant becomes
hard if the area is very large like a rain forest or industrial
territory. Therefore, more than one photograph is necessary to visualize the whole area. Agents such as drones are used for taking photographs. They take photographs at several points
(nodes) to cover the area. In that sense, the problem may be defined as a variant of TSP. Photographs are able to cover multiple nodes if taken, so it is not practical to go to every node to take photos. Instead, several photos are taken in nodes at the minimum cost, and all nodes are covered. We make use of
accessibility concept to incorporate this situation into our model. If several nodes are within the field of a particular node, drones
can go to that node, take a photo at that node, and are able to cover all accessible neighbor nodes.
In this study, we provide a unique mathematical model for this modified TSP, show that the problem is NP-Hard and provide a greedy heuristic to find solutions within 1-10% of the solutions and lower bounds on hand. We observe that if
photographing costs are kept lower than distance costs, the algorithm yields 1-5% gap, and as the photographing costs increase, performance of the algorithm falls to around 5-10% gap. In all cases, we are able to solve problem instances within seconds to several minutes. Our model based on photographing and accessibility is unique as it involves accessibility based on distance and heights; and the heuristic we provide differs from previous ones in that it incorporates two different sub-heuristics in addition to SCP optimization algorithm.
Index Terms—Modified traveling salesman problem (TSP), heuristics, network optimization, OR applications.
Murat Çal is with Tubitak Tusside, Turkey (e-mail: muratcal89@yahoo.com)
Ali Ekici is with Ozyegin University, Turkey (e-mail: ali.ekici@ozyegin.edu.tr)
[PDF]
Cite: Murat Çal and Ali Ekici, "Solving a Modified TSP Problem by a Greedy Heuristic
for Cost Minimization," International Journal of Modeling and Optimization vol. 8, no. 3, pp. 138-144, 2018.
