1 Introduction
2 Literature review
3 Detailed problem formulation
Notation | Description |
---|---|
n | Number of container types |
Q | Quality levels. Level 0 corresponds to perfect quality and level \(Q+1\) to unacceptable level |
F | Inspection is done on facility 0 and repair is done on facilities \(0,1,\ldots ,F\) |
T | Number of time periods in the planning horizon |
\({c}_{j}^{({{rej}})}\) | Cost of rejection of one container of type j, \(j=1,\ldots ,n\) |
\(c^{(ins)}_j\) | Cost of inspection of one container of type j and any quality level at any facility, \(j=1,\ldots ,n\) |
\( c_{{jq}}^{{({{rep}})}}\) | Cost of repair of one container of type j and quality level q at any facility, \(j=1,\ldots ,n\), \(q=0,1,\ldots ,Q\), \(c^{(rep)}_{j0}=0\) (for good quality containers) |
\( c_{j}^{{({{rep}})}} = \frac{{\sum\limits_{{q = 0}}^{Q} {c_{{{\text{jq}}}}^{{({{rep}})}} } p_{{{\text{jq}}}} }}{{100}} \) | Expected cost of repair of one container of type j and any quality level but quality level \(Q+1\) at any facility, \(j=1,\ldots ,n\) |
\( c_{f}^{{({{tra}})}} \) | Cost of transportation of one container of any type from facility 0 to facility f, \(f=1,\ldots ,F\) |
\( c_{f}^{{({{hol}})}} \) | Holding cost of one container of any type at facility f when passing from any time period t to time period \(t+1\), \(t=0,1,\ldots ,T\), \(f=0,1,\ldots ,F\) |
\( d_{{{\text{jt}}}} \) | Demand of containers of type j which is the number of good quality containers of type j that should be available for clients by the end of time period t, \(j=1,\ldots ,n\), \(t=1,\ldots ,T\). This demand can be satisfied by containers repaired in time periods \(1,\ldots ,t\), and it cannot be satisfied by those repaired in the later time periods |
\( g_{{{\text{jf}}}} \) | Initial inventory of good quality containers of type j at facility f at the beginning of time period 1, \(j=1,\ldots ,n\), \(f=0,1,\ldots ,F\) |
\( k_{{{\text{jt}}}} \) | Number of containers of type j arriving to facility 0 at the beginning of time period t, \(j=1,\ldots ,n\), \(t=1,\ldots ,T\) |
m | Transportation capacity, which is the total number of containers of any type that can be moved from facility 0 to all other facilities in any single time period. If the set M of vehicles, their container capacities \(cap_v\) and numbers of journeys \(num_v\) in any single time period are known, then \(m=\sum _{v\in M}cap_vnum_v\) |
\(\frac{p_{jq}}{100}\) | Probability that the quality level of any single non-inspected container of type j is q, \(p_{jq}\in \{0,1,\ldots ,100\}\), \(j=1,\ldots ,n\), \(q=0,1,\ldots ,Q+1\), \(\sum _{q=0}^{Q+1} p_{jq}=100\). It can be a historical percentage of containers of quality level q among all the inspected containers of type j. It is restrictively assumed that the number of containers of quality level q among any x non-inspected containers of type j is equal to \(\frac{p_{jq}x}{100}\) for any x. (Inderfurth et al. 2006),(Inderfurth et al. 2007) point out that it is often the case in practice that statistical observations provide information about the usual percentage of defective items |
\(r_{jq}\) | Number of working-hours required to repair one container of type j of quality level \(q\ne Q+1\) at any facility, \(j=1,\ldots ,n\), \(q=0,1,\ldots ,Q\), \(r_{j0}:=0\) (for good quality containers) |
\(r_j=\frac{\sum _{q=0}^Qr_{jq}p_{jq}}{100}\) | Expected number of working-hours required to repair one container of type j of any quality level but quality level \(Q+1\) at any facility, \(j=1,\ldots ,n\) |
\(s_j\) | Number of working-hours required to inspect one container of type j at any facility, \(j=1,\ldots ,n\) |
\(U_f\) | Upper bound on working-hours available for repair work in any time period at facility f, \(f=0,1,\ldots ,F\) |
\(u_{jf}\) | Initial inventory of non-inspected containers of type j at facility f at the beginning of time period 1, \(j=1,\ldots ,n\), \(f=0,1,\ldots ,F\) |
\(V_f\) | Upper bound on working-hours available for inspection in any time period at facility f, \(f=0,1,\ldots ,F\) |
\(W_f\) | Storage capacity of facility f, which is the number of containers of all types that can be simultaneously kept at f, \(f=0,1,\ldots ,F\) |
-
\(O_0\) – set of nodes each of which has at least one predecessor and at least one successor.
-
\(P_v\) – set of ingoing arcs of the node \(v\in O_0\).
-
\(S_v\) – set of outgoing arcs of the node \(v\in O_0\).
-
\(A^-\) – set of arcs corresponding to the flow of arriving and accepted containers via facility \(-1\) and to the flow of non-inspected and non-repaired containers over time at the same facility \(f\in \{0,1,\ldots ,F\}\). These are the unmarked arcs in Fig. 1.
-
\(A^\circ \) – set of arcs \(((f,t),(f,t+1),\circ )\) and \(((f,t),(F+1,t),\circ )\) corresponding to the good quality containers kept at facility f in the time period from t to \(t+1\) and that are carried from facility f to facility \(F+1\) in the same time period t, respectively. These containers were quality checked at time \(t-1\) or earlier and are therefore known to be of good quality when they arrive to facility f at t. These arcs are marked with symbol “\(\circ \)” in Fig. 1.
-
\(A^\bullet _{ft}\) – set of arcs \(((f,t),(f,t+1),\bullet )\) and \(((f,t),(F+1,t),\bullet )\) corresponding to the flow of good quality containers, which were inspected and possibly repaired at facility f at time t. These arcs are marked with symbol “\(\bullet \)” in Fig. 1.
-
\(A^\bullet =\cup _{f=0}^F\cup _{t=1}^T A^\bullet _{ft}\).
-
\(A^\times _{ft}\) – set of arcs corresponding to the transportation of non-inspected and non-repaired containers from facility 0 to facility \(f\in \{1,\ldots ,F\}\) in time period t. These arcs are marked with symbol “\(\times \)” in Fig. 1.
-
\(A^\times =\cup _{f=1}^F\cup _{t=1}^T A^\times _{ft}\).
-
\(A^\lozenge \) – set of arcs corresponding to the flow of non-repairable containers among containers inspected for quality. These arcs are marked with symbol “\(\lozenge \)” in Fig. 1.
-
\(A^\thicksim \) – set of arcs corresponding to the flow of rejected containers. These arcs are marked with symbol “\(\thicksim \)” in Fig. 1.
4 Computational complexity
5 Computer experiments
-
number of containers of type j arriving to facility 0 at the beginning of time period t: \(k_{jt}\in [100,300]\), \(j=1,\ldots ,n\), \(t=1,\ldots ,T\);
-
initial inventory of non-inspected containers of type j at facility f at the beginning of time period 1: \(u_{jf}\in [0,100]\), \(j=1,\ldots ,n\), \(f=0,1,\ldots ,F\);
-
initial inventory of good quality containers of type j at facility f at the beginning of time period 1: \(g_{jf}\in [0,100]\), \(j=1,\ldots ,n\), \(f=0,1,\ldots ,F\);
-
demand of containers of type j at the end of period t: \(d_{jt}\in [\lfloor 0.8D_j\rfloor ,\lfloor 1.2D_j\rfloor ]\), where \(D_j=\frac{\sum _{f=0}^F (u_{jf}+g_{jf})+\sum _{\tau =1}^T k_{j\tau }}{T}\) is the average amount of available containers per time period, \(j=1,\ldots ,n\), \(t=1,\ldots ,T\);
-
transportation capacity: \(m\in [\lfloor 0.8M\rfloor ,\lfloor 1.2M\rfloor ]\), where \(M=\frac{F\sum _{j=1}^nD_j}{F+1}\) is the average amount of available containers per time period multiplied by \(\frac{F}{F+1}\) to account for the containers which are not moved from facility 0;
-
nominator in the probability that the original quality level of any single inspected container of type j is q: \(p_{j0}\in [5,10]\), \(p_{j,Q+1}\in [0,5]\) and \(p_{jq}=\Big \lfloor \frac{(100-p_{j0}-p_{j,Q+1})\ x_q}{\sum _{h=1}^Q x_h}\Big \rfloor \), where random numbers \(x_q\in [0,100]\) for \(q\in \{1,\ldots ,Q\}\), \(j=1,\ldots ,n\). For each j, calculate \(\Delta _j=100-\sum _{q=0}^{Q+1}p_{jq}\). Note that \(\Delta _j\le Q\) due to the rounding down operation for \(p_{jq}\). Introduce set of indices \(H=\{1,\ldots ,Q\}\). For each j, generate random number \(h\in H\) and re-set \(p_{jh}:=p_{jh}+1\). Remove h from H and repeat generation of h and re-setting of \(p_{jh}\). Repeat this process \(\Delta _j\) times to get \(\sum _{q=0}^{Q+1}p_{jq}=100\), \(j=1,\ldots ,n\);
-
number of working-hours required to inspect one container of type j at any facility: \(s_j=\frac{s'_j}{60}\), where \(s'_j\in [20,60]\), \(j=1,\ldots ,n\);
-
upper bound on the available working-hours for inspection in each time period at facility f: \(V_f\in [\lfloor 1.2I\rfloor ,\lfloor 1.8I\rfloor ]\), where \(I=\frac{\sum _{j=1}^ns_jD_j}{F+1}\) is the average amount of working-hours required to inspect all the available containers per time period and facility, \(f=0,1,\ldots ,F\);
-
number of working-hours required to repair one container of type j and quality level \(q\in \{1,\ldots ,Q\}\) at any facility: \(r_{jq}=\frac{r'_{jq}}{60}\), where \(r'_{jq}\in [20q,20(q+1)]\), \(j=1,\ldots ,n\), \(q=1,\ldots ,Q\);
-
upper bound on working-hours available for repair work in any time period at facility f: \(U_f\in [\lfloor 1.2J\rfloor ,\lfloor 1.8J\rfloor ]\), where \(J=\frac{\sum _{j=1}^n\sum _{q=1}^Qp_{jq}r_{jq}D_j}{100(F+1)}\) is the average amount of working-hours required to repair all the available containers of quality levels \(1,\ldots ,Q\) per time period and facility, \(f=0,1,\ldots ,F\);
-
storage capacity of facility f: \(W_f\in [\lfloor 0.9\frac{(3\sum _{j=1}^nD_j)}{F+1}\rfloor ,\lfloor 1.1\frac{(3\sum _{j=1}^nD_j)}{F+1}\rfloor ]\), where \(\frac{3\sum _{j=1}^nD_j}{F+1}\) is the tripled average amount of the available containers per time period and facility to allow storage of the containers from the previous time periods, \(f=0,1,\ldots ,F\);
-
cost of inspection of one container of type j and any quality level at any facility: \(c^{(ins)}_j=20s_j\), where 20 is the cost of one working-hour of inspection work, \(j=1,\ldots ,n\).
-
cost of repair of one container of type j and quality level q at any facility: \(c^{(rep)}_{jq}=30r_{jq}\), where 30 is the cost of one working-hour of repair work, \(j=1,\ldots ,n\), \(q=1,\ldots ,Q\), \(c^{(rep)}_{j0}=0\) (for good quality containers);
-
cost of transportation of one container of any type from facility 0 to facility f: \(c^{(tra)}_f\in [50+10f,150+10f]\) , \(f=1,\ldots ,F\);
-
holding cost of one container of any type at facility f when passing from any time period t to time period \(t+1\), \(t=0,1,\ldots ,T\): \(c^{(hol)}_f\in [1+\frac{F-f}{2},2+\frac{F-f}{2}]\), \(f=0,1,\ldots ,F\).
-
number of instances for which no feasible solution was found within the time limit (row \(\#_{infeas}\)). For any instance in our experiments, either both problems CMCF and CMCF-R had feasible solutions or both of them had no feasible solution, which was established by running CPLEX until a feasible solution was found or infeasibility was established. Since any instance of CMCF-R was solved in less than 1 second, parameter \(\#_{infeas}\) is independent of the solution time limit;
-
number of instances of CMCF for which an optimal solution was provably found within the time limit (row \(\#_{opt}\)). Note that the number of feasible instances for which no optimal solution was provably found within the time limit is equal to \(20-\#_{infeas}-\#_{opt}\);
-
average and maximal run time of CPLEX for CMCF in minutes to find a solution with proven optimality (rows “Mean time to opt” and “Max time to opt,” respectively);
-
mean ratio of the number of rejected containers to the number of all arriving containers over feasible instances (row “Mean \(\frac{{\#\ \hbox {rejected}}}{\#\ \hbox {all}}\)”), where “\(\#\ \hbox {all}\)”\(=\sum _{j=1}^n\sum _{t=1}^T k_{jt}\) .
(T, Q) | (7,5) | (7,9) | (14,5) | (14,9) | (30,5) | (30,9) |
---|---|---|---|---|---|---|
\(\#_{infeas}\) | 0 | 1 | 0 | 0 | 0 | 0 |
Time limit k=5min | ||||||
\(\#_{opt}\) | 10 | 10 | 0 | 0 | 0 | 0 |
Mean time to opt, min | \(<1\) | 1 | – | – | – | – |
Max time to opt, min | \(<1\) | 2 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0.128 | 0.154 | 0.244 | 0.146 | 0.217 | 0.201 |
Time limit k=1h | ||||||
\(\#_{opt}\) | 12 | 13 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 3 | 5 | – | – | – | – |
Max time to opt, min | 31 | 39 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0.092 | 0.107 | 0.244 | 0.146 | 0.217 | 0.201 |
Time limit k=2h | ||||||
\(\#_{opt}\) | 13 | 13 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 8 | 5 | – | – | – | – |
Max time to opt, min | 66 | 39 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0.093 | 0.076 | 0.244 | 0.146 | 0.217 | 0.201 |
Time limit k=3h | ||||||
\(\#_{opt}\) | 13 | 13 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 8 | 5 | – | – | – | – |
Max time to opt, min | 66 | 39 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0.091 | 0.076 | 0.244 | 0.146 | 0.217 | 0.201 |
(T, Q) | (7,5) | (7,9) | (14,5) | (14,9) | (30,5) | (30,9) |
---|---|---|---|---|---|---|
\(\#_{infeas}\) | 0 | 0 | 0 | 0 | 0 | 0 |
Time limit k=5min | ||||||
\(\#_{opt}\) | 8 | 7 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 2 | 1 | – | – | – | – |
Max time to opt, min | 5 | 2 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0.001 | 0 | 0 | 0.001 | 0.001 | 0.002 |
Time limit k=1h | ||||||
\(\#_{opt}\) | 11 | 8 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 8 | 6 | – | – | – | – |
Max time to opt, min | 56 | 43 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0.001 | 0 | 0 | 0.001 | 0.001 | 0.001 |
Time limit k=2h | ||||||
\(\#_{opt}\) | 13 | 9 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 8 | 19 | – | – | – | – |
Max time to opt, min | 56 | 118 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0.001 | 0 | 0 | 0.001 | 0.001 | 0.001 |
Time limit k=3h | ||||||
\(\#_{opt}\) | 13 | 9 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 27 | 19 | – | – | – | – |
Max time to opt, min | 131 | 118 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0.001 | 0 | 0 | 0.001 | 0 | 0.001 |
(T, Q) | (7,5) | (7,9) | (14,5) | (14,9) | (30,5) | (30,9) |
---|---|---|---|---|---|---|
\(\#_{infeas}\) | 0 | 1 | 0 | 0 | 0 | 0 |
Time limit k=5min | ||||||
\(\#_{opt}\) | 5 | 7 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 2 | 1 | – | – | – | – |
Max time to opt, min | 4 | 3 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0 | 0 | 0 | 0.001 | 0.003 | 0.001 |
Time limit k=1h | ||||||
\(\#_{opt}\) | 7 | 10 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 11 | 10 | – | – | – | – |
Max time to opt, min | 42 | 44 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0 | 0 | 0 | 0.001 | 0.003 | 0.001 |
Time limit k=2h | ||||||
\(\#_{opt}\) | 9 | 11 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 32 | 17 | – | – | – | – |
Max time to opt, min | 117 | 88 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0 | 0 | 0 | 0.001 | 0.003 | 0.001 |
Time limit k=3h | ||||||
\(\#_{opt}\) | 9 | 11 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 32 | 17 | – | – | – | – |
Max time to opt, min | 117 | 88 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0 | 0 | 0 | 0.001 | 0.003 | 0.001 |
(T, Q) | (7,5) | (7,9) | (14,5) | (14,9) | (30,5) | (30,9) |
---|---|---|---|---|---|---|
\(\#_{infeas}\) | 1 | 1 | 0 | 0 | 0 | 0 |
Time limit k=5min | ||||||
\(\#_{opt}\) | 13 | 3 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 1 | 2 | – | – | – | – |
Max time to opt, min | 4 | 4 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0 | 0 | 0 | 0.000833 | 0 | 0.002985 |
Time limit k=1h | ||||||
\(\#_{opt}\) | 14 | 8 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 2 | 12 | – | – | – | – |
Max time to opt, min | 12 | 34 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0 | 0 | 0 | 0.001 | 0 | 0.003 |
Time limit k=2h | ||||||
\(\#_{opt}\) | 14 | 8 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 2 | 12 | – | – | – | – |
Max time to opt, min | 12 | 34 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0 | 0 | 0 | 0.001 | 0 | 0.003 |
Time limit k=3h | ||||||
\(\#_{opt}\) | 14 | 8 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 2 | 12 | – | – | – | – |
Max time to opt, min | 12 | 34 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0 | 0 | 0 | 0.001 | 0 | 0.003 |
(T, Q) | (7,5) | (7,9) | (14,5) | (14,9) | (30,5) | (30,9) |
---|---|---|---|---|---|---|
\(\#_{infeas}\) | 0 | 0 | 0 | 0 | 0 | 1 |
Time limit k=5min | ||||||
\(\#_{opt}\) | 6 | 5 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 1 | 1 | – | – | – | – |
Max time to opt, min | 3 | 4 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0 | 0 | 0 | 0 | 0 | 0.002 |
Time limit k=1h | ||||||
\(\#_{opt}\) | 8 | 12 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 4 | 15 | – | – | – | – |
Max time to opt, min | 15 | 58 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0 | 0 | 0 | 0 | 0 | 0.002 |
Time limit k=2h | ||||||
\(\#_{opt}\) | 8 | 12 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 4 | 15 | – | – | – | – |
Max time to opt, min | 15 | 58 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0.0002 | 0 | 0 | 0 | 0 | 0.002 |
Time limit k=3h | ||||||
\(\#_{opt}\) | 8 | 14 | 0 | 0 | 0 | 0 |
Mean time to opt, min | 4 | 31 | – | – | – | – |
Max time to opt, min | 15 | 130 | – | – | – | – |
Mean \(\frac{\#\ \hbox {rejected}}{\#\ \hbox {all}}\) | 0 | 0 | 0 | 0 | 0 | 0.002 |
k (hours) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
Instance 1 | ||||||||||
Gap | 0.428 | 0.337 | 0.297 | 0.282 | 0.276 | 0.271 | 0.266 | 0.262 | 0.246 | 0.226 |
\(\frac{C^{(kh)}}{C^{(R)}}\) | 1.753 | 1.514 | 1.428 | 1.398 | 1.386 | 1.376 | 1.368 | 1.36 | 1.33 | 1.297 |
Instance 2 | ||||||||||
Gap | 0.516 | 0.455 | 0.431 | 0.42 | 0.401 | 0.39 | 0.382 | 0.378 | 0.33 | 0.287 |
\(\frac{C^{(kh)}}{C^{(R)}}\) | 2.141 | 1.9 | 1.822 | 1.786 | 1.73 | 1.697 | 1.675 | 1.665 | 1.548 | 1.453 |