# Modeling the Multicommodity Multimodal Routing Problem with Schedule-Based Services and Carbon Dioxide Emission Costs

Authors: Yan Sun; Maoxiang Lang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We explore a freight routing problem wherein the aim is to assign optimal routes to move commodities through a multimodal transportation network. This problem belongs to the operational level of service network planning. The following formulation characteristics will be comprehensively considered: (1) multicommodity flow routing; (2) a capacitated multimodal transportation network with schedule-based rail services and time-flexible road services; (3) carbon dioxide emissions consideration; and (4) a generalized costs optimum oriented to customer demands. The specific planning of freight routing is thus defined as a capacitated time-sensitive multicommodity multimodal generalized shortest path problem. To solve this problem systematically, we first establish a node-arc-based mixed integer nonlinear programming model that combines the above formulation characteristics in a comprehensive manner. Then, we develop a linearization method to transform the proposed model into a linear one. Finally, a computational experiment from the Chinese inland container export business is presented to demonstrate the feasibility of the model and linearization method. The computational results indicate that implementing the proposed model and linearization method in the mathematical programming software Lingo can effectively solve the large-scale practical multicommodity multimodal transportation routing problem.


---

## Body

## 1. Introduction

### 1.1. Multimodal Transportation

Multimodal transportation utilizes more than one transportation service (rail, road, air, and maritime transportation) on the routes that serve to move commodities from their origins to their destinations [1–3]. Multimodal transportation differs significantly from traditional unimodal transportation which employs single transportation service provided by one transportation carrier. Due to the integrative combination of different advantages of various transportation services, multimodal transportation shows superiorities in lowering transportation costs and abating environmental pollution when compared with unimodal transportation in a long-haul transportation setting. Moreover, containers are widely used to carry commodities in multimodal transportation. They can simplify the packaging of product, economize on the package materials, and ensure transportation safety [4]. The standardization of containers in the physical structure of the transportation system also benefits the mechanization of the loading and unloading operations and can help improve the efficiency of these operations at terminals [5].Several empirical comparative studies have demonstrated the superiorities of multimodal transportation in costs and environmental protection. Janic [6] formulated the full costs (linear summation of the internal costs and external costs) of a multimodal and road freight transportation network. By using the simplified European multimodal transportation network (truck-rail combination) and its equivalent road transportation network as a case, that study summarized the trends of variation of the full costs of multimodal transportation and road transportation in relation to the transportation distances. These trends showed that, compared with road transportation, multimodal transportation decreases the average full costs more rapidly as the distance increases and shows fewer full costs if the transportation distance exceeds approximately 1000 km (the critical distance when the rail service frequency is 5 trains/week). Moreover, the critical distance decreases significantly as the rail service frequency increases. Liao et al. [7] compared the carbon dioxide emissions of the long-haul truck transportation and the multimodal transportation (truck-ocean combination) in a case study of container transportation between Kaohsiung and Keelung in Taiwan. The activity-based method was adopted to estimate the carbon dioxide emissions in the transportation process, and the computational results of the case indicated that the carbon dioxide emissions fell from 566,525 tonnes to 163,830 tonnes, corresponding to a 71% decrease, when truck transportation was replaced by multimodal transportation. These results supported the view that the use of multimodal transportation as an alternative to long-haul truck transportation can markedly decrease carbon dioxide emissions from the transportation sector.Many researchers have studied the empirical applications of multimodal transportation in specific cases; for example, Bookbinder and Fox [8] discussed multimodal transportation shortest time and minimal costs route selection for five commodity flows that need to be routed from Canada to Mexico in the North American Free Trade Agreement area. Banomyong and Beresford [9] explored multimodal transportation route selection for exporting commodities from Laos to the European Union and proposed a cost model for multimodal transportation to help exporters make decisions. Cho et al. [10] presented a weighted constrained shortest path problem model and a label setting algorithm to select multimodal transportation routes from Busan to Rotterdam. Meethom and Kengpol [11] combined the AHP (Analytic Hierarchy Process) method with 0-1 goal programming to design a decision support system for selecting an optimal multimodal transportation route from Bangkok to Danang.Currently, with the rapid development of economic globalization, international trade and the accompanying global circulation of commodities have grown remarkably. Consequently, transportation networks have expanded widely and commodity distribution routes have extended significantly. These changes represent challenges to transportation performance in terms of, for example, costs, timeliness, and environmental concerns [2, 12]. In response to these challenges, increasing numbers of companies have adopted multimodal transportation schemes to transport their products or raw materials. According to the relevant statistics, logistics costs represent 30–50% of the product cost [2]. For this reason, logistics cost is one of the most effective targets for companies to lower product cost, raise profits, and maintain competitiveness in the international trade market. Therefore, freight routing for commodity transportation has been given great importance by both the management decision makers and multimodal transport operators.


### 1.2. Formulation Characteristics of the Study

The practical demand for lowering logistics costs motivates research interests in the freight routing problem in multimodal transportation networks. The essence of this problem is to select optimal routes to move commodities from their origins to their destinations through a multimodal transportation network. In our study, we consider following formulation characteristics to make the formulation of this problem correspond more closely to actual practice.(
1) Multicommodity Flow Routing. Freight routing aims at satisfying customer demands at minimal costs. Each transportation demand can be represented by a commodity flow that is characterized by five attributes: origin, destination, volume, release time, and due date. From the perspective of the entire multimodal transportation network, more than one transportation demand within the planning horizon needs to be satisfied. Various transportation demands differ from each other in at least one of the five above-mentioned attributions. Thus, multiple commodity flows must be routed to satisfy the various transportation demands. Therefore, the freight routing problem explored in this study will be developed as a multicommodity problem.(
2) Schedule-Based and Time-Flexible Transportation Services. In a multimodal transportation network, we can combine different transportation services to move commodities along routes. The most obvious distinction among the transportation services is in terms of their operating modes. In this study, we define two categories for classifying transportation services. The first category is that of schedule-based services, that is, operations controlled by schedules. The second category is that of time-flexible services, that is, operations not controlled by schedules. This distinction is similar to that drawn in Moccia et al.’s study [13]. Schedule-based services (e.g., rail services) are operated based on schedules that are specified in advance. Conversely, time-flexible services (e.g., road services) are not constrained by time and can travel through the network flexibly. The operations of the two types of transportation services and the transshipments among them will be emphasized in Section 2.(
3) Consideration of Carbon Dioxide Emissions. With the evolution of society and improvement in the awareness of sustainable development, environmental issues have drawn increasing attention from both the government and the public, especially in developing countries, for example, China, a rapidly industrializing country. One of the most pressing environmental issues is global warming caused by greenhouse gas emissions. Carbon dioxide represents approximately 80% of the total greenhouse gas emissions [7], and the reduction of these emissions is acknowledged to be a highly challenging problem worldwide. In the transportation sector, various activities have been shown to represent up to 19% of the global energy consumption [14] and to produce large amounts of greenhouse gases (e.g., carbon dioxide, carbon monoxide, and methane) and air pollutants (e.g., sulfur dioxide and oxynitride) [15]. For example, according to Li et al.’s evaluation [16], carbon dioxide emissions from the Chinese transportation sector represent 8.37% (53.96%) of the total carbon dioxide emissions from fossil fuel (liquid fuel) consumption in 2007. Therefore, transportation is considered a key target in reducing carbon dioxide emissions. For this reason, it is necessary for decision makers to seriously consider the carbon dioxide emissions when planning multimodal transportation routes.(
4) Generalized Costs Optimum Oriented to Customer Demands. Transportation is a service industry, and transportation operation oriented to customer demands has been promoted vigorously with the development of traditional transportation practice into modern logistics. In freight routing, the goal of the shippers is to pay minimal costs for the transportation of their commodities. As service providers, the multimodal transport operators and the third party logistics companies should base their planning on customer demands, which means that lowering costs should be chosen as their planning objective for the transportation process. In this study, we use generalized costs to evaluate how much money the shippers should pay for transportation. The generalized costs cover not only the transportation costs but also the inventory costs, operation costs at terminals, carbon dioxide emissions costs, and additional service costs.


### 1.3. Literature Review

Because multimodal transportation routing has attracted substantial interest [17, 18], many relevant studies have been conducted in previous decades. Among the early studies (studies conducted before 2005), Min [2] developed a chance-constrained goal program model to provide the distribution manager with decision support in choosing international multimodal transportation routes. Minimizing the transportation costs and risk and satisfying the requirements of on-time service are formulated in the proposed model. Barnhart and Ratliff [19] discussed the minimal costs multimodal transportation routing problem and introduced two solution approaches that separately involved a shortest path algorithm and a matching algorithm. The two approaches were adopted to solve the routing problems with rail service costs expressed per trailer and per flatcar, respectively. Boardman et al. [20] designed a k-shortest path double-swap method to solve a multimodal transportation routing problem and incorporated this method with the a database and user interface to build a decision support system for the real-time routing of shipments through a multimodal transportation network. Ziliaskopoulos and Wardell [21] systematically presented a time-dependent multimodal optimum path algorithm for multimodal transportation networks. In their algorithm, many time parameters, including schedules, dynamic arc travel times, and transshipment delays, were comprehensively considered. This approach enhanced the feasibility of the algorithm in addressing the practical problem. Lozano and Storchi [22] defined the shortest viable path within an origin-destination pair in the multimodal transportation network and proposed an ad hoc modification of the chronological algorithm to solve the multimodal shortest path problem by obtaining a solution set of the problem. Lam and Srikanthan [18] improved the computational efficiency of the k-shortest algorithm by using clustering technique and applied this algorithm to multimodal transportation routing. Boussedjra et al. [23] addressed the multimodal shortest path problem and proposed a shortest path algorithm involving label correcting method to solve the single origin-destination pair problem. The efficiency of the algorithm was verified by comparing its performance with that of the branch-and-bound method.Essentially, in these previous studies, with the exception of Min’s study, researchers have emphasized the use of algorithms for selecting optimal multimodal transportation routes for commodities, and the development of optimization models attracted limited attention. However, it is necessary to construct optimization models, because it is difficult to find a universal optimization model to solve all types of multimodal transportation routing problems considering different formulation characteristics. Moreover, optimization models can provide an exact benchmark for systematically testing various solution algorithms.In recent years, with the constant improvement of the design of algorithms for solving problems in this area of study, increasing numbers of multimodal transportation routing models have been developed. In these studies, a few researchers have concentrated on the development of GIS-based models for the multimodal transportation routing problem. For example, Winebrake et al. [24] constructed a geospatial multimodal transportation routing model to select minimal costs, minimal time, and minimal carbon dioxide emissions routes for an origin-destination pair. The construction and solution of them model were conducted with ArcGIS software. Other researchers have continued to pursue studies on goal programming models and solution algorithms. Zhang and Guo [25] and Zhang et al. [26] separately presented the foundational frameworks of integer programming models for the multimodal transportation routing problem. Sun et al. [27] studied the basic uncapacitated single-commodity multimodal transportation routing problem without a demanded delivery time constraint and used the label correcting algorithm to solve it. A similar study was also conducted by Sun and Chen [28], whereas this study addressed an uncertain transportation case and considered biobjective optimization, including the minimization of total transportation costs and total carbon dioxide emissions. Using these studies as a springboard, many studies have highlighted transportation due date constraints and capacity constraints. In the formulation of transportation due date constraints, several studies (e.g., Liu et al. [29]) have treated the transportation due date as a hard constraint, which the total transportation time should not exceed. Furthermore, others have considered the transportation due date as an index for charging penalty costs, which means that if the transportation due date is violated, penalty costs must be paid to compensate for the loss, as in, for example, Zeng et al. [30], Wang et al. [31], Fan and Le [32], Li et al. [33], and Tang and Huo [34]. Regarding the capacity constraint, vehicle carrying capacity has been widely considered, for example, by Kang et al. [35], Wang et al. [31], Liu et al. [29], Li et al. [33], Çakır [36], Verma et al. [37], Cai et al. [38], Tang and Huo [34], and Lei et al. [39]. A few studies (e.g., Chang et al. [40]) have also defined terminal operating capacity and vehicle carrying capacity as capacity constraints. As for the scheduling issues, current studies, for example, Cai et al. [38], Xiong and Wang [41], and Lei et al. [39], have viewed schedules as “terminal schedule-based service time windows” to formulate a multimodal transportation routing problem with time windows. In these studies, the terminal scheduled service time windows are only related to the terminals, and different transportation services share one schedule-based service time window at the same terminal. A terminal cannot be covered in the multimodal transportation route if the arrival time of the commodity at this terminal is out of the range of the schedule-based service time window, and this consideration is also formulated as a hard constraint in the optimization models [13, 38, 39, 41, 42].In terms of comparisons with our study, first, apart from Çakır [36], Verma et al. [37], and Chang et al. [40], all other previous studies cited above preferred to optimize the single-commodity routing problem in a multimodal transportation network [27–35, 38, 39, 41], and this type of optimization cannot guarantee an optimum result for the overall performance of the entire multimodal transportation network. Second, in many studies, all types of transportation services were assumed to adopt a time-flexible service mode, and the operations at terminals were simplified as a continuous “arrival → transshipment → departure” process [27–41], which cannot be expected to match the practical reality that some transportation services, for example, rail, ocean, and air services, are operated according to schedules. The actual transshipments among the schedule-based and time-flexible transportation services are much more complicated than the “arrival → transshipment → departure” process, as will be explained in Section 2. Although some researchers used time windows to address the scheduling issues [38, 39, 41], the consideration of terminal schedule-based service time windows is not expected to represent the schedules in the model formulation exactly, because schedules regulate not only the transportation service times but also the transportation service routes. Additionally, different schedules regulate different service times even at the same terminal. Moreover, formulation of terminal schedule-based service time windows as a hard constraint itself [13, 38, 39, 41, 42] does not reflect the actual practice, because if their arrival times are not within the time windows, the commodities can wait until the lower bound of the current time window or that of the next time window and then be transshipped. Consequently, the transportation schemes designed by the studies above are less supportive of decision-making. Additionally, the network deformation method is widely used by researchers to convert actual multimodal transportation networks into a standard graph with one link between two conjoint nodes [27–29, 34, 38]. This method can simplify model formulation but will result in a substantial expansion of the network scale. Thus, this procedure may be feasible for a small-scale multimodal transportation networks, but it will be unfeasible for large scale ones in practice.


### 1.4. Similar Works and Problem

