# LSNDSP Benchmarks

The following presents results of our approach on LINERLIB dataset.

## LINERLIB

The [LINERLIB](https://github.com/blof/LINERLIB) benchmark suite presents
industry-standard instances for shipping network design problems. Introduced by
[Brouer et al. (2013)](https://pubsonline.informs.org/doi/abs/10.1287/trsc.2013.0471),
the suite offers extensive documentation and comprises seven instances,
gradually increasing in complexity based on the number of ports, demands, and
vessels. This work focuses on the base case, where no modifications to the
original data are made. The data was parsed into the format of our [API](https://developers.google.com/optimization/service/shipping/network_design).
The following table summarizes the characteristics of each instance after
parsing.

| Instance | Baltic | WAF | Mediterranean | Pacific | World Small | Europe Asia | World Large |
|---|---|---|---|---|---|---|---|
| **# Ports** | 12 | 19 | 39 | 45 | 47 | 111 | 197 |
| **# Demands** <br /> **# Containers** | 22 <br /> 4 904 | 38 <br /> 8 541 | 369 <br /> 7 545 | 722 <br /> 44 180 | 1 764 <br /> 138 247 | 4 000 <br /> 76 944 | 9 630 <br /> 138 914 |
| **# Vessels** | 6 | 42 | 21 | 100 | 263 | 176 | 501 |

> [!NOTE]
> **Note:** The Mediterranean original instance only allows for [20 vessels](https://github.com/blof/LINERLIB/blob/master/data/fleet_Mediterranean.csv) including 8 Feeder_800. However, the [Mediterranean solution file from LINERLIB](https://github.com/blof/LINERLIB/blob/master/results/BrouerDesaulniersPisinger2014/Med_base_best.log) actually uses 20.81 vessels including 8.88 Feeder_800 which we rounded up to 9.

### Assumptions

To ensure a fair comparison with previous work, parameters were set as follows:

- Minimum port stay time: *24 hours* for all ports
- Minimum transshipment time: *48 hours* for all ports
- Bunker cost: *600 USD* per metric ton
- Demand rejection penalty (or opportunity cost): *1000 USD* for all demands

As [suggested](https://github.com/blof/LINERLIB/blob/master/data/transittime_revision/README.txt)
by the LINERLIB authors, we only present results using **revised** transit
times.

We only report results on the 5 largest instances, as Baltic and WAF are usually
used for tuning purposes.

One of the key advantages of the [API](https://developers.google.com/optimization/service/shipping/network_design) is its ability to clearly define leg
candidates in terms of time and costs. This leaves all cost modeling to the
user, eliminating ambiguity in the definition of optimality. However, this
advantage comes at the cost of time discretization. Unless otherwise stated, leg
candidates' durations are generated with a 12-hour discretization.

## Baseline

To ensure a fair evaluation, our techniques are compared with the most recent
publicly available vessel services from [LINERLIB](https://github.com/blof/LINERLIB/tree/master/results/BrouerDesaulniersPisinger2014).
It is important to note that the LINERLIB services were optimized without regard
to demand transit times. Considering transit times significantly complicates the
problem, requiring joint scheduling of all vessel services and demands.

To better align with LINERLIB's vessel services, we included additional leg
candidates with the closest rounded hour in the input. Our approach, however,
does not utilize these additional legs and initiates the process anew.

To account for transit times in the LINERLIB vessel services, demands were
routed using a column generation-based optimization assuming a maximum of three
transshipments.

## Metrics

When comparing methods, the following metrics are considered:

- **Cost related metrics** :
  - *Profit*: The objective to be maximized, defined as revenue minus vessel services and transshipment costs.
  - *Revenue*: Sum of the revenue of fulfilled containers. The revenue of a container is its freight rate minus the loading and unloading costs plus the opportunity cost (or demand rejection penalty).
  - *Vessel service costs*: Operating costs of vessels deployed on all services, including bunker, charter and port stay costs.
  - *Transshipment costs*: Handling costs related to transshipments.
- **Other key metrics** :
  - Number of shipped containers
  - Number of vessels used

For comparison with existing work, where the opportunity cost of each container
is set to 1000$, conversion formulas to compute the profits presented in this
page are:

- from LINERLIB: `total_container_count` \* 1000 - `linerlib_half_yearly_objective` \* 7 / 180.
- from Koza: `total_container_count` \* 1000 - `koza_objective`.

## Results

The next table presents a comparison of our approach with the baseline. Solution
files for our approach and the baseline are available to download on [github](https://github.com/or-tools/data/tree/main/linerlib).

|   |   | Mediterranean | Pacific | World Small | Europe Asia | World Large |
|---|---|---|---|---|---|---|
|   | *# Containers* <br /> *# Vessels* | 7 545 <br /> 21 | 44 180 <br /> 100 | 138 247 <br /> 263 | 76 944 <br /> 176 | 138 914 <br /> 501 |
| **Our approach** | *Profit (objective)* <br /> *Container revenue* <br /> *Vessel service costs* <br /> *Transshipment costs* <br /> *# Shipped containers* <br /> *# Used vessels* | **5.23 M$** <br /> 7.47 M$ <br /> 2.05 M$ <br /> 0.20 M$ <br /> 5 391 <br /> 16 | **43.21 M$** <br /> 66.88 M$ <br /> 22.68 M$ <br /> 0.98 M$ <br /> 39 621 <br /> 96 | **173.11 M$** <br /> 266.78 M$ <br /> 86.89 M$ <br /> 6.78 M$ <br /> 106 861 <br /> 236 | **88.50 M$** <br /> 140.56 M$ <br /> 47.86 M$ <br /> 4.20 M$ <br /> 55 493 <br /> 146 | **119.38 M$** <br /> 209.07 M$ <br /> 81.76 M$ <br /> 7.93 M$ <br /> 78 983 <br /> 311 |
| **Baseline** | *Profit (objective)* <br /> *Container revenue* <br /> *Vessel service costs* <br /> *Transshipment costs* <br /> *# Shipped containers* <br /> *# Used vessels* | **2.63 M$** <br /> 5.83 M$ <br /> 3.07 M$ <br /> 0.14 M$ <br /> 4 097 <br /> 21 | **22.52 M$** <br /> 47.81 M$ <br /> 24.78 M$ <br /> 0.51 M$ <br /> 29 343 <br /> 99 | **70.78 M$** <br /> 173.84 M$ <br /> 98.90 M$ <br /> 4.17 M$ <br /> 76 829 <br /> 259 | **40.63 M$** <br /> 115.04 M$ <br /> 70.77 M$ <br /> 3.64 M$ <br /> 46 434 <br /> 172 |   |
| **Delta / baseline** | *Profit (objective)* <br /> *Container revenue* <br /> *Vessel service costs* <br /> *Transshipment costs* <br /> *# Shipped containers* <br /> *# Used vessels* | **99%** <br /> 28% <br /> -33% <br /> 47% <br /> 32% <br /> -24% | **92%** <br /> 40% <br /> -8% <br /> 93% <br /> 35% <br /> -3% | **145%** <br /> 53% <br /> -12% <br /> 63% <br /> 39% <br /> -9% | **118%** <br /> 22% <br /> -32% <br /> 16% <br /> 20% <br /> -15% |   |

Considering transit times in optimization significantly increases the potential
profit of a shipping network. Across all instances, the profit increase is
nearly 100%. Most of the profit increase comes from additional revenue as more
containers are shipped. However, it can also be achieved with a decrease in
vessel services costs by deploying only profitable services. This can
potentially unlock additional revenue from chartering out these vessels.

The following table compares profit numbers made available by
[Koza et al. (2020)](https://pubsonline.informs.org/doi/abs/10.1287/trsc.2018.0888).
We would like to emphasize that due to the lack of publicly available data, this
comparison is not made in depth and we are not fully confident that the same
assumptions were made for both studies.

|   | Mediterranean | Pacific | World Small | Europe Asia | World Large |
|---|---|---|---|---|---|
| **Our approach** | **5.23 M$** | **43.21 M$** | **173.11 M$** | **88.50 M$** | **119.38 M$** |
| **Koza et al. (2020)** | **4.80 M$** | **41.40 M$** | **170.85 M$** | **79.89 M$** |   |
| **Delta / Koza et al. (2020)** | **9%** | **4%** | **1%** | **11%** |   |

## Comparison in the case with no transit time

We compared our approach to LINERLIB's vessel services in a simplified scenario
without considering transit times. It is worth noting that even on the specific
criteria that LINERLIB's services were designed to optimize, our approach
demonstrates superior results in terms of profitability, as indicated in the
final table. Solution files for our approach and the baseline are available to
download on [github](https://github.com/or-tools/data/tree/main/linerlib).

|   |   | Mediterranean | Pacific | World Small | Europe Asia |
|---|---|---|---|---|---|
|   | *# Containers* <br /> *# Vessels* | 7 545 <br /> 21 | 44 180 <br /> 100 | 138 247 <br /> 263 | 76 944 <br /> 176 |
| **Our approach** | *Profit (objective)* <br /> *Container revenue* <br /> *Vessel service costs* <br /> *Transshipment costs* <br /> *# Shipped containers* <br /> *# Used vessels* | **6.49 M$** <br /> 9.46 M$ <br /> 2.67 M$ <br /> 0.30 M$ <br /> 7 003 <br /> 19 | **48.56 M$** <br /> 68.55 M$ <br /> 19.09 M$ <br /> 0.90 M$ <br /> 41 089 <br /> 99 | **205.50 M$** <br /> 293.46 M$ <br /> 81.60 M$ <br /> 6.36 M$ <br /> 117 255 <br /> 262 | **109.88 M$** <br /> 169.98 M$ <br /> 54.62 M$ <br /> 5.48 M$ <br /> 67 146 <br /> 173 |
| **Baseline** | *Profit (objective)* <br /> *Container revenue* <br /> *Vessel service costs* <br /> *Transshipment costs* <br /> *# Shipped containers* <br /> *# Used vessels* | **6.21 M$** <br /> 9.57 M$ <br /> 3.07 M$ <br /> 0.29 M$ <br /> 7 075 <br /> 21 | **47.24 M$** <br /> 72.87 M$ <br /> 24.78 M$ <br /> 0.85 M$ <br /> 43 459 <br /> 99 | **195.48 M$** <br /> 302.26 M$ <br /> 98.90 M$ <br /> 7.88 M$ <br /> 123 056 <br /> 259 | **107.30 M$** <br /> 183.57 M$ <br /> 70.77 M$ <br /> 5.50 M$ <br /> 73 614 <br /> 172 |
| **Delta / baseline** | *Profit (objective)* <br /> *Container revenue* <br /> *Vessel service costs* <br /> *Transshipment costs* <br /> *# Shipped containers* <br /> *# Used vessels* | **5%** <br /> -1% <br /> -13% <br /> 4% <br /> -1% <br /> -10% | **3%** <br /> -6% <br /> -23% <br /> 6% <br /> -5% <br /> 0% | **4%** <br /> -3% <br /> -17% <br /> -12% <br /> -5% <br /> 2% | **2%** <br /> -7% <br /> -23% <br /> 0% <br /> -9% <br /> 1% |