traveling salesman problem where the salesman has to reload packages at one of the reload stations due to range and carrying capacity
2 ビュー (過去 30 日間)
古いコメントを表示
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!
2 件のコメント
John D'Errico
2017 年 5 月 29 日
編集済み: John D'Errico
2017 年 5 月 29 日
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
2017 年 5 月 29 日
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 .
回答 (0 件)
参考
カテゴリ
Help Center および File Exchange で Particle Swarm についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!