15
$\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 and all are at the port at the same time. They need to stop each of the 4 ports to unload their freight. There is waiting time for each truck at each port. Please see the table. Truck1 is waiting 36.67 minutes at port1, 23.33 minutes at port2, 18.33 minutes at port3 and 12.33 minutes at port4. There cannot be 2 trucks at the the same port at the same time and trucks cannot be 2 different port at the same time. There is no specific order. I want to minimize total unloading time. What should be order trucks trucks?

\begin{array}{c|cccc} & p_1 & p_2 & p_3 & p_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}};

Proposed more consistent definition

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}

$\endgroup$
  • 1
    $\begingroup$ The formulation of the problem has to be reviewed. Currently there are some language or logical inconsistencies. $\endgroup$ – Anton Antonov Apr 9 '18 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 Apr 9 '18 at 14:37
  • $\begingroup$ I put a section with a more consistent definition. Please review. $\endgroup$ – Anton Antonov Apr 9 '18 at 19:47
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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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