基于遺傳算法卡車無人機旅行推銷員問題（Matlab代碼實作）

📋1 概述

本文利用遺傳算法解決了卡車無人機串聯或包裹遞送操作（即UPS，FedEx）的旅行推銷員問題的“最後一英裡”問題。每輛卡車都攜帶一架無人機，該無人機從一個站點發射，将範圍内的包裹運送到附近的站點，同時與卡車并行運作。卡車和無人機并行工作以運送包裹。無人機受到航程和容量的限制。是以，它必須作為操作在卡車附近運作。操作是指卡車發射無人機，卡車和無人機運送到不同的位置，然後卡車在會合地點回收無人機以進行電池更換和裝載。這個想法是确定卡車和無人機（以及操作）的路線，以最大限度地減少總時間。總時間基于操作（啟動-傳遞-恢複）的時間。操作（卡車或無人機）的最大時間用于計算路徑的總時間。

📝2 運作結果

部分代碼：

% Find the Best Route in the Population
         [minDist,index] = min(totalDist);
         distHistory(iter) = minDist;
         if minDist < globalMin
             globalMin  = minDist; 
             optPop2    = pop2(index,:);
             optPop1    = pop(index,:);
             if showprogress % gaph results
                 
                 tr_route = (optPop2==0).*optPop1;
                 tr_route = tr_route(tr_route>0);
                 tr_route = [tr_route tr_route(1)];
                 if optPop2(n)==1
                    dr_route = [optPop1 optPop1(1) ];
                 else
                    dr_route = [optPop1 ];
                 end
                 plot(xy(dr_route,1), xy(dr_route,2), 'k.--'); hold on;
                 plot(xy(tr_route,1),  xy(tr_route,2),'ks-');  
                 xlabel('x-coordinate (km)');
                 ylabel('y-coordinate (km)');
                 legend('drone','truck');
                  title(sprintf('Truck-1-drone time %1.1f',minDist)); 
                 hold off;   
                 drawnow;
             end  
         end
         
         % Genetic Algorithm Operators
         randomOrder = randperm(popSize);        for p = 5:5:popSize
                 % basically a random sampling in matrix format with a 
             rtes   = pop(randomOrder(p-4:p),:); 
       
             dists = totalDist(randomOrder(p-4:p));
                 % what are the min distances?
             [~,idx] = min(dists); 
                 % what is the best route
             bestOf5Route  = rtes(idx,:);
      
                 % randomly select two route insertion points and sort
             routeInsertionPoints = sort(ceil(n*rand(1,2)));                I = routeInsertionPoints(1); 
                 J = routeInsertionPoints(2);                
             for k = 1:5 % Mutate the Best row (dist) to get Three New Routes and orig.
                 % a small matrix of 4 rows of best time
                 tmpPop(k,:)  = bestOf5Route;
         
                 switch k
                        % flip two of the cities and cities between
                     case 2 % Flip
                            tmpPop(k,I:J) = tmpPop(k,J:-1:I);
                             
                     case 3 % Swap
                            tmpPop(k,[I J]) = tmpPop(k,[J I]);
                     case 4 % Slide segment 
                            tmpPop(k,I:J) = tmpPop(k,[I+1:J I]); 
 %                            tmpPop2(k,I2)=flag;
                     case 5 % increment sequence one space 
                             tmpPop(k,1:end) = tmpPop(k,[2:end 1]);                    otherwise % Do Nothing
                 end
             end
              % using the original population, create a new population
             newPop(p-4:p,:) = tmpPop; 
         end
         pop = newPop;  % update entire populations with mutations  end
  res=[optPop2;
       optPop1]      

📃3 參考文獻

📋4 Matlab代碼實作