A package that uses Hybrid Genetic Algorithm to solve any TSPD or FSTSP instance, based on the following paper:
https://arxiv.org/abs/2303.00614
@misc{mahmoudinazlou_hybrid,
author = {Mahmoudinazlou, Sasan and Kwon, Changhyun},
title = {A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone},
year = {2023},
doi = {10.48550/ARXIV.2303.00614},
url = {https://arxiv.org/abs/2303.00614},
}
To install:
import Pkg; Pkg.add(url="https://github.com/Sasanm88/TSPDroneHGATAC.jl")
or
] add https://github.com/Sasanm88/TSPDroneHGATAC.jl
To install TSPDrone.jl
:
] add https://github.com/chkwon/TSPDrone.jl
Using x
-y
coordinates.
Based on the coordinates, the Euclidean distances are calculated.
The Eucliden distances will be divided by truck_speed
and drone_speed
to calculate the travel cost for the truck and the drone, respectively.
using TSPDroneHGATAC
n = 10
x = rand(n); y = rand(n);
result1 = TSPDroneHGATAC.solve_tspd(x, y, truck_speed=1.0, drone_speed=2.0)
# compare with TSPDrone.jl
using TSPDrone
result2 = TSPDrone.solve_tspd(x, y, 1.0, 0.5)
@show result1.best_total_cost
@show result2.total_cost
You can also input the distance cost matrices for the truck and the drone directly.
using TSPDroneHGATAC
n = 10
dist_mtx = rand(n, n)
dist_mtx = dist_mtx + dist_mtx' # symmetric distance only
for i in 1:n # diagonal needs to be zero
dist_mtx[i, i] = 0.0
end
truck_cost_mtx = dist_mtx .* 1.0
drone_cost_mtx = truck_cost_mtx .* 0.5
result1 = TSPDroneHGATAC.solve_tspd(truck_cost_mtx, drone_cost_mtx)
# compare with TSPDrone.jl
using TSPDrone
result2 = TSPDrone.solve_tspd(truck_cost_mtx, drone_cost_mtx)
@show result1.best_total_cost
@show result2.total_cost
Based on the coordinates:
using TSPDroneHGATAC
n = 10
x = rand(n); y = rand(n);
result1 = TSPDroneHGATAC.solve_fstsp(x, y; truck_speed=1.0, drone_speed=2.0, flying_range=0.5, retrieval_time=0.1, launching_time=0.1)
@show result1.best_total_cost
Based on the cost matrices:
using TSPDroneHGATAC
n = 10
dist_mtx = rand(n, n)
dist_mtx = dist_mtx + dist_mtx' # symmetric distance only
for i in 1:n # diagonal needs to be zero
dist_mtx[i, i] = 0.0
end
truck_cost_mtx = dist_mtx ./ 1.0
drone_cost_mtx = truck_cost_mtx ./ 2.0
result1 = TSPDroneHGATAC.solve_fstsp(truck_cost_mtx, drone_cost_mtx; flying_range=0.5, retrieval_time=0.1, launching_time=0.1)
@show result1.best_total_cost