Among existing studies, those most similar to ours are those of Chang [42], Moccia et al. [13], and Ayar and Yaman [5]. Chang [42] addressed the problem of selecting the best routes to move commodities through international multimodal transportation networks. In his study, he considered multiobjective optimization and schedule-based transportation services and demanded delivery times and transportation economies of scale, and he formulated the route selection problem as a multiobjective multimodal multicommodity flow problem with time windows and concave costs. In his study, time window constraints were used to represent the restriction of schedules and demanded delivery times relative to best route selection in empirical cases. A concave piecewise linear function was adopted to measure the transportation costs of all commodity flows. Each commodity flow was considered to be splittable. In the proposed model, minimizing the total transportation costs and total transportation time were set as the objectives, and the weighted summation method was used to address the multicriteria-based optimization. The problem was decomposed into a series of more easily solved single-commodity flow subproblems by using the Lagrangian relaxation technique to relax the capacity constraint of the model. The subgradient optimization algorithm was then used to obtain the solutions to the subproblems. Finally, a reoptimization technique was designed to modify the solutions of subproblems to construct a feasible solution of the initial problem.Moccia et al. [13] explored the multimodal multicommodity flow problem with pickup and delivery time windows, and their study was similar to Chang’s [42]. The problem addressed in their study was oriented to a multimodal transportation network with time-flexible road services and schedule-based rail services. To address this problem, the authors first presented a virtual network representation to convert the physical multimodal transportation network into a detailed representation of operations by adding nodes to represent the pickup and delivery time windows and the scheduled departure times. Then, two mixed integer programming models, including an arc-node-based model and a path-based model, were formulated. The two models were both single-objective ones wherein the aim was to minimize the total transportation costs of all commodity flows. Nonconvex piecewise linear costs, time windows, and side constraints were all considered and formulated in the optimization models, and each commodity flow was unsplittable. Finally, a column generation algorithm was developed to achieve the lower bound of the problem, and it was embedded within heuristics to obtain feasible solutions of the problem.Ayar and Yaman’s study [5] was a special case of the multimodal multicommodity flow problem previously formulated by Moccia et al. [13]. In their study, the release times and due dates of commodities replaced the pickup time and delivery time windows, respectively; that is, the transportation of a certain commodity was defined to begin at or after its release time at its origin and was to be achieved before its due date at its destination. Additionally, in contrast to Chang’s [42] and Moccia et al.’s [13] approaches, to make the costs calculations more accessible and to make them correspond better to the real-world cases, the total transportation costs were evaluated by generalized costs covering transportation costs en route, operation costs, and inventory costs at terminals. Then, the authors proposed two mixed integer programming models and valid inequalities to solve the multicommodity routing problem in a truck-ocean transportation network where truck services were considered to be time flexible and uncapacitated, whereas maritime services were capacitated and operated according to schedules. The solution algorithm designed in this study was somewhat similar to Chang’s [42] in that a Lagrangian relaxation technique was used to relax the capacity constraint.Note that the freight routing problem that this study focuses on is extremely similar to the multicommodity multimodal transportation network design problem. Both of these problems relate to planning optimal routes to move multiple commodities through the transportation network by using multiple transportation services rationally. They also show obvious similarities in model formulation and solution algorithm design. The multicommodity multimodal transportation network design problem has always been a focus of transportation planning, and many studies have already been conducted to address this problem. Some representative studies are reviewed here. Crainic and Rousseau [43] presented a foundational modeling and algorithmic framework to solve the multicommodity multimodal transportation network design problem. An integer nonlinear programming model was constructed, and a solution algorithm involving decomposition and column generation was developed in this study. Their work provided a solid foundation for future related studies. Daeki et al. [44] explored the truck-aircraft service network design problem for express package delivery. The authors addressed this problem as a multimodal transportation network design problem with time windows, separately formulated an approximate model and an exact one to describe this problem, and designed a linear programming relaxation method optimized by valid inequalities to attain the optimal solution of the large-scale problem. Zhang et al. [45] developed a bilevel programming model to optimize the multicommodity multimodal transportation design problem with carbon dioxide emissions and economies of terminal scale. The upper level of the model adopted a genetic algorithm to design the optimal topology of the terminal network, while the lower level served to distribute the multicommodity flow through the multimodal transportation network. Qu et al. [46] built an integer nonlinear programming model considering transfer costs and carbon dioxide emission costs for the multicommodity multimodal transportation network design problem. Using linearization technique, the proposed model was transformed into a linear one that could be solved easily by mathematical programming software.Additionally, Crainic [47], Southworth and Peterson [48], Jansen et al. [49], and Yaghini and Akhavan [50] separately conducted systematic reviews of the service network design problem. All these reviews introduced this problem comprehensively from the perspectives of research content, current progress, model formulation, algorithm development, and research prospects, thus contributing to making the general research architecture more mature and ideal. Furthermore, to enhance the effectiveness of solving the network design problem, many studies discussed the solution approaches for the network design problem in detail, and a large number of solution approaches with high feasibility have been proposed, for example, a dual-ascent method by Balakrishnan et al. [51], a Lagrangian heuristic-based branch-and-bound approach by Holmberg and Yuan [52], a first multilevel cooperative tabu search algorithm by Crainic et al. [53], and a multiple choice 0-1 reformation and column-and-row generation method by Frangioni and Gendron [54]. All the studies discussed above significantly advanced the knowledge of the multicommodity multimodal transportation network design problem.Although similarities between the two types of problems are obvious, there are still three remarkable differences between them. Considering these differences helps to define obvious distinctions between the two types of problems in terms of model formulation.(1) In addition to the question of route selection, the network design problem also needs to solve the allocation of limited transportation resources to the network, that is, to determine the number of facilities or capacities of transportation services that should be installed on the routes, or the levels of transportation services that should be offered on the routes [47]. By contrast, the freight routing problem is based on an existing multimodal transportation network whose transportation resources have already been allocated, and it only focuses on planning origin-to-destination routes by selecting proper terminals and transportation services connecting them.(2) The network design problem is a form of tactical planning. The due dates of the commodities are usually not considered in this problem. By contrast, the freight routing problem is a part of the operational planning and must assign great importance to customer demands. The due dates of the commodities must be formulated as a constraint to satisfy the customer demands regarding timeliness.(3) In the network design problem, the detailed schedules of transportation services are rarely formulated by the researchers. However, in the freight routing problem, when utilizing schedule-based services to move commodities, the schedules must be followed strictly to guarantee the feasibility of routing in empirical cases. Consideration of service schedules improves the complexity of the freight routing problem in the multimodal transportation network.


### 1.5. Organization of the Rest of the Sections

All the studies reviewed above, regardless of the problem (freight routing problem or freight network design problem) they addressed, laid a solid foundation for our study with regard to the model formulation and algorithm design. The remaining sections of our study are organized as follows.In Section2, we first give a detailed introduction to multiple transportation services in the multimodal transportation network, including schedule-based rail services and the time-flexible road services. We then analyze the various transshipment manners that are available in the network. All this background information is considered in formulating the model. In Section 3, we define the multicommodity multimodal transportation routing problem from the perspectives of capacity constraint and time sensitivity, and we present an example containing a single-commodity flow to illustrate the selection of time-sensitive multimodal transportation routes. In Section 4, we establish an arc-node-based mixed integer nonlinear programming model to formulate the specific freight routing problem that we explore in this study. The proposed optimization model integrates the various formulation characteristics mentioned in the abstract. Then, we develop a linearization method to linearize the proposed model to make it easily solvable by mathematical programming software. In Section 5, a computational example from the Chinese inland container export business is presented to demonstrate the feasibility of the proposed model and the use of the linearization method to address the practical problem. Finally, the conclusions of this study are presented in Section 6.


## 1.1. Multimodal Transportation

Multimodal transportation utilizes more than one transportation service (rail, road, air, and maritime transportation) on the routes that serve to move commodities from their origins to their destinations [1–3]. Multimodal transportation differs significantly from traditional unimodal transportation which employs single transportation service provided by one transportation carrier. Due to the integrative combination of different advantages of various transportation services, multimodal transportation shows superiorities in lowering transportation costs and abating environmental pollution when compared with unimodal transportation in a long-haul transportation setting. Moreover, containers are widely used to carry commodities in multimodal transportation. They can simplify the packaging of product, economize on the package materials, and ensure transportation safety [4]. The standardization of containers in the physical structure of the transportation system also benefits the mechanization of the loading and unloading operations and can help improve the efficiency of these operations at terminals [5].Several empirical comparative studies have demonstrated the superiorities of multimodal transportation in costs and environmental protection. Janic [6] formulated the full costs (linear summation of the internal costs and external costs) of a multimodal and road freight transportation network. By using the simplified European multimodal transportation network (truck-rail combination) and its equivalent road transportation network as a case, that study summarized the trends of variation of the full costs of multimodal transportation and road transportation in relation to the transportation distances. These trends showed that, compared with road transportation, multimodal transportation decreases the average full costs more rapidly as the distance increases and shows fewer full costs if the transportation distance exceeds approximately 1000 km (the critical distance when the rail service frequency is 5 trains/week). Moreover, the critical distance decreases significantly as the rail service frequency increases. Liao et al. [7] compared the carbon dioxide emissions of the long-haul truck transportation and the multimodal transportation (truck-ocean combination) in a case study of container transportation between Kaohsiung and Keelung in Taiwan. The activity-based method was adopted to estimate the carbon dioxide emissions in the transportation process, and the computational results of the case indicated that the carbon dioxide emissions fell from 566,525 tonnes to 163,830 tonnes, corresponding to a 71% decrease, when truck transportation was replaced by multimodal transportation. These results supported the view that the use of multimodal transportation as an alternative to long-haul truck transportation can markedly decrease carbon dioxide emissions from the transportation sector.Many researchers have studied the empirical applications of multimodal transportation in specific cases; for example, Bookbinder and Fox [8] discussed multimodal transportation shortest time and minimal costs route selection for five commodity flows that need to be routed from Canada to Mexico in the North American Free Trade Agreement area. Banomyong and Beresford [9] explored multimodal transportation route selection for exporting commodities from Laos to the European Union and proposed a cost model for multimodal transportation to help exporters make decisions. Cho et al. [10] presented a weighted constrained shortest path problem model and a label setting algorithm to select multimodal transportation routes from Busan to Rotterdam. Meethom and Kengpol [11] combined the AHP (Analytic Hierarchy Process) method with 0-1 goal programming to design a decision support system for selecting an optimal multimodal transportation route from Bangkok to Danang.Currently, with the rapid development of economic globalization, international trade and the accompanying global circulation of commodities have grown remarkably. Consequently, transportation networks have expanded widely and commodity distribution routes have extended significantly. These changes represent challenges to transportation performance in terms of, for example, costs, timeliness, and environmental concerns [2, 12]. In response to these challenges, increasing numbers of companies have adopted multimodal transportation schemes to transport their products or raw materials. According to the relevant statistics, logistics costs represent 30–50% of the product cost [2]. For this reason, logistics cost is one of the most effective targets for companies to lower product cost, raise profits, and maintain competitiveness in the international trade market. Therefore, freight routing for commodity transportation has been given great importance by both the management decision makers and multimodal transport operators.


## 1.2. Formulation Characteristics of the Study

The practical demand for lowering logistics costs motivates research interests in the freight routing problem in multimodal transportation networks. The essence of this problem is to select optimal routes to move commodities from their origins to their destinations through a multimodal transportation network. In our study, we consider following formulation characteristics to make the formulation of this problem correspond more closely to actual practice.(
1) Multicommodity Flow Routing. Freight routing aims at satisfying customer demands at minimal costs. Each transportation demand can be represented by a commodity flow that is characterized by five attributes: origin, destination, volume, release time, and due date. From the perspective of the entire multimodal transportation network, more than one transportation demand within the planning horizon needs to be satisfied. Various transportation demands differ from each other in at least one of the five above-mentioned attributions. Thus, multiple commodity flows must be routed to satisfy the various transportation demands. Therefore, the freight routing problem explored in this study will be developed as a multicommodity problem.(
2) Schedule-Based and Time-Flexible Transportation Services. In a multimodal transportation network, we can combine different transportation services to move commodities along routes. The most obvious distinction among the transportation services is in terms of their operating modes. In this study, we define two categories for classifying transportation services. The first category is that of schedule-based services, that is, operations controlled by schedules. The second category is that of time-flexible services, that is, operations not controlled by schedules. This distinction is similar to that drawn in Moccia et al.’s study [13]. Schedule-based services (e.g., rail services) are operated based on schedules that are specified in advance. Conversely, time-flexible services (e.g., road services) are not constrained by time and can travel through the network flexibly. The operations of the two types of transportation services and the transshipments among them will be emphasized in Section 2.(
3) Consideration of Carbon Dioxide Emissions. With the evolution of society and improvement in the awareness of sustainable development, environmental issues have drawn increasing attention from both the government and the public, especially in developing countries, for example, China, a rapidly industrializing country. One of the most pressing environmental issues is global warming caused by greenhouse gas emissions. Carbon dioxide represents approximately 80% of the total greenhouse gas emissions [7], and the reduction of these emissions is acknowledged to be a highly challenging problem worldwide. In the transportation sector, various activities have been shown to represent up to 19% of the global energy consumption [14] and to produce large amounts of greenhouse gases (e.g., carbon dioxide, carbon monoxide, and methane) and air pollutants (e.g., sulfur dioxide and oxynitride) [15]. For example, according to Li et al.’s evaluation [16], carbon dioxide emissions from the Chinese transportation sector represent 8.37% (53.96%) of the total carbon dioxide emissions from fossil fuel (liquid fuel) consumption in 2007. Therefore, transportation is considered a key target in reducing carbon dioxide emissions. For this reason, it is necessary for decision makers to seriously consider the carbon dioxide emissions when planning multimodal transportation routes.(
4) Generalized Costs Optimum Oriented to Customer Demands. Transportation is a service industry, and transportation operation oriented to customer demands has been promoted vigorously with the development of traditional transportation practice into modern logistics. In freight routing, the goal of the shippers is to pay minimal costs for the transportation of their commodities. As service providers, the multimodal transport operators and the third party logistics companies should base their planning on customer demands, which means that lowering costs should be chosen as their planning objective for the transportation process. In this study, we use generalized costs to evaluate how much money the shippers should pay for transportation. The generalized costs cover not only the transportation costs but also the inventory costs, operation costs at terminals, carbon dioxide emissions costs, and additional service costs.


## 1.3. Literature Review

