1. INTRODUCTION
With the progress of globalization, the amount of trade through intercontinental maritime transport using containers has increased dramatically (Günther and Kim, 2006). In 2014, the number of containers transported worldwide was approximately 182 million twentyfootequivalent units (TEUs). Neighboring ports compete with each other for increasing their throughput by enhancing their service levels and attracting more customers. Various technology developments have been attempted to improve the productivity of container terminals (Kim et al., 2012; Singgih, 2016).
Containers can be classified into inbound, outbound, and transshipment containers. Transshipment containers may be transported between port container terminals by trucks. Each trucking company is generally responsible for transshipment containers of a shipping liner. Because deliveries of transshipment containers for a shipping liner are assigned to trucks of a company, it is highly probable that the trucks experience empty travels when they return after delivering transshipment containers to loading terminals. Figure 1 illustrates the transportation of transshipment containers by a trucking company; the transportation case in Figure 1 involves empty travels.
A trucking company generally schedules truck travels and decides the number of trucks to be deployed for transshipment operations, after it receives orders from a shipping liner. In a congested area such as a port, the level of congestion, which varies with time, exerts a significant impact on the travel time of trucks; this aspect is to be considered while scheduling transshipment operation.
Lee et al. (2012) addresses transshipment containers that are temporarily stored in storage yards after discharge from vessels and wait to be loaded onto other vessels in a near future. They addressed a storage space allocation problem in a large container transshipment hub with multiple terminals. The problem was formulated by an integer programming model and solved by a twolevel heuristic approach, while minimizing the total interterminal and intraterminal handling costs. Tierney et al. (2014) described numerous operational issues related to interterminal transportation (ITT) containers at container terminals. It was stated that ITT is a key factor in the decisionmaking process for the construction of new ports and expansion of existing ports. An integer programming model was developed to minimize container delivery delay after taking into account the key components of ITT including traffic congestion, multiple vehicle types, loading and unloading times, and arbitrary terminal configurations. A twostaged approach for solving the model was proposed, which takes into consideration the interaction of vehicle flows, multicommoDi_{t}y flow, and congestion constraints.
A few papers address collaborations among multiple terminals. He et al. (2013) proposed a strategy of sharing internal trucks for ITT among multiple container terminals. An integerprogramming model for assignment of trucks to delivery tasks was proposed, which minimizes the total overflowed workload and total transferring cost. A simulation optimization method, in which a genetic algorithm is integrated, was also proposed. Several papers addressed various types of collaboration in container terminals. Gharehgozli et al. (2016) compared various transportation modes for ITT and applied a game theoretic approach to determine a coalition for collaborative ITT operations among multiple trucking companies. Caballini et al. (2016) proposed an optimization model for cooperative planning of multiple truck carrier operations in a seaport environment for maximizing the total profit derived from their cooperation. A compensation mechanism was introduced to motivate carriers to share their trips. Phan and Kim (2016) suggested a new truck appointment process by which trucking companies and the terminal can exchange information on truck arrival and workload and decide the truck arrival times in a collaborative manner. A review of studies about transshipment of containers at a container terminal was provided by Vis and De Koster (2003). Heilig and Voß (2017) published the first survey paper focusing on interterminal transportation performed between multiple terminals.
This study solves the problem of interterminal transportation of containers in a collaborative manner among multiple trucking companies and proposes a mathematical model for scheduling transportation among multiple container terminals.
This paper contributes as follows:

(1) A strategy for improving the efficiency of interterminal transportation containers is proposed by reducing the empty travels of trucks. The strategy is based on the collaborative operation of trucks.

(2) For supporting the collaborative operation among multiple trucks in the interterminal transportation of containers, a mathematical model which is based on the timespace graph is proposed.

