16
$\begingroup$

I asked this question here 2 years ago. I didn't know this website at that time. I just realized I could ask it here. Here is the problem statement.

Assume I have 20 trucks, $t_j$, $j=1...20$ and all trucks are at the port at the same time. Each truck needs to stop at each of port's four docks $d_k$, $k=1...4$, to unload its freight. There is a waiting time $w_{j,k}$ for each truck $j$ at each dock $k$. Please see the table. Truck $t_1$ is waiting 36.67 minutes at dock $d_1$, 23.33 minutes at dock $d_2$, 18.33 minutes at dock $d_3$ and 12.33 minutes at dock $d_4$. There cannot be two trucks at the the same dock at the same time and a truck cannot be at two different docks at the same time. There is no specific order. I want to minimize the total unloading time. What should be the order in which the trucks are visiting the docks?

\begin{array}{c|cccc} & d_1 & d_2 & d_3 & d_4 \\\hline t_1 & 36.67 & 23.33 & 18.33 & 12.33 \\ t_2 & 20. & 33.33 & 30.83 & 10.33 \\ t_3 & 16.67 & 60.83 & 22.08 & 16.13 \\ t_4 & 26.67 & 53.33 & 24.33 & 11.93 \\ t_5 & 53.33 & 43.33 & 11.33 & 14.33 \\ t_6 & 60. & 13.33 & 14.58 & 23.13 \\ t_7 & 43.33 & 33.33 & 9.58 & 16.13 \\ t_8 & 36.67 & 23.33 & 27.08 & 16.53 \\ t_9 & 20. & 28.33 & 21.58 & 24.73 \\ t_{10} & 33.33 & 38.33 & 29.08 & 12.33 \\ t_{11} & 28.33 & 68.33 & 6.08 & 11.13 \\ t_{12} & 45. & 78.33 & 30.33 & 10.73 \\ t_{13} & 46.67 & 38.33 & 21.83 & 15.73 \\ t_{14} & 53.33 & 13.33 & 13.33 & 12.33 \\ t_{15} & 73.33 & 23.33 & 12.08 & 18.13 \\ t_{16} & 13.33 & 28.33 & 19.58 & 10.73 \\ t_{17} & 33.33 & 33.33 & 21.83 & 21.93 \\ t_{18} & 26.67 & 28.33 & 27.58 & 7.33 \\ t_{19} & 23.33 & 18.33 & 14.83 & 6.93 \\ t_{20} & 33.33 & 40.83 & 30.08 & 12.33 \\ \end{array}

Here is the data:

data = {{36.67, 23.33, 18.33, 12.33}, {20., 33.33, 30.83, 
    10.33}, {16.67, 60.83, 22.08, 16.13}, {26.67, 53.33, 24.33, 
    11.93}, {53.33, 43.33, 11.33, 14.33}, {60., 13.33, 14.58, 
    23.13}, {43.33, 33.33, 9.58, 16.13}, {36.67, 23.33, 27.08, 
    16.53}, {20., 28.33, 21.58, 24.73}, {33.33, 38.33, 29.08, 
    12.33}, {28.33, 68.33, 6.08, 11.13}, {45., 78.33, 30.33, 
    10.73}, {46.67, 38.33, 21.83, 15.73}, {53.33, 13.33, 13.33, 
    12.33}, {73.33, 23.33, 12.08, 18.13}, {13.33, 28.33, 19.58, 
    10.73}, {33.33, 33.33, 21.83, 21.93}, {26.67, 28.33, 27.58, 
    7.33}, {23.33, 18.33, 14.83, 6.93}, {33.33, 40.83, 30.08, 12.33}};

Addendum

Kirma gives a beautiful solution. In order to test his approach, I have an idea. Let assume I have following data2 which is subset of data. Since, I believe, there is $5!\times4!\times3!=17280$ permutations, we can use Brute-Force method on data2 and compare Kirma's method on the same data. But I could not solve the problem using Brute-Force method. Any idea? Here is the data2.

data2=Take[data, {1, 5}, {1, 3}]

