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.


* 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


* 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\]


    \[\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}\]


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