(3) It is shown by a numerical experiment, the strategy in this study reduces the total transportation cost of all the trucking companies significantly and can be a realistic solution to the improvement of the efficiency of ITT system.
This paper is organized as follows: Section 2 describes the ITT problem, and Section 3 proposes a mathematical formulation for the ITT problem. Section 4 uses an example for illustrating the model. Section 5 provides the result of numerical experiment. Section 6 provides the conclusion of this study and directions for future studies.
2. INTERTERMINAL TRANSPORTATION OF CONTAINERS
A typical flow of transshipment containers is illustrated in Figure 1. A transshipment container is unloaded from a vessel and then stacked in the yard of Terminal A. When the time for the transshipment container to be loaded onto another vessel approaches, Terminal B requests a truck company to transport the container to Terminal B. Then, the truck company dispatches a truck to load the container and transport it to Terminal B. If there is no order to deliver a container from Terminal B to A, then, the truck returns empty to Terminal A to load the next container. Figure 2 illustrates the layout of terminals in Busan New Port (BNP), Korea. ITTs happen among five terminals in BNP and five terminals in the north port of Busan which is located 30 km away from BNP. According to data collected in 2013, an average of approximately 2600 containers moved among the terminals on each day.
Table 1 illustrates actual transportation tasks among trucking companies. Each company has certain delivery tasks to perform, each of which involves delivery of multiple containers from a specified terminal to another within a prespecified timewindow. The timewindow is expressed by the earliest time and the latest time for a truck arrival at the destination terminal. The earliest time is related to the earliest time to pick up from the source terminal (note that an inbound container may be picked up only after it is discharged from a vessel), while the latest time is related to the loading schedule of the container onto a vessel at the destination terminal (because the container should arrive at the terminal before the load scheduling begins). However, the earliest pickup time must be adjusted to the earliest delivery time by adding the transportation time from the source terminal to the destination terminal. Each trucking company deploys a certain number of trucks to the transportation operations. There are two feasible strategies to move transshipment containers. In the first strategy, the traDi_{t}ional method is used, in which each company performs the transportation operations independently. The second strategy is for the various trucking companies to share their tasks. Each task has a predetermined price of delivery to be received from the corresponding shipping liner, and a trucking company is required to pay a certain amount of rental charge when it deploys a truck to the transportation operations during a day.
Figure 3 depicts a graphical representation of the problem of scheduling transportation operations. The planning horizon is divided into multiple timeperiods each of whose length is 10 or 20 minutes. Note that a node corresponds to a terminal at the end of a timeperiod. As time value in the formulation is expressed in units of a timeperiod, a transportation operation always starts or ends at a node, and therefore, the operation time is to be an integer multiple of the length of a period. That is, nodes representing terminals and depots at each timeperiod. There are two adDi_{t}ional types of nodes for each trucking company: a source node, from which trucks start their travel on a day, and a sink node, at which the trucks finish their travels on that day. An arc from a terminal node T1_{t} (representing terminal T1 at timeperiod t) to another terminal node T2_{s} (representing terminal T2 at timeperiod s) corresponds to a travel (loaded or empty travel) of a truck departing from terminal T1 at timeperiod t and arriving at terminal T2 at timeperiod s. An arc connects the two nodes T1_{t} and T2_{s} only if a truck arrives at terminal T2 at timeperiod s after leaving terminal T1 at timeperiod t. “Di_{t}” represents depot for trucking company i at timeperiod t. It is assumed that each trucking company has a single depot. An arc from T1_{t} (D1_{t}) to T1_{(t+1)} (D1_{(t+1)}) represents the stay of a truck at terminal T1 (D1) from timeperiod t to t+1. Note that containers may be moved from a terminal to another only by the truck travels.
Two terminologies are used in this study to express “time.” They are “travel time” and “flow time.” Travel time is the time required for a truck to travel from a terminal to another. Flow time is defined as the time required for completing all the activities between the departure of a truck from a terminal and the departure of the truck from the subsequent terminal. These activities include the travel between the terminals, wait at the second terminal, and transfer of the container. This study assumes that the travel time and flow time may vary between timeperiods because workload at a terminal and congestion on the road may vary between timeperiods.
This study introduces the following assumptions:

(1) If a truck arrives before the earliest possible delivery period, the truck is required to wait until the earliest possible delivery period, as it is not possible to perform the operation before that time.

(2) The travel time required by a truck for transporting a container between a specific source and destination terminals may vary between the time periods.

(3) A trucking company has one depot.