Because multimodal transportation routing has attracted substantial interest [17, 18], many relevant studies have been conducted in previous decades. Among the early studies (studies conducted before 2005), Min [2] developed a chance-constrained goal program model to provide the distribution manager with decision support in choosing international multimodal transportation routes. Minimizing the transportation costs and risk and satisfying the requirements of on-time service are formulated in the proposed model. Barnhart and Ratliff [19] discussed the minimal costs multimodal transportation routing problem and introduced two solution approaches that separately involved a shortest path algorithm and a matching algorithm. The two approaches were adopted to solve the routing problems with rail service costs expressed per trailer and per flatcar, respectively. Boardman et al. [20] designed a k-shortest path double-swap method to solve a multimodal transportation routing problem and incorporated this method with the a database and user interface to build a decision support system for the real-time routing of shipments through a multimodal transportation network. Ziliaskopoulos and Wardell [21] systematically presented a time-dependent multimodal optimum path algorithm for multimodal transportation networks. In their algorithm, many time parameters, including schedules, dynamic arc travel times, and transshipment delays, were comprehensively considered. This approach enhanced the feasibility of the algorithm in addressing the practical problem. Lozano and Storchi [22] defined the shortest viable path within an origin-destination pair in the multimodal transportation network and proposed an ad hoc modification of the chronological algorithm to solve the multimodal shortest path problem by obtaining a solution set of the problem. Lam and Srikanthan [18] improved the computational efficiency of the k-shortest algorithm by using clustering technique and applied this algorithm to multimodal transportation routing. Boussedjra et al. [23] addressed the multimodal shortest path problem and proposed a shortest path algorithm involving label correcting method to solve the single origin-destination pair problem. The efficiency of the algorithm was verified by comparing its performance with that of the branch-and-bound method.Essentially, in these previous studies, with the exception of Min’s study, researchers have emphasized the use of algorithms for selecting optimal multimodal transportation routes for commodities, and the development of optimization models attracted limited attention. However, it is necessary to construct optimization models, because it is difficult to find a universal optimization model to solve all types of multimodal transportation routing problems considering different formulation characteristics. Moreover, optimization models can provide an exact benchmark for systematically testing various solution algorithms.In recent years, with the constant improvement of the design of algorithms for solving problems in this area of study, increasing numbers of multimodal transportation routing models have been developed. In these studies, a few researchers have concentrated on the development of GIS-based models for the multimodal transportation routing problem. For example, Winebrake et al. [24] constructed a geospatial multimodal transportation routing model to select minimal costs, minimal time, and minimal carbon dioxide emissions routes for an origin-destination pair. The construction and solution of them model were conducted with ArcGIS software. Other researchers have continued to pursue studies on goal programming models and solution algorithms. Zhang and Guo [25] and Zhang et al. [26] separately presented the foundational frameworks of integer programming models for the multimodal transportation routing problem. Sun et al. [27] studied the basic uncapacitated single-commodity multimodal transportation routing problem without a demanded delivery time constraint and used the label correcting algorithm to solve it. A similar study was also conducted by Sun and Chen [28], whereas this study addressed an uncertain transportation case and considered biobjective optimization, including the minimization of total transportation costs and total carbon dioxide emissions. Using these studies as a springboard, many studies have highlighted transportation due date constraints and capacity constraints. In the formulation of transportation due date constraints, several studies (e.g., Liu et al. [29]) have treated the transportation due date as a hard constraint, which the total transportation time should not exceed. Furthermore, others have considered the transportation due date as an index for charging penalty costs, which means that if the transportation due date is violated, penalty costs must be paid to compensate for the loss, as in, for example, Zeng et al. [30], Wang et al. [31], Fan and Le [32], Li et al. [33], and Tang and Huo [34]. Regarding the capacity constraint, vehicle carrying capacity has been widely considered, for example, by Kang et al. [35], Wang et al. [31], Liu et al. [29], Li et al. [33], Çakır [36], Verma et al. [37], Cai et al. [38], Tang and Huo [34], and Lei et al. [39]. A few studies (e.g., Chang et al. [40]) have also defined terminal operating capacity and vehicle carrying capacity as capacity constraints. As for the scheduling issues, current studies, for example, Cai et al. [38], Xiong and Wang [41], and Lei et al. [39], have viewed schedules as “terminal schedule-based service time windows” to formulate a multimodal transportation routing problem with time windows. In these studies, the terminal scheduled service time windows are only related to the terminals, and different transportation services share one schedule-based service time window at the same terminal. A terminal cannot be covered in the multimodal transportation route if the arrival time of the commodity at this terminal is out of the range of the schedule-based service time window, and this consideration is also formulated as a hard constraint in the optimization models [13, 38, 39, 41, 42].In terms of comparisons with our study, first, apart from Çakır [36], Verma et al. [37], and Chang et al. [40], all other previous studies cited above preferred to optimize the single-commodity routing problem in a multimodal transportation network [27–35, 38, 39, 41], and this type of optimization cannot guarantee an optimum result for the overall performance of the entire multimodal transportation network. Second, in many studies, all types of transportation services were assumed to adopt a time-flexible service mode, and the operations at terminals were simplified as a continuous “arrival → transshipment → departure” process [27–41], which cannot be expected to match the practical reality that some transportation services, for example, rail, ocean, and air services, are operated according to schedules. The actual transshipments among the schedule-based and time-flexible transportation services are much more complicated than the “arrival → transshipment → departure” process, as will be explained in Section 2. Although some researchers used time windows to address the scheduling issues [38, 39, 41], the consideration of terminal schedule-based service time windows is not expected to represent the schedules in the model formulation exactly, because schedules regulate not only the transportation service times but also the transportation service routes. Additionally, different schedules regulate different service times even at the same terminal. Moreover, formulation of terminal schedule-based service time windows as a hard constraint itself [13, 38, 39, 41, 42] does not reflect the actual practice, because if their arrival times are not within the time windows, the commodities can wait until the lower bound of the current time window or that of the next time window and then be transshipped. Consequently, the transportation schemes designed by the studies above are less supportive of decision-making. Additionally, the network deformation method is widely used by researchers to convert actual multimodal transportation networks into a standard graph with one link between two conjoint nodes [27–29, 34, 38]. This method can simplify model formulation but will result in a substantial expansion of the network scale. Thus, this procedure may be feasible for a small-scale multimodal transportation networks, but it will be unfeasible for large scale ones in practice.


## 1.4. Similar Works and Problem

Among existing studies, those most similar to ours are those of Chang [42], Moccia et al. [13], and Ayar and Yaman [5]. Chang [42] addressed the problem of selecting the best routes to move commodities through international multimodal transportation networks. In his study, he considered multiobjective optimization and schedule-based transportation services and demanded delivery times and transportation economies of scale, and he formulated the route selection problem as a multiobjective multimodal multicommodity flow problem with time windows and concave costs. In his study, time window constraints were used to represent the restriction of schedules and demanded delivery times relative to best route selection in empirical cases. A concave piecewise linear function was adopted to measure the transportation costs of all commodity flows. Each commodity flow was considered to be splittable. In the proposed model, minimizing the total transportation costs and total transportation time were set as the objectives, and the weighted summation method was used to address the multicriteria-based optimization. The problem was decomposed into a series of more easily solved single-commodity flow subproblems by using the Lagrangian relaxation technique to relax the capacity constraint of the model. The subgradient optimization algorithm was then used to obtain the solutions to the subproblems. Finally, a reoptimization technique was designed to modify the solutions of subproblems to construct a feasible solution of the initial problem.Moccia et al. [13] explored the multimodal multicommodity flow problem with pickup and delivery time windows, and their study was similar to Chang’s [42]. The problem addressed in their study was oriented to a multimodal transportation network with time-flexible road services and schedule-based rail services. To address this problem, the authors first presented a virtual network representation to convert the physical multimodal transportation network into a detailed representation of operations by adding nodes to represent the pickup and delivery time windows and the scheduled departure times. Then, two mixed integer programming models, including an arc-node-based model and a path-based model, were formulated. The two models were both single-objective ones wherein the aim was to minimize the total transportation costs of all commodity flows. Nonconvex piecewise linear costs, time windows, and side constraints were all considered and formulated in the optimization models, and each commodity flow was unsplittable. Finally, a column generation algorithm was developed to achieve the lower bound of the problem, and it was embedded within heuristics to obtain feasible solutions of the problem.Ayar and Yaman’s study [5] was a special case of the multimodal multicommodity flow problem previously formulated by Moccia et al. [13]. In their study, the release times and due dates of commodities replaced the pickup time and delivery time windows, respectively; that is, the transportation of a certain commodity was defined to begin at or after its release time at its origin and was to be achieved before its due date at its destination. Additionally, in contrast to Chang’s [42] and Moccia et al.’s [13] approaches, to make the costs calculations more accessible and to make them correspond better to the real-world cases, the total transportation costs were evaluated by generalized costs covering transportation costs en route, operation costs, and inventory costs at terminals. Then, the authors proposed two mixed integer programming models and valid inequalities to solve the multicommodity routing problem in a truck-ocean transportation network where truck services were considered to be time flexible and uncapacitated, whereas maritime services were capacitated and operated according to schedules. The solution algorithm designed in this study was somewhat similar to Chang’s [42] in that a Lagrangian relaxation technique was used to relax the capacity constraint.Note that the freight routing problem that this study focuses on is extremely similar to the multicommodity multimodal transportation network design problem. Both of these problems relate to planning optimal routes to move multiple commodities through the transportation network by using multiple transportation services rationally. They also show obvious similarities in model formulation and solution algorithm design. The multicommodity multimodal transportation network design problem has always been a focus of transportation planning, and many studies have already been conducted to address this problem. Some representative studies are reviewed here. Crainic and Rousseau [43] presented a foundational modeling and algorithmic framework to solve the multicommodity multimodal transportation network design problem. An integer nonlinear programming model was constructed, and a solution algorithm involving decomposition and column generation was developed in this study. Their work provided a solid foundation for future related studies. Daeki et al. [44] explored the truck-aircraft service network design problem for express package delivery. The authors addressed this problem as a multimodal transportation network design problem with time windows, separately formulated an approximate model and an exact one to describe this problem, and designed a linear programming relaxation method optimized by valid inequalities to attain the optimal solution of the large-scale problem. Zhang et al. [45] developed a bilevel programming model to optimize the multicommodity multimodal transportation design problem with carbon dioxide emissions and economies of terminal scale. The upper level of the model adopted a genetic algorithm to design the optimal topology of the terminal network, while the lower level served to distribute the multicommodity flow through the multimodal transportation network. Qu et al. [46] built an integer nonlinear programming model considering transfer costs and carbon dioxide emission costs for the multicommodity multimodal transportation network design problem. Using linearization technique, the proposed model was transformed into a linear one that could be solved easily by mathematical programming software.Additionally, Crainic [47], Southworth and Peterson [48], Jansen et al. [49], and Yaghini and Akhavan [50] separately conducted systematic reviews of the service network design problem. All these reviews introduced this problem comprehensively from the perspectives of research content, current progress, model formulation, algorithm development, and research prospects, thus contributing to making the general research architecture more mature and ideal. Furthermore, to enhance the effectiveness of solving the network design problem, many studies discussed the solution approaches for the network design problem in detail, and a large number of solution approaches with high feasibility have been proposed, for example, a dual-ascent method by Balakrishnan et al. [51], a Lagrangian heuristic-based branch-and-bound approach by Holmberg and Yuan [52], a first multilevel cooperative tabu search algorithm by Crainic et al. [53], and a multiple choice 0-1 reformation and column-and-row generation method by Frangioni and Gendron [54]. All the studies discussed above significantly advanced the knowledge of the multicommodity multimodal transportation network design problem.Although similarities between the two types of problems are obvious, there are still three remarkable differences between them. Considering these differences helps to define obvious distinctions between the two types of problems in terms of model formulation.(1) In addition to the question of route selection, the network design problem also needs to solve the allocation of limited transportation resources to the network, that is, to determine the number of facilities or capacities of transportation services that should be installed on the routes, or the levels of transportation services that should be offered on the routes [47]. By contrast, the freight routing problem is based on an existing multimodal transportation network whose transportation resources have already been allocated, and it only focuses on planning origin-to-destination routes by selecting proper terminals and transportation services connecting them.(2) The network design problem is a form of tactical planning. The due dates of the commodities are usually not considered in this problem. By contrast, the freight routing problem is a part of the operational planning and must assign great importance to customer demands. The due dates of the commodities must be formulated as a constraint to satisfy the customer demands regarding timeliness.(3) In the network design problem, the detailed schedules of transportation services are rarely formulated by the researchers. However, in the freight routing problem, when utilizing schedule-based services to move commodities, the schedules must be followed strictly to guarantee the feasibility of routing in empirical cases. Consideration of service schedules improves the complexity of the freight routing problem in the multimodal transportation network.


## 1.5. Organization of the Rest of the Sections

All the studies reviewed above, regardless of the problem (freight routing problem or freight network design problem) they addressed, laid a solid foundation for our study with regard to the model formulation and algorithm design. The remaining sections of our study are organized as follows.In Section2, we first give a detailed introduction to multiple transportation services in the multimodal transportation network, including schedule-based rail services and the time-flexible road services. We then analyze the various transshipment manners that are available in the network. All this background information is considered in formulating the model. In Section 3, we define the multicommodity multimodal transportation routing problem from the perspectives of capacity constraint and time sensitivity, and we present an example containing a single-commodity flow to illustrate the selection of time-sensitive multimodal transportation routes. In Section 4, we establish an arc-node-based mixed integer nonlinear programming model to formulate the specific freight routing problem that we explore in this study. The proposed optimization model integrates the various formulation characteristics mentioned in the abstract. Then, we develop a linearization method to linearize the proposed model to make it easily solvable by mathematical programming software. In Section 5, a computational example from the Chinese inland container export business is presented to demonstrate the feasibility of the proposed model and the use of the linearization method to address the practical problem. Finally, the conclusions of this study are presented in Section 6.


## 2. Multiple Transportation Service Modes and Transshipments

### 2.1. Schedule-Based and Time-Flexible Services

