Maritime Inventory Routing · Distributional MIPLIB

Problem Description

The Maritime Inventory Routing Problem (MIRP) arises from global bulk shipping and involves both ship routing and inventory management. The problem not only determines routes from production (loading) ports to consumption (discharging) ports to minimize transportation costs, but also manages the inventory at these ports [Papageorgiou14]. [Papageorgiou14] introduced a mixed-integer programming core model of this problem class and developed a library of publicly available test instances (MIRPLib, mirplib.scl.gatech.edu).

Where the instances come from. The D-MIPLIB MIRP instances are the 118 instances (98 train + 20 test) of the “anonymous” benchmark of the ML4CO competition [Gasse22], a curated subset of MIRPLib whose variable/constraint names were anonymized. Every one of the 118 instances is numerically identical (same dimensions, nonzeros, coefficients, right-hand sides, bounds and objective coefficients) to exactly one MIRPLib MPS file. They come from three different MILP formulations, all of which are available on MIRPLib:

(A) MIRPLib Group 2 (33 instances; 4 in test): long-horizon, vessel-class arc-flow model of [Papageorgiou14] (instances LR1_DRxx_VCyy_Vzz_t{120,180,360}).
(B) Jiang–Grossmann discrete-time model (42 instances; 9 in test) [Jiang15] (MIRPLib files Maritime_Jiang_Grossmann_Group{1,2,3,5,6}_D-*).
(C) Jiang–Grossmann continuous-time model with port event points (43 instances; 7 in test) [Jiang15] (MIRPLib files Maritime_Jiang_Grossmann_Group{1,2,3,5,6}_E-*).

Hence the distribution is a mixture of formulations. Models (B) and (C) contain no general integer variables; model (A) contains binaries and general integers. The full formulations are given below; click a model to expand it.

(A) MIRPLib Group 2 model: vessel-class arc-flow formulation [Papageorgiou14]

Each port forms its own region; all instances have a single loading port. Vessels travel full from the loading port to a discharging port and empty back (only out-and-back trips), so loaded/discharged quantities are implied by the arcs used.

Sets and parameters.

