3

家のトリム モールディングを切断していますが、さまざまな長さのトリム ピースがあり、無駄を最小限に抑えるためにそれらを最適にグループ化したいと考えています。基本的に、必要な長さを利用可能なより長い長さに最適にグループ化 (またはパック) しようとしています。

私はこれにアプローチする方法に少し困惑しており、現在は手作業で行っていますが、間違いが原因で操作全体をやり直すことになります。私は Java をある程度知っていますが、最近はもっぱら R を使用しているので、現時点では R が最もなじみのある言語です。これにアプローチする方法についての提案はありますか?

このようなアルゴリズムを手動でループするよりも、これを行うためのより良い方法はありますか (私はアイデアをスケッチしているだけです。正しい構文を探してはいけません):

trim_lengths <- c(44, 57, 86, 86, 40, 88, 88, 41, 40, 40,
  62, 62, 54, 54, 55, 55, 63, 63, 75, 75, 100, 100)

avail_lengths <- c(120, 103, rep(100, 9), 98, rep(97, 4),
  95, rep(88, 3), 85, 65)

while(length(trim_lengths) > 0) {
  current_max <- max(trim_lengths)
  current_min <- min(trim_lengths)

  if(current_max + current_min > max(avail_lengths) {
    find smallest value in avail_lengths that's greater than current_max
    store current_max and optimal value from avail_lengths in list or vector
      to indicate the pairing/grouping
  }

  else {
    group <- c(current_max, current_min)
    current_max <- trim_lengths minux elements in group
    if <- sum(group) + current_max > max(avail_lengths) {
      store group and corresponding avail_length element in list/vector
    }

    else{
      basically, keep trying to group until solved
    }
  }

ベクトルの「外側」からチェックしているため、それが最適ではないことはすでにわかっていtrim_lengthsます。手作業で行ったペアリングでは、小さいレベルと中間レベルの値を、非常に見やすい利用可能な長さにペアリングすることがよくあります。上記のペアリングより2つ長い。

とにかく、それは興味深い問題であり、解決策として心に浮かぶ参考文献や明白な提案があるかどうか疑問に思いました. 関連する質問のいくつかでは、最初のコメントで「何を試しましたか」という質問がよく寄せられました。私は本当にそうではありません... 私は今困惑しているので. 私が考えた他の唯一のことは、組み合わせをランダムにブルートフォースし、無駄を最小限に抑えるソリューションを保存することでした.

これをベクトル化された方法で解決するためのいくつかの提案が欲しいです-ある種の行列演算、またはおそらく問題の線形モデル表現。私も引き続き考えてみます。

4

4 に答える 4

3

このmultiple-knapsack問題は、 を使ってみるのが楽しい問題のように思えましlpSolveAPIた。整数計画法のアプローチを使用して、トリムの問題に対する最適なソリューションを見つけました。

まず、私が見つけた解決策は次のようになります。

ここに画像の説明を入力

ご覧のとおり、まったく必要のない 5 つの利用可能なピースがありました。(100%黒字)

処方

  • a_1、a_2、...、a_k を使用可能なピースの長さとします。

  • t_1、t_2、...、t_n を必要なトリム長とします。

  • 変数:トリムtが利用可能なピースaから切り取られた場合は X_a_t を 1に、そうでない場合は 0 にします

Surplus_i を A_i から j=1..n の (X_a_t * t_j) の合計を引いたものと定義します。

  • 目的: すべての A (1..k) の Surplus_i の合計を最小化する

制約

  • Set Partitioning Constraint: (英語) すべてのトリムは一部から切り取る必要があります

      Sum over A(1..k) X_a_t = 1 for all t (1..n)

また、すべての余剰は >= 0 でなければなりません # マイナスは許可されません

A_i - sum over j in 1..k X_ai_tj * t_j  = Surplus_i (for each Ai) # definitional constraint.

lpSolveAPI を使用した R コード

私の A マトリックス (列の最初のセットは余剰変数で、次のセットは X_a_t 変数です。制約の最初のセットは「カバーの設定」制約です。制約の 2 番目のセットは「余剰」非負制約です。調べます。完全な配合を表示するには、trimIP.lp ファイルを参照してください。

警告:コードは私が思っていたよりも長いですが、ここにあります:

library(lpSolveAPI)

#Problem definition
trim.lengths <- c(44, 57, 86, 86, 40, 88, 88, 41, 40, 40, 62, 62, 54, 54, 55, 55, 63, 63, 75, 75, 100, 100)
avail.lengths <- c(120, 103, rep(100, 9), 98, rep(97, 4), 95, rep(88, 3), 85, 65)
num.trims = length(trim_lengths) #22
num.avail = length(avail.lengths) #22
a.set<-1:num.avail
t.set <- 1:num.trims

#set rownames & colnames
setRowAndColNames<- function() {  
  a.and.t<- t(outer(a.set, t.set, paste, sep="_"))
  col.names <- paste("x_", a.and.t, sep="")
  s.vars <- paste("Surplus_", a.set, sep="")
  c.names <- c(s.vars, col.names)
  r.names <- setRowNames() 
  return( list(r.names, c.names)  )
}

setRowNames <- function() {
  cover.rows<- paste("CoverTrim", t.set, sep="_") #Cover constraints
  surplus.rows <- paste("DefineSurplus", a.set, sep="_") #non-neg constraints
  r.names <- c(cover.rows, surplus.rows)
  return(r.names)
}

populate.Amatrix <- function() {  
  df <- data.frame(matrix(0, n.rows, n.cols))  #create a dataframe shell  
  for (row in 1:num.trims) {
    skip = num.avail #for the surplus variables
    cols <- seq(0, (num.trims*num.avail)-1, by=num.avail)    
    df[row, skip+cols+row] <- 1
  }
  print("Done with cover Trims Constraints")
  st.row <- num.trims+1
  end.row<- st.row+num.avail-1
  for (row in st.row:end.row) {
    surplus.column <- row - num.trims
    df[row,surplus.column] <- 1
    current.a <- surplus.column
    acols <- num.avail + ((current.a-1)*num.trims) + (1:num.trims)
    df[row,acols] <- trim.lengths

  }
  return(df)
}


defineIP <- function(lp) {
  obj.vector <- c(rep(1, num.avail), rep(0, num.avail*num.trims))
  set.objfn(lp, obj.vector ) #minimize surplusses
  set.constr.type(lp, rep("=", n.rows), 1:n.rows) 
  rhs.vector <- c(rep(1, num.avail), avail.lengths)
  set.rhs(lp, b=rhs.vector, constraints=1:n.rows) # assign rhs values   

  #Set all the columns at once
  for (col in 1:n.cols) {
    set.column(lp, col, df[ ,col])  
  }

  for (col in (num.avail+1):n.cols) {
    print(col)
    set.type(lp, col, "binary")      
  }

  #assemble it all
  dimnames(lp) <- setRowAndColNames()
  write.lp(lp, "trimIP.lp", "lp")#write it out
}


# actual problem definition
n.rows <- num.trims + num.avail
n.cols <- (num.avail+1) * num.trims  #the extra one is for surplus variables
df <- populate.Amatrix()

lptrim <- make.lp(nrow=n.rows, ncol=n.cols)
defineIP(lptrim)
lptrim
solve(lptrim)
sol <- get.variables(lptrim)
sol <- c(sol, trim.lengths)
sol.df <- data.frame(matrix(sol, nrow=24, ncol=22 , byrow=T)) #you can examine the solution data frame

演習全体を再現したい場合は、コードを github gist として配置しました

于 2013-08-06T07:18:55.437 に答える
3

ここに画像の説明を入力   http://xkcd.com/287/の礼儀

(はい、これはコメントであり、回答ではありません。小さなコメント行に imgs のみをロードできれば)

于 2013-08-03T20:31:45.297 に答える
1

私には、1-D のカッティング ストックの問題のように見えます。http://en.wikipedia.org/wiki/Cutting_stock_problemをご覧ください 。このトピックについては、かなりの数の記事があります。

お役に立てれば。誰かが現実的な問題を抱えていて、やみくもに突っ込むのではなく、実際に問題を解決する方法を考えているとき、私はそれが大好きです。あなたが実際に実際の仕事をするのを忘れる複雑さも!

于 2013-08-04T20:50:42.000 に答える
0

遺伝的アルゴリズムの使用を検討したことがありますか?

于 2013-08-04T21:12:45.170 に答える