data2={{36.67, 23.33, 18.33}, {20., 33.33, 30.83}, {16.67, 60.83, 22.08}, {26.67, 53.33, 24.33}, {53.33, 43.33, 11.33}};

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The formulation of the problem has to be reviewed. Currently there are some language or logical inconsistencies. $\endgroup$
    – Anton Antonov
    Commented Apr 9, 2018 at 11:50
  • $\begingroup$ @AntonAntonov Can you please elaborate more? If there is some unclear part I am happy to give more details. You are free to edit the question. Thanks for the comment. $\endgroup$
    – OkkesDulgerci
    Commented Apr 9, 2018 at 14:37
  • $\begingroup$ I put a section with a more consistent definition. Please review. $\endgroup$
    – Anton Antonov
    Commented Apr 9, 2018 at 19:47

2 Answers 2

Reset to default
19
$\begingroup$

Turning a comment into an answer. This is more or less a straight-forward adaptation of a solution in Efficient solution for a discrete assignment problem with pairwise costs to the problem. This method performs small weighted permutations of an ordered list representing the truck-post schedule. Permutations are accepted if they improve the metric, but may be accepted with decreasing probability also when the metric worsens as a result. This is a method to increase chances of exiting local minima, and is controlled below by the parameter alpha. (In the case of this problem and the way permutations, schedule list and the metric interoperate this is practically unnecessary, but comes along from earlier answer.)

First we define a function that computes time when the last job is done at any port (which is the same as the time to unload the last truck):

ClearAll[scheduleTime, scheduleStep];

scheduleStep[{truckportdelays_, {trucktime_, porttime_}}, 
  tuple : {truck_, port_}] := 
 With[{time = 
    Max[{trucktime[[truck]], porttime[[port]]} + 
      Extract[truckportdelays, 
       tuple]]}, {truckportdelays, {ReplacePart[trucktime, 
     truck -> time], ReplacePart[porttime, port -> time]}}]; 