\(\mathcal{T}=\{0,\dots,T-1\}\): time periods (days), \(T\in\{120,180,360\}\).
\(\mathcal{J}=\mathcal{J}^P\cup\mathcal{J}^C\): loading and discharging ports; \(\Delta_j=+1\) if \(j\in\mathcal{J}^P\), \(-1\) if \(j\in\mathcal{J}^C\).
\(\mathcal{VC}\): vessel classes; class \(vc\) has \(|\mathcal{V}_{vc}|\) identical vessels of capacity \(Q_{vc}\).
\(\mathcal{N}=\{(j,t): j\in\mathcal{J}, t\in\mathcal{T}\}\): regular nodes of the time-space network, plus a source node \(n_s\) and a sink node \(n_e\).
\(\mathcal{A}_{vc}\): arcs of class \(vc\): source arcs \((n_s,(j,t))\), waiting arcs \(((j,t),(j,t+1))\), inter-regional travel arcs \(((j,t),(j',t+\tau^{vc}_{jj'}))\) between a loading and a discharging port, and sink arcs \(((j,t),n_e)\). \(FS^{vc}_n\) / \(RS^{vc}_n\): arcs of class \(vc\) leaving / entering node \(n\). \(\mathcal{O}^{vc}_n\subseteq FS^{vc}_n\): the travel arcs and the sink arc leaving \(n\) (a vessel that takes one of them loads/discharges a full load \(Q_{vc}\) at \(n\)).
\(C^{vc}_a\): arc cost (source arc: port fee \(\pi_j\); waiting arc: 0; travel arc \((j,j')\): \(C^{vc}_{km}\delta_{jj'}\) (discounted by \(1-\gamma^{vc}\) when travelling empty) \(+\,\pi_{j'}\); sink arc from \((j,t)\): \(-(T-1-t)\rho\) with \(\rho=0.01\), a reward for each period remaining after \(t\)).
\(N^{vc}_n\): number of vessels of class \(vc\) that become available at node \(n\) (initial positions).
\(d_{j,t}\): production/consumption at port \(j\) in period \(t\); \(S^{\max}_j\): storage capacity (\(S^{\min}_j=0\)); \(s_{j,0}\): initial inventory; \(B_j\): berth limit.
\(P_t=P^{spot}(\gamma^{spot})^t\): unit penalty for lost production/stockout (spot market) in period \(t\) (decreasing in \(t\); \(P^{spot}=100\), \(\gamma^{spot}=0.999\) in the instances checked).

Variables. \(x^{vc}_a\): number of class-\(vc\) vessels using arc \(a\) (binary on travel arcs; integer in \(\{0,\dots,|\mathcal{V}_{vc}|\}\) on waiting and sink arcs; fixed on source arcs); \(s_{j,t}\ge 0\): inventory at port \(j\) at the start of period \(t\) (\(t=0,\dots,T\)); \(\alpha_{j,t}\ge 0\): lost production / unmet demand (spot-market slack).

\begin{align} \min\ & \sum_{vc\in\mathcal{VC}}\sum_{a\in\mathcal{A}_{vc}} C^{vc}_a x^{vc}_a+\sum_{j\in\mathcal{J}}\sum_{t\in\mathcal{T}} P_t\,\alpha_{j,t} \\ \text{s.t. } & \sum_{a\in FS^{vc}_n} x^{vc}_a-\sum_{a\in RS^{vc}_n} x^{vc}_a=0, && \forall n\in\mathcal{N},\ vc\in\mathcal{VC} \quad\text{(vessel flow balance)}\\ & x^{vc}_{(n_s,n)}=N^{vc}_n, && \forall n\in\mathcal{N},\ vc\in\mathcal{VC} \quad\text{(initial positions)}\\ & s_{j,t+1}=s_{j,t}+\Delta_j\Big(d_{j,t}-\sum_{vc\in\mathcal{VC}}\sum_{a\in\mathcal{O}^{vc}_{(j,t)}} Q_{vc}\,x^{vc}_a-\alpha_{j,t}\Big), && \forall j\in\mathcal{J},\ t\in\mathcal{T} \quad\text{(port inventory balance)}\\ & \sum_{vc\in\mathcal{VC}}\sum_{a\in\mathcal{O}^{vc}_{(j,t)}} x^{vc}_a\le B_j, && \forall j\in\mathcal{J},\ t\in\mathcal{T} \quad\text{(berth limit)}\\ & 0\le s_{j,t}\le S^{\max}_j,\ \ t=1,\dots,T; \quad s_{j,0}\ \text{fixed}; \quad \alpha_{j,t}\ge 0, && \forall j\in\mathcal{J}\\ & x^{vc}_a\in\{0,1\}\ \text{(travel arcs)},\quad x^{vc}_a\in\{0,\dots,|\mathcal{V}_{vc}|\}\ \text{(waiting and sink arcs)}. \end{align}

The model has \(|\mathcal{J}|\,T\,|\mathcal{VC}|\) flow-balance rows, \(|\mathcal{J}|\,T\) inventory rows and \(|\mathcal{J}|\,T\) berth rows (the source-arc fixings are variable bounds).

(B) Jiang–Grossmann discrete-time model [Jiang15]

In the Jiang–Grossmann instances, the sequence of ports visited by each ship is an input (parameter \(x_{v,n,m}=1\) if ship \(v\) sails directly from port \(n\) to port \(m\)); the model decides when ships wait, prepare, load/discharge and sail, so as to keep port inventories within bounds at minimum cost.

Sets and parameters.

\(\mathcal{N}=\mathcal{P}\cup\mathcal{D}\cup\{o,e\}\): production ports \(\mathcal{P}\), consumption ports \(\mathcal{D}\), and a virtual origin \(o\) and virtual destination \(e\) of all ships; \(\mathcal{V}\): ships; \(\mathcal{T}=\{1,\dots,|\mathcal{T}|\}\): time periods (the horizon \(H\) divided into \(|\mathcal{T}|=2H\) periods).
\(x_{v,n,m}\in\{0,1\}\): given route of ship \(v\); \(\tau_{nm}\): sailing time in periods (\(\tau_{o,m}\ge 1\)).
\(B_n\): number of ships that can operate at port \(n\) simultaneously; \(R_p\) / \(R_d\): production / consumption per period; \(q_{v,p}\) / \(\delta_{v,d}\): amount loaded / discharged by ship \(v\) per period of operation; \(f_{v,n}\): number of preparation periods before operating; \(W_v\): maximum number of waiting periods per port; \(L_v\): ship capacity; \(S^{lo}_n,S^{up}_n\): port inventory bounds (0 for the virtual ports); \(S^0_n\): initial inventory.
Costs: \(c^{sf}_v\) fixed and \(c^{sv}_v\) load-dependent sailing cost per period sailed; \(c^{w}_{v,n}\) waiting cost; \(c^{o}_{v,n}\) cost per period of preparation or operation.

Variables. Binary: \(op_{v,n,t}\) (ship \(v\) operates at \(n\) in \(t\)), \(of_{v,n,t}\) (prepares for operation), \(wa_{v,n,t}\) (waits), \(sa_{v,n,m,t}\) (starts sailing from \(n\) to \(m\) in \(t\)). Continuous, nonnegative: \(st_{n,t}\) (port stock at the beginning of \(t\)), \(la_{v,t}\) (ship load at the beginning of \(t\)), \(\lambda^1_{v,n,m,t},\lambda^2_{v,n,m,t}\) (linearization of \(la_{v,t}\,sa_{v,n,m,t}\)). Let \(\bar{\mathcal{N}}=\mathcal{P}\cup\mathcal{D}\) and \(OP_{v,n,t}=op_{v,n,t}+of_{v,n,t}\).

\begin{align} \min\ & \sum_{v,n,m,t}\tau_{nm}\big(c^{sf}_v\,sa_{v,n,m,t}+c^{sv}_v\,\lambda^1_{v,n,m,t}\big)+\sum_{v,n,t}c^{w}_{v,n}\,wa_{v,n,t}+\sum_{v,n,t}c^{o}_{v,n}\big(of_{v,n,t}+op_{v,n,t}\big)\\ \text{s.t. } & sa_{v,n,m,t}\le x_{v,n,m}, && \forall v,n,m,t\\ & \sum_{m\in\bar{\mathcal{N}}\cup\{e\}}\sum_{t} sa_{v,o,m,t}=1,\qquad \sum_{n\in\bar{\mathcal{N}}\cup\{o\}}\ \sum_{t\le|\mathcal{T}|-\tau_{ne}} sa_{v,n,e,t}=1, && \forall v\\ & \sum_{v}OP_{v,n,t}\le B_n, && \forall n\in\bar{\mathcal{N}},t\\ & \sum_{m\in\bar{\mathcal{N}}\cup\{o\}} sa_{v,m,n,t-\tau_{mn}}+wa_{v,n,t-1}=of_{v,n,t}+wa_{v,n,t}, && \forall v,n\in\bar{\mathcal{N}},t\\ & OP_{v,n,t-1}=\sum_{m\in\bar{\mathcal{N}}\cup\{e\}} sa_{v,n,m,t}+op_{v,n,t}, && \forall v,n\in\bar{\mathcal{N}},t\\ & OP_{v,n,t-1}\le OP_{v,n,t}+\sum_{m\in\bar{\mathcal{N}}\cup\{e\}} sa_{v,n,m,t}, && \forall v,n,t\\ & op_{v,n,t-1}\ge \sum_{m\in\bar{\mathcal{N}}\cup\{e\}} sa_{v,n,m,t}, && \forall v,n\in\bar{\mathcal{N}},t\\ & \sum_{t'\gt t} of_{v,n,t'}+op_{v,n,t}\le 1, && \forall v,n,t\\ & st_{p,t+1}=st_{p,t}-\sum_v q_{v,p}\,op_{v,p,t}+R_p, && \forall p\in\mathcal{P},t\lt |\mathcal{T}|\\ & st_{d,t+1}=st_{d,t}+\sum_v \delta_{v,d}\,op_{v,d,t}-R_d, && \forall d\in\mathcal{D},t\lt |\mathcal{T}|\\ & la_{v,t+1}=la_{v,t}+\sum_{p}q_{v,p}\,op_{v,p,t}-\sum_{d}\delta_{v,d}\,op_{v,d,t}, && \forall v,t\lt |\mathcal{T}|\\ & S^{lo}_p\le st_{p,|\mathcal{T}|}-\sum_v q_{v,p}\,op_{v,p,|\mathcal{T}|}+R_p\le S^{up}_p, && \forall p\in\mathcal{P}\\ & S^{lo}_d\le st_{d,|\mathcal{T}|}+\sum_v \delta_{v,d}\,op_{v,d,|\mathcal{T}|}-R_d\le S^{up}_d, && \forall d\in\mathcal{D}\\ & S^{lo}_n\le st_{n,t}\le S^{up}_n, && \forall n,t\\ & la_{v,t}\le L_v\ \ \forall v,t,\qquad la_{v,|\mathcal{T}|}+\sum_{p}q_{v,p}\,op_{v,p,|\mathcal{T}|}-\sum_{d}\delta_{v,d}\,op_{v,d,|\mathcal{T}|}\le L_v, && \forall v\\ & \sum_t wa_{v,n,t}\le W_v, && \forall v,n\\ & \sum_t of_{v,n,t}=f_{v,n}\sum_m x_{v,m,n}, && \forall v,n\\ & \lambda^1_{v,n,m,t}+\lambda^2_{v,n,m,t}=la_{v,t},\quad \lambda^1_{v,n,m,t}\le L_v\,sa_{v,n,m,t},\quad \lambda^2_{v,n,m,t}\le L_v(1-sa_{v,n,m,t}), && \forall v,n,m,t\\ & st_{n,1}=S^0_n,\ \ la_{v,1}=0;\qquad op,of,wa,sa\in\{0,1\};\quad st,la,\lambda^1,\lambda^2\ge 0. \end{align}

(Terms with a time index outside \(\mathcal{T}\) are omitted. Variables and constraints are generated for all index combinations, so most \(sa\) variables are forced to 0 by the first constraint.)

Same data as (B), but time is continuous on \([0,H]\) (distances \(\mathrm{dist}_{nm}\), preparation time \(t^f_{v,n}\) and handling time per unit \(t^v_{v,n}\) in time units; \(R_p,R_d\) are rates per time unit). Each port \(n\) has event points \(l\in\mathcal{L}_n=\{1,\dots,E_n\}\), with \(E_n=3\times\)(number of ship visits to \(n\)) (\(E_o=3|\mathcal{V}|\)). Let \(k_{v,n}=\sum_m x_{v,m,n}\in\{0,1\}\) indicate that ship \(v\) visits \(n\).

Variables. Binary: \(y^s_{v,n,l}\), \(y^f_{v,n,l}\), \(y^e_{v,n,l}\) (ship \(v\) starts operation / finishes preparation / ends operation at event point \(l\) of port \(n\)). Continuous, nonnegative: event times \(T_{n,l}\); times \(t^a_{v,n}\) (arrival), \(t^o_{v,n}\) (start of operation), \(t^{fi}_{v,n}\) (end of preparation), \(t^l_{v,n}\) (departure), waiting time \(t^w_{v,n}\); amounts \(q_{v,p}\), \(r_{v,d}\) loaded/discharged; stock \(st_{n,l}\); ship load before/after operation \(la^1_{v,n},la^2_{v,n}\); linearization variables \(\phi^{f}_{v,n,l,l'}=y^f_{v,n,l}T_{n,l'}\), \(\phi^{e}_{v,n,l,l'}=y^e_{v,n,l}T_{n,l'}\), \(\psi^q_{v,p,l}=y^f_{v,p,l}q_{v,p}\), \(\psi^r_{v,d,l}=y^f_{v,d,l}r_{v,d}\) and their complements \(\bar\phi^{f},\bar\phi^{e},\bar\psi^q,\bar\psi^r\).

\begin{align} \min\ & \sum_v\Big[\sum_{n,m}x_{v,n,m}\,\mathrm{dist}_{nm}\big(c^{sf}_v+c^{sv}_v\,la^2_{v,n}\big)+\sum_n c^w_{v,n}\,t^w_{v,n}+\sum_{n\in\bar{\mathcal{N}}}c^o_{v,n}\big(t^l_{v,n}-t^o_{v,n}\big)\Big]\\ \text{s.t. } & T_{n,l}\le H,\quad T_{n,l}\ge T_{n,l'}\ \ (l\gt l'), && \forall n,\ l,l'\in\mathcal{L}_n\\ & \sum_{l}y^s_{v,n,l}=\sum_{l}y^e_{v,n,l}=k_{v,n}\ (n\ne o),\quad \sum_{l}y^s_{v,o,l}=\sum_{l}y^e_{v,o,l}=1,\quad \sum_l y^f_{v,n,l}=\sum_l y^s_{v,n,l}, && \forall v,n\\ & |T_{n,l}-t^o_{v,n}|\le H(1-y^s_{v,n,l}),\ \ |T_{n,l}-t^{l}_{v,n}|\le H(1-y^e_{v,n,l}),\ \ |T_{n,l}-t^{fi}_{v,n}|\le H(1-y^f_{v,n,l}), && \forall v,n,l\in\mathcal{L}_n\\ & \sum_v\sum_{l'\le l}\big(y^s_{v,n,l'}-y^e_{v,n,l'}\big)\le B_n, && \forall n,l\in\mathcal{L}_n\\ & t^a_{v,n}=\sum_m x_{v,m,n}\big(t^l_{v,m}+\mathrm{dist}_{mn}\big)\ (n\ne o),\quad t^o_{v,n}\ge t^a_{v,n},\quad t^w_{v,n}=t^o_{v,n}-t^a_{v,n}, && \forall v,n\\ & t^{fi}_{v,n}=t^o_{v,n}+k_{v,n}t^f_{v,n},\quad t^l_{v,p}=t^{fi}_{v,p}+k_{v,p}t^v_{v,p}q_{v,p},\quad t^l_{v,d}=t^{fi}_{v,d}+k_{v,d}t^v_{v,d}r_{v,d}, && \forall v,n,p,d\\ & t^l_{v,o}=t^{fi}_{v,o},\quad t^l_{v,e}=t^o_{v,e}=t^a_{v,e}\le H,\quad t^w_{v,n}\le W_v\ (n\ne o), && \forall v,n\\ & st_{p,l+1}=st_{p,l}-\sum_v\sum_{l'\le l}\frac{\phi^f_{v,p,l',l+1}-\phi^e_{v,p,l',l+1}-\phi^f_{v,p,l',l}+\phi^e_{v,p,l',l}}{t^v_{v,p}}+R_p\big(T_{p,l+1}-T_{p,l}\big), && \forall p,\ l\lt E_p\\ & st_{d,l+1}=st_{d,l}+\sum_v\sum_{l'\le l}\frac{\phi^f_{v,d,l',l+1}-\phi^e_{v,d,l',l+1}-\phi^f_{v,d,l',l}+\phi^e_{v,d,l',l}}{t^v_{v,d}}-R_d\big(T_{d,l+1}-T_{d,l}\big), && \forall d,\ l\lt E_d\\ & st_{p,1}=S^0_p+R_pT_{p,1},\quad st_{d,1}=S^0_d-R_dT_{d,1}, && \forall p,d \text{ with } E_n\gt 0\\ & S^{lo}_p\le st_{p,E_p}+R_p(H-T_{p,E_p})\le S^{up}_p,\quad S^{lo}_d\le st_{d,E_d}-R_d(H-T_{d,E_d})\le S^{up}_d, && \forall p,d \text{ with } E_n\gt 0\\ & S^{lo}_n\le st_{n,l}\le S^{up}_n, && \forall n,l\in\mathcal{L}_n\\ & la^2_{v,p}=la^1_{v,p}+\sum_l\psi^q_{v,p,l},\quad la^2_{v,d}=la^1_{v,d}-\sum_l\psi^r_{v,d,l},\quad la^1_{v,n}=\sum_m x_{v,m,n}\,la^2_{v,m}\ (n\in\bar{\mathcal{N}}),\quad la^2_{v,p}\le L_v, && \forall v,p,d\\ & \phi^f_{v,n,l,l'}\le H y^f_{v,n,l},\ \ \bar\phi^f_{v,n,l,l'}\le H(1-y^f_{v,n,l}),\ \ \phi^f_{v,n,l,l'}+\bar\phi^f_{v,n,l,l'}=T_{n,l'}\ \ (\text{same for }\phi^e\text{ with }y^e), && \forall v,n,\ l,l'\in\mathcal{L}_n\\ & \psi^q_{v,p,l}\le L_v y^f_{v,p,l},\ \ \bar\psi^q_{v,p,l}\le L_v(1-y^f_{v,p,l}),\ \ \psi^q_{v,p,l}+\bar\psi^q_{v,p,l}=q_{v,p}\ \ (\text{same for }\psi^r\text{ with }r_{v,d}), && \forall v,p,d,l\\ & la^1_{v,o}=la^2_{v,o}=0;\qquad y^s,y^f,y^e\in\{0,1\};\quad \text{all other variables}\ \ge 0. \end{align}

In both Jiang–Grossmann models the objective is written in the instance files through a free variable equal to the total cost, which is minimized.

Instance distributions

The table below summarizes the distributions that have been used in previous works, along with download links.

Hardness Level	Distribution Source (ML4MILPs)	# Var B	# Var I	# Var C	# Constr	Instance sources (MIRPLib)	# Ports	# Vessels	Planning horizon	Related Literature
Medium	[Gasse22]	13532.91	1547.66	19576.15	44429.7	118 instances (98 train / 20 test): 33 Group 2 [Papageorgiou14], 42 Jiang–Grossmann discrete-time, 43 Jiang–Grossmann continuous-time [Jiang15]	Group 2: 3–9 (1 loading + 2–8 discharging); J–G: 6 (2–4 loading + 2–4 discharging, plus 2 virtual)	Group 2: 6–40 vessels in 1–5 classes; J–G: 2–3 ships	Group 2: 120, 180 or 360 days; J–G: 60 or 70 time units (discrete-time model: 120 or 140 periods)	ML4CO [Gasse22]

License

The MIRP in Distributional MIPLIB was downloaded from the Github repository of ML4CO. ML4CO is licensed under the BSD-3-Clause license. See ML4CO License for details about the license and the copyright notice from CERC Data Science For Decision Making.

Related Literature

A curated set of MIRP instances have been used as a hidden test set in the Machine Learning for Combinatorial Optimization Competition (ML4CO) [Gasse22]. We included this benchmark in Distributional MIPLIB and provide the statistics. We adhered to the train, validation, and test split established in ML4CO. A larger set of MIRP instances is also available at the MIRPLIB [Papageorgiou14] (link).

Citations

Any work that uses any of the above instances should cite the papers below:

Distributional MIPLIB

@misc{huang2024distributional,
      title={Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods}, 
      author={Weimin Huang and Taoan Huang and Aaron M Ferber and Bistra Dilkina},
      year={2024},
      eprint={2406.06954},
      archivePrefix={arXiv},
      primaryClass={cs.LG}
}

Original Formulation & Generator

@article{papageorgiou2014mirplib,
  title={MIRPLib--A library of maritime inventory routing problem instances: Survey, core model, and benchmark results},
  author={Papageorgiou, Dimitri J and Nemhauser, George L and Sokol, Joel and Cheon, Myun-Seok and Keha, Ahmet B},
  journal={European Journal of Operational Research},
  volume={235},
  number={2},
  pages={350--366},
  year={2014},
  publisher={Elsevier}
}

ML4CO

@inproceedings{gasse2022machine,
  title={The machine learning for combinatorial optimization competition (ml4co): Results and insights},
  author={Gasse, Maxime and Bowly, Simon and Cappart, Quentin and Charfreitag, Jonas and Charlin, Laurent and Ch{\'e}telat, Didier and Chmiela, Antonia and Dumouchelle, Justin and Gleixner, Ambros and Kazachkov, Aleksandr M and others},
  booktitle={NeurIPS 2021 competitions and demonstrations track},
  pages={220--231},
  year={2022},
  organization={PMLR}
}

References

[Gasse22] Gasse, Maxime, et al. "The machine learning for combinatorial optimization competition (ML4CO): Results and insights." In NeurIPS 2021 Competitions and Demonstrations Track, PMLR vol. 176, pp. 220–231, 2022. [paper]

[Papageorgiou14] Papageorgiou, Dimitri J., et al. "MIRPLib – A library of maritime inventory routing problem instances: Survey, core model, and benchmark results." European Journal of Operational Research, vol. 235, no. 2, pp. 350–366, 2014. [paper]

[Jiang15] Jiang, Yongheng, and Ignacio E. Grossmann. "Alternative mixed-integer linear programming models of a maritime inventory routing problem." Computers & Chemical Engineering, vol. 77, pp. 147–161, 2015. [paper]