Rail services in the transportation network are controlled by a central authority in China. The rail services are scheduled in advance under macroscopic control. The freight trains are operated through the multimodal transportation network strictly according to the rail service schedules/timetables. A typical rail service diagram is shown in Figure1. Some rail services show periodicity in their operating frequencies within the planning horizon. For the convenience of modeling, we consider the same rail services viewed in different operating periods as different services.Figure 1
Diagram of rail services between two terminals.The following components of a rail service are regulated by its schedule to control the operations of a train:(1)
Route, including the operation direction of the train and its terminal sequence.
(2)
Arrival times of the train at the terminals on the route and its departure times from them.
(3)
Service time windows of the train at the terminals on the route. Each service time window is a closed interval from operation (loading/unloading) start time to operation cutoff time.
(4)
Carrying capacity of the train.Accordingly, the operations of commodities at terminals are a process with the following characteristics:(1)
The commodity cannot be unloaded from the train at a terminal until the rail service reaches its operation start time.
(2)
Once the operation cutoff time is reached, the rail service will stop operating immediately.
(3)
After being loaded on board, the commodity will depart from the terminal at the scheduled departure time of the rail service.
(4)
If the commodity arrives at the terminal and completes the unloading operation earlier than the operation start time of the rail service, it must wait until the operation start time. In this case, the commodity needs to occupy a freight yard or warehouse to be stored. Hence, its inventory costs are created according to the charged inventory time.The commodity must observe the following two rules to be able to use a rail service at a terminal:(1)
The capacity of the service at the terminal must admit its volume.
(2)
Its loading completion time on the train should not be later than the operation cutoff time of the rail service at the terminal.In this study, we specifically focus on freight routing in the multimodal truck-rail transportation network where all the commodities are carried in containers. In China, to allow a rapid development of container transportation, block container trains are extensively operated in the rail service network and have gradually become the backbone of rail container transportation. For this reason, the rail service addressed in this study is the block container train service. Although block container train service is a component of schedule-based rail service, its operation differs from that of the common rail service shown in Figure 1. Compared with the common rail service, the block container train is a point-to-point rail service (see in Figure 2), and it conducts loading and unloading operations separately at its loading organization terminals and unloading organization terminals on the route. Intermediate terminals along the route where loading and unloading operations are not undertaken can be regarded as invalid terminals in the routing and can be removed from the multimodal transportation network topology. Apart from the difference cited above, the operation of block container train is identical to the common rail service. The utilization of block container trains in the routing should also observe the rules above. Many block container trains have multiple loading/unloading organization terminals. For convenience, we further classify the same block container train into different train units according to its loading/unloading organization terminals; that is, if a block container train has n origin terminals and m destination terminals, it will be considered as n
×
m a different block container train.Figure 2
Operation of a block container train.The outstanding advantage of road services is their high flexibility due to the rapid travel speeds of the trucks and wide distribution and high density of the road service network. Compared with rail services, road services have much less control over their operations, and the trucks can travel feasibly over the road service network. Moreover, it is easy to assign adequate numbers of trucks to the terminals to carry the commodities. Hence, we consider that road services are uncapacitated in the multimodal transportation network. Road services are not scheduled, and their unloading and loading operations are not restricted in time. A commodity can start to be loaded on trucks immediately upon arrival at a terminal, and trucks can depart from the terminals once the loading is completed. There are mainly three types of road services in a multimodal transportation network, including pickup and delivery services, rail terminal connecting service, and direct origin-destination road service, as indicated by Figure3.Figure 3
Road services in the multimodal transportation network.When moving a commodity from one terminal (e.g., terminalh in Figure 4) to another one (terminal k) by road service, one or more intermediate terminals (terminal i and terminal j) may be visited along the road service route. There is no need to transship commodities at the intermediate terminals, because the extra transshipments not only delay the delivery of the commodities but also increase the transportation costs. Therefore, commodities can be moved directly among the intermediate terminal. To facilitate modeling, we split every road service along a route from origin to destination into several segments (e.g., in Figure 4, road service h
,
k is split into 6 segments, including h
,
i, h
,
j, h
,
k, i
,
j, i
,
k, and j
,
k) and consider that two conjoint segments (e.g., i
,
j and j
,
k in Figure 4) cannot be covered in a commodity flow route simultaneously to avoid an extra transshipment.Figure 4
An example of road services along a route.


### 2.2. Transshipments between Multiple Transportation Services

The transshipments that consider schedules in the multimodal transportation network can be divided into three categories: “road service→ rail service,” “rail service → another rail service,” and “rail service → road service.” However, there is no “road service → road service” transshipment, because we view road service as a type of time-flexible service mode and trucks can travel feasibly trough the road service network; the “road service → road service” transshipment is extra.The transshipment from road service to rail service and that between different rail services have similar processes, which are illustrated by Figures5 and 6, respectively. For the two figures, the representations of time parameters are shown in Table 1.Table 1
Symbols in Figures5 and 6 and their representations.
Symbol
Representation
t
1
Departure time of road service from terminalh (Figure 5); scheduled departure time of rail service s from terminal h (Figure 6).
t
2
Arrival time of road service at terminali (Figure 5); scheduled arrival time of rail service r at terminal i (Figure 6).
t
′
Scheduled operation start time of rail servicer (Figure 6).
t
3
Completion time of unloading commodity from the trucks (road service) at terminali (Figure 5); completion time of unloading commodity from the train (rail service r) at terminal i (Figure 6).
t
4
Scheduled operation start time of rail services at terminal i.
t
5
Completion time of loading commodity on the train (rail services) at terminal i.
t
6
Scheduled departure time of rail services from terminal i.
t
7
Scheduled arrival time of rail services at terminal j.
Δ
t
34
Waiting time for loading at terminali, Δ
t
34
=
m
a
x
0
,
t
4
-
t
3.Figure 5
Transshipment from road service to rail service.Figure 6
Transshipment between different rail services.As shown in Figures5 and 6, the main difference between the two transshipments is that the transshipment between different rail services has an additional unloading waiting process: the commodity should wait until the operation start time of the predecessor rail service before being unloaded. Compared with the two transshipments above, the process of transshipping a commodity from a rail service to a road service is much simpler, as can be observed in Figure 7. Representations of the time parameters in Figure 7 are given in Table 2.Table 2
Symbols in Figure7 and their representations.
Symbol
Representation
t
1
Scheduled departure time of rail services from terminal h.
t
2
Scheduled arrival time of rail services at terminal i.
t
3
Scheduled operation start time of rail services at terminal i.
t
4
Completion time of unloading commodity from the train (rail services) at terminal i.
t
5
Completion time of loading commodity on the trucks (road service) at terminali.
t
6
Arrival time of road service at terminalj.Figure 7
Transshipment from rail service to road service.Note that due to the highly mechanized operation of the block container trains at the terminals, the times of loading/unloading commodities on/from the trains can be negligible, as can be the times of loading/unloading commodities on/from the trucks. For the sake of generalization, we still consider these times in Figures5, 6, and 7, but we will neglect these loading/unloading times in the following problem description and model formulation.


## 2.1. Schedule-Based and Time-Flexible Services

Rail services in the transportation network are controlled by a central authority in China. The rail services are scheduled in advance under macroscopic control. The freight trains are operated through the multimodal transportation network strictly according to the rail service schedules/timetables. A typical rail service diagram is shown in Figure1. Some rail services show periodicity in their operating frequencies within the planning horizon. For the convenience of modeling, we consider the same rail services viewed in different operating periods as different services.Figure 1
Diagram of rail services between two terminals.The following components of a rail service are regulated by its schedule to control the operations of a train:(1)
Route, including the operation direction of the train and its terminal sequence.
(2)
Arrival times of the train at the terminals on the route and its departure times from them.
(3)
Service time windows of the train at the terminals on the route. Each service time window is a closed interval from operation (loading/unloading) start time to operation cutoff time.
(4)
Carrying capacity of the train.Accordingly, the operations of commodities at terminals are a process with the following characteristics:(1)
The commodity cannot be unloaded from the train at a terminal until the rail service reaches its operation start time.
(2)
Once the operation cutoff time is reached, the rail service will stop operating immediately.
(3)
After being loaded on board, the commodity will depart from the terminal at the scheduled departure time of the rail service.
(4)
If the commodity arrives at the terminal and completes the unloading operation earlier than the operation start time of the rail service, it must wait until the operation start time. In this case, the commodity needs to occupy a freight yard or warehouse to be stored. Hence, its inventory costs are created according to the charged inventory time.The commodity must observe the following two rules to be able to use a rail service at a terminal:(1)
The capacity of the service at the terminal must admit its volume.
(2)
Its loading completion time on the train should not be later than the operation cutoff time of the rail service at the terminal.In this study, we specifically focus on freight routing in the multimodal truck-rail transportation network where all the commodities are carried in containers. In China, to allow a rapid development of container transportation, block container trains are extensively operated in the rail service network and have gradually become the backbone of rail container transportation. For this reason, the rail service addressed in this study is the block container train service. Although block container train service is a component of schedule-based rail service, its operation differs from that of the common rail service shown in Figure 1. Compared with the common rail service, the block container train is a point-to-point rail service (see in Figure 2), and it conducts loading and unloading operations separately at its loading organization terminals and unloading organization terminals on the route. Intermediate terminals along the route where loading and unloading operations are not undertaken can be regarded as invalid terminals in the routing and can be removed from the multimodal transportation network topology. Apart from the difference cited above, the operation of block container train is identical to the common rail service. The utilization of block container trains in the routing should also observe the rules above. Many block container trains have multiple loading/unloading organization terminals. For convenience, we further classify the same block container train into different train units according to its loading/unloading organization terminals; that is, if a block container train has n origin terminals and m destination terminals, it will be considered as n
×
m a different block container train.Figure 2
Operation of a block container train.The outstanding advantage of road services is their high flexibility due to the rapid travel speeds of the trucks and wide distribution and high density of the road service network. Compared with rail services, road services have much less control over their operations, and the trucks can travel feasibly over the road service network. Moreover, it is easy to assign adequate numbers of trucks to the terminals to carry the commodities. Hence, we consider that road services are uncapacitated in the multimodal transportation network. Road services are not scheduled, and their unloading and loading operations are not restricted in time. A commodity can start to be loaded on trucks immediately upon arrival at a terminal, and trucks can depart from the terminals once the loading is completed. There are mainly three types of road services in a multimodal transportation network, including pickup and delivery services, rail terminal connecting service, and direct origin-destination road service, as indicated by Figure3.Figure 3
Road services in the multimodal transportation network.When moving a commodity from one terminal (e.g., terminalh in Figure 4) to another one (terminal k) by road service, one or more intermediate terminals (terminal i and terminal j) may be visited along the road service route. There is no need to transship commodities at the intermediate terminals, because the extra transshipments not only delay the delivery of the commodities but also increase the transportation costs. Therefore, commodities can be moved directly among the intermediate terminal. To facilitate modeling, we split every road service along a route from origin to destination into several segments (e.g., in Figure 4, road service h
,
k is split into 6 segments, including h
,
i, h
,
j, h
,
k, i
,
j, i
,
k, and j
,
k) and consider that two conjoint segments (e.g., i
,
j and j
,
k in Figure 4) cannot be covered in a commodity flow route simultaneously to avoid an extra transshipment.Figure 4
An example of road services along a route.


## 2.2. Transshipments between Multiple Transportation Services

The transshipments that consider schedules in the multimodal transportation network can be divided into three categories: “road service→ rail service,” “rail service → another rail service,” and “rail service → road service.” However, there is no “road service → road service” transshipment, because we view road service as a type of time-flexible service mode and trucks can travel feasibly trough the road service network; the “road service → road service” transshipment is extra.The transshipment from road service to rail service and that between different rail services have similar processes, which are illustrated by Figures5 and 6, respectively. For the two figures, the representations of time parameters are shown in Table 1.Table 1
Symbols in Figures5 and 6 and their representations.
Symbol
Representation
t
1
Departure time of road service from terminalh (Figure 5); scheduled departure time of rail service s from terminal h (Figure 6).
t
2
Arrival time of road service at terminali (Figure 5); scheduled arrival time of rail service r at terminal i (Figure 6).
t
′
Scheduled operation start time of rail servicer (Figure 6).
t
3
Completion time of unloading commodity from the trucks (road service) at terminali (Figure 5); completion time of unloading commodity from the train (rail service r) at terminal i (Figure 6).
t
4
Scheduled operation start time of rail services at terminal i.
t
5
Completion time of loading commodity on the train (rail services) at terminal i.
t
6
Scheduled departure time of rail services from terminal i.
t
7
Scheduled arrival time of rail services at terminal j.
Δ
t
34
Waiting time for loading at terminali, Δ
t
34
=
m
a
x
0
,
t
4
-
t
3.Figure 5
Transshipment from road service to rail service.Figure 6
Transshipment between different rail services.As shown in Figures5 and 6, the main difference between the two transshipments is that the transshipment between different rail services has an additional unloading waiting process: the commodity should wait until the operation start time of the predecessor rail service before being unloaded. Compared with the two transshipments above, the process of transshipping a commodity from a rail service to a road service is much simpler, as can be observed in Figure 7. Representations of the time parameters in Figure 7 are given in Table 2.Table 2
Symbols in Figure7 and their representations.
Symbol
Representation
t
1
Scheduled departure time of rail services from terminal h.
t
2
Scheduled arrival time of rail services at terminal i.
t
3
Scheduled operation start time of rail services at terminal i.
t
4
Completion time of unloading commodity from the train (rail services) at terminal i.
t
5
Completion time of loading commodity on the trucks (road service) at terminali.
t
6
Arrival time of road service at terminalj.Figure 7
Transshipment from rail service to road service.Note that due to the highly mechanized operation of the block container trains at the terminals, the times of loading/unloading commodities on/from the trains can be negligible, as can be the times of loading/unloading commodities on/from the trucks. For the sake of generalization, we still consider these times in Figures5, 6, and 7, but we will neglect these loading/unloading times in the following problem description and model formulation.


## 3. Problem Description

