Service network design problem

サービスネットワーク設計問題とは,宅配便などの長期レベルのネットワークを設計するためのモデルである.このようなモデルは諸外国では成功しているが,我が国ではデータ未整備や意思決定におけるストラテジックなビジョンが不足しているため,未だ使用されていない.

Consider a service network:

Center (i) => Base (k) => Base (\ell ) =>Center (j)

Number of centers is more than 1000.

Number of bases is around 200.

Given:

* c_{ik} : transportation cost of a vehicle between points i and k
* Q: capacity of vehicles
* D_{ij}: demand from origin i to destination j

Variable:

* x_{ik}: =1 if center i is assigned to base k, =0 otherwise
* y_{k \ell}: number of vehicles between k and \ell

Since the number of variables is too large, we need to restrict the search domain in the following way:

For center i, the candidate bases to be assigned are restricted to the “near” bases.

For center i, let C^*_i is the cost (or distance) to the nearest base.

Given a parameter \alpha > 1, we restrict the set of bases to be assigned to center i:

    \[\{ k \in Base | C_{ik} \leq \alpha C^*_i \}\]

If x_{ik}=1 and x_{j \ell}=1, the flow volume between bases j and \ell is increaded by D_{ij}.

We get:

    \[\sum_{i,j} D_{ij} x_{ik} x_{j \ell} \leq Q y_{k \ell} \ \ \ \forall k,\ell.\]

We also get the number of vehicles between center i and base k:

    \[\sum_{j} D_{ij} x_{ik} \leq Q y_{ik} \ \ \ \forall i,k\]

and

    \[\sum_{j} D_{ji} x_{ik} \leq Q y_{ki} \ \ \ \forall i,k\]

Capacity of base k is less than or equal to CAP_k:

    \[\sum_{i} \sum_{j} (D_{ij} + D_{ji}) x_{ik} \leq CAP_k \ \ \ \forall k\]

The objective function

    \[\sum_{i,j} c_{ij} y_{ij}\]

should be minimized under the constraints:

    \[\sum_{k} x_{ik} =1 \ \ \forall i\]

For the MIP solver, we need to rewrite

    \[\sum_{i,j} D_{ij} x_{ik} x_{j \ell} \leq Q y_{k \ell} \ \ \ \forall k,\ell.\]

into linear constraints:

By intruducing a new 0-1 variable z_{ikj\ell} that is equal to 1 if and only if x_{ik}=x_{j\ell}=1,
we get:

    \[x_{ik} + x_{j \ell} -1 \leq z_{ikj\ell}\]

and

    \[\sum_{i,j} D_{ij} z_{ikj\ell} \leq Q y_{k \ell} \ \ \ \forall k,\ell.\]

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>