GENERALIZATION OF A UAV LOCATION AND ROUTING PROBLEM BY TIME WINDOWS

Year 2016, Volume: 12 Issue: 2, 67 - 78, 14.11.2016

Ertan Yakıcı

Abstract

In this study we extend
and generalize a locating and routing problem for UAVs, with an objective of
maximization of the total score collected from interest points visited.  By solving the problem we determine
simultaneously take-off and landing stations and visit order of interest points
for each UAV. The problem is defined by an integer linear programming (ILP) formulation.
An ant colony optimization approach is altered for the introduced problem.
Computational experiments are performed to compare CPLEX solver and the
heuristic. We observe that the heuristic performed well on the experienced instances. 

Keywords

Location and Routing Problem, Ant Colony Optimization, UAV

References

• [1] Yakıcı E., (2016). Solving location and routing problem for UAVs,, Computers & Industrial Engineering, in press, doi: 10.1016/j.cie.2016.10.029.
• [2] Ahn J., DeWeck O., and Hoffman J., (2008). An optimization framework for global planetary surface exploration campaigns, Journal of the British Interplanetary Society, 61(12), pp. 487-498.
• [3] Ahn J., DeWeck O., Geng Y., and Klabjan D., (2012). Column generation based heuristics for a generalized location routing problem with profits arising in space exploration, European Journal of Operational Research, 223(1), pp. 47-59.
• [4] Drexl M., and Schneider M., (2015). A survey of variants and extensions of the location-routing problem, European Journal of Operational Research, 241(2), pp. 283-308.
• [5] Prodhon C., and Prins C., (2014). A survey of recent research on location-routing problems, European Journal of Operational Research, 238(1), pp. 1-17.
• [6] Stützle T., and Hoos H., (1997). Max-min ant system and local search for the traveling salesman problem, In Evolutionary Computation, IEEE International Conference on, pp. 309-314, IEEE.
• [7] Stützle T., and Hoos H., (2000). Max-min ant system, Future generation computer systems, 16(8), pp. 889-914.