## 3 Problem Formulation
### Problem Description  
Container liner operators are under constant pressure to balance network coverage, asset utilization, and profitability. They must decide which cyclic routes to operate, how to deploy heterogeneous ships, and how much freight demand to accept, all while facing volatile fuel prices, charter rates, and regulatory surcharges. Recent policy proposals to levy additional port fees on China-built ships calling at U.S. ports have further complicated fleet planning. These surcharges specifically apply only to China-built ships above a certain capacity threshold, while ships constructed in other countries or smaller China-built ships are exempt [50]. As a result, carriers with mixed fleets must now carefully account for route-dependent surcharges in their cost structure. Against this backdrop, a strategic yet tractable planning framework is indispensable for maximizing profit without jeopardizing service reliability. For the shipping company, three interdependent planning tasks are of primary importance: selecting a subset of candidate routes to operate, assigning a suitable mix of ship types to each operated route to meet the required ship count, and determining how much of the origin-destination (OD) demand to accept and how to allocate the accepted demand across the selected network. If route deployment and fleet composition are poorly matched to demand geography, high-yield OD pairs may be rejected, deployed ships may be underutilized, or routes may involve China-built ships incurring avoidable penalties at U.S. ports. In light of these considerations, it is crucial to precisely choose operating routes based on transport demand and associated costs, including fuel cost, berthing cost, and route-specific surcharges for certain ship types, and to allocate the fleet accordingly. Making informed decisions on ship deployment and chartering actions, including when to charter in and charter out ships, is vital to maintaining the cost-effectiveness and competitiveness of the operator's network. Consider the route-ship-demand allocation problem in a liner-shipping network that provides stable containerized services over a set of predefined cyclic routes. The set of all candidate routes is denoted by \(R\) (indexed by \(r\)). Each route represents a predefined closed-loop trajectory involving a sequence of ports and is a candidate for service deployment with a fixed weekly schedule. The set of OD pairs is denoted by \(W\), where each element \((o,d)\) indicates an origin port \(o\) and a destination port \(d\). For each OD pair, the subset of feasible routes that connect the two ports is denoted by \(R_{od}\subseteq R\). The set of all legs between consecutive ports of call on route \(r\) is denoted by \(L_{r}\) (indexed by \(l_{r}\)). For each leg \(l_{r}\), we denote the set of OD pairs routing passes through the leg by \(W_{l_{r}}\subseteq W\). The set of available ship types is denoted by \(S\), where ships built in China are represented by the subset \(\hat{S}\subseteq S\). The available fleet includes both ships owned by the shipping company and charteable ships. To ensure a weekly departure frequency on any operated route, a sufficient number of ships must be deployed to maintain the required frequency, given the time needed to complete a full loop. We assume that all ships sail at a uniform speed when deployed on the same route, and the total number of ships required on route \(r\), denoted by \(N_{r}\), is numerically equal to the round-trip time (in weeks) for route \(r\), as one ship must depart each week while another completes the full loop. The weekly transport demand for each OD pair is denoted by \(D_{od}\), and the corresponding revenue earned per TEU transported is denoted by \(p_{od}\). The total volume of accepted demand for each OD pair cannot exceed \(D_{od}\), and the shipping company is allowed to reject part of the demand if full acceptance leads to unprofitable operations. Each ship type \(s\) has a capacity of \(Q_{s}\) twenty-foot equivalent units (TEUs).