(4) The number of available trucks is unlimited at the beginning of each day, when the truck scheduling is performed.
3. MATHEMATICAL FORMULATION
The formulation of the ITT problem for one trucking company is provided below. The notation used in the mathematical formulation are defined as Table 2, Table 3, and Table 4.(8)
subject to
The objective function (1) maximizes the profit, which can be calculated from the total revenue, total operation cost, and total truck rentalfee. The operations cost includes the delay cost. The delay cost is related to the arrival time of a truck at the destination terminal. The delivery of a container after the latest feasible time incurs a penalty cost. The lower bound of the time window is considered as a hard constraint, while the upper bound of the time window as a soft constraint. The revenue term is always constant in this study and thus it may be omitted from the mathematical model. However, considering a delivery order is obtained by a specific trucking company and the order may be performed by another company in the collaboration system, how to share the revenue may be an interesting remaining issue for the future study. By this reason, we keep this term in the objective function for a future study. Constraints (2) and (3) specify the number of trucks leaving from and returning to each depot at time zero and the end of the planning horizon. Constraint (4) ensures that the total inflow of trucks into a terminal is equivalent to the total outflow of trucks from the terminal in each timeperiod. Inflowing trucks include the empty and loaded trucks arriving at a terminal and those that stay at the terminal from the previous timeperiod. Similarly, outflowing trucks include the empty and loaded trucks leaving a terminal and those staying at the terminal until the next timeperiod. Constraint (5) ensure that the number of deployed trucks from each company does not exceed the number of available trucks. Constraint (6) ensures that the number of containers that are moved from a terminal to another does not exceed the number of trucks moving through the same route. Constraint (7) ensures that the number of moved containers satisfies the required number of transshipment containers to be transported.
4. ILLUSTRATIVE NUMERICAL EXAMPLE
This section presents a numerical example to illustrate the mathematical model. Table 5 provides the input data for delivery tasks. Tables 6 and 7 present the estimated travel times and flow times among terminals at various timeperiods. In this example, two trucking companies are assumed to perform eight tasks from/to three container terminals during 12 timeperiods. Figure 3 illustrates the graphical representation of this example problem. The lengths of arcs correspond to the expected travel times and flow times. For example, a truck requires three unit timeperiods for it to travel from Terminal 2 to Terminal 3, complete the task, and leave, by starting from Terminal 2 at timeperiod 3. It requires only two timeperiods for the same if it departs from Terminal 2 at timeperiod 8. The operation (service) time at a terminal is assumed to be one timeperiod. Moreover, it is assumed that one timeperiod corresponds to 15 min in this example.
Tables 6 and 7 present the travel times and flow times. The notation ∞ indicates that there is no feasible arc for connecting the two corresponding nodes. Note that a truck can begin its travel at time period 0 from the source (Si) and should return to the sink (Fi) at time period 12. Table 8 presents the cost parameters used in this example.
The IP formulation, which is introduced in section 3, has been solved by using IBM ILOG CPLEX Optimization solver. The test problems were run on a computer incorporating Intel Core i7 (4.00 GHz) and 16.0 GB of RAM. Figures 4 and 5 depict the truck routes and schedule of container deliveries, respectively, of the final solution with the collaboration. In Figure 4, each arc represents the travel of trucks. The number of trucks to travel on each arc is presented on each arc. Figure 5 illustrates the movement of the containers between terminals. Note that a numeric value within the parenthesis represents the task number and that outside the parenthesis represents the number of containers to be moved. For example, among the thirty five containers for task 6, which are to be moved from terminal 2 to terminal 3, thirty two are moved at timeperiod 2 and three at timeperiod 9.
Tables 9 and 10 present the revenue, the profit, and various cost terms in the optimal solution when the companies deliver containers independently and in collaboration, respectively. Through the collaboration, truck companies can achieve total profit higher than that without collaboration by $ 1110. Note that the number of trucks used in the entire system is substantially reduced by the collaboration.
5. NUMERICAL EXPERIMENT
Eighteen problems were solved as part of the numerical experiment. The sizes of the problems are summarized in Table 11. Table 12 presents the average values of the various cost parameters.
The cases of independent operation and collaborative operation were compared in terms of the number of trucks, the revenue, the profit, and various cost terms. The results are presented in Table 13. It is determined that for all the problems, the profit has been significantly increased by collaborative operation. It was determined that the collaboration through sharing of trucks and orders among multiple trucking companies contributes significantly to reduction of empty travel by trucks. In adDi_{t}ion, it was found that the number of trucks deployed to the entire system was smaller in the case of collaboration than in the case of independent operation. The computational time depends on the number of trucking companies, the number of tasks per company, and the number of time windows, which determines the number of decision variables.
AdDi_{t}ional experiments for sensitivity analysis were conducted on various cases. Figure 6 presents the relationship between the average number of tasks assigned to each trucking company and percentage of total cost reduction from the collaboration. In this experiment, the planning horizon was 12 h (48 timeperiods). Five trucking companies are involved in the transportation of containers among four terminals. It was determined that as the average number of tasks assigned to each truck company increases, the percentage of the total cost reduction decreases. When the number of tasks assigned to each trucking company increases, empty travel distance becomes smaller notwithstanding an absence of collaboration. Thus, the effect of collaboration decreases when the number of tasks assigned to each trucking company increases. In adDi_{t}ion, as illustrated in Figure 7, as the number of tasks assigned to each trucking company increases, the number of necessary trucks increases. However, the percentage of reduction in the required number of trucks after the collaboration decreases.
Figure 8 illustrates the relationship between the degree of the slackness of timewindows and the total cost reduction from the collaboration. The degree of the slackness of time windows in an experiment indicates how wide time windows are set to be. A higher degree of the slackness in an experiment implies wider time window constraints. Suppose that a time window is (x, y) in an experiment with a degree of the slackness of n. Then, in the experiment with the degree of the slackness of (n+1), the time window is extended to (x2, y+2). As illustrated in Figure 8, a higher degree of the slackness results in a smaller reduction in the total cost from the collaboration.
6. CONCLUSIONS AND FUTURE WORKS
This study explored the possibility of sharing trucks and delivery orders for interterminal transportation of containers, among multiple trucking companies. A mathematical programming model was proposed for scheduling transport operations for a trucking company and multiple trucking companies. From the numerical experiment, it was determined that the effect of collaboration reduces the total cost significantly, and a smaller number of trucks are required for completing all the delivery orders. It was also determined that as the average number of tasks assigned to each truck company increases, the percentage of the total cost reduction decreases. Moreover, as the number of tasks assigned to each trucking company increases, the number of necessary trucks increases; however, the percentage of reduction in the required number of trucks after collaboration decreases. According to the numerical experiment, as the timewindows for deliveries become wider, the reduction of the total cost becomes smaller.
The sizes of the problems in the numerical experiment were small. Thus, the problems could be solved by a package for integer linear programs. However, for largersized practical problems, it is necessary to develop a heuristic algorithm. This study demonstrated that it is feasible to reduce the total cost by collaborative operation among trucking companies. However, how the collaboration effects the interests of participating trucking companies and mechanism of reallocation of the profits of the companies were not discussed.