As asserted in Section1, the multicommodity multimodal transportation routing problem aims at selecting minimal generalized costs routes to move multiple commodities from their origins to their destinations via capacitated schedule-based rail services and uncapacitated time-flexible road services. A route can be created by a single road service, a single rail service with necessary additional pickup and delivery services, or various truck-rail combinations. Because the carrying capacities of the block container trains are limited, the routing problem in this study is a capacitated one. The commodities that are loaded on a block container train at its loading organization terminal should not exceed its carrying capacity.The routing problem in this study is a time-sensitive one that is constrained by the transportation due dates of the multiple commodities and the schedules of the rail services. The selected routes, therefore, must be time feasible from two aspects. The first time feasibility is that the arrival time of each commodity at the destination along the route should not be later than its transportation due date. Second, if the commodity needs to be moved from the current terminal to the successor terminal by rail service, the loading completion time of the commodity on the train at the current terminal should not be later than the operation cutoff time of the rail service.Here, we give an example of a single-commodity flow in Figure8 to illustrate the time-sensitive routing problem. Figure 8 shows a directed multimodal transportation network containing seven terminals (1,2
,
…
,
7, where 1 and 7 represent the origin and destination, resp.) and seven block container train services (R
1
,
…
,
R
7). The release time of the commodity at the origin is 10 o’clock on the first day (shown as 10), and its due date at the destination is 22 o’clock on the second day (shown as 22
+
24
=
46). In Figure 8, the rail services are represented by solid lines, and the road services are represented by dashed lines. The travel times of road services on different arcs are given beside the dashed lines (unit: h). For the rail services, we sequentially give the operation start time, operation cutoff time, and departure time of each block container train at and from the loading organization terminal and the arrival time and operation start time at the unloading organization terminal. In Figure 8, all the time parameters are converted into natural numbers (e.g., 10:30 is converted into 10.5), and a time that exceeds 24 corresponds to the second day (24:00 to 48:00).Figure 8
A multimodal transportation network example.In the example in Figure8, there are, overall, 18 routes to route the commodity flow from terminal 1 to terminal 7. However, only the 9 following routes are time feasible:(1)
Depart from terminal 1 by road service at 10 and arrive at terminal 2 at 14; complete unloading from trucks at 14 (loading/unloading times at the terminals are neglected here and below), wait until 25, and complete loading onR
4 at 25; depart from terminal 2 by R
4 at 27.5 and arrive at terminal 5 at 35.5; complete unloading from R
4 and loading on R
5 at 36; depart from terminal 5 by R
5 at 38.5 and finally arrive at terminal 7 at 44.5.
(2)
Complete loading onR
1 at 11; depart from terminal 1 by R
1 at 13.25 and arrive at terminal 2 at 18; complete unloading from R
1 at 18.5, wait until 25, and complete loading on R
4 at 25; depart from terminal 2 by R
4 at 27.5 and arrive at terminal 5 at 35.5; complete unloading from R
4 and loading on R
5 at 36; depart from terminal 5 by R
5 at 38.5 and finally arrive at terminal 7 at 44.5.
(3)
Depart from terminal 1 by road service at 10 and arrive at terminal 2 at 14; complete unloading from trucks and loading onR
3 at 14; depart from terminal 2 by R
3 at 16 and arrive at terminal 4 at 24; complete unloading from R
3 and loading on trucks at 25; depart from terminal 4 by road service at 25, visit terminal 6 without transshipment, and finally arrive at terminal 7 at 40.
(4)
Depart from terminal 1 by road service at 10 and arrive at terminal 2 at 14; complete unloading from trucks at 14, wait until 25, and complete loading onR
4 at 25; depart from terminal 2 by R
4 at 27.5 and arrive at terminal 5 at 35.5; complete unloading from R
4 and loading on R
5 at 36; depart from terminal 5 by R
4 at 38.5 and finally arrive at terminal 7 at 44.5.
(5)
Depart from terminal 1 by road service at 10, visit terminals 4 and 6 without transshipment, and finally arrive at terminal 7 at 35.
(6)
Depart from terminal 1 by road service at 10 and arrive at terminal 4 at 20; complete unloading from trucks at 20, wait until 27, and complete loading onR
6 at 27; depart from terminal 4 by R
6 at 32 and finally arrive at terminal 7 at 43.
(7)
Depart from terminal 1 by road service at 10, visit terminal 4 without transshipment, and arrive at terminal 5 at 25; complete unloading from trucks at 25, wait until 33, and complete loading onR
5 at 33; depart from terminal 5 by R
5 at 38.5 and finally arrive at terminal 7 at 44.5.
(8)
Depart from terminal 1 by road service at 10 and arrive at terminal 3 at 16; complete unloading from trucks at 16, wait until 19, and then complete loading onR
2 at 19; depart from terminal 3 by R
2 at 22.25 and arrive at terminal 6 at 28; complete unloading from R
2 and loading on trucks at 28.5; depart from terminal 6 by road service at 18.5 and finally arrive at terminal 7 at 35.5.
(9)
Depart from terminal 1 by road service at 10, visit terminals 3 and 6 without transshipment, and finally arrive at terminal 7 at 31.


## 4. Model Formulation and Linearization

### 4.1. Estimation of Carbon Dioxide Emissions

In 2012, to control greenhouse gas emissions, the National Development and Reform Commission of China proposed the development of relevant pilot projects on trading carbon emissions rights. Thus, the transportation industry may be charged for carbon dioxide emissions in the future to reduce their emissions and promote the development of ecofriendly freight transportation [55]. To price the carbon dioxide emissions accurately, the first step is to estimate the volume of carbon dioxide emissions when multimodal transportation is adopted to move commodities.Carbon dioxide emitted en route during the transportation represents the majority of total carbon dioxide emissions. By contrast, the carbon dioxide emitted by the operations at the terminals is negligible. In this study, we consider the former emissions when estimating the carbon dioxide emitted by the transportation of commodities. Generally, there are two primary methods that can be used to estimate the carbon dioxide emitted in the transportation process, that is, energy-based method and activity-based method [46]. The activity-based method has been developed more extensively and has been widely used in many studies, for example, Liao et al. [7], Chang et al. [40], and Qu et al. [46], which in turn demonstrate its feasibility. For this reason, we adopt the activity-based method to estimate carbon dioxide emissions in this study.The activity-based method calculates the carbon dioxide emissions of a transportation services as η
s
×
Q
×
L where η
s is the emission factor for carbon dioxide of service s (unit: g/TEU-km), Q is the volume of the commodity that must be moved (unit: TEU), and L is the transportation distance (unit: km). Different types of transportation services have different carbon dioxide emission factor. According to the data from Winebrake et al.’s study [24] (unit: g/TEU-mi), the carbon dioxide emissions factors of rail services and road services are set to 125 g/TEU-km and 626 g/TEU-km, respectively.


### 4.2. Notations

In this study, we useG
=
N
,
A
,
S to represent a multimodal transportation network, where N, A, and S are the terminal set, the directed arc set, and transportation service set in the network, respectively. Let K denotes the set of the commodities that need to be moved through the network. For a certain commodity k
∈
K, its origin o
k, destination d
k, release time at origin t
r
e
l
e
a
s
e
k, due date T
k, and the volume q
k (unit: TEU) demanded by the shipper are all known. The rest of the symbols in the optimization model and their representations are listed shown in Table 3.Table 3
Symbols in the optimization model and their representations.
Indices
Representation
h
,
i
,
j
Index of the terminals, andh
,
i
,
j
∈
N.
s
,
r
Index of the transportation service, ands
,
r
∈
S.
(i
,
j)
Directed arc from terminali to terminal j, and (
i
,
j
)
∈
A.
Sets
Representation
Γ
i
j
Set of rail services onarc
⁡
(
i
,
j
), and Γ
i
j
⊆
S.
Ω
i
j
Set of road services onarc
⁡
(
i
,
j
), and Ω
i
j
⊆
S.
S
i
j
Set of the transportation services onarc
⁡
(
i
,
j
), S
i
j
=
Γ
i
j
∪
Ω
i
j, and S
i
j
⊆
S.
δ
-
i
Set of the predecessor terminals to terminali, and δ
-
i
⊆
N.
δ
+
i
Set of the successor terminals to terminali, and δ
+
i
⊆
N.
Parameters
Representation
l
i
s
Operation start time of rail services at terminal i.
u
i
s
Operation cutoff time of rail services at terminal i.
S
A
i
s
Scheduled arrival time of rail services at terminal i.
S
D
i
s
Scheduled departure time of services from terminal i.
Q
i
j
s
Available capacity of rail services at terminal i when being operated on arc
⁡
(
i
,
j
), unit: TEU.
d
i
j
s
Transportation distance of services on arc
⁡
(
i
,
j
), unit: km.
t
i
j
s
Transportation time of services on arc
⁡
(
i
,
j
), unit: h.
C
i
j
s
k
Transportation costs of moving commodityk on arc
⁡
(
i
,
j
) by service s, unit: ¥.
c
s
Unit costs of loading/unloading operation of services, unit: ¥/TEU.
c
s
t
o
r
e
Unit inventory costs of rail service, unit: ¥/TEU-h.
c
p
i
c
k
Additional charges for picking up the unit commodity from shipper at a rail terminal by rail service at origin, unit: ¥/TEU.
c
d
e
l
i
v
e
r
Additional charges for delivering the unit commodity from rail terminal to receiver by rail service at destination, unit: ¥/TEU.
φ
k
A parameter indicating whether origin pickup service is needed for commodityk. If the service is needed, φ
k
=
1; otherwise, φ
k
=
0.
μ
k
A parameter indicating whether destination delivery service is needed for commodityk. If the service is needed, μ
k
=
1; otherwise, μ
k
=
0.
c
c
o
2
Unit carbon dioxide emissions costs, unit: ¥/g.
η
s
Emission factor for carbon dioxide of services, unit: g/TEU-km.
M
A large positive number.
Decision variables
Representation
X
i
j
s
k
0-1 decision variable. If commodityk is moved from terminal i to terminal j by service s, X
i
j
s
k
=
1; otherwise, X
i
j
s
k
=
0.
Y
i
k
Arrival time of commodityk at terminal i.
Z
i
j
s
k
Charged inventory time of commodityk at terminal i before being moved on arc
⁡
(
i
,
j
) by rail service s, unit: h.


### 4.3. Node-Arc-Based Mixed Integer Nonlinear Programming Model

Using the symbols above, we propose the following node-arc-based mixed integer nonlinear programming model to describe the capacitated time-sensitive multicommodity multimodal generalized shortest path problem.(i) Mixed Integer Nonlinear Programming ModelObjective Function.We have the following:(1)
minimize
∑
k
∈
K
∑
i
,
j
∈
A
∑
s
∈
S
i
j
C
i
j
s
k
·
X
i
j
s
k
(2)
+
∑
k
∈
K
∑
i
∈
N
∑
h
∈
δ
-
i
∑
r
∈
S
h
i
c
r
·
q
k
·
X
h
i
r
k
+
∑
j
∈
δ
+
i
∑
s
∈
S
i
j
c
s
·
q
k
·
X
i
j
s
k
(3)
+
∑
k
∈
K
∑
i
,
j
∈
A
∑
s
∈
Γ
i
j
c
s
t
o
r
e
·
q
k
·
Z
i
j
s
k
(4)
+
∑
k
∈
K
φ
k
·
∑
j
∈
δ
+
o
k
∑
s
∈
Γ
o
k
j
c
p
i
c
k
·
q
k
·
X
o
k
j
s
k
+
∑
k
∈
K
μ
k
·
∑
i
∈
δ
-
d
k
∑
s
∈
Γ
i
d
k
c
d
e
l
i
v
e
r
·
q
k
·
X
i
d
k
s
k
(5)
+
∑
k
∈
K
∑
i
,
j
∈
A
∑
s
∈
S
i
j
c
c
o
2
·
η
s
·
q
k
·
d
i
j
s
·
X
i
j
s
k
.In this formulation, the objective function is to minimize the total generalized costs of moving multiple commodities through the multimodal transportation network. The generalized costs are the linear summation of Components (1)–(5), where Components (1)–(5) are the transportation costs en route, loading and unloading operation costs at terminals, inventory costs at terminals, additional origin picking up service costs and destination delivery costs, and carbon dioxide emissions costs, respectively:(6)
Subject  to
∑
j
∈
δ
+
i
∑
s
∈
S
i
j
X
i
j
s
k
-
∑
h
∈
δ
-
i
∑
r
∈
S
h
i
X
h
i
r
k
=
1
i
=
o
k
0
∀
i
∈
N
∖
o
k
,
d
k
-
1
i
=
d
k
∀
k
∈
K
,
∀
i
∈
N
(7)
∑
s
∈
S
i
j
X
i
j
s
k
≤
1
∀
k
∈
K
,
∀
i
,
j
∈
A
.Constraint (6) is the general commodity flow conservation constraint. Constraint (7) ensures that only one transportation service can be adopted to move a specific commodity on one arc. The combination of the two constraints ensures that each commodity is unsplittable/nonbifurcated and follows exactly one route from its origin terminal to its destination terminal through the multimodal transportation network [54, 56]:(8)
X
h
i
r
k
+
X
i
j
s
k
≤
1
∀
k
∈
K
,
∀
i
∈
N
,
∀
h
∈
δ
-
i
,
∀
j
∈
δ
+
i
,
∀
s
∈
Ω
i
j
,
∀
r
∈
Ω
h
i
.Constraint (8) ensures that the two conjoint segments of a road service route cannot be covered in a route simultaneously to avoid an extra transshipment at the terminals; that is, if commodity k plans to be moved from terminal h to terminal j via terminal i by road service, it should directly use the equivalent segment h
,
j that is generated in the multimodal transportation network based on the road service route deformation illustrated by Figure 4. For more details, we can refer to the statement in Section 2.1:(9)
∑
k
∈
K
q
k
·
X
i
j
s
k
≤
Q
i
j
s
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
.Constraint (9) is the rail service carrying capacity constraint. It ensures that the total volume of commodities loaded on the block container trains at the origin terminals will not exceed their available carrying capacities at the same terminals:(10)
Y
o
k
k
=
t
r
e
l
e
a
s
e
k
∀
k
∈
K
.Constraint (10) means that the arrival time of each commodity at the origin equals its release time at the origin:(11)
max
⁡
Y
i
k
,
S
D
i
s
+
t
i
j
s
-
Y
j
k
·
X
i
j
s
k
=
0
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
S
i
j
.Constraint (11) reflects the relationship between the arrival time variables and the commodity flow variables. It also successively computes the arrival times of each commodity at all the terminals that are covered in their transportation routes. For s
∈
Ω
i
j, there exists no scheduled departure time, and S
D
i
s is therefore set to 0 in this study. For s
∈
Γ
i
j, we are far more concerned about its operation start time at terminal j than about its arrival time at the same terminal, because when the commodity k arrives at terminal j, it will not be unloaded until l
j
s. Therefore, we consider l
j
s to be the valid arrival time of commodity k at terminal j when moved by rail service s on arc i
,
j. Hence, Y
j
k equals l
j
s instead of S
A
i
s and, consequently, in this case, t
i
j
s
=
l
j
s
-
S
D
i
s:(12)
Y
i
k
≤
u
i
s
·
X
i
j
s
k
+
M
·
1
-
X
i
j
s
k
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
.Constraint (12) is the operation service time constraint. It means that when adopting rail service, the arrival time of the commodity at the terminal should not be later than the operation cutoff time of the service. For this equation, if X
i
j
s
k
=
0, then Y
i
k
≤
M. This inequality is always satisfied, that is, the arrival time of the commodity at the terminal is not constrained by the operation cutoff time of a rail service that is not adopted in the routing:(13)
Y
d
k
k
≤
T
k
∀
k
∈
K
.Constraint (13) is the due date constraint. It ensures that the arrival time of each commodity at the destination does not exceed its claimed due date:(14)
m
a
x
0
,
l
i
s
-
Y
i
k
-
π
-
Z
i
j
s
k
·
X
i
j
s
k
=
0
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
.Constraint (14) indicates the relationship between the charged inventory time variables and the commodity flow variables. It also computes the charged inventory times of each commodity at all the origin terminals of the rail services that are adopted in their transportation routes. The inventory is needed only if the arrival times of the commodity at the terminals are earlier than the operation start times of the rail services at the same terminals. There also exists a period of inventory free of charge denoted by π (unit: h), such that if the inventory time of the commodity at a terminal is shorter than π, no inventory costs will be charged. For road services, there is no inventory at the terminals:(15)
C
i
j
s
k
=
c
r
a
i
l
1
+
c
r
a
i
l
2
·
d
i
j
s
·
q
k
s
∈
Γ
i
j
c
r
o
a
d
2
·
q
k
·
d
i
j
s
s
∈
Ω
i
j
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
S
i
j
.Constraint (15) computes the costs of operating services on the arcs according to the regulations proposed by the China Ministry of Railways and Ministry of Transport. In this equation, c
r
a
i
l
1 are the cost parameters related to the volume of the commodities (unit: ¥/TEU), while c
r
a
i
l
2 and c
r
o
a
d
2 are the cost parameters related to the turnover of commodities (unit: ¥/TEU-km). The values of the above parameters are regulated by the two ministries:(16)
X
i
j
s
k
∈
0,1
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
S
i
j
,
(17)
Y
i
k
≥
0
∀
k
∈
K
,
∀
i
∈
N
,
(18)
Z
i
j
s
k
≥
0
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
.Constraints (16)–(18) are the variable domain constraints.


