*P1 Sets i rectangles index row label1 /1*4/ l index of entry exit points of rectangles row label2 /1*8/ sp index of the search pattern within a rectangle /1*9/ ; alias(i,j); alias(l,k); Scalar N large number /1000/; Table D(i,l,j,k) distance from point l of rectangle i to point k of rectangle j 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 1.1 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 9.165 9.400 10.069 9.995 6.513 6.317 5.128 5.236 9.210 9.361 11.900 12.034 12.491 12.394 9.981 9.799 7.901 8.101 11.279 11.332 9.901 9.758 5.798 5.659 1.2 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 9.165 9.370 10.069 9.995 6.513 6.317 5.128 5.236 9.210 9.361 11.900 12.034 12.491 12.394 9.981 9.799 7.901 8.101 11.279 11.332 9.901 9.758 5.798 5.659 1.3 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 9.165 9.370 10.069 9.995 6.513 6.317 5.128 5.236 9.210 9.361 11.900 12.034 12.491 12.394 9.981 9.799 7.901 8.101 11.279 11.332 9.901 9.758 5.798 5.659 1.4 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 9.165 9.370 10.069 9.995 6.513 6.317 5.128 5.236 9.210 9.361 11.900 12.034 12.491 12.394 9.981 9.799 7.901 8.101 11.279 11.332 9.901 9.758 5.798 5.659 1.5 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 9.165 9.370 10.069 9.995 6.513 6.317 5.128 5.236 9.210 9.361 11.900 12.034 12.491 12.394 9.981 9.799 7.901 8.101 11.279 11.332 9.901 9.758 5.798 5.659 1.6 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 9.165 9.370 10.069 9.995 6.513 6.317 5.128 5.236 9.210 9.361 11.900 12.034 12.491 12.394 9.981 9.799 7.901 8.101 11.279 11.332 9.901 9.758 5.798 5.659 1.7 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 9.165 9.370 10.069 9.995 6.513 6.317 5.128 5.236 9.210 9.361 11.900 12.034 12.491 12.394 9.981 9.799 7.901 8.101 11.279 11.332 9.901 9.758 5.798 5.659 1.8 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 9.165 9.370 10.069 9.995 6.513 6.317 5.128 5.236 9.210 9.361 11.900 12.034 12.491 12.394 9.981 9.799 7.901 8.101 11.279 11.332 9.901 9.758 5.798 5.659 2.1 9.165 9.165 9.165 9.165 9.165 9.165 9.165 9.165 1000 1000 1000 1000 1000 1000 1000 1000 5.558 3.619 6.903 7.103 10.347 10.407 9.524 9.355 11.349 11.629 15.564 15.719 17.133 17.063 13.569 13.374 2.2 9.370 9.370 9.370 9.370 9.370 9.370 9.370 9.370 1000 1000 1000 1000 1000 1000 1000 1000 5.510 3.883 6.772 6.971 10.271 10.335 9.508 9.341 11.417 11.696 15.624 15.780 17.262 17.194 13.723 13.528 2.3 10.069 10.069 10.069 10.069 10.069 10.069 10.069 10.069 1000 1000 1000 1000 1000 1000 1000 1000 3.283 3.883 4.060 4.259 7.733 7.818 7.382 7.242 10.048 10.312 14.086 14.259 16.521 16.483 13.402 13.202 2.4 9.995 9.995 9.995 9.995 9.995 9.995 9.995 9.995 1000 1000 1000 1000 1000 1000 1000 1000 3.085 3.689 3.909 4.108 7.548 7.631 7.184 7.044 9.864 10.127 13.894 14.068 16.356 16.320 13.260 13.060 2.5 6.513 6.513 6.513 6.513 6.513 6.513 6.513 6.513 1000 1000 1000 1000 1000 1000 1000 1000 2.740 2.182 5.417 5.563 6.966 6.942 5.205 5.009 6.373 6.653 10.595 10.747 12.433 12.384 9.241 9.041 2.6 6.317 6.317 6.317 6.317 6.317 6.317 6.317 6.317 1000 1000 1000 1000 1000 1000 1000 1000 2.937 2.371 5.615 5.761 7.125 7.097 5.317 5.120 6.351 6.632 10.582 10.732 12.333 12.282 9.103 8.903 2.7 5.128 5.128 5.128 5.128 5.128 5.128 5.128 5.128 1000 1000 1000 1000 1000 1000 1000 1000 5.311 2.371 7.804 7.978 9.822 9.801 8.011 7.812 8.349 8.629 12.557 12.683 13.309 13.221 9.569 9.379 2.8 5.236 5.236 5.236 5.236 5.236 5.236 5.236 5.236 1000 1000 1000 1000 1000 1000 1000 1000 5.395 2.182 7.858 8.034 9.946 9.929 8.166 7.968 8.545 8.824 12.753 12.881 13.497 13.408 9.746 9.557 3.1 9.210 9.210 9.210 9.210 9.210 9.210 9.210 9.210 5.558 5.510 3.283 3.085 2.740 2.937 5.311 5.395 1000 1000 1000 1000 1000 1000 1000 1000 7.034 7.280 10.912 11.092 13.836 13.823 11.180 10.984 3.2 9.361 9.361 9.361 9.361 9.361 9.361 9.361 9.361 5.482 5.426 3.140 2.942 2.873 3.070 5.386 5.464 1000 1000 1000 1000 1000 1000 1000 1000 7.228 7.473 11.092 11.273 14.036 14.023 11.377 11.180 3.3 11.900 11.900 11.900 11.900 11.900 11.900 11.900 11.900 6.903 6.772 4.060 3.909 5.417 5.615 7.804 7.858 1000 1000 1000 1000 1000 1000 1000 1000 8.800 9.002 12.175 12.369 15.820 15.832 13.544 13.352 3.4 12.034 12.034 12.034 12.034 12.034 12.034 12.034 12.034 7.103 6.971 4.259 4.108 5.563 5.761 7.978 8.034 1000 1000 1000 1000 1000 1000 1000 1000 8.802 9.000 12.128 12.322 15.832 15.846 13.601 13.410 3.5 12.491 12.491 12.491 12.491 12.491 12.491 12.491 12.491 10.347 10.271 7.733 7.548 6.966 7.125 9.822 9.946 1000 1000 1000 1000 1000 1000 1000 1000 6.708 6.803 9.000 9.200 13.544 13.601 12.259 12.093 3.6 12.394 12.394 12.394 12.394 12.394 12.394 12.394 12.394 10.407 10.335 7.818 7.631 6.942 7.097 9.801 9.929 1000 1000 1000 1000 1000 1000 1000 1000 6.530 6.621 8.800 9.000 13.352 13.410 12.093 11.928 3.7 9.981 9.981 9.981 9.981 9.981 9.981 9.981 9.981 9.524 9.508 7.382 7.184 5.205 5.317 8.011 8.166 1000 1000 1000 1000 1000 1000 1000 1000 4.176 4.317 7.228 7.422 11.180 11.218 9.604 9.434 3.8 9.799 9.799 9.799 9.799 9.799 9.799 9.799 9.799 9.355 9.341 7.242 7.044 5.009 5.120 7.812 7.968 1000 1000 1000 1000 1000 1000 1000 1000 4.123 4.276 7.280 7.473 11.146 11.180 9.502 9.330 4.1 7.901 7.901 7.901 7.901 7.901 7.901 7.901 7.901 11.349 11.417 10.048 9.864 6.373 6.351 8.349 8.545 7.034 9.220 8.800 8.802 6.708 6.530 4.176 4.123 1000 1000 1000 1000 1000 1000 1000 1000 4.2 8.101 8.101 8.101 8.101 8.101 8.101 8.101 8.101 11.629 11.696 10.312 10.127 6.653 6.632 8.629 8.824 7.280 9.502 9.002 9.000 6.803 6.621 4.317 4.276 1000 1000 1000 1000 1000 1000 1000 1000 4.3 11.279 11.279 11.279 11.279 11.279 11.279 11.279 11.279 15.564 15.624 14.086 13.894 10.595 10.582 12.557 12.753 10.912 13.454 12.175 12.128 9.000 8.800 7.228 7.280 1000 1000 1000 1000 1000 1000 1000 1000 4.4 11.332 11.332 11.332 11.332 11.332 11.332 11.332 11.332 15.719 15.780 14.259 14.068 10.747 10.732 12.683 12.881 11.092 13.736 12.369 12.322 9.200 9.000 7.422 7.473 1000 1000 1000 1000 1000 1000 1000 1000 4.5 9.901 9.901 9.901 9.901 9.901 9.901 9.901 9.901 17.133 17.262 16.521 16.356 12.433 12.333 13.309 13.497 13.836 19.105 15.820 15.832 13.544 13.352 11.180 11.146 1000 1000 1000 1000 1000 1000 1000 1000 4.6 9.758 9.758 9.758 9.758 9.758 9.758 9.758 9.758 17.063 17.194 16.483 16.320 12.384 12.282 13.221 13.408 13.823 19.105 15.832 15.846 13.601 13.410 11.218 11.180 1000 1000 1000 1000 1000 1000 1000 1000 4.7 5.798 5.798 5.798 5.798 5.798 5.798 5.798 5.798 13.569 13.723 13.402 13.260 9.241 9.103 9.569 9.746 11.180 15.149 13.544 13.601 12.259 12.093 9.604 9.502 1000 1000 1000 1000 1000 1000 1000 1000 4.8 5.659 5.659 5.659 5.659 5.659 5.659 5.659 5.659 13.374 13.528 13.202 13.060 9.041 8.903 9.379 9.557 10.984 14.866 13.352 13.410 12.093 11.928 9.434 9.330 1000 1000 1000 1000 1000 1000 1000 1000 ; Table T(i,l,k,sp) distance from point l to point k of rectangle i using search pattern sp 1 2 3 4 5 6 7 8 9 2.1.5 51 45 2.1.8 48 42 2.2.3 52 43 2.2.6 47 3.1.8 45 40 3.1.5 42 3.2.6 47 3.2.3 42 4.1.8 93 85 76 4.1.5 89 81 4.2.3 91 80 4.2.6 86 74 ; Variable objec y(i,l,j,k) if platform flies from point l of rectangle i to point k of rectangle j z(i,l,k,sp) if platform flies from point l to point k of rectangle i using search pattern s ; Binary Variable y(i,l,j,k) if platform flies from point l of rectangle i to point k of rectangle j z(i,l,k,sp) if platform flies from point l to point k of rectangle i using search pattern s; Positive Variable u(i) u(j) ; Equation obj total distance traveled con2 air platfrom enters and leaves each reactangle and origin only once con3 air platfrom enters and leaves each reactangle and origin only once con4 allows a single search pattern for each rectangle con5 search pattern is chosen only if there is an entry and exit points of the pattern con6 search pattern is chosen only if there is an entry and exit points of the pattern con7 modified subtour elimination; obj.. objec =e= sum((i,l,j,k), D(i,l,j,k)*y(i,l,j,k)) + sum((i,l,k,sp), T(i,l,k,sp)*z(i,l,k,sp)); con2(j).. sum((i,l,k), y(i,l,j,k)) =e= 1; con3(i).. sum((j,l,k), y(i,l,j,k)) =e= 1; con4(i)$(ord(i)>1).. sum((l,k,sp), z(i,l,k,sp)) =e= 1; con5(l,i)$(ord(i)>1).. sum((k,sp), z(i,l,k,sp) ) =l= sum((j,k), y(j,k,i,l) ); con6(k,i)$(ord(i)>1).. sum((l,sp), z(i,l,k,sp) ) =l= sum((j,l), y(i,k,j,l) ); con7(i,j)$(ord(i)>1 and ord(j)>1 and not sameas(i,j)).. u(i)-u(j)+N*(sum((l,k), y(i,l,j,k))) =l= N-1; model MTD /all/; solve MTD using mip minimizing objec;