Icebreaker convoys on the Northern Sea Route

Task

Approach

1. 01Ice into travel times

   Weekly ice grids of 269 × 217 cells become a graph of passable cells; a shortest path between every pair of route points gives each leg its length and average ice. A rule table turns ice class, ice level and escort into a speed, and the speed into whole hours.

   $${\delta }_{k,e,a}=\mathrm{round}\left(\frac{{\ell }_e}{u_{k,e,a}}\right),u_{k,e,a}=\min \{{\iota }_e(1-{\pi }_{c_k,{\iota }_e,a}),{\bar{u}}_k\}$$

2. 02Candidate routes per ship

   Each ship may only use legs from its ten shortest routes between origin and destination, about 20 of the 146 directed legs. Icebreakers keep the whole graph.

3. 03One time-expanded network

   Every ship and icebreaker is a unit of flow over (point, hour) nodes, with sailing arcs (alone or escorted) and one-hour waiting arcs, and each unit ends exactly once. An escorted departure needs an icebreaker leaving on the same leg in the same hour, with at most three ships behind it; there are no ship-to-icebreaker assignment variables at all.

   $$\sum _{v\in V}{x}_{v,e,t}^{\text{esc}}\le 3\sum _{i\in I}{x}_{i,e,t}\forall e,t$$

4. 04A soft destination

   The objective is the time from release to the end of each ship’s route, plus five times the remaining shortest time to its destination if it ends elsewhere. Every planning window stays feasible, even when a voyage cannot finish inside it.

   $$\min \sum _{v\in V}\sum _{p,t}[(t-{\tau }_v)+5{\Delta }_{v,p}]s_{v,p,t}+\frac{1}{100}\sum _d{\delta }_d{x}_d$$

5. 05Rolling horizon and repair

   Plan a week plus two days of look-ahead, aligned to the weekly ice snapshots; commit the week, hand positions over and repeat, eleven windows in all. At least two icebreakers finish each window in the Kara Sea sector, so the fleet does not drift away from where it will be needed. A repair pass then moves each convoy at its slowest member’s speed and pushes the delays forward.

6. 06A service, not a notebook

   Scenarios and runs behind a FastAPI service, a Dash dashboard with Gantt charts and route, convoy and ice maps, HiGHS through Pyomo, all in Docker.

Result

Stack