### 4.4. Model Linearization

The proposed model above is a typical nonlinear programming formulation. When using the standard mathematical programming software to solve this problem directly, the computational results will represent local optimum, and much computational time will also be consumed; that is, the quality of the solutions and the solving efficiency will both be lowered due to the nonlinearity of the proposed model.The nonlinearity of the model is caused by Constraints (11) and (14), which include a nonlinear function (max
⁡
· function) and multiplications of different variables. Thus, to make the proposed model easily solvable by mathematical programming software, we linearize the two nonlinear constraints to transform the proposed model into a mixed integer linear programming formulation according to the following two propositions.Proposition 1.
Nonlinear constraintmax
⁡
Y
i
k
,
S
D
i
s
+
t
i
j
s
-
Y
j
k
·
X
i
j
s
k
=
0  ∀
k
∈
K, ∀
i
,
j
∈
A, and ∀
s
∈
S
i
j can be linearized by using the following four constraints:(19)
S
D
i
s
+
t
i
j
s
-
Y
j
k
≥
M
·
X
i
j
s
k
-
1
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
,
(20)
S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
M
·
1
-
X
i
j
s
k
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
,
(21)
Y
i
k
+
t
i
j
s
-
Y
j
k
≥
M
·
X
i
j
s
k
-
1
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Ω
i
j
,
(22)
Y
i
k
+
t
i
j
s
-
Y
j
k
≤
M
·
1
-
X
i
j
s
k
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Ω
i
j
.Proof.
Constraints (19) and (20) and Constraints (21) and (22) correspond separately to two independent but similar scenarios. Here, we only address Scenario 1. Scenario 1 contains two independent subscenarios: Scenarios 1.1 and 1.2.
Scenario
1. For rail service s on arc i
,
j, we have the following.
Scenario
1.1. If it is used to move commodity k, then X
i
j
s
k
=
1, and according to Constraint (11), S
D
i
s
+
t
i
j
s
-
Y
j
k
=
0. In this scenario, Constraints (19) and (20) equal S
D
i
s
+
t
i
j
s
-
Y
j
k
≥
0 and S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
0, respectively. Hence, the following deductive process exists. The deductive result ensures the existing equation relationship between S
D
i
s and Y
j
k: (23)
S
D
i
s
+
t
i
j
s
-
Y
j
k
≥
0
S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
0
⟹
0
≤
S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
0
⟹
Y
j
k
=
S
D
i
s
+
t
i
j
s
.
Scenario
1.2. Otherwise, X
i
j
s
k
=
0, and according to Constraint (11), S
D
i
s and Y
j
k are not related to each other. In this scenario, Constraints (19) and (20) equal S
D
i
s
+
t
i
j
s
-
Y
j
k
≥
-
M and S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
M, respectively. Therefore, the following deductive process exists. The deductive result ensures that there is no relationship between S
D
i
s and Y
j
k:(24)
S
D
i
s
+
t
i
j
s
-
Y
j
k
≥
-
M
S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
M
⟹
-
M
≤
S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
M
.Proposition 2.
Nonlinear constraintmax
⁡
0
,
l
i
s
-
Y
i
k
-
π
-
Z
i
j
s
k
·
X
i
j
s
k
=
0  ∀
k
∈
K, ∀
i
,
j
∈
A, and ∀
s
∈
Γ
i
j can be linearized by using the following two constraints: (25)
Z
i
j
s
k
≥
M
·
X
i
j
s
k
-
1
+
l
i
s
-
Y
i
k
-
π
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
,
(26)
Z
i
j
s
k
≤
M
·
X
i
j
s
k
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
.Proof.
We consider two independent Scenarios 1 and 2.
Scenario 1. When the commodity k is not moved from terminal i to terminal j by rail service s, then X
i
j
s
k
=
0, and according to Constraint (14), there is no charged inventory time for commodity k towards rail service s on a
r
c
i
,
j. In this scenario, because M is a large positive number, -
M
+
l
i
s
-
Y
i
k
-
π is equivalent to -
M. Consequently, Constraints (25) and (26) separately equal Z
i
j
s
k
≥
-
M and Z
i
j
s
k
≤
0. When combined with the nonnegative constraint of Z
i
j
s
k (Constraint (17)), the following deductive process exists. The deductive result ensures that there is no charged inventory time for commodity k toward rail service s on a
r
c
i
,
j in this scenario:(27)
Z
i
j
s
k
≥
-
M
Z
i
j
s
k
≤
0
Z
i
j
s
k
≥
0
⟹
0
≤
Z
i
j
s
k
≤
0
⟹
Z
i
j
s
k
=
0
.
Scenario
2. When commodity k is moved from terminal i to terminal j by rail service s, then X
i
j
s
k
=
1. This scenario contains two following independent subscenarios: Scenarios 2.1 and 2.2.
Scenario
2.1. If l
i
s
-
Y
i
k
-
π
≤
0, there is no charged inventory time for commodity k towards rail service s on a
r
c
i
,
j based on Constraint (14). In this scenario, Constraints (21) and (22) equal Z
i
j
s
k
≥
l
i
s
-
Y
i
k
-
π and Z
i
j
s
k
≤
M, respectively. Considering the nonnegative constraint of Z
i
j
s
k (Constraint (17)), the following deductive process exists, in which the control of the minimization of Component (3) in the objective function towards the deductive result in the first step will lead to the final deductive result. The deductive result ensures that when commodity k is moved on a
r
c
i
,
j by rail service s, as long as l
i
s
-
Y
i
k
-
π
≤
0, the charged inventory time will not be generated:(28)
Z
i
j
s
k
≥
l
i
s
-
Y
i
k
-
π
Z
i
j
s
k
≤
M
Z
i
j
s
k
≥
0
l
i
s
-
Y
i
k
-
π
≤
0
⟹
0
≤
Z
i
j
s
k
≤
M
⟹
Z
i
j
s
k
=
0
.
Scenario
2.2. If l
i
s
-
Y
i
k
-
π
>
0, the charged inventory time l
i
s
-
Y
i
k
-
π exists for commodity k toward rail service s on a
r
c
i
,
j based on Constraint (14). In this scenario, considering the nonnegative constraint of Z
i
j
s
k (Constraint (17)), the following deductive process exists, in which the control of the minimization of Component (3) in the objective function towards the deductive result in the first step will lead to the final deductive result. The deductive result ensures that when commodity k is moved on a
r
c
i
,
j by rail service s and l
i
s
-
Y
i
k
-
π
>
0, the charged inventory time will be l
i
s
-
Y
i
k
-
π:(29)
Z
i
j
s
k
≥
l
i
s
-
Y
i
k
-
π
Z
i
j
s
k
≤
M
Z
i
j
s
k
≥
0
l
i
s
-
Y
i
k
-
π
>
0
⟹
l
i
s
-
Y
i
k
-
π
≤
Z
i
j
s
k
≤
M
⟹
Z
i
j
s
k
=
l
i
s
-
Y
i
k
-
π
.The final model is now a mixed integer linear programming model as follows. It can be easily solved by any mathematical programming software, for example, Lingo, Cplex, or GAMS, to obtain the optimal solution to the capacitated time-sensitive multicommodity multimodal generalized shortest path problem in a specific case.
(ii) Mixed Integer Linear Programming Model
Objective Function.We have the following:(30)
minimize
1
+
2
+
3
+
4
+
5
Subject to. Constraints (6)–(10), (12), (13), and (15)–(22), (25), and (26).


## 4.1. Estimation of Carbon Dioxide Emissions

In 2012, to control greenhouse gas emissions, the National Development and Reform Commission of China proposed the development of relevant pilot projects on trading carbon emissions rights. Thus, the transportation industry may be charged for carbon dioxide emissions in the future to reduce their emissions and promote the development of ecofriendly freight transportation [55]. To price the carbon dioxide emissions accurately, the first step is to estimate the volume of carbon dioxide emissions when multimodal transportation is adopted to move commodities.Carbon dioxide emitted en route during the transportation represents the majority of total carbon dioxide emissions. By contrast, the carbon dioxide emitted by the operations at the terminals is negligible. In this study, we consider the former emissions when estimating the carbon dioxide emitted by the transportation of commodities. Generally, there are two primary methods that can be used to estimate the carbon dioxide emitted in the transportation process, that is, energy-based method and activity-based method [46]. The activity-based method has been developed more extensively and has been widely used in many studies, for example, Liao et al. [7], Chang et al. [40], and Qu et al. [46], which in turn demonstrate its feasibility. For this reason, we adopt the activity-based method to estimate carbon dioxide emissions in this study.The activity-based method calculates the carbon dioxide emissions of a transportation services as η
s
×
Q
×
L where η
s is the emission factor for carbon dioxide of service s (unit: g/TEU-km), Q is the volume of the commodity that must be moved (unit: TEU), and L is the transportation distance (unit: km). Different types of transportation services have different carbon dioxide emission factor. According to the data from Winebrake et al.’s study [24] (unit: g/TEU-mi), the carbon dioxide emissions factors of rail services and road services are set to 125 g/TEU-km and 626 g/TEU-km, respectively.


## 4.2. Notations

In this study, we useG
=
N
,
A
,
S to represent a multimodal transportation network, where N, A, and S are the terminal set, the directed arc set, and transportation service set in the network, respectively. Let K denotes the set of the commodities that need to be moved through the network. For a certain commodity k
∈
K, its origin o
k, destination d
k, release time at origin t
r
e
l
e
a
s
e
k, due date T
k, and the volume q
k (unit: TEU) demanded by the shipper are all known. The rest of the symbols in the optimization model and their representations are listed shown in Table 3.Table 3
Symbols in the optimization model and their representations.
Indices
Representation
h
,
i
,
j
Index of the terminals, andh
,
i
,
j
∈
N.
s
,
r
Index of the transportation service, ands
,
r
∈
S.
(i
,
j)
Directed arc from terminali to terminal j, and (
i
,
j
)
∈
A.
Sets
Representation
Γ
i
j
Set of rail services onarc
⁡
(
i
,
j
), and Γ
i
j
⊆
S.
Ω
i
j
Set of road services onarc
⁡
(
i
,
j
), and Ω
i
j
⊆
S.
S
i
j
Set of the transportation services onarc
⁡
(
i
,
j
), S
i
j
=
Γ
i
j
∪
Ω
i
j, and S
i
j
⊆
S.
δ
-
i
Set of the predecessor terminals to terminali, and δ
-
i
⊆
N.
δ
+
i
Set of the successor terminals to terminali, and δ
+
i
⊆
N.
Parameters
Representation
l
i
s
Operation start time of rail services at terminal i.
u
i
s
Operation cutoff time of rail services at terminal i.
S
A
i
s
Scheduled arrival time of rail services at terminal i.
S
D
i
s
Scheduled departure time of services from terminal i.
Q
i
j
s
Available capacity of rail services at terminal i when being operated on arc
⁡
(
i
,
j
), unit: TEU.
d
i
j
s
Transportation distance of services on arc
⁡
(
i
,
j
), unit: km.
t
i
j
s
Transportation time of services on arc
⁡
(
i
,
j
), unit: h.
C
i
j
s
k
Transportation costs of moving commodityk on arc
⁡
(
i
,
j
) by service s, unit: ¥.
c
s
Unit costs of loading/unloading operation of services, unit: ¥/TEU.
c
s
t
o
r
e
Unit inventory costs of rail service, unit: ¥/TEU-h.
c
p
i
c
k
Additional charges for picking up the unit commodity from shipper at a rail terminal by rail service at origin, unit: ¥/TEU.
c
d
e
l
i
v
e
r
Additional charges for delivering the unit commodity from rail terminal to receiver by rail service at destination, unit: ¥/TEU.
φ
k
A parameter indicating whether origin pickup service is needed for commodityk. If the service is needed, φ
k
=
1; otherwise, φ
k
=
0.
μ
k
A parameter indicating whether destination delivery service is needed for commodityk. If the service is needed, μ
k
=
1; otherwise, μ
k
=
0.
c
c
o
2
Unit carbon dioxide emissions costs, unit: ¥/g.
η
s
Emission factor for carbon dioxide of services, unit: g/TEU-km.
M
A large positive number.
Decision variables
Representation
X
i
j
s
k
0-1 decision variable. If commodityk is moved from terminal i to terminal j by service s, X
i
j
s
k
=
1; otherwise, X
i
j
s
k
=
0.
Y
i
k
Arrival time of commodityk at terminal i.
Z
i
j
s
k
Charged inventory time of commodityk at terminal i before being moved on arc
⁡
(
i
,
j
) by rail service s, unit: h.


## 4.3. Node-Arc-Based Mixed Integer Nonlinear Programming Model

