GENERALIZATION OF A UAV LOCATION AND ROUTING PROBLEM BY TIME WINDOWS

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. [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. [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. [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. [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. [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. [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. [7] Stützle T., and Hoos H., (2000). Max-min ant system, Future generation computer systems, 16(8), pp. 889-914.