Operation research using Matlab
ammcllagraphyproject 421 Term 161
Objective 1:
a. Assumptions:
By using initial Random node (min tour)
With Min total distance
b. Methodology:
We tried to solve this problem by using GAMS but the the problem GAMS was running for about three days without any optimal solution
So we use Heuristic method to find the initial solution
For 1- 6 spaceships.
We use MATLAB to find the min total distance as following:
c. Solutions
After that we got the solution and the best tour for each spaceship as following
Figure 1screen shot of the matlab program
Matlab code:
function varargout = mtspf_ga(varargin)
% Initialize default configuration
defaultConfig.xy = 10*rand(401,3);
defaultConfig.dmat = [
0 82.68615362 102.3767552 125.7696307 113.9605195 102.5816748 79.71198153 79.63039621 105.3897528 101.4199191 118.6001686 109.4897255 109.7816014 95.38343672 113.2166066 122.6947432 118.3638458 130.1768028 .
.
.
156.0801076 193.5071058 212.6734586 193.5484435 134.4172608 224.182961 145.8389523 95.50916186 183.3930206 231.8296789 156.2466 48.36320916 163.5389862 211.7947119 62.10475022 141.4284271 0
];
defaultConfig.nSalesmen = 1;
defaultConfig.minTour = 2;
defaultConfig.popSize = 80;
defaultConfig.numIter = 1000000;
defaultConfig.showProg = true;
defaultConfig.showResult = true;
defaultConfig.showWaitbar = false;
% Interpret user configuration inputs
if ~nargin
userConfig = struct();
elseif isstruct(varargin{1})
userConfig = varargin{1};
else
try
userConfig = struct(varargin{:});
catch
error('Expected inputs are either a structure or parameter/value pairs');
end
end
% Override default configuration with user inputs
configStruct = get_config(defaultConfig,userConfig);
% Extract configuration
xy = configStruct.xy;
dmat = configStruct.dmat;
nSalesmen = configStruct.nSalesmen;
minTour = configStruct.minTour;
popSize = configStruct.popSize;
numIter = configStruct.numIter;
showProg = configStruct.showProg;
showResult = configStruct.showResult;
showWaitbar = configStruct.showWaitbar;
if isempty(dmat)
nPoints = size(xy,1);
a = meshgrid(1:nPoints);
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),nPoints,nPoints);
end
% Verify Inputs
[N,dims] = size(xy);
[nr,nc] = size(dmat);
if N ~= nr || N ~= nc
error('Invalid XY or DMAT inputs!')
end
n = N - 1; % Separate Start/End City
% Sanity Checks
nSalesmen = max(1,min(n,round(real(nSalesmen(1)))));
minTour = max(1,min(floor(n/nSalesmen),round(real(minTour(1)))));
popSize = max(8,8*ceil(popSize(1)/8));
numIter = max(1,round(real(numIter(1))));
showProg = logical(showProg(1));
showResult = logical(showResult(1));
showWaitbar = logical(showWaitbar(1));
% Initializations for Route Break Point Selection
nBreaks = nSalesmen-1;
dof = n - minTour*nSalesmen; % degrees of freedom
addto = ones(1,dof+1);
for k = 2:nBreaks
addto = cumsum(addto);
end
cumProb = cumsum(addto)/sum(addto);
% Initialize the Populations
popRoute = zeros(popSize,n); % population of routes
popBreak = zeros(popSize,nBreaks); % population of breaks
popRoute(1,:) = (1:n) + 1;
popBreak(1,:) = rand_breaks();
for k = 2:popSize
popRoute(k,:) = randperm(n) + 1;
popBreak(k,:) = rand_breaks();
end
% Select the Colors for the Plotted Routes
pclr = ~get(0,'DefaultAxesColor');
clr = [1 0 0; 0 0 1; 0.67 0 1; 0 1 0; 1 0.5 0];
if nSalesmen > 5
clr = hsv(nSalesmen);
end
% Run the GA
globalMin = Inf;
totalDist = zeros(1,popSize);
distHistory = zeros(1,numIter);
tmpPopRoute = zeros(8,n);
tmpPopBreak = zeros(8,nBreaks);
newPopRoute = zeros(popSize,n);
newPopBreak = zeros(popSize,nBreaks);
if showProg
figure('Name','MTSPF_GA | Current Best Solution','Numbertitle','off');
hAx = gca;
end
if showWaitbar
hWait = waitbar(0,'Searching for near-optimal solution ...');
end
for iter = 1:numIter
% Evaluate Members of the Population
for p = 1:popSize
d = 0;
pRoute = popRoute(p,:);
pBreak = popBreak(p,:);
rng = [[1 pBreak+1];[pBreak n]]';
for s = 1:nSalesmen
d = d + dmat(1,pRoute(rng(s,1))); % Add Start Distance
for k = rng(s,1):rng(s,2)-1
d = d + dmat(pRoute(k),pRoute(k+1));
end
d = d + dmat(pRoute(rng(s,2)),1); % Add End Distance
end
totalDist(p) = d;
end
% Find the Best Route in the Population
[minDist,index] = min(totalDist);
distHistory(iter) = minDist;
if minDist < globalMin
globalMin = minDist;
optRoute = popRoute(index,:);
optBreak = popBreak(index,:);
rng = [[1 optBreak+1];[optBreak n]]';
if showProg
% Plot the Best Route
for s = 1:nSalesmen
rte = [1 optRoute(rng(s,1):rng(s,2)) 1];
if dims > 2, plot3(hAx,xy(rte,1),xy(rte,2),xy(rte,3),'.-','Color',clr(s,:));
else plot(hAx,xy(rte,1),xy(rte,2),'.-','Color',clr(s,:)); end
hold(hAx,'on');
end
if dims > 2, plot3(hAx,xy(1,1),xy(1,2),xy(1,3),'o','Color',pclr);
else plot(hAx,xy(1,1),xy(1,2),'o','Color',pclr); end
title(hAx,sprintf('Total Distance = %1.4f, Iteration = %d',minDist,iter));
hold(hAx,'off');
drawnow;
end
end
% Genetic Algorithm Operators
randomOrder = randperm(popSize);
for p = 8:8:popSize
rtes = popRoute(randomOrder(p-7:p),:);
brks = popBreak(randomOrder(p-7:p),:);
dists = totalDist(randomOrder(p-7:p));
[ignore,idx] = min(dists); %#ok
bestOf8Route = rtes(idx,:);
bestOf8Break = brks(idx,:);
routeInsertionPoints = sort(ceil(n*rand(1,2)));
I = routeInsertionPoints(1);
J = routeInsertionPoints(2);
for k = 1:8 % Generate New Solutions
tmpPopRoute(k,:) = bestOf8Route;
tmpPopBreak(k,:) = bestOf8Break;
switch k
case 2 % Flip
tmpPopRoute(k,I:J) = tmpPopRoute(k,J:-1:I);
case 3 % Swap
tmpPopRoute(k,[I J]) = tmpPopRoute(k,[J I]);
case 4 % Slide
tmpPopRoute(k,I:J) = tmpPopRoute(k,[I+1:J I]);
case 5 % Modify Breaks
tmpPopBreak(k,:) = rand_breaks();
case 6 % Flip, Modify Breaks
tmpPopRoute(k,I:J) = tmpPopRoute(k,J:-1:I);
tmpPopBreak(k,:) = rand_breaks();
case 7 % Swap, Modify Breaks
tmpPopRoute(k,[I J]) = tmpPopRoute(k,[J I]);
tmpPopBreak(k,:) = rand_breaks();
case 8 % Slide, Modify Breaks
tmpPopRoute(k,I:J) = tmpPopRoute(k,[I+1:J I]);
tmpPopBreak(k,:) = rand_breaks();
otherwise % Do Nothing
end
end
newPopRoute(p-7:p,:) = tmpPopRoute;
newPopBreak(p-7:p,:) = tmpPopBreak;
end
popRoute = newPopRoute;
popBreak = newPopBreak;
% Update the waitbar
if showWaitbar && ~mod(iter,ceil(numIter/325))
waitbar(iter/numIter,hWait);
end
end
if showWaitbar
close(hWait);
end
if showResult
% Plots
figure('Name','MTSPF_GA | Results','Numbertitle','off');
subplot(2,2,1);
if dims > 2, plot3(xy(:,1),xy(:,2),xy(:,3),'.','Color',pclr);
else plot(xy(:,1),xy(:,2),'.','Color',pclr); end
title('planet Locations');
subplot(2,2,2);
imagesc(dmat([1 optRoute],[1 optRoute]));
title('Distance Matrix');
subplot(2,2,3);
rng = [[1 optBreak+1];[optBreak n]]';
for s = 1:nSalesmen
rte = [1 optRoute(rng(s,1):rng(s,2)) 1];
if dims > 2, plot3(xy(rte,1),xy(rte,2),xy(rte,3),'.-','Color',clr(s,:));
else plot(xy(rte,1),xy(rte,2),'.-','Color',clr(s,:)); end
title(sprintf('Total Distance = %1.4f',minDist));
hold on;
a = optRoute
b = optBreak
end
if dims > 2, plot3(xy(1,1),xy(1,2),xy(1,3),'o','Color',pclr);
else plot(xy(1,1),xy(1,2),'o','Color',pclr); end
subplot(2,2,4);
plot(distHistory,'b','LineWidth',2);
title('Best Solution History');
set(gca,'XLim',[0 numIter+1],'YLim',[0 1.1*max([1 distHistory])]);
end
% Return Output
if nargout
resultStruct = struct( ...
'xy', xy, ...
'dmat', dmat, ...
'nSalesmen', nSalesmen, ...
'minTour', minTour, ...
'popSize', popSize, ...
'numIter', numIter, ...
'showProg', showProg, ...
'showResult', showResult, ...
'showWaitbar', showWaitbar, ...
'optRoute', optRoute, ...
'optBreak', optBreak, ...
'minDist', minDist);
varargout = {resultStruct};
end
% Generate Random Set of Break Points
function breaks = rand_breaks()
if minTour == 1 % No Constraints on Breaks
tmpBreaks = randperm(n-1);
breaks = sort(tmpBreaks(1:nBreaks));
else % Force Breaks to be at Least the Minimum Tour Length
nAdjust = find(rand < cumProb,1)-1;
spaces = ceil(nBreaks*rand(1,nAdjust));
adjust = zeros(1,nBreaks);
for kk = 1:nBreaks
adjust(kk) = sum(spaces == kk);
end
breaks = minTour*(1:nBreaks) + cumsum(adjust);
end
end
end
% Subfunction to override the default configuration with user inputs
function config = get_config(defaultConfig,userConfig)
% Initialize the configuration structure as the default
config = defaultConfig;
% Extract the field names of the default configuration structure
defaultFields = fieldnames(defaultConfig);
% Extract the field names of the user configuration structure
userFields = fieldnames(userConfig);
nUserFields = length(userFields);
% Override any default configuration fields with user values
for i = 1:nUserFields
userField = userFields{i};
isField = strcmpi(defaultFields,userField);
if nnz(isField) == 1
thisField = defaultFields{isField};
config.(thisField) = userConfig.(userField);
end
end
end
1- Space shipment 1:
Solution:
The total distance = 8581.0086
Number of iterations = 80072
Route for spaceship one:
For all tours Starting from earth and end with earth and passing through these planets by sequence
a = optRoute
b = optBreak
a =
Columns 1 through 15
63 74 228 173 283 272 261 227 331 92 347 254 314 183 238
Columns 16 through 30
257 179 156 371 134 73 214 243 338 28 321 155 209 296 208
Columns 31 through 45
306 322 339 98 398 187 344 217 184 167 71 20 278 262 386
Columns 46 through 60
327 251 93 234 379 380 258 177 49 182 397 317 198 256 277
Columns 61 through 75
224 97 159 395 253 94 192 31 390 123 101 130 250 235 381
Columns 76 through 90
337 335 80 96 264 27 113 75 38 58 111 135 54 273 84
Columns 91 through 105
384 144 160 342 171 232 236 124 129 309 298 191 391 114 320
Columns 106 through 120
23 90 263 151 268 89 269 3 82 152 382 164 203 176 5
Columns 121 through 135
11 48 29 34 81 86 336 165 376 12 44 240 292 222 202
Columns 136 through 150
145 37 375 154 332 199 147 255 116 57 368 245 88 87 340
Columns 151 through 165
13 68 118 161 319 62 189 127 360 313 66 2 10 211 326
Columns 166 through 180
387 310 302 121 294 282 4 287 312 200 175 56 242 288 170
Columns 181 through 195
149 300 169 316 51 266 166 181 39 369 120 128 311 248 137
Columns 196 through 210
79 237 109 274 60 110 46 389 85 271 324 348 72 359 223
Columns 211 through 225
328 148 216 100 367 18 230 307 305 206 249 401 61 131 52
Columns 226 through 240
195 293 345 26 201 356 108 76 69 8 218 197 372 7 399
Columns 241 through 255
133 16 36 157 212 117 220 392 378 363 289 180 259 358 99
Columns 256 through 270
231 226 196 281 323 275 303 158 194 193 207 396 286 40 95
Columns 271 through 285
14 364 229 205 334 178 233 153 35 400 67 25 385 247 325
Columns 286 through 300
42 362 55 15 47 136 219 315 353 9 370 301 333 329 383
Columns 301 through 315
304 132 162 112 343 59 19 241 30 374 239 139 119 393 103
Columns 316 through 330
267 91 388 221 244 213 299 122 70 146 50 297 373 355 354
Columns 331 through 345
350 186 168 351 357 252 41 279 65 366 394 6 24 142 349
Columns 346 through 360
64 185 270 188 265 280 126 17 377 102 150 78 284 365 141
Columns 361 through 375
104 53 341 45 330 43 106 77 107 318 125 83 115 276 210
Columns 376 through 390
308 246 33 32 22 138 290 361 291 172 215 143 346 285 140
Columns 391 through 400
260 21 295 105 163 352 204 190 174 225
b =
Empty matrix: 1-by-0
2- Space shipment 2:
Solution:
The total distance = 8615.1068
Number of iterations = 982625
Routes for two spaceships:
Starting from earth and end with earth and passing through these planets by sequence
a = optRoute
b = optBreak
Tour 1 for spaceship one:
a =
Columns 1 through 15
190 174 225 63 74 228 173 237 79 109 274 46 60 110 374
Columns 16 through 30
30 241 19 239 139 119 393 103 267 91 388 299 122 70 146
Columns 31 through 45
162 112 132 272 283 304 383 329 35 153 333 364 229 205 334
Columns 46 through 60
178 233 400 67 25 385 247 325 10 261 227 331 347 254 314
Columns 61 through 75
78 150 366 65 92 354 279 41 252 350 186 355 373 297 50
Columns 76 through 90
168 351 357 24 6 394 377 102 17 126 98 398 187 32 54
Columns 91 through 105
135 346 215 143 165 306 155 208 296 209 34 81 86 336 44
Columns 106 through 120
12 376 57 147 375 154 332 199 240 255 116 127 189 62 319
Columns 121 through 135
161 13 68 340 87 368 245 88 257 238 183 179 156 134 73
Columns 136 through 150
214 243 338 28 321 322 339 344 217 184 71 20 278 188 270
Columns 151 through 165
265 280 167 33 246 308 284 365 141 104 53 64 349 142 185
Columns 166 through 180
77 107 318 125 83 115 327 59 262 386 251 234 93 236 231
Columns 181 through 195
226 395 159 97 256 277 224 323 196 281 193 194 275 303 158
Columns 196 through 210
207 14 95 301 370 131 52 396 286 40 100 216 148 328 223
Columns 211 through 225
359 72 348 324 389 85 271 221 244 213 343 106 43 330 45
Columns 226 through 240
341 276 210 182 198 317 397 49 177 258 380 379 337 80 335
Columns 241 through 255
38 75 113 250 235 381 130 101 123 390 31 192 94 253 129
Columns 256 through 270
124 309 171 232 160 342 96 264 144 384 27 273 111 58 84
Columns 271 through 285
285 140 260 21 295 105 163 352 204 172 291 361 290 22 138
Columns 286 through 300
371 181 37 145 202 222 292 29 48 11 5 176 203 164 382
Columns 301 through 315
152 82 269 3 399 7 372 197 218 8 69 76 108 133 16
Columns 316 through 330
36 157 212 117 220 392 89 268 378 363 289 180 259 358 99
Columns 331 through 345
298 191 391 114 320 23 90 263 151 201 356 26 345 293 195
Columns 346 through 360
401 61 249 206 305 307 230 18 367 9 353 315 219 136 242
Columns 361 through 375
56 287 4 42 362 55 15 47 282 294 121 302 310 387 211
Columns 376 through 390
326 118 200 312 175 360 313 166 266 51 316 2 66 288 170
Columns 391 through 400
149 169 300 137 248 311 128 120 369 39
b =
3
Tour 2 for spaceship two:
a =
Columns 1 through 15
190 174 225 63 74 228 173 237 79 109 274 46 60 110 374
Columns 16 through 30
30 241 19 239 139 119 393 103 267 91 388 299 122 70 146
Columns 31 through 45
162 112 132 272 283 304 383 329 35 153 333 364 229 205 334
Columns 46 through 60
178 233 400 67 25 385 247 325 10 261 227 331 347 254 314
Columns 61 through 75
78 150 366 65 92 354 279 41 252 350 186 355 373 297 50
Columns 76 through 90
168 351 357 24 6 394 377 102 17 126 98 398 187 32 54
Columns 91 through 105
135 346 215 143 165 306 155 208 296 209 34 81 86 336 44
Columns 106 through 120
12 376 57 147 375 154 332 199 240 255 116 127 189 62 319
Columns 121 through 135
161 13 68 340 87 368 245 88 257 238 183 179 156 134 73
Columns 136 through 150
214 243 338 28 321 322 339 344 217 184 71 20 278 188 270
Columns 151 through 165
265 280 167 33 246 308 284 365 141 104 53 64 349 142 185
Columns 166 through 180
77 107 318 125 83 115 327 59 262 386 251 234 93 236 231
Columns 181 through 195
226 395 159 97 256 277 224 323 196 281 193 194 275 303 158
Columns 196 through 210
207 14 95 301 370 131 52 396 286 40 100 216 148 328 223
Columns 211 through 225
359 72 348 324 389 85 271 221 244 213 343 106 43 330 45
Columns 226 through 240
341 276 210 182 198 317 397 49 177 258 380 379 337 80 335
Columns 241 through 255
38 75 113 250 235 381 130 101 123 390 31 192 94 253 129
Columns 256 through 270
124 309 171 232 160 342 96 264 144 384 27 273 111 58 84
Columns 271 through 285
285 140 260 21 295 105 163 352 204 172 291 361 290 22 138
Columns 286 through 300
371 181 37 145 202 222 292 29 48 11 5 176 203 164 382
Columns 301 through 315
152 82 269 3 399 7 372 197 218 8 69 76 108 133 16
Columns 316 through 330
36 157 212 117 220 392 89 268 378 363 289 180 259 358 99
Columns 331 through 345
298 191 391 114 320 23 90 263 151 201 356 26 345 293 195
Columns 346 through 360
401 61 249 206 305 307 230 18 367 9 353 315 219 136 242
Columns 361 through 375
56 287 4 42 362 55 15 47 282 294 121 302 310 387 211
Columns 376 through 390
326 118 200 312 175 360 313 166 266 51 316 2 66 288 170
Columns 391 through 400
149 169 300 137 248 311 128 120 369 39
b =
3
3- Space shipment 3:
Solution:
The total distance = 9086.2961
Number of iterations = 903444
Routes for three spaceships:
Starting from earth and end with earth and passing through these planets by sequence
a = optRoute
b = optBreak
Tour 1 for spaceship one:
a =
Columns 1 through 15
63 74 283 272 331 227 261 10 68 13 118 302 121 310 326
Columns 16 through 30
211 387 247 325 42 4 287 200 294 282 47 15 362 55 149
Columns 31 through 45
329 383 400 67 25 385 2 66 170 288 136 219 315 353 9
Columns 46 through 60
370 301 95 364 229 389 348 324 139 239 119 393 103 271 85
Columns 61 through 75
244 213 221 267 91 388 299 122 70 162 112 343 46 60 110
Columns 76 through 90
241 19 30 374 281 196 323 275 303 158 194 193 289 363 378
Columns 91 through 105
151 268 89 392 220 117 212 157 36 269 3 105 163 204 352
Columns 106 through 120
263 90 140 260 21 295 152 82 222 202 145 7 372 399 133
Columns 121 through 135
16 401 61 249 206 305 307 230 18 367 100 216 148 328 72
Columns 136 through 150
359 223 14 207 396 286 40 131 52 76 69 8 108 356 201
Columns 151 through 165
195 293 345 26 79 237 109 274 173 228 297 373 355 186 350
Columns 166 through 180
146 107 77 106 43 330 45 341 276 115 327 251 386 262 59
Columns 181 through 195
83 125 318 185 366 65 92 347 254 314 183 238 257 156 179
Columns 196 through 210
88 245 368 87 340 62 189 127 116 255 147 332 199 29 34
Columns 211 through 225
81 11 5 176 203 164 382 48 285 346 209 296 208 155 321
Columns 226 through 240
28 338 22 32 49 177 258 380 234 93 236 232 124 129 309
Columns 241 through 255
253 94 192 171 342 160 191 23 320 114 391 298 180 259 358
Columns 256 through 270
99 231 226 395 159 97 224 277 256 198 317 397 182 210 308
Columns 271 through 285
246 33 126 17 98 398 243 214 73 134 371 138 290 361 291
Columns 286 through 300
172 135 54 273 75 113 250 235 130 101 123 390 31 381 337
Columns 301 through 315
379 38 335 80 96 264 27 384 144 84 111 58 190 225 174
Columns 316 through 330
120 128 166 266 51 316 57 313 360 319 161 312 175 56 242
Columns 331 through 345
197 218 311 248 300 169 137 333 35 153 334 205 178 233 304
Columns 346 through 360
132 50 168 351 357 252 354 279 41 24 394 6 142 349 64
Columns 361 through 375
53 104 141 365 284 78 150 102 377 265 280 270 188 278 20
Columns 376 through 390
71 167 184 217 344 187 339 322 306 165 376 12 336 86 44
Columns 391 through 400
240 292 143 215 154 375 37 181 369 39
b =
158 313
Tour 2 for spaceship two:
a =
Columns 1 through 15
63 74 283 272 331 227 261 10 68 13 118 302 121 310 326
Columns 16 through 30
211 387 247 325 42 4 287 200 294 282 47 15 362 55 149
Columns 31 through 45
329 383 400 67 25 385 2 66 170 288 136 219 315 353 9
Columns 46 through 60
370 301 95 364 229 389 348 324 139 239 119 393 103 271 85
Columns 61 through 75
244 213 221 267 91 388 299 122 70 162 112 343 46 60 110
Columns 76 through 90
241 19 30 374 281 196 323 275 303 158 194 193 289 363 378
Columns 91 through 105
151 268 89 392 220 117 212 157 36 269 3 105 163 204 352
Columns 106 through 120
263 90 140 260 21 295 152 82 222 202 145 7 372 399 133
Columns 121 through 135
16 401 61 249 206 305 307 230 18 367 100 216 148 328 72
Columns 136 through 150
359 223 14 207 396 286 40 131 52 76 69 8 108 356 201
Columns 151 through 165
195 293 345 26 79 237 109 274 173 228 297 373 355 186 350
Columns 166 through 180
146 107 77 106 43 330 45 341 276 115 327 251 386 262 59
Columns 181 through 195
83 125 318 185 366 65 92 347 254 314 183 238 257 156 179
Columns 196 through 210
88 245 368 87 340 62 189 127 116 255 147 332 199 29 34
Columns 211 through 225
81 11 5 176 203 164 382 48 285 346 209 296 208 155 321
Columns 226 through 240
28 338 22 32 49 177 258 380 234 93 236 232 124 129 309
Columns 241 through 255
253 94 192 171 342 160 191 23 320 114 391 298 180 259 358
Columns 256 through 270
99 231 226 395 159 97 224 277 256 198 317 397 182 210 308
Columns 271 through 285
246 33 126 17 98 398 243 214 73 134 371 138 290 361 291
Columns 286 through 300
172 135 54 273 75 113 250 235 130 101 123 390 31 381 337
Columns 301 through 315
379 38 335 80 96 264 27 384 144 84 111 58 190 225 174
Columns 316 through 330
120 128 166 266 51 316 57 313 360 319 161 312 175 56 242
Columns 331 through 345
197 218 311 248 300 169 137 333 35 153 334 205 178 233 304
Columns 346 through 360
132 50 168 351 357 252 354 279 41 24 394 6 142 349 64
Columns 361 through 375
53 104 141 365 284 78 150 102 377 265 280 270 188 278 20
Columns 376 through 390
71 167 184 217 344 187 339 322 306 165 376 12 336 86 44
Columns 391 through 400
240 292 143 215 154 375 37 181 369 39
b =
158 313
a =
Tour 3 for spaceship three:
Columns 1 through 15
63 74 283 272 331 227 261 10 68 13 118 302 121 310 326
Columns 16 through 30
211 387 247 325 42 4 287 200 294 282 47 15 362 55 149
Columns 31 through 45
329 383 400 67 25 385 2 66 170 288 136 219 315 353 9
Columns 46 through 60
370 301 95 364 229 389 348 324 139 239 119 393 103 271 85
Columns 61 through 75
244 213 221 267 91 388 299 122 70 162 112 343 46 60 110
Columns 76 through 90
241 19 30 374 281 196 323 275 303 158 194 193 289 363 378
Columns 91 through 105
151 268 89 392 220 117 212 157 36 269 3 105 163 204 352
Columns 106 through 120
263 90 140 260 21 295 152 82 222 202 145 7 372 399 133
Columns 121 through 135
16 401 61 249 206 305 307 230 18 367 100 216 148 328 72
Columns 136 through 150
359 223 14 207 396 286 40 131 52 76 69 8 108 356 201
Columns 151 through 165
195 293 345 26 79 237 109 274 173 228 297 373 355 186 350
Columns 166 through 180
146 107 77 106 43 330 45 341 276 115 327 251 386 262 59
Columns 181 through 195
83 125 318 185 366 65 92 347 254 314 183 238 257 156 179
Columns 196 through 210
88 245 368 87 340 62 189 127 116 255 147 332 199 29 34
Columns 211 through 225
81 11 5 176 203 164 382 48 285 346 209 296 208 155 321
Columns 226 through 240
28 338 22 32 49 177 258 380 234 93 236 232 124 129 309
Columns 241 through 255
253 94 192 171 342 160 191 23 320 114 391 298 180 259 358
Columns 256 through 270
99 231 226 395 159 97 224 277 256 198 317 397 182 210 308
Columns 271 through 285
246 33 126 17 98 398 243 214 73 134 371 138 290 361 291
Columns 286 through 300
172 135 54 273 75 113 250 235 130 101 123 390 31 381 337
Columns 301 through 315
379 38 335 80 96 264 27 384 144 84 111 58 190 225 174
Columns 316 through 330
120 128 166 266 51 316 57 313 360 319 161 312 175 56 242
Columns 331 through 345
197 218 311 248 300 169 137 333 35 153 334 205 178 233 304
Columns 346 through 360
132 50 168 351 357 252 354 279 41 24 394 6 142 349 64
Columns 361 through 375
53 104 141 365 284 78 150 102 377 265 280 270 188 278 20
Columns 376 through 390
71 167 184 217 344 187 339 322 306 165 376 12 336 86 44
Columns 391 through 400
240 292 143 215 154 375 37 181 369 39
b =
158 313
>>
4- Space shipment 4:
Solution:
The total distance = 9391.6361
Number of iterations = 949508
Routes for four spaceships:
Starting from earth and end with earth and passing through these planets by sequence
a = optRoute
b = optBreak
Tour 1 for spaceship one:
a =
Columns 1 through 15
104 141 365 284 32 75 113 27 384 264 96 335 80 250 235
Columns 16 through 30
234 93 251 386 262 278 20 71 167 184 217 344 187 398 98
Columns 31 through 45
17 126 280 265 188 270 185 142 349 64 53 272 283 331 92
Columns 46 through 60
65 366 347 88 245 368 87 340 319 62 189 127 116 44 86
Columns 61 through 75
336 12 376 165 306 134 314 254 150 78 102 377 394 6 24
Columns 76 through 90
41 279 252 354 355 186 350 357 351 168 50 132 112 162 146
Columns 91 through 105
70 122 299 244 389 46 60 110 241 30 374 119 139 239 19
Columns 106 through 120
59 327 276 43 45 74 63 317 198 256 277 224 97 159 395
Columns 121 through 135
253 94 192 31 390 123 101 130 381 337 379 38 58 291 361
Columns 136 through 150
290 138 22 73 214 243 338 54 273 111 84 144 160 342 171
Columns 151 through 165
232 236 124 129 309 298 191 391 114 320 23 259 180 289 358
Columns 166 through 180
99 231 226 196 323 281 193 194 303 275 378 363 158 293 201
Columns 181 through 195
356 195 401 61 396 207 223 359 216 100 367 18 353 9 311
Columns 196 through 210
8 69 345 26 120 128 3 269 16 36 157 212 117 220 392
Columns 211 through 225
90 263 352 204 190 174 225 274 109 79 333 301 370 40 286
Columns 226 through 240
95 364 229 14 328 148 72 348 324 393 103 267 91 388 221
Columns 241 through 255
271 85 205 334 153 35 400 67 25 385 247 310 325 42 362
Columns 256 through 270
55 15 47 242 136 219 315 230 307 305 206 249 131 52 76
Columns 271 through 285
108 218 197 372 7 399 133 151 268 89 295 105 163 21 260
Columns 286 through 300
140 285 34 81 29 48 11 5 176 203 164 382 152 82 222
Columns 301 through 315
202 292 240 199 145 166 51 266 169 300 137 248 369 39 397
Columns 316 through 330
182 49 380 258 177 33 246 308 210 341 330 77 107 318 125
Columns 331 through 345
115 83 106 343 213 178 233 297 373 387 227 261 10 211 326
Columns 346 through 360
302 121 294 282 4 287 56 175 312 200 118 68 13 161 360
Columns 361 through 375
313 255 147 332 154 215 143 172 135 346 209 296 208 155 321
Columns 376 through 390
28 339 322 183 238 257 179 156 371 181 37 375 57 316 2
Columns 391 through 400
66 288 170 149 329 383 304 228 173 237
b =
112 217 314
Tour 2 for spaceship two:
a =
Columns 1 through 15
104 141 365 284 32 75 113 27 384 264 96 335 80 250 235
Columns 16 through 30
234 93 251 386 262 278 20 71 167 184 217 344 187 398 98
Columns 31 through 45
17 126 280 265 188 270 185 142 349 64 53 272 283 331 92
Columns 46 through 60
65 366 347 88 245 368 87 340 319 62 189 127 116 44 86
Columns 61 through 75
336 12 376 165 306 134 314 254 150 78 102 377 394 6 24
Columns 76 through 90
41 279 252 354 355 186 350 357 351 168 50 132 112 162 146
Columns 91 through 105
70 122 299 244 389 46 60 110 241 30 374 119 139 239 19
Columns 106 through 120
59 327 276 43 45 74 63 317 198 256 277 224 97 159 395
Columns 121 through 135
253 94 192 31 390 123 101 130 381 337 379 38 58 291 361
Columns 136 through 150
290 138 22 73 214 243 338 54 273 111 84 144 160 342 171
Columns 151 through 165
232 236 124 129 309 298 191 391 114 320 23 259 180 289 358
Columns 166 through 180
99 231 226 196 323 281 193 194 303 275 378 363 158 293 201
Columns 181 through 195
356 195 401 61 396 207 223 359 216 100 367 18 353 9 311
Columns 196 through 210
8 69 345 26 120 128 3 269 16 36 157 212 117 220 392
Columns 211 through 225
90 263 352 204 190 174 225 274 109 79 333 301 370 40 286
Columns 226 through 240
95 364 229 14 328 148 72 348 324 393 103 267 91 388 221
Columns 241 through 255
271 85 205 334 153 35 400 67 25 385 247 310 325 42 362
Columns 256 through 270
55 15 47 242 136 219 315 230 307 305 206 249 131 52 76
Columns 271 through 285
108 218 197 372 7 399 133 151 268 89 295 105 163 21 260
Columns 286 through 300
140 285 34 81 29 48 11 5 176 203 164 382 152 82 222
Columns 301 through 315
202 292 240 199 145 166 51 266 169 300 137 248 369 39 397
Columns 316 through 330
182 49 380 258 177 33 246 308 210 341 330 77 107 318 125
Columns 331 through 345
115 83 106 343 213 178 233 297 373 387 227 261 10 211 326
Columns 346 through 360
302 121 294 282 4 287 56 175 312 200 118 68 13 161 360
Columns 361 through 375
313 255 147 332 154 215 143 172 135 346 209 296 208 155 321
Columns 376 through 390
28 339 322 183 238 257 179 156 371 181 37 375 57 316 2
Columns 391 through 400
66 288 170 149 329 383 304 228 173 237
b =
112 217 314
Tour 3 for spaceship three:
a =
Columns 1 through 15
104 141 365 284 32 75 113 27 384 264 96 335 80 250 235
Columns 16 through 30
234 93 251 386 262 278 20 71 167 184 217 344 187 398 98
Columns 31 through 45
17 126 280 265 188 270 185 142 349 64 53 272 283 331 92
Columns 46 through 60
65 366 347 88 245 368 87 340 319 62 189 127 116 44 86
Columns 61 through 75
336 12 376 165 306 134 314 254 150 78 102 377 394 6 24
Columns 76 through 90
41 279 252 354 355 186 350 357 351 168 50 132 112 162 146
Columns 91 through 105
70 122 299 244 389 46 60 110 241 30 374 119 139 239 19
Columns 106 through 120
59 327 276 43 45 74 63 317 198 256 277 224 97 159 395
Columns 121 through 135
253 94 192 31 390 123 101 130 381 337 379 38 58 291 361
Columns 136 through 150
290 138 22 73 214 243 338 54 273 111 84 144 160 342 171
Columns 151 through 165
232 236 124 129 309 298 191 391 114 320 23 259 180 289 358
Columns 166 through 180
99 231 226 196 323 281 193 194 303 275 378 363 158 293 201
Columns 181 through 195
356 195 401 61 396 207 223 359 216 100 367 18 353 9 311
Columns 196 through 210
8 69 345 26 120 128 3 269 16 36 157 212 117 220 392
Columns 211 through 225
90 263 352 204 190 174 225 274 109 79 333 301 370 40 286
Columns 226 through 240
95 364 229 14 328 148 72 348 324 393 103 267 91 388 221
Columns 241 through 255
271 85 205 334 153 35 400 67 25 385 247 310 325 42 362
Columns 256 through 270
55 15 47 242 136 219 315 230 307 305 206 249 131 52 76
Columns 271 through 285
108 218 197 372 7 399 133 151 268 89 295 105 163 21 260
Columns 286 through 300
140 285 34 81 29 48 11 5 176 203 164 382 152 82 222
Columns 301 through 315
202 292 240 199 145 166 51 266 169 300 137 248 369 39 397
Columns 316 through 330
182 49 380 258 177 33 246 308 210 341 330 77 107 318 125
Columns 331 through 345
115 83 106 343 213 178 233 297 373 387 227 261 10 211 326
Columns 346 through 360
302 121 294 282 4 287 56 175 312 200 118 68 13 161 360
Columns 361 through 375
313 255 147 332 154 215 143 172 135 346 209 296 208 155 321
Columns 376 through 390
28 339 322 183 238 257 179 156 371 181 37 375 57 316 2
Columns 391 through 400
66 288 170 149 329 383 304 228 173 237
b =
112 217 314
Tour 4 for spaceship four:
a =
Columns 1 through 15
104 141 365 284 32 75 113 27 384 264 96 335 80 250 235
Columns 16 through 30
234 93 251 386 262 278 20 71 167 184 217 344 187 398 98
Columns 31 through 45
17 126 280 265 188 270 185 142 349 64 53 272 283 331 92
Columns 46 through 60
65 366 347 88 245 368 87 340 319 62 189 127 116 44 86
Columns 61 through 75
336 12 376 165 306 134 314 254 150 78 102 377 394 6 24
Columns 76 through 90
41 279 252 354 355 186 350 357 351 168 50 132 112 162 146
Columns 91 through 105
70 122 299 244 389 46 60 110 241 30 374 119 139 239 19
Columns 106 through 120
59 327 276 43 45 74 63 317 198 256 277 224 97 159 395
Columns 121 through 135
253 94 192 31 390 123 101 130 381 337 379 38 58 291 361
Columns 136 through 150
290 138 22 73 214 243 338 54 273 111 84 144 160 342 171
Columns 151 through 165
232 236 124 129 309 298 191 391 114 320 23 259 180 289 358
Columns 166 through 180
99 231 226 196 323 281 193 194 303 275 378 363 158 293 201
Columns 181 through 195
356 195 401 61 396 207 223 359 216 100 367 18 353 9 311
Columns 196 through 210
8 69 345 26 120 128 3 269 16 36 157 212 117 220 392
Columns 211 through 225
90 263 352 204 190 174 225 274 109 79 333 301 370 40 286
Columns 226 through 240
95 364 229 14 328 148 72 348 324 393 103 267 91 388 221
Columns 241 through 255
271 85 205 334 153 35 400 67 25 385 247 310 325 42 362
Columns 256 through 270
55 15 47 242 136 219 315 230 307 305 206 249 131 52 76
Columns 271 through 285
108 218 197 372 7 399 133 151 268 89 295 105 163 21 260
Columns 286 through 300
140 285 34 81 29 48 11 5 176 203 164 382 152 82 222
Columns 301 through 315
202 292 240 199 145 166 51 266 169 300 137 248 369 39 397
Columns 316 through 330
182 49 380 258 177 33 246 308 210 341 330 77 107 318 125
Columns 331 through 345
115 83 106 343 213 178 233 297 373 387 227 261 10 211 326
Columns 346 through 360
302 121 294 282 4 287 56 175 312 200 118 68 13 161 360
Columns 361 through 375
313 255 147 332 154 215 143 172 135 346 209 296 208 155 321
Columns 376 through 390
28 339 322 183 238 257 179 156 371 181 37 375 57 316 2
Columns 391 through 400
66 288 170 149 329 383 304 228 173 237
b =
112 217 314
5- Space shipment 5:
Solution:
The total distance = 9606.1561
Number of iterations = 993120
Routes for five spaceships:
Starting from earth and end with earth and passing through these planets by sequence
a = optRoute
b = optBreak
Tour 1 for spaceship one:
a =
Columns 1 through 15
225 174 151 163 295 89 268 378 363 392 220 117 212 157 36
Columns 16 through 30
16 401 61 249 206 305 307 230 18 315 219 353 9 370 95
Columns 31 through 45
301 333 367 100 216 72 348 103 267 91 388 221 299 122 70
Columns 46 through 60
146 162 112 343 205 178 233 400 67 25 385 325 247 310 302
Columns 61 through 75
121 294 4 287 312 175 200 118 326 211 10 68 13 340 87
Columns 76 through 90
368 88 257 238 179 245 261 227 387 373 355 297 132 50 186
Columns 91 through 105
350 24 142 349 64 185 276 125 83 115 327 182 198 317 397
Columns 106 through 120
49 177 258 380 379 58 84 111 135 291 166 266 248 311 8
Columns 121 through 135
69 76 52 131 40 14 364 229 334 153 35 304 228 173 283
Columns 136 through 150
272 53 104 341 210 308 278 20 246 33 32 187 398 98 17
Columns 151 through 165
126 167 184 217 344 339 322 321 155 296 209 28 338 243 214
Columns 166 through 180
73 156 183 284 365 141 314 254 347 331 168 351 357 252 41
Columns 181 through 195
279 354 92 65 366 6 394 150 78 102 377 265 280 188 270
Columns 196 through 210
318 107 77 330 45 43 106 213 244 85 271 389 374 30 241
Columns 211 through 225
110 60 46 79 237 120 128 356 201 293 345 26 194 275 303
Columns 226 through 240
158 195 108 218 197 372 7 399 133 269 3 105 82 222 203
Columns 241 through 255
164 152 382 176 5 11 48 29 81 34 143 215 346 285 140
Columns 256 through 270
260 21 202 145 332 199 292 240 44 86 336 12 57 313 51
Columns 271 through 285
316 2 66 288 170 169 300 137 329 383 149 55 15 362 42
Columns 286 through 300
282 47 136 242 56 360 161 319 62 189 127 116 255 147 375
Columns 301 through 315
154 37 369 39 181 371 376 165 208 306 134 138 172 361 290
Columns 316 through 330
22 54 273 27 264 96 160 342 335 80 38 75 113 250 71
Columns 331 through 345
235 130 101 381 337 234 93 123 390 31 192 94 253 129 124
Columns 346 through 360
309 171 232 236 231 99 358 289 180 259 23 320 114 391 298
Columns 361 through 375
191 144 384 90 263 352 204 190 256 277 224 97 251 386 262
Columns 376 through 390
59 19 239 139 119 393 324 223 359 148 328 286 396 207 193
Columns 391 through 400
281 159 395 226 196 323 274 109 63 74
b =
115 215 304 398
Tour 2 for spaceship two:
a =
Columns 1 through 15
225 174 151 163 295 89 268 378 363 392 220 117 212 157 36
Columns 16 through 30
16 401 61 249 206 305 307 230 18 315 219 353 9 370 95
Columns 31 through 45
301 333 367 100 216 72 348 103 267 91 388 221 299 122 70
Columns 46 through 60
146 162 112 343 205 178 233 400 67 25 385 325 247 310 302
Columns 61 through 75
121 294 4 287 312 175 200 118 326 211 10 68 13 340 87
Columns 76 through 90
368 88 257 238 179 245 261 227 387 373 355 297 132 50 186
Columns 91 through 105
350 24 142 349 64 185 276 125 83 115 327 182 198 317 397
Columns 106 through 120
49 177 258 380 379 58 84 111 135 291 166 266 248 311 8
Columns 121 through 135
69 76 52 131 40 14 364 229 334 153 35 304 228 173 283
Columns 136 through 150
272 53 104 341 210 308 278 20 246 33 32 187 398 98 17
Columns 151 through 165
126 167 184 217 344 339 322 321 155 296 209 28 338 243 214
Columns 166 through 180
73 156 183 284 365 141 314 254 347 331 168 351 357 252 41
Columns 181 through 195
279 354 92 65 366 6 394 150 78 102 377 265 280 188 270
Columns 196 through 210
318 107 77 330 45 43 106 213 244 85 271 389 374 30 241
Columns 211 through 225
110 60 46 79 237 120 128 356 201 293 345 26 194 275 303
Columns 226 through 240
158 195 108 218 197 372 7 399 133 269 3 105 82 222 203
Columns 241 through 255
164 152 382 176 5 11 48 29 81 34 143 215 346 285 140
Columns 256 through 270
260 21 202 145 332 199 292 240 44 86 336 12 57 313 51
Columns 271 through 285
316 2 66 288 170 169 300 137 329 383 149 55 15 362 42
Columns 286 through 300
282 47 136 242 56 360 161 319 62 189 127 116 255 147 375
Columns 301 through 315
154 37 369 39 181 371 376 165 208 306 134 138 172 361 290
Columns 316 through 330
22 54 273 27 264 96 160 342 335 80 38 75 113 250 71
Columns 331 through 345
235 130 101 381 337 234 93 123 390 31 192 94 253 129 124
Columns 346 through 360
309 171 232 236 231 99 358 289 180 259 23 320 114 391 298
Columns 361 through 375
191 144 384 90 263 352 204 190 256 277 224 97 251 386 262
Columns 376 through 390
59 19 239 139 119 393 324 223 359 148 328 286 396 207 193
Columns 391 through 400
281 159 395 226 196 323 274 109 63 74
b =
115 215 304 398
Tour 3 for spaceship three:
a =
Columns 1 through 15
225 174 151 163 295 89 268 378 363 392 220 117 212 157 36
Columns 16 through 30
16 401 61 249 206 305 307 230 18 315 219 353 9 370 95
Columns 31 through 45
301 333 367 100 216 72 348 103 267 91 388 221 299 122 70
Columns 46 through 60
146 162 112 343 205 178 233 400 67 25 385 325 247 310 302
Columns 61 through 75
121 294 4 287 312 175 200 118 326 211 10 68 13 340 87
Columns 76 through 90
368 88 257 238 179 245 261 227 387 373 355 297 132 50 186
Columns 91 through 105
350 24 142 349 64 185 276 125 83 115 327 182 198 317 397
Columns 106 through 120
49 177 258 380 379 58 84 111 135 291 166 266 248 311 8
Columns 121 through 135
69 76 52 131 40 14 364 229 334 153 35 304 228 173 283
Columns 136 through 150
272 53 104 341 210 308 278 20 246 33 32 187 398 98 17
Columns 151 through 165
126 167 184 217 344 339 322 321 155 296 209 28 338 243 214
Columns 166 through 180
73 156 183 284 365 141 314 254 347 331 168 351 357 252 41
Columns 181 through 195
279 354 92 65 366 6 394 150 78 102 377 265 280 188 270
Columns 196 through 210
318 107 77 330 45 43 106 213 244 85 271 389 374 30 241
Columns 211 through 225
110 60 46 79 237 120 128 356 201 293 345 26 194 275 303
Columns 226 through 240
158 195 108 218 197 372 7 399 133 269 3 105 82 222 203
Columns 241 through 255
164 152 382 176 5 11 48 29 81 34 143 215 346 285 140
Columns 256 through 270
260 21 202 145 332 199 292 240 44 86 336 12 57 313 51
Columns 271 through 285
316 2 66 288 170 169 300 137 329 383 149 55 15 362 42
Columns 286 through 300
282 47 136 242 56 360 161 319 62 189 127 116 255 147 375
Columns 301 through 315
154 37 369 39 181 371 376 165 208 306 134 138 172 361 290
Columns 316 through 330
22 54 273 27 264 96 160 342 335 80 38 75 113 250 71
Columns 331 through 345
235 130 101 381 337 234 93 123 390 31 192 94 253 129 124
Columns 346 through 360
309 171 232 236 231 99 358 289 180 259 23 320 114 391 298
Columns 361 through 375
191 144 384 90 263 352 204 190 256 277 224 97 251 386 262
Columns 376 through 390
59 19 239 139 119 393 324 223 359 148 328 286 396 207 193
Columns 391 through 400
281 159 395 226 196 323 274 109 63 74
b =
115 215 304 398
Tour 4 for spaceship four:
a =
Columns 1 through 15
225 174 151 163 295 89 268 378 363 392 220 117 212 157 36
Columns 16 through 30
16 401 61 249 206 305 307 230 18 315 219 353 9 370 95
Columns 31 through 45
301 333 367 100 216 72 348 103 267 91 388 221 299 122 70
Columns 46 through 60
146 162 112 343 205 178 233 400 67 25 385 325 247 310 302
Columns 61 through 75
121 294 4 287 312 175 200 118 326 211 10 68 13 340 87
Columns 76 through 90
368 88 257 238 179 245 261 227 387 373 355 297 132 50 186
Columns 91 through 105
350 24 142 349 64 185 276 125 83 115 327 182 198 317 397
Columns 106 through 120
49 177 258 380 379 58 84 111 135 291 166 266 248 311 8
Columns 121 through 135
69 76 52 131 40 14 364 229 334 153 35 304 228 173 283
Columns 136 through 150
272 53 104 341 210 308 278 20 246 33 32 187 398 98 17
Columns 151 through 165
126 167 184 217 344 339 322 321 155 296 209 28 338 243 214
Columns 166 through 180
73 156 183 284 365 141 314 254 347 331 168 351 357 252 41
Columns 181 through 195
279 354 92 65 366 6 394 150 78 102 377 265 280 188 270
Columns 196 through 210
318 107 77 330 45 43 106 213 244 85 271 389 374 30 241
Columns 211 through 225
110 60 46 79 237 120 128 356 201 293 345 26 194 275 303
Columns 226 through 240
158 195 108 218 197 372 7 399 133 269 3 105 82 222 203
Columns 241 through 255
164 152 382 176 5 11 48 29 81 34 143 215 346 285 140
Columns 256 through 270
260 21 202 145 332 199 292 240 44 86 336 12 57 313 51
Columns 271 through 285
316 2 66 288 170 169 300 137 329 383 149 55 15 362 42
Columns 286 through 300
282 47 136 242 56 360 161 319 62 189 127 116 255 147 375
Columns 301 through 315
154 37 369 39 181 371 376 165 208 306 134 138 172 361 290
Columns 316 through 330
22 54 273 27 264 96 160 342 335 80 38 75 113 250 71
Columns 331 through 345
235 130 101 381 337 234 93 123 390 31 192 94 253 129 124
Columns 346 through 360
309 171 232 236 231 99 358 289 180 259 23 320 114 391 298
Columns 361 through 375
191 144 384 90 263 352 204 190 256 277 224 97 251 386 262
Columns 376 through 390
59 19 239 139 119 393 324 223 359 148 328 286 396 207 193
Columns 391 through 400
281 159 395 226 196 323 274 109 63 74
b =
115 215 304 398
Tour 5 for spaceship five:
a =
Columns 1 through 15
225 174 151 163 295 89 268 378 363 392 220 117 212 157 36
Columns 16 through 30
16 401 61 249 206 305 307 230 18 315 219 353 9 370 95
Columns 31 through 45
301 333 367 100 216 72 348 103 267 91 388 221 299 122 70
Columns 46 through 60
146 162 112 343 205 178 233 400 67 25 385 325 247 310 302
Columns 61 through 75
121 294 4 287 312 175 200 118 326 211 10 68 13 340 87
Columns 76 through 90
368 88 257 238 179 245 261 227 387 373 355 297 132 50 186
Columns 91 through 105
350 24 142 349 64 185 276 125 83 115 327 182 198 317 397
Columns 106 through 120
49 177 258 380 379 58 84 111 135 291 166 266 248 311 8
Columns 121 through 135
69 76 52 131 40 14 364 229 334 153 35 304 228 173 283
Columns 136 through 150
272 53 104 341 210 308 278 20 246 33 32 187 398 98 17
Columns 151 through 165
126 167 184 217 344 339 322 321 155 296 209 28 338 243 214
Columns 166 through 180
73 156 183 284 365 141 314 254 347 331 168 351 357 252 41
Columns 181 through 195
279 354 92 65 366 6 394 150 78 102 377 265 280 188 270
Columns 196 through 210
318 107 77 330 45 43 106 213 244 85 271 389 374 30 241
Columns 211 through 225
110 60 46 79 237 120 128 356 201 293 345 26 194 275 303
Columns 226 through 240
158 195 108 218 197 372 7 399 133 269 3 105 82 222 203
Columns 241 through 255
164 152 382 176 5 11 48 29 81 34 143 215 346 285 140
Columns 256 through 270
260 21 202 145 332 199 292 240 44 86 336 12 57 313 51
Columns 271 through 285
316 2 66 288 170 169 300 137 329 383 149 55 15 362 42
Columns 286 through 300
282 47 136 242 56 360 161 319 62 189 127 116 255 147 375
Columns 301 through 315
154 37 369 39 181 371 376 165 208 306 134 138 172 361 290
Columns 316 through 330
22 54 273 27 264 96 160 342 335 80 38 75 113 250 71
Columns 331 through 345
235 130 101 381 337 234 93 123 390 31 192 94 253 129 124
Columns 346 through 360
309 171 232 236 231 99 358 289 180 259 23 320 114 391 298
Columns 361 through 375
191 144 384 90 263 352 204 190 256 277 224 97 251 386 262
Columns 376 through 390
59 19 239 139 119 393 324 223 359 148 328 286 396 207 193
Columns 391 through 400
281 159 395 226 196 323 274 109 63 74
b =
115 215 304 398
6- Space shipment 6:
Solution:
The total distance = 9992.9800
Number of iterations =
Routes for six spaceships:
Starting from earth and end with earth and passing through these planets by sequence
a = optRoute
b = optBreak
Tour 1 for spaceship one:
a =
Columns 1 through 15
369 128 197 218 372 7 399 133 3 82 105 163 263 90 320
Columns 16 through 30
114 391 298 191 232 171 309 129 124 236 342 160 96 264 80
Columns 31 through 45
379 380 177 258 93 234 251 327 256 277 224 358 99 231 226
Columns 46 through 60
97 241 19 30 159 395 253 94 192 31 390 123 130 250 217
Columns 61 through 75
184 33 246 308 210 182 397 317 198 181 57 116 255 240 147
Columns 76 through 90
332 199 145 202 215 143 34 29 48 11 5 176 222 203 164
Columns 91 through 105
382 152 220 117 157 212 392 36 269 16 315 353 219 56 175
Columns 106 through 120
312 200 10 211 326 387 354 92 65 366 150 78 394 6 349
Columns 121 through 135
64 142 24 41 279 252 350 186 357 351 168 355 373 297 122
Columns 136 through 150
299 221 85 244 213 205 178 233 304 79 237 109 274 275 323
Columns 151 through 165
196 281 374 207 14 364 229 334 153 35 400 67 362 42 287
Columns 166 through 180
4 282 294 121 302 310 247 325 385 25 2 66 288 170 169
Columns 181 through 195
300 137 311 248 266 316 51 166 37 375 154 292 81 86 336
Columns 196 through 210
44 12 376 165 155 208 296 209 338 22 361 291 172 135 54
Columns 211 through 225
273 113 27 144 384 285 140 295 89 268 151 204 190 174 74
Columns 226 through 240
228 173 46 389 110 60 59 262 386 115 83 318 125 276 278
Columns 241 through 255
20 167 71 235 101 381 337 335 38 75 32 49 58 111 84
Columns 256 through 270
346 260 21 352 23 259 180 289 303 363 378 195 293 396 286
Columns 271 through 285
40 328 359 223 324 139 239 119 393 103 271 348 72 148 216
Columns 286 through 300
100 367 47 15 55 149 383 329 333 301 95 370 131 52 76
Columns 301 through 315
69 8 108 356 201 345 120 26 194 193 158 401 61 249 206
Columns 316 through 330
305 307 230 18 9 136 242 313 360 161 319 127 189 62 118
Columns 331 through 345
68 13 340 87 88 179 290 138 371 156 257 238 183 314 254
Columns 346 through 360
347 185 270 188 280 265 377 102 17 126 98 339 322 243 214
Columns 361 through 375
73 134 306 321 28 344 187 398 284 365 141 104 53 331 245
Columns 376 through 390
368 261 227 272 283 132 50 146 70 388 267 91 343 112 162
Columns 391 through 400
77 107 106 43 330 45 341 63 225 39
b =
69 146 224 307 398
Tour 2 for spaceship two:
a =
Columns 1 through 15
369 128 197 218 372 7 399 133 3 82 105 163 263 90 320
Columns 16 through 30
114 391 298 191 232 171 309 129 124 236 342 160 96 264 80
Columns 31 through 45
379 380 177 258 93 234 251 327 256 277 224 358 99 231 226
Columns 46 through 60
97 241 19 30 159 395 253 94 192 31 390 123 130 250 217
Columns 61 through 75
184 33 246 308 210 182 397 317 198 181 57 116 255 240 147
Columns 76 through 90
332 199 145 202 215 143 34 29 48 11 5 176 222 203 164
Columns 91 through 105
382 152 220 117 157 212 392 36 269 16 315 353 219 56 175
Columns 106 through 120
312 200 10 211 326 387 354 92 65 366 150 78 394 6 349
Columns 121 through 135
64 142 24 41 279 252 350 186 357 351 168 355 373 297 122
Columns 136 through 150
299 221 85 244 213 205 178 233 304 79 237 109 274 275 323
Columns 151 through 165
196 281 374 207 14 364 229 334 153 35 400 67 362 42 287
Columns 166 through 180
4 282 294 121 302 310 247 325 385 25 2 66 288 170 169
Columns 181 through 195
300 137 311 248 266 316 51 166 37 375 154 292 81 86 336
Columns 196 through 210
44 12 376 165 155 208 296 209 338 22 361 291 172 135 54
Columns 211 through 225
273 113 27 144 384 285 140 295 89 268 151 204 190 174 74
Columns 226 through 240
228 173 46 389 110 60 59 262 386 115 83 318 125 276 278
Columns 241 through 255
20 167 71 235 101 381 337 335 38 75 32 49 58 111 84
Columns 256 through 270
346 260 21 352 23 259 180 289 303 363 378 195 293 396 286
Columns 271 through 285
40 328 359 223 324 139 239 119 393 103 271 348 72 148 216
Columns 286 through 300
100 367 47 15 55 149 383 329 333 301 95 370 131 52 76
Columns 301 through 315
69 8 108 356 201 345 120 26 194 193 158 401 61 249 206
Columns 316 through 330
305 307 230 18 9 136 242 313 360 161 319 127 189 62 118
Columns 331 through 345
68 13 340 87 88 179 290 138 371 156 257 238 183 314 254
Columns 346 through 360
347 185 270 188 280 265 377 102 17 126 98 339 322 243 214
Columns 361 through 375
73 134 306 321 28 344 187 398 284 365 141 104 53 331 245
Columns 376 through 390
368 261 227 272 283 132 50 146 70 388 267 91 343 112 162
Columns 391 through 400
77 107 106 43 330 45 341 63 225 39
b =
69 146 224 307 398
Tour 3 for spaceship three:
a =
Columns 1 through 15
369 128 197 218 372 7 399 133 3 82 105 163 263 90 320
Columns 16 through 30
114 391 298 191 232 171 309 129 124 236 342 160 96 264 80
Columns 31 through 45
379 380 177 258 93 234 251 327 256 277 224 358 99 231 226
Columns 46 through 60
97 241 19 30 159 395 253 94 192 31 390 123 130 250 217
Columns 61 through 75
184 33 246 308 210 182 397 317 198 181 57 116 255 240 147
Columns 76 through 90
332 199 145 202 215 143 34 29 48 11 5 176 222 203 164
Columns 91 through 105
382 152 220 117 157 212 392 36 269 16 315 353 219 56 175
Columns 106 through 120
312 200 10 211 326 387 354 92 65 366 150 78 394 6 349
Columns 121 through 135
64 142 24 41 279 252 350 186 357 351 168 355 373 297 122
Columns 136 through 150
299 221 85 244 213 205 178 233 304 79 237 109 274 275 323
Columns 151 through 165
196 281 374 207 14 364 229 334 153 35 400 67 362 42 287
Columns 166 through 180
4 282 294 121 302 310 247 325 385 25 2 66 288 170 169
Columns 181 through 195
300 137 311 248 266 316 51 166 37 375 154 292 81 86 336
Columns 196 through 210
44 12 376 165 155 208 296 209 338 22 361 291 172 135 54
Columns 211 through 225
273 113 27 144 384 285 140 295 89 268 151 204 190 174 74
Columns 226 through 240
228 173 46 389 110 60 59 262 386 115 83 318 125 276 278
Columns 241 through 255
20 167 71 235 101 381 337 335 38 75 32 49 58 111 84
Columns 256 through 270
346 260 21 352 23 259 180 289 303 363 378 195 293 396 286
Columns 271 through 285
40 328 359 223 324 139 239 119 393 103 271 348 72 148 216
Columns 286 through 300
100 367 47 15 55 149 383 329 333 301 95 370 131 52 76
Columns 301 through 315
69 8 108 356 201 345 120 26 194 193 158 401 61 249 206
Columns 316 through 330
305 307 230 18 9 136 242 313 360 161 319 127 189 62 118
Columns 331 through 345
68 13 340 87 88 179 290 138 371 156 257 238 183 314 254
Columns 346 through 360
347 185 270 188 280 265 377 102 17 126 98 339 322 243 214
Columns 361 through 375
73 134 306 321 28 344 187 398 284 365 141 104 53 331 245
Columns 376 through 390
368 261 227 272 283 132 50 146 70 388 267 91 343 112 162
Columns 391 through 400
77 107 106 43 330 45 341 63 225 39
b =
69 146 224 307 398
Tour 4 for spaceship four:
a =
Columns 1 through 15
369 128 197 218 372 7 399 133 3 82 105 163 263 90 320
Columns 16 through 30
114 391 298 191 232 171 309 129 124 236 342 160 96 264 80
Columns 31 through 45
379 380 177 258 93 234 251 327 256 277 224 358 99 231 226
Columns 46 through 60
97 241 19 30 159 395 253 94 192 31 390 123 130 250 217
Columns 61 through 75
184 33 246 308 210 182 397 317 198 181 57 116 255 240 147
Columns 76 through 90
332 199 145 202 215 143 34 29 48 11 5 176 222 203 164
Columns 91 through 105
382 152 220 117 157 212 392 36 269 16 315 353 219 56 175
Columns 106 through 120
312 200 10 211 326 387 354 92 65 366 150 78 394 6 349
Columns 121 through 135
64 142 24 41 279 252 350 186 357 351 168 355 373 297 122
Columns 136 through 150
299 221 85 244 213 205 178 233 304 79 237 109 274 275 323
Columns 151 through 165
196 281 374 207 14 364 229 334 153 35 400 67 362 42 287
Columns 166 through 180
4 282 294 121 302 310 247 325 385 25 2 66 288 170 169
Columns 181 through 195
300 137 311 248 266 316 51 166 37 375 154 292 81 86 336
Columns 196 through 210
44 12 376 165 155 208 296 209 338 22 361 291 172 135 54
Columns 211 through 225
273 113 27 144 384 285 140 295 89 268 151 204 190 174 74
Columns 226 through 240
228 173 46 389 110 60 59 262 386 115 83 318 125 276 278
Columns 241 through 255
20 167 71 235 101 381 337 335 38 75 32 49 58 111 84
Columns 256 through 270
346 260 21 352 23 259 180 289 303 363 378 195 293 396 286
Columns 271 through 285
40 328 359 223 324 139 239 119 393 103 271 348 72 148 216
Columns 286 through 300
100 367 47 15 55 149 383 329 333 301 95 370 131 52 76
Columns 301 through 315
69 8 108 356 201 345 120 26 194 193 158 401 61 249 206
Columns 316 through 330
305 307 230 18 9 136 242 313 360 161 319 127 189 62 118
Columns 331 through 345
68 13 340 87 88 179 290 138 371 156 257 238 183 314 254
Columns 346 through 360
347 185 270 188 280 265 377 102 17 126 98 339 322 243 214
Columns 361 through 375
73 134 306 321 28 344 187 398 284 365 141 104 53 331 245
Columns 376 through 390
368 261 227 272 283 132 50 146 70 388 267 91 343 112 162
Columns 391 through 400
77 107 106 43 330 45 341 63 225 39
b =
69 146 224 307 398
Tour 5 for spaceship five:
a =
Columns 1 through 15
369 128 197 218 372 7 399 133 3 82 105 163 263 90 320
Columns 16 through 30
114 391 298 191 232 171 309 129 124 236 342 160 96 264 80
Columns 31 through 45
379 380 177 258 93 234 251 327 256 277 224 358 99 231 226
Columns 46 through 60
97 241 19 30 159 395 253 94 192 31 390 123 130 250 217
Columns 61 through 75
184 33 246 308 210 182 397 317 198 181 57 116 255 240 147
Columns 76 through 90
332 199 145 202 215 143 34 29 48 11 5 176 222 203 164
Columns 91 through 105
382 152 220 117 157 212 392 36 269 16 315 353 219 56 175
Columns 106 through 120
312 200 10 211 326 387 354 92 65 366 150 78 394 6 349
Columns 121 through 135
64 142 24 41 279 252 350 186 357 351 168 355 373 297 122
Columns 136 through 150
299 221 85 244 213 205 178 233 304 79 237 109 274 275 323
Columns 151 through 165
196 281 374 207 14 364 229 334 153 35 400 67 362 42 287
Columns 166 through 180
4 282 294 121 302 310 247 325 385 25 2 66 288 170 169
Columns 181 through 195
300 137 311 248 266 316 51 166 37 375 154 292 81 86 336
Columns 196 through 210
44 12 376 165 155 208 296 209 338 22 361 291 172 135 54
Columns 211 through 225
273 113 27 144 384 285 140 295 89 268 151 204 190 174 74
Columns 226 through 240
228 173 46 389 110 60 59 262 386 115 83 318 125 276 278
Columns 241 through 255
20 167 71 235 101 381 337 335 38 75 32 49 58 111 84
Columns 256 through 270
346 260 21 352 23 259 180 289 303 363 378 195 293 396 286
Columns 271 through 285
40 328 359 223 324 139 239 119 393 103 271 348 72 148 216
Columns 286 through 300
100 367 47 15 55 149 383 329 333 301 95 370 131 52 76
Columns 301 through 315
69 8 108 356 201 345 120 26 194 193 158 401 61 249 206
Columns 316 through 330
305 307 230 18 9 136 242 313 360 161 319 127 189 62 118
Columns 331 through 345
68 13 340 87 88 179 290 138 371 156 257 238 183 314 254
Columns 346 through 360
347 185 270 188 280 265 377 102 17 126 98 339 322 243 214
Columns 361 through 375
73 134 306 321 28 344 187 398 284 365 141 104 53 331 245
Columns 376 through 390
368 261 227 272 283 132 50 146 70 388 267 91 343 112 162
Columns 391 through 400
77 107 106 43 330 45 341 63 225 39
b =
69 146 224 307 398
Tour 6 for spaceship six:
a =
Columns 1 through 15
369 128 197 218 372 7 399 133 3 82 105 163 263 90 320
Columns 16 through 30
114 391 298 191 232 171 309 129 124 236 342 160 96 264 80
Columns 31 through 45
379 380 177 258 93 234 251 327 256 277 224 358 99 231 226
Columns 46 through 60
97 241 19 30 159 395 253 94 192 31 390 123 130 250 217
Columns 61 through 75
184 33 246 308 210 182 397 317 198 181 57 116 255 240 147
Columns 76 through 90
332 199 145 202 215 143 34 29 48 11 5 176 222 203 164
Columns 91 through 105
382 152 220 117 157 212 392 36 269 16 315 353 219 56 175
Columns 106 through 120
312 200 10 211 326 387 354 92 65 366 150 78 394 6 349
Columns 121 through 135
64 142 24 41 279 252 350 186 357 351 168 355 373 297 122
Columns 136 through 150
299 221 85 244 213 205 178 233 304 79 237 109 274 275 323
Columns 151 through 165
196 281 374 207 14 364 229 334 153 35 400 67 362 42 287
Columns 166 through 180
4 282 294 121 302 310 247 325 385 25 2 66 288 170 169
Columns 181 through 195
300 137 311 248 266 316 51 166 37 375 154 292 81 86 336
Columns 196 through 210
44 12 376 165 155 208 296 209 338 22 361 291 172 135 54
Columns 211 through 225
273 113 27 144 384 285 140 295 89 268 151 204 190 174 74
Columns 226 through 240
228 173 46 389 110 60 59 262 386 115 83 318 125 276 278
Columns 241 through 255
20 167 71 235 101 381 337 335 38 75 32 49 58 111 84
Columns 256 through 270
346 260 21 352 23 259 180 289 303 363 378 195 293 396 286
Columns 271 through 285
40 328 359 223 324 139 239 119 393 103 271 348 72 148 216
Columns 286 through 300
100 367 47 15 55 149 383 329 333 301 95 370 131 52 76
Columns 301 through 315
69 8 108 356 201 345 120 26 194 193 158 401 61 249 206
Columns 316 through 330
305 307 230 18 9 136 242 313 360 161 319 127 189 62 118
Columns 331 through 345
68 13 340 87 88 179 290 138 371 156 257 238 183 314 254
Columns 346 through 360
347 185 270 188 280 265 377 102 17 126 98 339 322 243 214
Columns 361 through 375
73 134 306 321 28 344 187 398 284 365 141 104 53 331 245
Columns 376 through 390
368 261 227 272 283 132 50 146 70 388 267 91 343 112 162
Columns 391 through 400
77 107 106 43 330 45 341 63 225 39
b =
69 146 224 307 398
Objective 2:
a. Assumptions:
b. Methodology:
c. Solutions
Objective 3:(a)
a. Assumptions:
Assuming that we have 40 satellites and each satellite can maintain ten nearest planets
b. Methodology:
This problem can be solved by using Total Cover Modeling.
Given n satellites, and m existing planets, determine the minimum (w.r.t to a cost) number of satellites and their location to cover all of the existing planets.
c. Solutions :
Given 1: 𝑖 = 1, … , 𝑚 existing planets i=1,...,400
Given 2: 𝑗 = 1, … , 𝑛 satellites where a satellite can maintain a planet j=1,…40 (by assumption)
Given 3: If a satellite is placed here, then it can cover some existing planets. This information is denoted by parameter aij
Criterion: Every satellite j has cost 𝒄j to maintain a planet.
cj = cost of maintaining a planet by satellite j
Variable: xij = 1 if a planet i is maintained by s satellite j
0 otherwise
Min :
s.t :
every existing planet should be maintained by at least one satellite j
for all i = 1,…400
Xij
If we assume that we have 40 satellites and the distance between the relay station and the hub planet is less than 50×1013 𝐾𝑚 so each satellite can maintain ten nearest planets to it so the cove matrix will be in the attached file .
Objective 3:(b)
a. Assumptions:
Minimizing the distance.
d. Methodology:
By calculating the difference between the hub planet and the ten neighbors we well have the distance as
|
Hub |
d1 |
43.87482 |
d2 |
101.4199 |
d3 |
113.2166 |
d4 |
92.07063 |
d5 |
122.9878 |
d6 |
63.30877 |
d7 |
102.1029 |
d8 |
116.8033 |
d9 |
92.49324 |
d10 |
109.1971 |
And then , based on these distance the optimal locations for the planets will be the one which has the minimum distance from earth.
e. Solutions: by using gams :
alias (i,j,k);
table d(i,j)
Hub
d1 43.87482194
d2 101.4199191
d3 113.2166066
d4 92.07062507
d5 122.9878043
d6 63.30876717
d7 102.1028893
d8 116.8032534
d9 92.493243
d10 109.1970696
;
set(i,j)$(ord(i)>ord(j)) = yes;
free variable z;
binary variable x(i,j);
equations obj;
obj.. z =e= sum(d(i,j)*x(i,j));
sum(lt(i,k), x(i,k)) + sum(lt(k,j),x(k,j)) =e= 2;
model match /obj/;
solve match minimizing z using cplex;
Work done by:
Work done by |
Objective |
Nasser and Ammar |
1 |
Nasser and Ammar |
2 |
Mohammed Al-Nass Mohammed Al-Mulla |
3 |