Using the symbols above, we propose the following node-arc-based mixed integer nonlinear programming model to describe the capacitated time-sensitive multicommodity multimodal generalized shortest path problem.(i) Mixed Integer Nonlinear Programming ModelObjective Function.We have the following:(1)
minimize
∑
k
∈
K
∑
i
,
j
∈
A
∑
s
∈
S
i
j
C
i
j
s
k
·
X
i
j
s
k
(2)
+
∑
k
∈
K
∑
i
∈
N
∑
h
∈
δ
-
i
∑
r
∈
S
h
i
c
r
·
q
k
·
X
h
i
r
k
+
∑
j
∈
δ
+
i
∑
s
∈
S
i
j
c
s
·
q
k
·
X
i
j
s
k
(3)
+
∑
k
∈
K
∑
i
,
j
∈
A
∑
s
∈
Γ
i
j
c
s
t
o
r
e
·
q
k
·
Z
i
j
s
k
(4)
+
∑
k
∈
K
φ
k
·
∑
j
∈
δ
+
o
k
∑
s
∈
Γ
o
k
j
c
p
i
c
k
·
q
k
·
X
o
k
j
s
k
+
∑
k
∈
K
μ
k
·
∑
i
∈
δ
-
d
k
∑
s
∈
Γ
i
d
k
c
d
e
l
i
v
e
r
·
q
k
·
X
i
d
k
s
k
(5)
+
∑
k
∈
K
∑
i
,
j
∈
A
∑
s
∈
S
i
j
c
c
o
2
·
η
s
·
q
k
·
d
i
j
s
·
X
i
j
s
k
.In this formulation, the objective function is to minimize the total generalized costs of moving multiple commodities through the multimodal transportation network. The generalized costs are the linear summation of Components (1)–(5), where Components (1)–(5) are the transportation costs en route, loading and unloading operation costs at terminals, inventory costs at terminals, additional origin picking up service costs and destination delivery costs, and carbon dioxide emissions costs, respectively:(6)
Subject  to
∑
j
∈
δ
+
i
∑
s
∈
S
i
j
X
i
j
s
k
-
∑
h
∈
δ
-
i
∑
r
∈
S
h
i
X
h
i
r
k
=
1
i
=
o
k
0
∀
i
∈
N
∖
o
k
,
d
k
-
1
i
=
d
k
∀
k
∈
K
,
∀
i
∈
N
(7)
∑
s
∈
S
i
j
X
i
j
s
k
≤
1
∀
k
∈
K
,
∀
i
,
j
∈
A
.Constraint (6) is the general commodity flow conservation constraint. Constraint (7) ensures that only one transportation service can be adopted to move a specific commodity on one arc. The combination of the two constraints ensures that each commodity is unsplittable/nonbifurcated and follows exactly one route from its origin terminal to its destination terminal through the multimodal transportation network [54, 56]:(8)
X
h
i
r
k
+
X
i
j
s
k
≤
1
∀
k
∈
K
,
∀
i
∈
N
,
∀
h
∈
δ
-
i
,
∀
j
∈
δ
+
i
,
∀
s
∈
Ω
i
j
,
∀
r
∈
Ω
h
i
.Constraint (8) ensures that the two conjoint segments of a road service route cannot be covered in a route simultaneously to avoid an extra transshipment at the terminals; that is, if commodity k plans to be moved from terminal h to terminal j via terminal i by road service, it should directly use the equivalent segment h
,
j that is generated in the multimodal transportation network based on the road service route deformation illustrated by Figure 4. For more details, we can refer to the statement in Section 2.1:(9)
∑
k
∈
K
q
k
·
X
i
j
s
k
≤
Q
i
j
s
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
.Constraint (9) is the rail service carrying capacity constraint. It ensures that the total volume of commodities loaded on the block container trains at the origin terminals will not exceed their available carrying capacities at the same terminals:(10)
Y
o
k
k
=
t
r
e
l
e
a
s
e
k
∀
k
∈
K
.Constraint (10) means that the arrival time of each commodity at the origin equals its release time at the origin:(11)
max
⁡
Y
i
k
,
S
D
i
s
+
t
i
j
s
-
Y
j
k
·
X
i
j
s
k
=
0
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
S
i
j
.Constraint (11) reflects the relationship between the arrival time variables and the commodity flow variables. It also successively computes the arrival times of each commodity at all the terminals that are covered in their transportation routes. For s
∈
Ω
i
j, there exists no scheduled departure time, and S
D
i
s is therefore set to 0 in this study. For s
∈
Γ
i
j, we are far more concerned about its operation start time at terminal j than about its arrival time at the same terminal, because when the commodity k arrives at terminal j, it will not be unloaded until l
j
s. Therefore, we consider l
j
s to be the valid arrival time of commodity k at terminal j when moved by rail service s on arc i
,
j. Hence, Y
j
k equals l
j
s instead of S
A
i
s and, consequently, in this case, t
i
j
s
=
l
j
s
-
S
D
i
s:(12)
Y
i
k
≤
u
i
s
·
X
i
j
s
k
+
M
·
1
-
X
i
j
s
k
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
.Constraint (12) is the operation service time constraint. It means that when adopting rail service, the arrival time of the commodity at the terminal should not be later than the operation cutoff time of the service. For this equation, if X
i
j
s
k
=
0, then Y
i
k
≤
M. This inequality is always satisfied, that is, the arrival time of the commodity at the terminal is not constrained by the operation cutoff time of a rail service that is not adopted in the routing:(13)
Y
d
k
k
≤
T
k
∀
k
∈
K
.Constraint (13) is the due date constraint. It ensures that the arrival time of each commodity at the destination does not exceed its claimed due date:(14)
m
a
x
0
,
l
i
s
-
Y
i
k
-
π
-
Z
i
j
s
k
·
X
i
j
s
k
=
0
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
.Constraint (14) indicates the relationship between the charged inventory time variables and the commodity flow variables. It also computes the charged inventory times of each commodity at all the origin terminals of the rail services that are adopted in their transportation routes. The inventory is needed only if the arrival times of the commodity at the terminals are earlier than the operation start times of the rail services at the same terminals. There also exists a period of inventory free of charge denoted by π (unit: h), such that if the inventory time of the commodity at a terminal is shorter than π, no inventory costs will be charged. For road services, there is no inventory at the terminals:(15)
C
i
j
s
k
=
c
r
a
i
l
1
+
c
r
a
i
l
2
·
d
i
j
s
·
q
k
s
∈
Γ
i
j
c
r
o
a
d
2
·
q
k
·
d
i
j
s
s
∈
Ω
i
j
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
S
i
j
.Constraint (15) computes the costs of operating services on the arcs according to the regulations proposed by the China Ministry of Railways and Ministry of Transport. In this equation, c
r
a
i
l
1 are the cost parameters related to the volume of the commodities (unit: ¥/TEU), while c
r
a
i
l
2 and c
r
o
a
d
2 are the cost parameters related to the turnover of commodities (unit: ¥/TEU-km). The values of the above parameters are regulated by the two ministries:(16)
X
i
j
s
k
∈
0,1
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
S
i
j
,
(17)
Y
i
k
≥
0
∀
k
∈
K
,
∀
i
∈
N
,
(18)
Z
i
j
s
k
≥
0
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
.Constraints (16)–(18) are the variable domain constraints.


## 4.4. Model Linearization

The proposed model above is a typical nonlinear programming formulation. When using the standard mathematical programming software to solve this problem directly, the computational results will represent local optimum, and much computational time will also be consumed; that is, the quality of the solutions and the solving efficiency will both be lowered due to the nonlinearity of the proposed model.The nonlinearity of the model is caused by Constraints (11) and (14), which include a nonlinear function (max
⁡
· function) and multiplications of different variables. Thus, to make the proposed model easily solvable by mathematical programming software, we linearize the two nonlinear constraints to transform the proposed model into a mixed integer linear programming formulation according to the following two propositions.Proposition 1.
Nonlinear constraintmax
⁡
Y
i
k
,
S
D
i
s
+
t
i
j
s
-
Y
j
k
·
X
i
j
s
k
=
0  ∀
k
∈
K, ∀
i
,
j
∈
A, and ∀
s
∈
S
i
j can be linearized by using the following four constraints:(19)
S
D
i
s
+
t
i
j
s
-
Y
j
k
≥
M
·
X
i
j
s
k
-
1
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
,
(20)
S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
M
·
1
-
X
i
j
s
k
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
,
(21)
Y
i
k
+
t
i
j
s
-
Y
j
k
≥
M
·
X
i
j
s
k
-
1
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Ω
i
j
,
(22)
Y
i
k
+
t
i
j
s
-
Y
j
k
≤
M
·
1
-
X
i
j
s
k
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Ω
i
j
.Proof.
Constraints (19) and (20) and Constraints (21) and (22) correspond separately to two independent but similar scenarios. Here, we only address Scenario 1. Scenario 1 contains two independent subscenarios: Scenarios 1.1 and 1.2.
Scenario
1. For rail service s on arc i
,
j, we have the following.
Scenario
1.1. If it is used to move commodity k, then X
i
j
s
k
=
1, and according to Constraint (11), S
D
i
s
+
t
i
j
s
-
Y
j
k
=
0. In this scenario, Constraints (19) and (20) equal S
D
i
s
+
t
i
j
s
-
Y
j
k
≥
0 and S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
0, respectively. Hence, the following deductive process exists. The deductive result ensures the existing equation relationship between S
D
i
s and Y
j
k: (23)
S
D
i
s
+
t
i
j
s
-
Y
j
k
≥
0
S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
0
⟹
0
≤
S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
0
⟹
Y
j
k
=
S
D
i
s
+
t
i
j
s
.
Scenario
1.2. Otherwise, X
i
j
s
k
=
0, and according to Constraint (11), S
D
i
s and Y
j
k are not related to each other. In this scenario, Constraints (19) and (20) equal S
D
i
s
+
t
i
j
s
-
Y
j
k
≥
-
M and S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
M, respectively. Therefore, the following deductive process exists. The deductive result ensures that there is no relationship between S
D
i
s and Y
j
k:(24)
S
D
i
s
+
t
i
j
s
-
Y
j
k
≥
-
M
S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
M
⟹
-
M
≤
S
D
i
s
+
t
i
j
s
-
Y
j
k
≤
M
.Proposition 2.
Nonlinear constraintmax
⁡
0
,
l
i
s
-
Y
i
k
-
π
-
Z
i
j
s
k
·
X
i
j
s
k
=
0  ∀
k
∈
K, ∀
i
,
j
∈
A, and ∀
s
∈
Γ
i
j can be linearized by using the following two constraints: (25)
Z
i
j
s
k
≥
M
·
X
i
j
s
k
-
1
+
l
i
s
-
Y
i
k
-
π
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
,
(26)
Z
i
j
s
k
≤
M
·
X
i
j
s
k
∀
k
∈
K
,
∀
i
,
j
∈
A
,
∀
s
∈
Γ
i
j
.Proof.
We consider two independent Scenarios 1 and 2.
Scenario 1. When the commodity k is not moved from terminal i to terminal j by rail service s, then X
i
j
s
k
=
0, and according to Constraint (14), there is no charged inventory time for commodity k towards rail service s on a
r
c
i
,
j. In this scenario, because M is a large positive number, -
M
+
l
i
s
-
Y
i
k
-
π is equivalent to -
M. Consequently, Constraints (25) and (26) separately equal Z
i
j
s
k
≥
-
M and Z
i
j
s
k
≤
0. When combined with the nonnegative constraint of Z
i
j
s
k (Constraint (17)), the following deductive process exists. The deductive result ensures that there is no charged inventory time for commodity k toward rail service s on a
r
c
i
,
j in this scenario:(27)
Z
i
j
s
k
≥
-
M
Z
i
j
s
k
≤
0
Z
i
j
s
k
≥
0
⟹
0
≤
Z
i
j
s
k
≤
0
⟹
Z
i
j
s
k
=
0
.
Scenario
2. When commodity k is moved from terminal i to terminal j by rail service s, then X
i
j
s
k
=
1. This scenario contains two following independent subscenarios: Scenarios 2.1 and 2.2.
Scenario
2.1. If l
i
s
-
Y
i
k
-
π
≤
0, there is no charged inventory time for commodity k towards rail service s on a
r
c
i
,
j based on Constraint (14). In this scenario, Constraints (21) and (22) equal Z
i
j
s
k
≥
l
i
s
-
Y
i
k
-
π and Z
i
j
s
k
≤
M, respectively. Considering the nonnegative constraint of Z
i
j
s
k (Constraint (17)), the following deductive process exists, in which the control of the minimization of Component (3) in the objective function towards the deductive result in the first step will lead to the final deductive result. The deductive result ensures that when commodity k is moved on a
r
c
i
,
j by rail service s, as long as l
i
s
-
Y
i
k
-
π
≤
0, the charged inventory time will not be generated:(28)
Z
i
j
s
k
≥
l
i
s
-
Y
i
k
-
π
Z
i
j
s
k
≤
M
Z
i
j
s
k
≥
0
l
i
s
-
Y
i
k
-
π
≤
0
⟹
0
≤
Z
i
j
s
k
≤
M
⟹
Z
i
j
s
k
=
0
.
Scenario
2.2. If l
i
s
-
Y
i
k
-
π
>
0, the charged inventory time l
i
s
-
Y
i
k
-
π exists for commodity k toward rail service s on a
r
c
i
,
j based on Constraint (14). In this scenario, considering the nonnegative constraint of Z
i
j
s
k (Constraint (17)), the following deductive process exists, in which the control of the minimization of Component (3) in the objective function towards the deductive result in the first step will lead to the final deductive result. The deductive result ensures that when commodity k is moved on a
r
c
i
,
j by rail service s and l
i
s
-
Y
i
k
-
π
>
0, the charged inventory time will be l
i
s
-
Y
i
k
-
π:(29)
Z
i
j
s
k
≥
l
i
s
-
Y
i
k
-
π
Z
i
j
s
k
≤
M
Z
i
j
s
k
≥
0
l
i
s
-
Y
i
k
-
π
>
0
⟹
l
i
s
-
Y
i
k
-
π
≤
Z
i
j
s
k
≤
M
⟹
Z
i
j
s
k
=
l
i
s
-
Y
i
k
-
π
.The final model is now a mixed integer linear programming model as follows. It can be easily solved by any mathematical programming software, for example, Lingo, Cplex, or GAMS, to obtain the optimal solution to the capacitated time-sensitive multicommodity multimodal generalized shortest path problem in a specific case.
(ii) Mixed Integer Linear Programming Model
Objective Function.We have the following:(30)
minimize
1
+
2
+
3
+
4
+
5
Subject to. Constraints (6)–(10), (12), (13), and (15)–(22), (25), and (26).


## 5. Computational Experiment

