## 4 Branch-and-Price-and-Cut Algorithm
### Master Problem  
We reformulate the problem as an integer linear master problem with an exponential number of columns (variables). To define the master problem, the following notations are needed. All feasible truck routes are represented by the set \(\Omega\). Each feasible route \(r\in\Omega\) is associated with a cost \(C^{r}\), which is the summation of a truck's fixed cost and travel cost. \(a_{i}^{r}\) is a binary parameter that takes the value 1 if node \(i\) is visited by route \(r\). Additionally, let \(T_{critical}\) denote the set of critical times. We also define an integer parameter \(B_{t}^{r}\) to indicate the accumulated increment in the depot's inventory of empty containers before critical time \(t\). For illustration, if route \(r\) picks up 1 empty container from the depot and delivers 2 empty containers back to the depot before critical time \(t\), then \(B_{t}^{r}=(-1)+(+2)=1\). We define a 0-1 variable \(\theta^{r}\) such that \(\theta^{r}=1\) if and only if route \(r\) is chosen in the solution. Based on the notations provided above, the master problem is modeled as below:  
\[\min\sum_{r\in\Omega}C^{r}\theta^{r} \tag{21}\]  
\[s.t.\quad\sum_{r\in\Omega}a_{i}^{r}\theta^{r}=1,\quad\forall i\in N_{IF}\cup N _{OF}\cup N_{OE} \tag{22}\]  
\[\sum_{r\in\Omega}a_{i}^{r}\theta^{r}\leq 1,\quad\forall i\in N_{IF}^{p}\cup N _{IF}^{D}\cup N_{E}^{p} \tag{23}\]  
\[\sum_{r\in\Omega}B_{t}^{r}\theta^{r}+E\geq 0,t\in T_{critical} \tag{24}\]  
\[\sum_{r\in\Omega}B_{t}^{r}\theta^{r}+E\leq Q,t\in T_{critical} \tag{25}\]  
\[\sum_{r\in\Omega}\theta^{r}\leq K_{truck} \tag{26}\]  
\[\theta_{r}\in\{0,1\},\quad r\in\Omega \tag{27}\]  
Objective function (21) aims at minimizing the overall cost of the chosen routes. Constraints (22) clarify that each node representing a pickup/delivery inland container transportation request is included in exactly one of the selected routes. Similarly, constraints (23) state that each node representing a pickup/delivery depot is covered by at most one of the selected routes. Constraints (24) and constraints (25) pertain to empty containers, ensuring  
Figure 4: Framework of the proposed branch-and-price-and-cut algorithm. that the depot's inventory remains within the range [0, \(Q\)]. Constraints (26) guarantee that the total number of selected routes should stay within the limit of the available trucks. Notice that constraints (24) and constraints (25) are imposed merely on the critical times. If empty constraints are satisfied at critical times, it also holds for other times, as the inventory of empty containers changes only when a truck heads to the depot for picking up or storing an empty container. The aforementioned critical times and principles for creating truck routes can be determined by the following proposition. **Proposition 1**. : _The master problem always provides an optimal solution, without any trucks waiting at the depot. That is, \(\Omega\) can be composed of routes in which there is no waiting time at the depot._  
Proof. : We proof the proposition by contradiction. Suppose that the conclusion is false. Then, in an optimal solution to the problem, there is at least one route where the truck waits at the depot. We can distinguish three cases. **Case 1:** In the optimal solution, a truck (Truck1) awaits the arrival of an empty container at the depot. This case happens when empty containers are out of stock. After an empty container is carried to the depot by a truck (Truck2), Truck1 can pick up this empty container and then depart from the depot to serve a customer in need of an empty container (marked by A). Truck2 departs from the depot to serve a customer who does not need an empty container (marked by B). We denote the subsequent partial routes of Truck1 and Truck2 after serving A/B by Route1 and Route2, respectively.