基于改进遗传算法的卡车和两架无人机旅行推销员问题（D2TSP）Matlab代码.zip

% D2TSP_GA Truck and 2 drones Tream Traveling Salesmen Problem %% % Truck and two Drones Traveling Salesman Problem: % (D2-TSP) To run default values, just press the run button! % % The idea is to use a truck and two drones in tandem to deliver % small parcels to randomly distributed customers such that % all stops are delivered to by a truck or a drone % exactly once then return to starting location (depot). Both drones % are constrained by range and capacity. Each drone must rendezvous % back with the truck at a downtream stop to swap out drone battery. % Each drone may visit 1 to 3 stops based on capacity before returning % to the truck. The central idea is found in literature under the key % word (last mile, drone delivery, drone TSP, two drone TSP). % % Algorithm highlights: Genetic Algorithm (GA). Finds a (near) optimal % solution to the d2-TSP (D2TSP or d2TSP) by setting up a GA to search % for the shortest timed route - least time needed for the in-tandem team % to travel and deliver to all stops (i.e. UPS/FedEx) and then return to % their starting locations-depots. For each operation launch-deliver- % rendezvous, the max time of the truck or either drone is used to % calculate the time for the route. The objective of the algorithm is to % minimize total time for team, return the route for truck, 2 drones, and % to denote where the operations take place. % % Summary: % 1. Each truck drone team travels to a their own stops and then % rendezvous at an operation start/end for recharging the drones. % 2. Each stop is visited by a truck, a drone, or both (rendezvous op). % 3. Drone are constrained by capacity and range and must return to % truck at the end of range and to pick up another parcel to % deliver. % 4. Energy is also calculated as this is becoming a more interesting % topic for drone deliveries. % 5. % Input: % USERCONFIG (structure) with zero or more of the following fields: % Input variables as a structure: example and description % defaultConfig.nCities = 50;(integer) number of stops or deliveries % defaultConfig.capacity = 3; (integer) for drone capacity (1,2,3) % defaultConfig.range = 10;(real) drone range (10, 15, 20) % defaultConfig.speed = 2; (integer)drone speed as factor of % truck speed at 35km/hr. % defaultConfig.energy = 5e4; (real) drone energy J/km % defaultConfig.energyP = 5e4; (real) drone energy J/parcel-km % defaultConfig.energyT = 8.08e6; (real) truck energy J/km % defaultConfig.energyTP = 4.04e4; (real) truck J/parcel-km % defaultConfig.cost = .04; (real) drone cost/km % defaultConfig.costT = .70; (real) truck cost/km % defaultConfig.xy = 10*rand(defaultConfig.nCities,2); % randomly generated coordinates of stops % defaultConfig.dmat = []; (real) distance matrix % defaultConfig.popSize = 200; (integer) population size % defaultConfig.numIter = 2.5e2; (integer) number of iterations % defaultConfig.showProg = true; (boolean) show progress of route % defaultConfig.showResult = true; (boolean) show results-output % defaultConfig.showWaitbar = false; (boolean) show wait bar % Input Notes: % 1. Rather than passing in a structure containing these fields, any of % these inputs can be passed in as parameter/value pairs in any order. % 2. Field/parameter names are case insensitive. % % Output: The results are displayed in the command prompt upon completion. % The the inputs above as well as note below on outputs for % for descriptions on each field. % RESULTSTRUCT (structure) with comprised of various fields: % 'xy', xy, ... % 'dmat', dmat, ... % 'popSize', popSize, ... % 'numIter', numIter, ... % 'showProg', showProg, ... % 'showResult', showResult, ... % 'showWaitbar', showWaitbar, ... % 'optRoute', optRoute, ... % 'opOps', opOps, ... % 'opTrk', opTrk, ... % 'opDrn', opDrn, ... % 'opDrn2', opDrn2, ... % 'nCities', nCities, ... % 'cap', cap, ... % 'range', range, ... % 'speed', speed, ... % 'cost', cost, ... % 'costT', costT, ... % 'energy', energy, ... % 'energyT', energyT, ... % 'energyP', energyP, ... % 'energyTP', energyTP, ... % 'minEnergy', minEnergy, ... % 'minEnergyP', minEnergyP, ... % 'minCost', minCost, ... % 'minTime', minTime, ... % 'minDist', minDist); % % Route/Operations Details: % There is one truck and two drones in this scenario (d2TSP). % Therefore a possible truck rout rte = [5 6 9 1 4 2 8 10 3 7] % possible capacity(2) drone rout of 2 rte2 = [5 10 11 9 12 14 8 15 7] % possible operations ops = [5 9 8 7] % These are found by taking the binary routes (trk, drn, ops) and % multiplying by the opt route (working generic route) % Once multiled, remove zeros and these denote the truck route % solution, drone route solution as well as the rendezvous operations % where the truck swaps out a battery for the drone. As such: % . Truck 1: travels stops 5, 6, 9, 1, 4, 8, 10, 3, 7 then 5 % . Drone 1: travels from stop 5, 10, 11, 9, 12, 14, 8, 15, 7,5 % . Operations: team rendezvous at 5, 9, 8, 7 % % Usage: % dtsp_ga % -or- % dtsp_ga(userConfig) % -or- % resultStruct = dtsp_ga; % -or- % resultStruct = dtsp_ga(userConfig); % -or- % [...] = dtsp_ga('Param1',Value1,'Param2',Value2, ...); % % Examples (function only): % dtsp_ga; % function call % resultStruct = dtsp_ga; % function call with results % % Examples (pass in simple stuctures values directly % userConfig = struct('xy',10*rand(35,2)); % resultStruct = dtsp_ga(userConfig); % % % Change the defaults for GA population size and number of iterations % userConfig = struct('popSize',200,'numIter',1e4); % resultStruct = dtsp_ga(userConfig); % % % Turn off the plots but show a waitbar % userConfig = struct('showProg',false,'showResult',false,'showWaitbar',true); % resultStruct = dtsp_ga(userConfig); % % Acknowledgement/Attribution: based in part on the principles of % genetic algorithms for sequencing (mutations) as depicted by % by Joseph Kirk - author/contributor to MATLAB, 2010-2016. % % Primary Author: Robert K. Rich % Email: rrich1000@gmail.com % Release: 1.0 % Release Date: 012/10/2016 % keywords also: tsp_ga,dtsp_ga, d2tsp_ga, mtsp_ga, genetic algorithms function [varargout ] = d2tsp_ga(varargin) % Initialize default configuration defaultConfig.nCities = 30; %number stops defaultConfig.capacity = 3; %drone capacity (1,2,3) defaultConfig.range = 10; %(10, 15, 20) defaultConfig.speed = 2; %drone speed factor of truck =1 defaultConfig.energy = 5e4; %(drone 5e4, 1e5, 2e5) defaultConfig.energyP = 5e4; %(drone 5e4, 1e5, 1.3e4) defaultConfig.energyT = 8.08e6; %(truck 8.08e6, 6.0e6) defaultConfig.energyTP = 4.04e4; %(truck , 4.04e4, 1.2e5) defaultConfig.cost = .04; % $0.04, $0.08, $0.20 defaultConfig.costT = .70; % $0.70, $0.40 defaultConfig.xy = 10*rand(defaultConfig.nCities,2); defaultConfig.dmat = []; %dist matrix defaultConfig.popSize = 200; %population size defaultConfig.numIter = 2.5e2; %1.25e3; %iterations