In this section, we design a large-scale empirical example to demonstrate the feasibility of the proposed model and the linearization method in addressing the practical problem by using the mathematical programming software Lingo. The values of the cost parameters in the proposed model are given in Table4. The unit loading/unloading costs of the rail and road services and the rail service’s unit inventory costs are shown in Table 5. Moreover, the period of inventory free of charge of rail services is 48 h, and the unit carbon dioxide emissions cost is 100 ¥/ton.Table 4
Values of the cost parameters.
Service
Parameter
Container feet
Unit
20 ft
40 ft
Road
c
r
o
a
d
2
6
4.5
¥/TEU-km
Rail
c
r
a
i
l
1
500
340
¥/TEU
c
r
a
i
l
2
2.025
1.377
¥/TEU-kmTable 5
Values of the loading/unloading and inventory costs.
Service
Container feet
Loading/unloading costs
Pickup/delivery costs
Inventory costs
(unit: ¥/TEU)
(unit: ¥/TEU)
(unit: ¥/TEU-h)
Road
20 ft
25
—
—
40 ft
19
—
—
Rail
20 ft
195
225
3.125
40 ft
146.25
337.5
3.125In this empirical example, which is based on a Chinese scenario, we study multimodal transportation routing for moving multiple commodities carried in containers from inland cities (e.g., Lanzhou, Hohhot, Guiyang, and Changsha) to the eastern sea ports (e.g., Qingdao, Shanghai, Guangzhou, and Shenzhen). Multimodal transportation routing for this example starts from a deterministic and known date, and the data used in this example should first be discretized into real numbers.The rail terminals of the block container trains are the backbone of the multimodal transportation network. A total of 40 terminals and 118 arcs were used to build the entire multimodal transportation network topology shown in Figure9. There are 42 periodic operated rail services and 78 road services in the multimodal transportation network that can be adopted to move containers from inland cities to the sea ports. In the large-scale multimodal transportation network below, the transportation distances and times of the road services are given in Table 6. The data for this table were collected by using the online digital map, and the relevant operating information for the rail services is given in Table 7. In China, the average time interval between the arrival time and the operation start time of a block container train at the unloading organization terminals is approximately 40 min, and the average time interval between the departure time and the operation cutoff time at the loading organization terminals is approximately 30 min. If there are marshaling or classifying operations at the two types of terminals, the two time intervals will increase to 70 min and 60 min, respectively.Table 6
Transportation distances and times for road services in the large-scale empirical example.
Arc
Distance
Time
Arc
Distance
Time
(unit: km)
(unit: h)
(unit: km)
(unit: h)
(1, 2)
147
4.5
(20, 40)
225
6
(1, 3)
656
10
(22, 14)
868
14
(1, 10)
1081
24.5
(22, 40)
2273
34
(2, 1)
147
4.5
(22, 34)
1923
23
(2, 3)
801
12.5
(22, 35)
1645
29.5
(2, 9)
1161
29.5
(22, 36)
1748
27.5
(3, 9)
449
10.5
(22, 37)
1846
28
(3, 10)
489
12
(22, 38)
1578
23.5
(3, 13)
558
14.5
(23, 32)
96
2
(4, 5)
362
5
(24, 23)
103
3
(4, 6)
419
7
(24, 32)
9
0.5
(4, 7)
525
9.5
(25, 23)
133
3
(4, 8)
618
11.5
(25, 32)
41
1.5
(4, 11)
1083
18
(26, 23)
130
3
(4, 12)
1082
19.5
(26, 32)
37
1.5
(4, 13)
1613
29
(27, 23)
124
4
(4, 14)
821
16
(27, 32)
29
1
(4, 18)
2016
34.5
(28, 23)
168
5
(8, 11)
474
6.5
(28, 32)
72
2
(8, 12)
473
8
(29, 23)
153
4.5
(8, 13)
1004
17.5
(29, 32)
59
2
(9, 13)
225
4.5
(30, 23)
138
4.5
(9, 18)
788
9
(30, 32)
47
1.5
(10, 13)
218
3
(31, 23)
135
4.5
(10, 18)
774
9
(31, 32)
45
1.5
(13, 18)
566
7
(32, 23)
100
2
(14, 21)
271
3.5
(33, 15)
1016
21.5
(14, 22)
869
14
(33, 40)
989
16
(14, 32)
1613
26
(33, 34)
519
9.5
(15, 18)
93
3.5
(33, 35)
335
6
(15, 40)
207
3.5
(33, 36)
467
12
(16, 18)
71
2.5
(33, 37)
566
12.5
(16, 40)
223
6
(33, 38)
292
8
(17, 18)
59
1.5
(39, 14)
659
8.5
(17, 40)
183
4.5
(39, 21)
319
15.5
(18, 40)
235
3
(39, 22)
518
8.5
(19, 18)
71
2.5
(39, 23)
1106
20
(19, 40)
229
6
(39, 32)
1005
18.5
(20, 18)
61
2
(40, 15)
209
3.5Table 7
Operating information for rail services in the large-scale empirical example.
Rail service number
1
2
3
4
5
6
7
Origin
1
2
5
6
7
8
8
Operation start time
—
20.7
5.8
2.6
9
—
—
Operation cutoff time
0.8
22.2
6.8
4.1
11
—
—
Departure time
1.8
22.7
7.3
4.6
12
0.1
0.1
Destination
3
3
3
3
3
9
10
Arrival time
46.5
46.5
42.9
42.9
42.9
45.2
45.9
Operation start time
47.7
47.7
43.6
43.6
43.6
46.4
46.6
Distance (unit: km)
686
847
1415
1358
1272
1281
1326
Capacity (unit: TEU)
44
61
50
30
20
50
55
Operation period (unit: day/train)
2
2
2
2
2
3.5
3.5
Rail service number
8
9
10
11
12
13
14
Origin
11
11
11
12
12
12
14
Operation start time
—
—
9
—
—
—
18
Operation cutoff time
—
—
11.9
—
—
—
22.4
Departure time
0.4
0.4
12.4
0.8
0.8
0.8
22.9
Destination
9
10
13
9
10
13
15
Arrival time
25.9
26.5
30.3
25.9
26.5
30.3
111
Operation start time
27.1
27.2
31
27.1
27.2
31
111.7
Distance (unit: km)
763
821
585
767
812
576
2210
Capacity (unit: TEU)
22
38
40
20
20
60
16
Operation period (unit: day/train)
2
2
2
2
2
2
2
Rail service number
15
16
17
18
19
20
21
Origin
14
14
14
14
14
14
14
Operation start time
18
18
18
18
18
14.5
14.5
Operation cutoff time
22.4
22.4
22.4
22.4
22.4
17.3
17.3
Departure time
22.9
22.9
22.9
22.9
22.9
17.8
17.8
Destination
16
17
18
19
20
23
24
Arrival time
104.8
106
109
105.4
101.4
102.7
109
Operation start time
105.5
106.7
107.7
106.1
102.1
103.4
109.7
Distance (unit: km)
2240
2265
2334
2249
2255
2357
2254
Capacity (unit: TEU)
10
22
42
10
5
100
28
Operation period (unit: day/train)
2
2
2
2
2
2
2
Rail service number
22
23
24
25
26
27
28
Origin
14
14
14
21
21
21
21
Operation start time
14.5
14.5
14.5
19
1
1
1
Operation cutoff time
17.3
17.3
17.3
20.7
3.5
3.5
3.5
Departure time
17.8
17.8
17.8
21.2
4
4
4
Destination
26
27
28
23
24
26
27
Arrival time
102.2
102.1
108.8
78.7
109
102.2
102.1
Operation start time
102.9
102.8
109.5
79.9
109.7
102.9
102.8
Distance (unit: km)
2213
2223
2280
1848
1745
1704
1714
Capacity (unit: TEU)
6
10
4
100
14
8
10
Operation period (unit: day/train)
2
2
2
2
2
2
2
Rail service number
29
30
31
32
33
34
35
Origin
21
22
22
22
22
22
22
Operation start time
1
7
7
7
7
7
7
Operation cutoff time
3.5
9.5
9.5
9.5
9.5
9.5
9.5
Departure time
4
10
10
10
10
10
10
Destination
28
24
25
26
28
29
30
Arrival time
108.8
93.5
87.5
82.2
74.6
78.1
85.2
Operation start time
109.5
94.2
88.2
82.9
75.3
78.8
85.9
Distance (unit: km)
1771
1661
1644
1640
1573
1590
1603
Capacity (unit: TEU)
20
8
10
6
8
4
12
Operation period (unit: day/train)
2
2
2
2
2
2
2
Rail service number
36
37
38
39
40
41
42
Origin
22
22
34
35
36
37
38
Operation start time
7
7
17
20.5
10
16
15.5
Operation cutoff time
9.5
9.5
17.9
21.8
11.5
18.4
17.9
Departure time
10
10
18.4
22.3
12
18.9
18.4
Destination
31
32
40
40
40
40
40
Arrival time
80.8
89.5
56.6
56.6
56.6
56.6
56.6
Operation start time
81.5
90.2
57.3
57.3
57.3
57.3
57.3
Distance (unit: km)
1610
1660
789
826
671
553
861
Capacity (unit: TEU)
16
36
14
16
10
12
48
Operation period (unit: day/train)
2
2
2
2
2
2
2Figure 9
A large-scale multimodal transportation network for China inland container export.The multiple commodities for this example are presented in Table8. These commodities are all carried in 20 ft containers. The due dates of the commodities are usually determined by the loading cutoff times of the container vessels at the sea ports. If the arrival times of the commodities at the sea port exceed the container vessels’ loading cutoff time, the commodities cannot be carried by the container vessels to be further moved overseas. Considering these commodities as the optimization object, we then used the mathematical programming software Lingo 12 on a Lenovo Laptop with Intel Core i5 3235 M 2.60 GHz CPU and 4 GB RAM to solve large-scale empirical example.Table 8
Information on the multiple commodity flows in the large-scale empirical example.
Number
Pickup service
Delivery service
Origin
Destination
Volume (TEU)
Release time
Due date
1
Y
N
1
3
21
8
40
2
Y
Y
1
10
30
36
109
3
N
Y
1
10
10
39
120
4
Y
N
2
3
43
16
111
5
Y
Y
2
3
14
74
161
6
N
Y
2
9
45
10
138
7
Y
Y
4
13
32
28
183
8
N
Y
4
13
16
111
198
9
Y
N
4
18
19
15
105
10
Y
N
4
18
37
90
201
11
Y
N
8
13
48
22
106
12
Y
N
8
13
28
137
210
13
Y
Y
14
32
44
18
70
14
Y
Y
14
32
18
68
196
15
N
Y
22
40
52
4
60
16
Y
N
22
40
8
15
98
17
Y
N
22
40
40
67
205
18
Y
N
33
15
39
5
106
19
Y
Y
33
15
10
81
173
20
Y
Y
33
15
14
125
208
21
N
Y
33
40
55
12
58
22
Y
Y
33
40
19
77
199
23
Y
N
39
23
11
124
210
24
Y
Y
39
23
15
85
192
25
N
Y
39
32
37
98
226The computational results for the large-scale empirical example are presented in Table9. Moreover, we simulated the routing in the road service network that is contained in the large-scale empirical example. The corresponding computational result for the single road service routing is 5,806,742 ¥. The computational results for this example indicate that the multimodal transportation routing can lower the generalized costs of moving commodities by approximately 10% (5251563
-
5806742
/
5806742) compared with single road service routing, which indicates the superiority of multimodal transportation in the terms of economic efficiency.Table 9
Computational results of Lingo 12 towards the large-scale empirical example.
Service mode
Solver type
Solution
Computational time
State
Multimodal service
B-and-B
5,251,563 ¥
1 min 35 sec
Global optThe cost structure of the two types of service modes in the large-scale empirical example is shown in Figure10, where C1 to C5 successively represent the costs incurred during the routes, the loading/unloading costs, the inventory costs, the additional pickup/delivery costs, and the carbon dioxide emissions costs, which separately correspond to Components (1)–(5) in the objective function of the proposed model.Figure 10
Cost structure for the large-scale empirical example.Finally, the corresponding optimal multimodal transportation routing framework is given in Table10 where the items such as X9514/3 and X9518/7 are the train numbers of the utilized block container trains, and their operation routes are all presented in Figure 9.Table 10
Optimal multimodal transportation routing framework for the large-scale empirical example.
Number
Multimodal transportation route
Arrival time at destination
1
1r
o
a
d
s
e
r
v
i
c
e
→ 3
18
2
1X
9514
/
3
→ 3 r
o
a
d
s
e
r
v
i
c
e
→ 10
107.7
3
1X
9514
/
3
→ 3 r
o
a
d
s
e
r
v
i
c
e
→ 10
107.1
4
2X
9514
/
3
→ 3
95.7
5
2X
9514
/
3
→ 3
143.7
6
2X
9514
/
3
→ 3 r
o
a
d
s
e
r
v
i
c
e
→ 9
58.2
7
4r
o
a
d
s
e
r
v
i
c
e
→ 12 X
9518
/
7
→ 13
127
8
4r
o
a
d
s
e
r
v
i
c
e
→ 12 X
9518
/
7
→ 13
175
9
4r
o
a
d
s
e
r
v
i
c
e
→ 11 X
9518
/
7
→ 13 r
o
a
d
s
e
r
v
i
c
e
→ 18
86
10
4r
o
a
d
s
e
r
v
i
c
e
→ 12 X
9518
/
7
→ 13 r
o
a
d
s
e
r
v
i
c
e
→ 18
182
11
8r
o
a
d
s
e
r
v
i
c
e
→ 12 X
9518
/
7
→ 13
79
12
8r
o
a
d
s
e
r
v
i
c
e
→ 11 X
9518
/
7
→ 13
175
13
14r
o
a
d
s
e
r
v
i
c
e
→ 32
44
14
14r
o
a
d
s
e
r
v
i
c
e
→ 21 X
95
5
8
/
7
→ 23 r
o
a
d
s
e
r
v
i
c
e
→ 32
177.9
15
22r
o
a
d
s
e
r
v
i
c
e
→ 40
38
16
22r
o
a
d
s
e
r
v
i
c
e
→ 40
49
17
22r
o
a
d
s
e
r
v
i
c
e
→ 38 X
9540
/
39
→ 40
201.3
18
33r
o
a
d
s
e
r
v
i
c
e
→ 38 X
95
40
/
39
→ 40 r
o
a
d
s
e
r
v
i
c
e
→ 15
60.8
19
33r
o
a
d
s
e
r
v
i
c
e
→ 38 X
95
40
/
39
→ 40 r
o
a
d
s
e
r
v
i
c
e
→ 15
156.8
20
33r
o
a
d
s
e
r
v
i
c
e
→ 35 X
95
40
/
39
→ 40 r
o
a
d
s
e
r
v
i
c
e
→ 15
204.8
21
33r
o
a
d
s
e
r
v
i
c
e
→ 40
28
22
33r
o
a
d
s
e
r
v
i
c
e
→ 38 X
95
40
/
39
→ 40
153.3
23
39r
o
a
d
s
e
r
v
i
c
e
→ 23
144
24
39r
o
a
d
s
e
r
v
i
c
e
→ 21 X
95
58
/
7
→ 23
175.9
25
39r
o
a
d
s
e
r
v
i
c
e
→ 32
116.5


## 6. Conclusions

In this study, we explore the multimodal transportation routing problem. To address this combinatorial optimization problem, a node-arc-based mixed integer nonlinear programming model is first established. A linearization method is then developed to transform the proposed nonlinear model into a linear one by linearizing its nonlinear constraints. Finally, a computational example is presented to demonstrate the feasibility of the proposed model and linearization method in addressing the large-scale empirical example.The main contribution of this study is that it comprehensively considers(
1
) multicommodity flow, (
2
) capacitated schedule-based rail service and uncapacitated time-flexible road service, (
3
) carbon dioxide emissions estimation, and (
4
) generalized costs optimum to satisfy customer demands. Moreover, it formulates the multimodal transportation routing problem as a capacitated time-sensitive multicommodity multimodal generalized shortest path problem. Specifically, the time-sensitive routing better matches the operational characteristics of the schedule-based services, corresponds to transportation practice, and can, hence, provide better decision support for decision makers. Additionally, from the perspectives of solvability, the linearization method that we have developed can easily linearize the model, which makes it effectively solvable by any mathematical programming software.Although several advances have been made by this study, weaknesses still exist. The most significant one is that the problem addressed by this study is oriented toward the demands of a deterministic transportation environment, which means that all the transportation demands are known and determined. In reality, many studies and practical data have indicated that transportation demands show remarkable spatial and temporal uncertainty. For this reason, satisfying fluctuating transportation demands presents great challenges for both decision makers and researchers [57, 58]. Therefore, further study is needed to address the stochastic multimodal transportation routing problem.



---

*Source: 406218-2015-12-15.xml*