scheduleTime[tuples_, truckportdelays_] := 
 Max@Fold[scheduleStep, {truckportdelays, 
     Table[0, #] & /@ Dimensions@truckportdelays}, tuples][[2, 2]];

And then adapt the previous solution to this:

ClearAll@timeMinimize;

timeMinimize[truckportdelays_, alpha_, iter_Integer] := 
  Module[{permutationCost, prependCost, symmetricRandomPermute, 
    proposedCandidate, acceptanceProbability, newCandidate, 
    initialCandidate, minimizationStep},

   permutationCost[perm_List] := scheduleTime[perm, truckportdelays];

   prependCost[perm_List] := {permutationCost@perm, perm};

   symmetricRandomPermute[{_, perm_List}] := 
    Permute[perm, 
     Cycles[{RandomSample[Range@Length@perm, 
        Min[Length@perm, 
         2 + RandomVariate[GeometricDistribution[1/2]]]]}]];

   proposedCandidate[candidate_List] := 
    prependCost@symmetricRandomPermute[candidate];

   acceptanceProbability[candnew_List, candold_List] := 
    Min[1, Exp[-alpha (First@candnew - First@candold)/
        First@candold]];

   newCandidate[candidate_List] := 
    With[{newcand = proposedCandidate@candidate}, 
     RandomChoice[{#, 1 - #} &@
        acceptanceProbability[newcand, candidate] -> {newcand, 
        candidate}]];

   initialCandidate = 
    prependCost@
     RandomSample@
      Flatten[Table[{i, j}, {i, Dimensions[truckportdelays][[1]]}, {j,
          Dimensions[truckportdelays][[2]]}], 1];

   minimizationStep[{lastmin_List, candidate_List}] := 
    With[{newcand = newCandidate@candidate}, {First@
       TakeSmallestBy[{lastmin, newcand}, First, 1], newcand}];

   First@Nest[minimizationStep, {initialCandidate, initialCandidate}, 
     iter]];

Now we get the following result after 1000 iterations (important one being the first value, time):

timeMinimize[data, 500, 1000]

{723.32, {{9, 2}, {3, 4}, {18, 3}, {17, 1}, {6, 4}, {10, 1}, {12, 4}, {17, 4}, {5, 3}, {4, 1}, {19, 4}, {17, 3}, {11, 2}, {18, 2}, {16, 4}, {7, 3}, {4, 4}, {1, 4}, {15, 1}, {3, 3}, {8, 2}, {16, 1}, {17, 2}, {7, 1}, {14, 2}, {16, 3}, {19, 3}, {2, 2}, {13, 3}, {19, 1}, {10, 2}, {5, 1}, {1, 2}, {6, 1}, {16, 2}, {20, 2}, {15, 2}, {3, 2}, {20, 1}, {13, 2}, {12, 1}, {14, 3}, {18, 4}, {7, 2}, {19, 2}, {4, 2}, {11, 1}, {8, 3}, {14, 1}, {2, 4}, {13, 4}, {10, 4}, {6, 3}, {14, 4}, {1, 3}, {6, 2}, {12, 3}, {18, 1}, {10, 3}, {8, 4}, {1, 1}, {4, 3}, {9, 1}, {13, 1}, {8, 1}, {11, 3}, {15, 4}, {7, 4}, {9, 3}, {2, 3}, {20, 3}, {11, 4}, {9, 4}, {2, 1}, {12, 2}, {15, 3}, {5, 4}, {5, 2}, {20, 4}, {3, 1}}}

We can compare this with the minimum and mean of million random schedules:

Table[scheduleTime[
   RandomSample@
    Flatten[Table[{i, j}, {i, 20}, {j, 4}], 1], data], 1000000] // {Min@#, Mean@#} &

{723.32, 898.777}

And here's a visualization of the answer above:

ClearAll[scheduleForPorts, portScheduleStep];

portScheduleStep[{truckportdelays_, {trucktime_, porttime_}, 
   portused_}, tuple : {truck_, port_}] := 
 With[{time = 
    Max[{trucktime[[truck]], porttime[[port]]} + 
      Extract[truckportdelays, 
       tuple]]}, {truckportdelays, {ReplacePart[trucktime, 
     truck -> time], ReplacePart[porttime, port -> time]}, 
   ReplacePart[portused, 
    port -> Append[portused[[port]], 
      Interval[{Max[{trucktime[[truck]], porttime[[port]]}], 
        time}]]]}]; 

scheduleForPorts[tuples_, truckportdelays_] := 
 Fold[portScheduleStep, {truckportdelays, 
    Table[0, #] & /@ Dimensions@truckportdelays, {} & /@ 
     Range@Dimensions[truckportdelays][[2]]}, tuples][[3]];

scheduleForPorts[{{9, 2}, {3, 4}, {18, 3}, {17, 1}, {6, 4}, {10, 
   1}, {12, 4}, {17, 4}, {5, 3}, {4, 1}, {19, 4}, {17, 3}, {11, 
   2}, {18, 2}, {16, 4}, {7, 3}, {4, 4}, {1, 4}, {15, 1}, {3, 3}, {8, 
   2}, {16, 1}, {17, 2}, {7, 1}, {14, 2}, {16, 3}, {19, 3}, {2, 
   2}, {13, 3}, {19, 1}, {10, 2}, {5, 1}, {1, 2}, {6, 1}, {16, 
   2}, {20, 2}, {15, 2}, {3, 2}, {20, 1}, {13, 2}, {12, 1}, {14, 
   3}, {18, 4}, {7, 2}, {19, 2}, {4, 2}, {11, 1}, {8, 3}, {14, 1}, {2,
    4}, {13, 4}, {10, 4}, {6, 3}, {14, 4}, {1, 3}, {6, 2}, {12, 
   3}, {18, 1}, {10, 3}, {8, 4}, {1, 1}, {4, 3}, {9, 1}, {13, 1}, {8, 
   1}, {11, 3}, {15, 4}, {7, 4}, {9, 3}, {2, 3}, {20, 3}, {11, 4}, {9,
    4}, {2, 1}, {12, 2}, {15, 3}, {5, 4}, {5, 2}, {20, 4}, {3, 1}}, data] // NumberLinePlot

enter image description here

So, in practice, unloading time is limited by capacity of ports 1 and 2.

Also, this solution must be optimal under the criterion at use - port 1 cannot complete the task faster under any circumistances:

Total@data

{723.32, 721.6, 406.35, 285.2}

If you want to minimize total operating time of ports (including idle time between jobs), you can replace Max in scheduleTime with Total. This "encourages" finding a scheduling order with no gaps, and works surprisingly well!

enter image description here

Improve this answer
$\endgroup$
0
$\begingroup$

Here is Brute-Force method for $4\times4$ case to compare(This approach gives worse case scenario). So we will solve the problem for the first four trucks.

I know this method will not be efficient even for $5\times5$. See http://mathworld.wolfram.com/LatinSquare.html

(data = {{36.67, 23.33, 18.33, 12.33}, {20., 33.33, 30.83, 10.33}, {16.67, 
  60.83, 22.08, 16.13}, {26.67, 53.33, 24.33, 11.93}}) // MatrixForm

$\left( \begin{array}{cccc} 36.67 & 23.33 & 18.33 & 12.33 \\ 20. & 33.33 & 30.83 & 10.33 \\ 16.67 & 60.83 & 22.08 & 16.13 \\ 26.67 & 53.33 & 24.33 & 11.93 \\ \end{array} \right)$

Let each color represent truck's color. 

ArrayPlot[#, 
   ColorRules -> {Alternatives @@ data[[1]] -> Red, 
     Alternatives @@ data[[2]] -> Darker@Green, 
     Alternatives @@ data[[3]] -> Darker@Magenta, _ -> Blue}, 
   Epilog -> 
    Join @@ MapIndexed[
      Inset[Style[#, White, 26], Reverse[#2 - 1/2]] &, 
      Reverse@#, {2}], ImageSize -> 400, Mesh -> All, Frame -> True, 
   MeshStyle -> White] &@data

enter image description here

We can use the @Mark 's code here

    MatrixOK2[matrix_, columns_] := 
      Max[Length[#] & /@ 
         Flatten[Outer[Intersection, mat, matrix, 1], 1]] <= 1;
    matrixSize = {4, 4};
    (mat = ArrayReshape[Range@(Times @@ matrixSize), matrixSize]) // 
      MatrixForm;
    sub = Subsets[#, {2, matrixSize[[2]]}] & /@ mat;
    columns = Transpose@mat;
    columnPermutations = Permutations[#, {matrixSize[[1]]}] & /@ columns;
    allPossibilities = Transpose /@ Tuples[columnPermutations];
    okChoices = Select[allPossibilities, MatrixOK2[#, matrixSize[[2]]] &];

s = Table[
   SparseArray[
    Thread[Join @@ Position[okChoices[[i]], #] & /@ Range@16 -> 
      Flatten@data]], {i, Length@okChoices}];
totalTime = Total /@ Map[Max, s, {2}];

min = totalTime // Min

170.82

    pos = Position[totalTime, min];
MatrixForm /@ Extract[s, pos] // Normal;

ArrayPlot[#, 
   ColorRules -> {Alternatives @@ data[[1]] -> Red, 
     Alternatives @@ data[[2]] -> Darker@Green, 
     Alternatives @@ data[[3]] -> Darker@Magenta, _ -> Blue}, 
   Epilog -> 
    Join @@ MapIndexed[
      Inset[Style[#, White, 26], Reverse[#2 - 1/2]] &, 
      Reverse@#, {2}], ImageSize -> 400] & /@ Extract[s, pos][[;; 3]]

enter image description here

We are basically shuffling columnwise and taking max of each row and then summing total time. First solution says, take first row and wait 60.83min, and take second row and wait 23.33min, and take third row and wait 53.33min, take last row and wait 33.33. Total waiting time is $60.83+23.33+53.33+33.33=170.82$ Here we are checking all 576 possible combinations.

Here is the solution using @kirma 's code. Data is as above (4 truck only).

timeMinimize[data, 500, 1000]

{170.82, {{4, 3}, {4, 4}, {3, 1}, {2, 2}, {1, 2}, {1, 3}, {3, 4}, {2, 1}, {3, 2}, {2, 3}, {4, 1}, {2, 4}, {1, 4}, {1, 1}, {4, 2}, {3, 3}}}

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.