traveling salesman problem where the salesman has to reload packages at one of the reload stations due to range and carrying capacity

Hello Matlab community,

I have to design an algorithm that finds the shortest route for an UAV that has to deliver packages to customers. The UAV is able to carry multiple packages but has a weight and an range constraint. There is a truck with batteries and packages in the back and the UAV can swap battery an get new packages at a truckstop. Only the UAV is allowed to deliver packages, not the truck. Does anyone have an algorithm that looks slightly like this, or is able to help me to alter an generic algorithm for example.

Thanks!

[John D'Errico]

This is probably a homework project for you, and we try not to do homework projects for people, as it is the thinking through a problem that helps you to learn, because you need to learn to think.

Regardless, this is a long way from being a question about MATLAB, as you have yet no idea what algorithm you would even use to solve it. You cannot write MATLAB code until you know exactly what the code must do. So I expect the odds are pretty small that you get a good, usable answer in a reasonable time. And if this really is homework, then I hope that nobody actually does your work for you.

No matter what, no algorithm will be assured of finding a globally optimal solution, as this problem will be very complex if it is at all large. So look for a simple scheme that will work decently. The point is, greedy algorithms are often good choices when no other idea percolates up. Find a scheme that works decently. Then as time permits, look for improvements. At some point, an AHA! moment might happen, when you see the light to a truly great solution. Until then, accept a viable solution.

[Walter Roberson]

If the truck is at a fixed location, and if the packages are all the same weight, then this is a Capacitated Vehicle Routing Problem. If the packages are different weights then you start to add in Knapsack Problem difficulties.

If the truck moves, then planning for the truck has to be added in, and you also need to add in the question of whether the UAV can hitch a ride with the truck to the next truckstop .