一般化割当法 (運搬経路問題における)

【いっぱんかわりあてほう (generalized assignment method)】

運搬経路問題に対する近似解法であり, 顧客集合の各運搬車への割り当てを行う. まず運搬車の台数分の種点(seed points)を領域内に適当に設定し, デポ(depot)と種点を往復する巡回路を仮定し, 各顧客を巡回路に挿入したときの費用の増分を計算する. 続いて運搬車の積載量を超過しないという条件のもと, 費用が最小となるように顧客を運搬車に割り当てる. この問題は一般化割当問題に帰着される.