Solving a Modified TSP Problem by a Greedy Heuristic for Cost Minimization - Volume 8 Number 3 (Jun. 2018) - ijmo
  • Aug 01, 2018 News! [CFP] 2019 the annual meeting of IJMO Editorial Board, ECDMO 2019, will be held in Amsterdam, Netherlands, February 16-18, 2019.   [Click]
  • Aug 06, 2018 News! Vol.7, No.1 has been indexed by EI (Inspec).   [Click]
  • Aug 06, 2018 News! Vol.6, No.5 has been indexed by EI (Inspec).   [Click]
General Information
Editor-in-chief
Prof. Adrian Olaru
University Politehnica of Bucharest, Romania
I'm happy to take on the position of editor in chief of IJMO. It's a journal that shows promise of becoming a recognized journal in the area of modelling and optimization. I'll work together with the editors to help it progress.
IJMO 2018 Vol.8(3): 138-144 ISSN: 2010-3697
DOI: 10.7763/IJMO.2018.V8.638

Solving a Modified TSP Problem by a Greedy Heuristic for Cost Minimization

Murat Çal and Ali Ekici
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.

Copyright © 2008-2015.International Journal of Modeling and Optimization. All rights reserved.
E-mail: ijmo@iacsitp.com