Abstract
This paper investigates a dynamic and stochastic shipment matching problem faced by network operators in hinterland synchromodal transportation. We consider a platform that receives contractual and spot shipment requests from shippers, and receives multimodal services from carriers. The platform aims to provide optimal matches between shipment requests and multimodal services within a finite horizon under spot request uncertainty. Due to the capacity limitation of multimodal services, the matching decisions made for current requests will affect the ability to make good matches for future requests. To solve the problem, this paper proposes an anticipatory approach which consists of a rolling horizon framework that handles dynamic events, a sample average approximation method that addresses uncertainties, and a progressive hedging algorithm that generates solutions at each decision epoch. Compared with the greedy approach which is commonly used in practice, the anticipatory approach has total cost savings up to 8.18% under realistic instances. The experimental results highlight the benefits of incorporating stochastic information in dynamic decision making processes of the synchromodal matching system.
Introduction
Hinterland transportation is the movement of shipments between deepsea ports and inland terminals by trucks, trains, barges, or any combination of them (SteadieSeifi et al. 2014). Typically, a hinterland transport system is made up of multiple stakeholders that interact with each other, including network operators, shippers, carriers, terminal operators, and institutional authorities (Crainic et al. 2018). Network operators (e.g., logistics service providers and alliances formed by multiple carriers) control the transport system. Shippers (e.g., manufacturers, ocean carriers, and freight forwarders) generate freight transport demand and outsource transport activities to network operators. Carriers (e.g., truck, train, and barge companies) provide transport services and supply timely transport capacity to network operators. Terminal operators handle transshipment operations at terminals. Institutional authorities (e.g., governments and public administrations) charge tax, give incentives, and regulate transport activities to network operators, such as the charging of carbon emissions.
As shippers become more timesensitive that require shipments to be delivered within tight time windows, trucks are used more often which contributes to road traffic congestion, transport costs, and carbon emissions (Demir et al. 2016). However, due to the increasing environmental issues and the enforced regulations, companies in the transport industry are required to control carbon emissions (Demir et al. 2016). Synchromodal transportation, as an emerging and attractive concept, aims to manage different types of shipments considering the tradeoff among costs, delays, and emissions through integrated realtime planning and synchronization of activities (Giusti et al. 2019). Under synchromodality, shippers only specify shipments’ origin, destination, volume, release time, and due time, and leave the choice of modes, routes, and departure and arrival times to network operators. For example, for timesensitive shipments, network operators can assign trucks for transportation; but if time available, barges, trains or bargetruck can be assigned taking into account their impact on costs, time, and emissions.
With the development of digitization in the logistics industry, increasing online booking platforms have appeared in freight transportation, such as Uber Freight, Quicargo, and Maersk Spot. In this paper, we consider a synchromodal matching platform owned by a network operator (e.g., European Gateway Services or Contargo) that receives contractual and spot shipment requests from shippers and receives timescheduled services (e.g., trains) and departure timeflexible services (e.g., trucks) from carriers. The platform aims to provide optimal matches between shipment requests and transport services over a given planning horizon. Having a match between a shipment and a service means that the shipment will be transported by the service from the service’s origin terminal to the service’s destination terminal. The platform combines the matched services into shipments’ itineraries.
In practice, container transport companies receive shipment requests from both longterm contracts and spot markets (Meng et al. 2019). Different from the contractual requests received from large shippers whose information is known before the operational planning horizon, the information of spot requests is unknown and revealed dynamically (Guo et al. 2020). The demand from the spot market is influenced by many factors, such as global economy, seasonality, fluctuations of freight rate, and competitions from other companies (Wang and Meng 2021). Due to the capacity limitation of multimodal services, the capacity assigned to current requests will be unavailable for future requests which might be more profitable. Thanks to the advancements in information technologies, such as increased use of sensors in transport infrastructures, communication technologies, open data sources, and data analytics, exploiting stochastic information of spot requests is increasingly achievable (Gendreau et al. 2016). With the stochastic information, network operators might hold some barge and train capacities available for spot requests which are predicted to be more profitable.
In this paper, we define the matching of shipments and services under spot request uncertainty with the aim to minimize total costs over a given planning horizon as the dynamic and stochastic shipment matching (DSSM) problem. The complexity of the DSSM problem lies in three aspects. First, spot requests arrive in the platform in realtime which calls for a dynamic approach that handles dynamic events. Second, the stochastic information of spot requests is available which calls for a stochastic approach that addresses uncertainties. Third, the computation complexity of the optimization problem calls for an efficient algorithm that generates timely solutions at each decision epoch.
In the literature, Guo et al. (2020) developed a myopic approach to solve the DSSM problem which does not consider the stochasticity of spot requests. The myopic approach involves a rolling horizon framework that handles dynamic events and a preprocessingbased heuristic algorithm that generates timely solutions at each decision epoch. As an extension of Guo et al. (2020), this paper proposes an anticipatory approach to incorporate the stochastic information of spot requests in the dynamic shipment matching processes. The anticipatory approach involves a sample average approximation method that addresses spot request uncertainties and a progressive hedging algorithm that solves the deterministic formulations at each decision epoch of a rolling horizon framework.
The remainder of this paper is structured as follows. We briefly review the relevant literature and specify our contributions in Sect. 2. In Sect. 3, we describe the DSSM problem. In Sect. 4, we design the rolling horizon framework, the sample average approximation method, and the progressive hedging algorithm. In Sect. 5, we describe the experimental setup, and present the experimental results. Finally, in Sect. 6, we provide concluding remarks and directions for future research.
Literature review
In the past decades, because of economic factors and environmental concerns, different management concepts have appeared in the literature and in the logistics industry: multimodal, intermodal, comodal and synchromodal transportation. While multimodality refers to the utilization of multiple modes, intermodality emphasizes the utilization of standardized loading units (i.e., containers), namely the vertical integration of different modes (SteadieSeifi et al. 2014); comodality focuses on the optimal and sustainable utilization of different modes on their own or in combination, namely the horizontal integration of different modes. As an extension of intermodality and comodality, synchromodality adds the (realtime) flexibility in planning when disturbances happen (Giusti et al. 2019).
The implementation of synchromodal transportation relies on collaboration among stakeholders, information technologies, and integrated planning at different decision levels. Typically, synchromodal transport planning can be divided into three levels: strategic, tactical, and operational level. While strategic and tactical planning focus on physical network design (e.g., hub location) and service network design (e.g., service selection, service frequency) in long and medium time horizons, operational planning deals with the routing of shipments under dynamic and stochastic environments (Giusti et al. 2019).
In the literature, the majority of the studies (e.g., Ayar and Yaman 2011; Chang 2008; Moccia et al. 2010; van Riessen et al. 2014) related to synchromodal transport planning are conducted in a static and deterministic environment, namely, all the inputs are known beforehand and decisions do not change once they are set. However, in practice, there are many sources of uncertainties in synchromodal transportation, such as demand uncertainty. With the growing amount of historical data, the stochastic information about uncertainties is available. Incorporating stochastic information in decisionmaking processes has been proven to have better performance than the corresponding myopic approaches in many fields, such as vehicle routing problems (AlbaredaSambola et al. 2014) and dialaride problems (Schilde et al. 2011).
In the field of stochastic synchromodal transport planning, Demir et al. (2016) studied a green intermodal service network design problem with demand and travel time uncertainties. In this study, the origins, destinations, time windows of shipments are known in advance, but the actual demand (i.e, the number of containers) is uncertain. A sample average approximation method was proposed to generate robust plans. Hrušovský et al. (2016) proposed a hybrid approach combining a deterministic model with a simulation model to investigate an intermodal transport planning problem with travel time uncertainty. Sun et al. (2018) established a fuzzy chanceconstrained mixed integer nonlinear programming model to describe rail service capacity uncertainty and road traffic congestion. Generally, stochastic transport planning problems have the probability distributions of random variables and the optimization process is performed before their realization. The transport plan will not be updated after the realization, thus, it is often referred to as apriori optimization (Ritzinger et al. 2015).
The trend towards digitalization in transportation allows gathering realtime information and thus dynamic decision making. In synchromodal transportation, some input data are revealed during the execution of the plan. The most common dynamic events are the arrival of new shipment requests, but demands and travel times are possible dynamics as well. In the literature, Li et al. (2015) presented a receding horizon intermodal container flow control approach to deal with the dynamic transport demands and dynamic traffic conditions. Mes and Iacob (2015) considered the realtime planning of shipment requests under a synchromodal network with the objective to minimize costs, delays, and emissions. van Heeswijk et al. (2016) proposed an online planning algorithm to schedule the transport of less than truckload freight via intermodal networks. Guo et al. (2020) developed a rolling horizon approach to handle shipment requests that arrive dynamically in a synchromodal matching platform.
The advances in information and communication technologies as well as the computing power allow the incorporation of stochastic information of future events in dynamic decisionmaking processes. Approaches for dynamic and stochastic transport planning problems can be divided into two categories: methods based on preprocessed decisions and methods based on online decisions. Solution approaches in the first group (preprocessed decisions) determine the values and policies of decision making before the execution of the transport plan (Ritzinger et al. 2015). Therefore, possible states need to be constructed in advance and evaluated based on possible dynamic events and stochastic information over a planning horizon. For example, van Riessen et al. (2016) designed a decision tree to derive realtime decision rules for suitable allocation of shipment requests to services. Rivera and Mes (2017) proposed an algorithm based on approximate dynamic programming to tackle the curse of dimensionality of a Markov decision process model. The second group (online decisions) focuses on the computation when a dynamic event occurs. Specifically, decisions are made online with respect to the current system state and the available stochastic information. SteadieSeifi (2017) proposed a rolling horizon approach to handle dynamic demands. At each iteration of the rolling horizon framework, the author proposed a scenariobased twostage stochastic programming model to incorporate the stochastic information of future demands.
In this paper, we investigate the dynamic and stochastic shipment matching (DSSM) problem in synchromodal transportation at the operational level. The formulation characteristics of the DSSM problem include: (1) contractual and spot shipment requests; (2) stochastic information of spot requests; (3) unsplittable shipments, i.e., a shipment should be delivered as a whole; (4) soft time windows, i.e., delay in delivery is available but with a penalty; (5) capacitated and timescheduled barge and train services; (6) departure timeflexible truck services with timedependent travel times; (7) transshipment operations at terminals; (8) minimizing generalized costs which consist of transport costs, delay costs, and carbon tax over a planning horizon. The formulation characteristics, solution approaches, and experimental size of related articles are summarized in Table 1.
Our work has three main contributions to the literature. First, we introduce the stochasticity of spot requests in the dynamic shipment matching processes. Second, we propose an anticipatory approach to solve the problem under realistic instances in a reasonable time. The anticipatory approach uses a sample average approximation method to address spot request uncertainty and applies a progressive hedging algorithm to get solutions at each decision epoch of a rolling horizon framework. This approach enables to consider a large set of scenarios (within 1 min of computation time) to more accurately represent the stochasticity and this in turn increases the benefits of incorporating stochastic information in dynamic decisionmaking processes. Third, thanks to the above developed methodologies we propose a platform in which companies can manage different types of shipments (e.g., timesensitive shipments) under a synchromodal network considering the tradeoff among costs, delays, and emissions. Such a platform provides the means for a more efficient, effective and sustainable decisionmaking framework for transportation systems.
Problem description and preprocessing procedures
In this section, we first describe the DSSM problem in detail, and then briefly present the preprocessing procedures designed to reduce the computational complexity.
Problem description
We consider an online matching platform that receives contractual and spot shipment requests from shippers, receives timescheduled and departuretime flexible services from carriers, and receives unlimited handling services (i.e., loading and unloading) from terminal operators. Let N be the set of terminals. Let \(lc^{\mathrm {barge}}_i\), \(lc^{\mathrm {train}}_i\), \(lc^{\mathrm {truck}}_i\) be the loading/unloading cost coefficient of barge, train, and truck services at terminal \(i\in N\), respectively. Let \(lt^{\mathrm {barge}}_i\), \(lt^{\mathrm {train}}_i\), \(lt^{\mathrm {truck}}_i\) be the loading/unloading time of barge, train, and truck services at terminal \(i\in N\), respectively. Let \(c^{\mathrm {storage}}_i\) be the storage cost coefficient at terminal \(i\in N\). The \(CO_2\) emissionsrelated cost coefficient is set as \(c^{\mathrm {emission}}\).
Let R be the set of shipment requests. Each shipment request \(r \in R\) is characterized by its announce time \(t_r^{\mathrm {announce}}\) (i.e., the time when the platform receives the request), release time \(t_{r}^{\mathrm {release}}\) (i.e., the time when the shipment is available for hinterland transportation) at origin terminal \(o_{r}\), due time \(t_{r}^{\mathrm {due}}\) (i.e., the time that the shipment needs to be delivered) at destination terminal \(d_{r}\), expiry date \(t_r^{\mathrm {expire}}\) (i.e., the time that the matching decisions for request r cannot be further postponed), and container volume \(u_{r}\). Delay in delivery is available but with a penalty cost per container per hour overdue \(c_r^{\mathrm {delay}}\).
Requests R can be divided into two groups: contractual requests \(R^{\mathrm {contract}}\) and spot requests \(R^{\mathrm {spot}}\). While \(R^{\mathrm {contract}}\) are known beforehand, \(R^{\mathrm {spot}}\) are unknown and revealed dynamically. However, the probability distributions \(\{\pi _o, \pi _d, \pi _u, \pi _{t^{\mathrm {announce}}}, \pi _{t^{\mathrm {release}}}, \pi _{t^{\mathrm {due}}}, \pi _{t^{\mathrm {expire}}}\}\) of spot requests’ origin, destination, volume, announce time, release time, due time, and expiry date are assumed available from historic data. In addition, shippers require their shipments to be transported as a whole, and ask to receive the transport plan before shipments’ release time, namely the expiry date is equal to the release time, \(t^{\mathrm {release}}_r=t^{\mathrm {expire}}_r\).
Let V be the set of transport services, all the services are received before the planning horizon. According to the time schedules, services can be divided into two groups:

Timescheduled barge and train services. Each barge or train service \(v \in V^{\mathrm {barge}} \cup V^{\mathrm {train}}\) is characterized by its departure time \(t^{\mathrm {depature}}_v\) at origin terminal \(o_v\), arrival time \(t^{\mathrm {arrival}}_v\) at destination terminal \(d_v\), free capacity \(U_v\), transport cost \(c_v\) and carbon emissions \(e_v\).

Departure timeflexible truck services. We view each truck service as a fleet of trucks which has flexible departure times and an unlimited capacity. Thus, a truck service might have multiple departure times for different shipments. Due to traffic congestion at several time periods throughout a day, the travel time of truck services is timedependent (Ichoua et al. 2003). Therefore, each truck service \(v \in V^{\mathrm {truck}}\) is characterized by its origin terminal \(o_v\), destination terminal \(d_v\), timedependent travel time function \(t_v^{\mathrm {truck}}(\tau )\), transport cost \(c_v\), and carbon emissions \(e_v\).
The objective of the platform is to provide optimal online matches in total costs between shipment requests and transport services over a planning horizon T. The total costs consist of transit costs generated by using services, transfer costs and storage costs generated at transshipment terminals, penalty costs caused by delay in delivery, and carbon tax charged for services’ carbon emissions.
Preprocessing procedures
In this section, we briefly present the preprocessing procedures that aim to reduce the computational complexity of the DSSM problem by identifying infeasible matches between shipments and services. It consists of two steps: the preprocessing of feasible path and the preprocessing of feasible matches.

Preprocessing of feasible path. We define a path p as a combination of services in sequence. A path p is feasible if the services inside a combination satisfy timespatial compatibility. Specifically, for two consecutive services \(v_i,v_{i+1}\) within path p, the destination of service \(v_i\) must be the same as the origin of service \(v_{i+1}\); the arrival time of service \(v_i\) must be earlier than the departure time of service \(v_{i+1}\) minus loading and unloading time at transshipment terminal \(d_{v_i}\). The set P denotes the collection of feasible paths.

Preprocessing of feasible matches. A match (r, p) means shipment r will be transported by path p from its origin to its destination. A match between request \(r \in R\) and path \(p=\left[ v_1,...,v_l\right] \in P\) is feasible if it satisfies timespatial compatibility:

Spatial compatibility. The origin terminal of shipment request r should be the same as the origin of service \(v_1\); the destination of request r should be the same as the destination of service \(v_l\).

Time compatibility. The release time of request r should be earlier than the departure time of service \(v_1\) minus loading time at origin terminal \(o_r\).
Let \(P_r\) be the set of feasible paths for request r, and let \(c_{rp}\) denote the costs of matching request r with path p including transport costs, delay costs and carbon tax. The details of the preprocessing procedures are presented in Guo et al. (2020).

An illustrative example of shipment matching with feasible paths is shown in Fig. 1. Here, a shipment needs to be transported from origin terminal 1 to destination terminal 8 after release time 00:00, and the due time of the shipment is 24:00. The shipment can be matched with different paths (i.e., service combinations). Using feasible path 1, the shipment will be loaded at origin terminal 1 and transported by a barge service to transshipment terminal 5, and then the shipment is transferred to a train service which delivers the shipment to its destination terminal.
The notation used in this paper is presented in Table 2.
Solution approaches
In this section, we propose an anticipatory approach (AA) to solve the DSSM problem and use the myopic approach (MA) proposed by Guo et al. (2020) as a benchmark. Both the AA and the MA are implemented under a rolling horizon framework. However, the MA is based on deterministic information only while the AA incorporates stochastic information of future requests at each decision epoch, as shown in Fig. 2.
Myopic approach
The MA presented in Guo et al. (2020) utilizes a rolling horizon framework to handle dynamic events, which is known as an efficient periodic reoptimization approach for dynamic problems (e.g., Arslan et al. 2019; Najmi et al. 2017; Wang and Kopfer 2015; Yang et al. 2004). The planning horizon is rolled forward to incorporate the dynamically released information, and the process continues until the end of the horizon. Under the MA, the system is optimized periodically at prespecified points in time called optimization times (i.e., decision epochs). Let \({\hat{R}}^t=\{r\in R t1<t^{\mathrm {announce}}_r \le t\}\) be the set of spot requests received during time interval \(\left( t1,t\right]\), \(t>0\). At decision epoch t, decisions for all active shipment requests \({\bar{R}}^t\) are made. Request r is active if it is already announced but not expired yet, formally \({\bar{R}}^t=\{r\in R t_r^{\mathrm {announce}} \le t, t_r^{\mathrm {expire}} > t\}\). However, the decision for request \(r \in {\bar{R}}^{t}\) is fixed only if \(r \in R^t=\{r\in R t_r^{\mathrm {announce}} \le t, t < t_r^{\mathrm {expire}} \le t+1\}\), namely the request will expire before the next decision epoch. The platform will inform shippers the decisions only if a match is fixed for them. Thus, only the matches fixed at stage t have effects on the free capacity of service \(v \in V^{\mathrm {barge}} \cup V^{\mathrm {train}}\) at stage \(t+1\).
We define \(x_{rp}^t\) as the binary variable which is 1 if request in \(r \in R^t\) is matched with path \(p \in P\) and define \(y_{rp}^t\) as the binary variable which is 1 if request in \(r \in {\bar{R}}^t \backslash R^t\) is matched with path \(p \in P\). Let \(P_{rv}\) be the set of feasible paths for shipment request r including service v, \(P_{rv}=\{p\in P_r v\in p\}\). Under the MA, the objective function is to minimize the total costs of the currentstage decisions made for active requests \({\bar{R}}^t\). The formulation of the DSSM problem at stage \(t \in \{0,1,...,T\}\) under the MA is:
subject to
Constraints (2–3) ensure that each request will be matched with one feasible path only. Constraints (4) ensure that the total container volumes of shipments assigned to service \(v \in V^{\mathrm {barge}} \cup V^{\mathrm {train}}\) does not exceed its free capacity at stage t. Constraints (5) represent that the free capacity of service \(v \in V^{\mathrm {barge}} \cup V^{\mathrm {train}}\) at the next stage is only influenced by the free capacity of service v at the current stage and the matching decisions made for requests \(R^t\) which will expire before the next stage.
Anticipatory approach
In this section, we propose the AA to incorporate the stochastic information of future requests at each decision epoch of the rolling horizon framework, in contrast to the MA in which dynamic decisions are made based on deterministic information only. The implementation of the AA for a synchromodal matching system is shown in Algorithm 1. Before the planning horizon, the system applies the preprocessing of feasible path to get the set of feasible paths. At each decision epoch of the rolling horizon framework, the system generates scenarios of future requests by randomly sampling from their probability distributions, applies the preprocessing procedure to obtain feasible matches for active requests and sampled requests, utilizes a sample average approximation method presented in Sect. 4.2.1 to get deterministic formulations, and utilizes a progressive hedging algorithm presented in Sect. 4.2.2 to generate solutions. The state of the system is updated based on the decisions made for requests \(R^t\). Then the system is rolled forward to obtain the decisions for the next stage.
Sample average approximation method
The sample average approximation method is an approach to solve stochastic optimization problems by generating scenarios. In this technique, the expected objective function is approximated by a sample average estimate derived from a random sample (Verweij et al. 2003). At decision epoch t, a sample \(\{\omega ^1,\omega ^2,...,\omega ^{\gamma },...,\omega ^{\varGamma }\}\) of \(\varGamma\) scenarios is generated by randomly sampling from the probability distributions of spot requests \(\{\pi _o,\pi _d,\pi _u,\pi _{t^{\mathrm {announce}}},\pi _{t^{\mathrm {release}}},\pi _{t^{\mathrm {due}}},\pi _{t^{\mathrm {expire}}}\}\). For companies that do not have accurate probability distributions, scenarios can also be sampled randomly from their historical operational data. Each scenario includes a realization of shipment requests from stage \(t+1\) to stage \(t+H\), \(\omega ^{\gamma }=\{\omega ^{\gamma (t+1)},\omega ^{\gamma (t+2)},...,\omega ^{\gamma (t+H)}\}\). Here, H is the prediction horizon that is just long enough to obtain good decisions at stage t. The expected cost over the prediction horizon is approximated by the sample average function \(\frac{1}{\varGamma }\sum _{\gamma =1}^{\varGamma }\sum _{k=t+1}^{t+H}\sum _{r \in \omega ^{\gamma k}}\sum _{p \in P_r} c_{rp}z_{rp}^{{\gamma }k}\), which is an unbiased estimator of future costs as the sample size \(\varGamma\) goes to infinity and the prediction horizon \(t+H=T\) (Ruszczyński and Shapiro 2003). We define K as the set of predicted time stages at stage t, \(K=\{t+1,...,\min \{t+H,T\}\}, \forall t \in \{0,1,...,T1\}\); \(K=\emptyset \ \mathrm {when} \ t=T\). Let \(z_{rp}^{\gamma k}\) be the binary variable which equals to 1 if request \(r\in \omega ^{\gamma k}\) is matched with path \(p \in P\) under scenario \(\gamma \in \{1,..,\varGamma \}\) at stage \(k \in K\). The formulation of the DSSM problem at stage t changes to:
subject to Constraints (2–3, 5–7),
In formulation \(\mathbf{P2}\), \(x^t\) and \(y^t\) are firststage decisions which do not depend on the scenarios, \(z^{t}\) is the secondstage decision which depends on the corresponding scenarios. However, only \(x^t\) will be implemented at each decision epoch, \(y^t\) and \(z^{t}\) will be released after the optimization.
Progressive hedging algorithm
Formulation \(\mathbf{P2}\) is a largescale deterministic binary integer program which is nonconvex and highly complex to solve. In this section, we apply the progressive hedging algorithm (PHA) to solve the formulation. The PHA is first proposed by Rockafellar and Wets (1991) and has been implemented in many applications, such as stochastic network design problems (Crainic et al. 2014) and stochastic resource allocation problems (Watson and Woodruff 2010). It is a horizontal decomposition method which decomposes \(\mathbf{P2}\) by scenarios rather than by time stages, and iteratively solves penalized version of the scenariobased subproblems to gradually enforce implementability (also called nonanticipativity) (Gade et al. 2016).
In \(\mathbf{P2}\), the condition that the firststage decisions \(x^t\), \(y^t\) must not depend on the realization of random variables is implicit. In the PHA scheme, we write the nonanticipativity constraints explicitly. We define \(x_{rp}^{t\gamma }\) as the binary variable which equals to 1 if request \(r \in R^t\) is matched with path \(p \in P\) under scenario \(\gamma\), \(y_{rp}^{t\gamma }\) as the binary variable which equals to 1 if request \(r \in {\bar{R}}^t \backslash R^t\) is matched with path \(p \in P\) under scenario \(\gamma\). Let \({\bar{x}}^{t}\) and \({\bar{y}}^t\) be the ‘overall design vector’. The DSSM problem is then reformulated as:
subject to
Constraints (17–18) are the nonanticipatory constraints which stipulate that in all feasible solutions, the firststage decisions are not allowed to depend on scenarios. Therefore, the newly added variables do not affect the optimal solution, and thus P3 is equivalent to P2.
Following the PHA scheme, we drop off the constant coefficient \(\varGamma ^{1}\), and move the nonanticipativity constraints (17–18) into the objective function based on augmented Lagrangian strategy, which yields the objective function as follows:
subject to Constraints (13–16, 19–22).
In formulation P4, \(\lambda _{rp}^{t\gamma }\) and \({\tilde{\lambda }}_{rp}^{t\gamma }\) are Lagrangian multipliers, \(\rho _{rp}^{t\gamma }\) and \({\tilde{\rho }}_{rp}^{t\gamma }\) are penalty factors. Given the binary requirements for variables \(x^t, y^t, {\bar{x}}^t, {\bar{y}}^t\), the objective function can be further formulated as:
subject to Constraints (13–16, 19–22).
For a given overall design \({\bar{x}}^t\), \({\bar{y}}^t\), the relaxed formulation P5 is separable on a scenario basis. As it contains \(\varGamma\) scenarios, it can be broken down into \(\varGamma\) individual subproblems. An arbitrary subproblem indexed by \(\gamma \in \{1,...,\varGamma \}\) by dropping constant terms has the following form:
subject to
Formulation \(\mathbf{P6}\) is a scenariobased binary integer program which can be solved by using commercial solvers within an acceptable computational time, such as CPLEX. For a given scenario subproblem \(\gamma\), the Lagrangian multiplier \(\lambda _{rp}^{t\gamma }\) (\({\tilde{\lambda }}_{rp}^{t\gamma }\)) and the penalty parameter \(\rho _{rp}^{t\gamma }\) (\({\tilde{\rho }}_{rp}^{t\gamma }\)) contribute to penalize the difference in terms of values between the local variable \(x_{rp}^{t\gamma }\) (\(y_{rp}^{t\gamma }\)) and the current overall design \({\bar{x}}_{rp}^{t}\) (\({\bar{y}}_{rp}^{t}\)).
The pseudocode of the PHA at each decision epoch is shown in Algorithm 2. Each iteration of the PHA involves an optimization (Step 2) for scenariobased subproblems, an aggregation (Step 3) which corresponds to a projection of the individual scenario solutions onto the subspace of nonanticipative policies, a termination criteria (Step 4) to make sure the algorithm converges to within a tolerance, and a modification (Step 5) to update multipliers.
The key to success in implementing the PHA under a rolling horizon framework is to choose a proper \(\rho\)value to avoid slow convergence. However, in the literature, there are no conclusive results on the selection of \(\rho\)value. In this paper, we choose the \(\rho\) in proportion to the matching cost of the associated request and path, namely \(\rho ^t_{rp}=\alpha c_{rp}\) for \(r\in R^t\), \(p\in P\). This method will be evaluated in the experiments in comparison to a commonly used method in container transportation \(\rho ^{n+1}=\alpha \rho ^n\) (Crainic et al. 2011; Dong et al. 2015).
Numerical experiments
In this section, we evaluate the performance of the anticipatory approach (AA) on the DSSM problem in comparison to the myopic approach (MA) proposed by Guo et al. (2020) and the commonly used greedy approach (GA) in the container transport industry (van Riessen et al. 2016). The GA is sometimes also referred to as a first come first served approach (Meng et al. 2019). Under the GA, a shipment request is assigned to the cheapest feasible path at the time of request arrival. To provide a theoretical lower bound of the AA, we also report the optimal solutions obtained when all the input information is known beforehand. The approaches are implemented in MATLAB, and all experiments are executed on 3.70 GHz Intel Xeon processors with 32 GB of RAM. The optimization problems are solved with CPLEX 12.6.3.
Experimental setup
In this paper, we use the hinterland synchromodal network designed by Guo et al. (2020) for the numerical experiments, which includes 3 deepsea terminals in the port of Rotterdam (i.e., node 1, 2, and 3) and 7 inland terminals in the Netherlands, Belgium, and Germany (i.e., node 4, 5, 6, 7, 8, 9, and 10), as shown in Fig. 3. The network consists of 116 services, including 49 barge services, 33 train services, and 34 truck services. The detailed information of the services is presented in the Appendix.
We generate several instances to represent different characteristics of shipment requests within a given planning horizon. Each shipment request is characterized by its origin, destination, container volume, announce time, release time, expiry date, and due time. We assume that:

the origins of shipments are independent and identically distributed among \(\{1,2,3\}\) with probabilities \(\{0.66,0.2,0.14\}\); the destinations of shipments are independent and identically distributed among \(\{4,5,6,7,8,9,10\}\) with probabilities \(\{0.306,0.317,0.153,0.076,0.071,0.034,0.043\}\);

the container volumes of shipment requests which arrive before the planning horizon (i.e., contractual requests) are drawn independently from a uniform distribution with range [10, 30], the average container volume of contractual requests \(U_1^{\mathrm {AVE}}=20\); the container volumes of spot requests are drawn independently from uniform distributions with range [1, 9], the average container volume of spot requests \(U_2^{\mathrm {AVE}}=5\);

the announce time of contractual requests is 0, while the frequency of spot requests arriving in the system belongs to Poisson distributions with mean \(AT^{\mathrm {AVE}}\);

the release time of contractual requests is drawn independently from a uniform distribution with range [1, 120]; the release time of spot requests is generated based on its announce time, \(t_{r}^{\mathrm {release}}=\lceil t_{r}^{\mathrm {announce}} \rceil +\varDelta T\), \(\varDelta T\) belongs to a uniform distribution with range [1, 6]; the expiry date is equal to the release time;

the due time of shipment requests is generated based on its release time and lead time, \(t_{r}^{\mathrm {due}}=t_{r}^{\mathrm {release}}+LD_r\), the lead time of shipments is independent and identically distributed among \(\{24,48,72\}\) (unit: hours) with probabilities \(\{0.15,0.6,0.25\}\). The delay cost coefficients of shipments with lead time 24, 48, and 72 h are 100, 70, and 50 €/hTEU, respectively.
We use \(\mathrm {EU}n_1n_2\) to represent an instance with \(n_1\) contractual requests and \(n_2\) spot requests. We set \(AT^{\mathrm {AVE}}\) to 20, 10, 6, 5, and 4 min (i.e., about 0.33, 0.17, 0.1, 0.08, and 0.07 h per request) for instances EU300400, EU200800, EU1001200, EU501400, and EU01600, respectively, as shown in Fig. 4. We define the degree of dynamism as the ratio between the number of containers from spot requests and the total number of containers, namely, degree of dynamism=\(\frac{n_2*U_2^{\mathrm {AVE}}}{n1*U_1^{\mathrm {AVE}}+n2*U_2^{\mathrm {AVE}}}\). Therefore, the degrees of dynamism for instances EU300400, EU200800, EU1001200, EU501400, and EU01600 are 25%, 50%, 75%, 87.5%, and 100%, respectively.
The length of the planning horizon is set to 168 h for all the instances. The length of the optimization interval is set to 1 h in the MA and the AA. At each decision epoch of the AA, a sample is generated randomly based on the probability distributions presented above. In case of sample instability, for each instance, we replicate the optimization process 10 times under the AA.
Impact of the degree of dynamism
To test the influence of the degree of dynamism, we set the number of scenarios to 10, and the length of prediction horizon to 12 h. We use ‘gaps in total costs’ as the performance indicator which is given by (benchmark value  objective value)/benchmark value. Here, the total cost generated by the MA is the benchmark value, while the total cost generated by the AA is the objective value. Therefore, the higher the ‘gaps in total costs’, the better the performance of the AA in reducing total costs. Fig. 5 shows that the AA has better performance than the MA in all the instances in reducing total costs, and the gap between the AA and the MA grows with the increasing of the degree of dynamism from 25% to 87.5%. Nevertheless, further increasing the degree of dynamism to 100%, the gap in total costs stays around 4%.
Impact of the number of scenarios and the length of prediction horizon
With regards to the number of scenarios, we set the degree of dynamism to 87.5% (i.e., instance EU501400), and the length of prediction horizon to 12 h. The number of scenarios is varied from 1 to 30. Figure 6a shows that increasing the number of scenarios, the gap in total costs between the AA and the MA becomes larger. The reason is that the larger the number of scenarios, the more accurate the representation of the future. On the other hand, we set the number of scenarios to 10, and vary the length of prediction horizon from 1 to 24 h for instance EU501400. Figure 6b shows that the length of prediction horizon has high influences on the performance of the AA in reducing total costs. The longer the prediction horizon, the more the stochastic information of future requests will be considered. The system thus reserves capacities for predicted future requests which are more ‘valuable’. In turn, the performance of the system over the planning horizon becomes better.
Impact of the selection of \(\rho\)value
To test the impact of the selection of \(\rho\)value, we design 10 instances with different number of requests, different number of scenarios and different length of prediction horizon. The proposed cost proportional method (i.e., \(\rho _{rp}=\alpha c_{rp}\)) is evaluated in comparison to the typical iterative method (i.e., \(\rho ^{n+1}={\hat{\alpha }} \rho ^n\)). We set \(\alpha =1, {\hat{\alpha }}=1.1, \rho ^0=1\). Table 3 shows that the costs generated by these two methods are almost the same in all the instances. However, the number of iterations (i.e., N. Iteration) and the computation time (i.e., CPU) under the typical iterative method are way much higher than the cost proportional method. The larger the number of scenarios and the length of prediction horizon, the higher the gaps between these two methods. We also notice that the CPU increases dramatically with the increase of shipment requests under the typical iterative method. In comparison, all these instances can be solved by the cost proportional method within 20 s. With the cost proportional method, the PHA can be implemented under a rolling horizon framework to provide timely solutions at each decision epoch.
Comparison between the GA, the MA, and the AA
In this section, we test the performance of the AA in comparison to the MA and the GA. While the result obtained from the GA provides an upper bound of the AA, we use the solutions obtained when all the input information is known in advance as the theoretical lower bounds. Specifically, we assume all the contractual and spot requests are received before the planning horizon, which gives rise to an optimization problem that includes all the shipments and services. Due to the computational complexity, the problem is solved by the heuristic algorithm designed in Guo et al. (2020). We set \(\varGamma =100, H=48, N^{\mathrm {iteration}}=100, \alpha =1, \eta =0.001\) for the AA. The comparison between the GA, the MA, and the AA is shown in Table 4. We consider three performance indicators: the total costs (€), the ave. CPU (s), and the improvements. The ave. CPU of the GA, the MA, and the AA is the average computation time per stage over the planning horizon (i.e., 168 time stages). Although the AA needs to solve a large number of subproblems at each decision epoch due to the iteration of Lagrangian multipliers, applying the parallel computing techniques enables to use multiple CPUs to solve the subproblems in a single iteration of the AA simultaneously. We use the results obtained from the GA as the benchmark, the improvements between the MA/AA and the GA are given by (benchmark value  objective value)/benchmark value. Table 4 shows that the AA outperforms the GA and the MA in all the instances. While the MA has average improvements of about 2.37% in comparison to the GA, the AA has average improvements of about 6.12%. Impressively, we notice that with the designed AA, the gap between the AA and the theoretical lower bounds is no more than 2.65% on average.
Conclusions and future research
In this paper, we introduced a dynamic and stochastic shipment matching (DSSM) problem in hinterland synchromodal transportation. The problem is considered dynamic since spot requests arrive in the system in realtime. The problem is considered stochastic since the information of spot requests is not known with certainty. To solve the problem, we developed an anticipatory approach (AA) which uses a sample average approximation method to address spot request uncertainties and a progressive hedging algorithm to generate solutions at each decision epoch of a rolling horizon framework.
We validated the performance of the AA on the DSSM problem in comparison with the myopic approach (MA) proposed by Guo et al. (2020) in which dynamic decisions are made based on deterministic information only and the greedy approach (GA) which is commonly used in practice. The experimental results indicate that the AA outperforms the GA and the MA in all the instances of the synchromodal matching system. Compared with the GA, the AA has total cost savings up to 8.18%.
From a managerial viewpoint, with the proposed AA, the utilization of barges, trains, and trucks can be managed more efficiently by taking into account the timesensitivity of current received requests and the predicted future requests. Besides, the proposed approach enables the decision makers to dynamically update the decisions of the previously received shipments when the newly received ones can be better served with the previously matched services. This increases the adaptive nature of transport systems to meet today’s environment. Furthermore, the experimental results show that the more the stochastic information is incorporated, the better the performance of the AA. However, the computational complexity increases with the increase of stochastic information. To implement such an approach in practice, the tradeoff between solution quality and computational complexity must be considered.
Future research can be conducted under three directions. First, due to the capacity limitation of road infrastructures, the number of trucks is limited in a synchromodal network. Therefore, the rejection of shipment requests can be considered in the online matching processes to avoid infeasible solutions. Another research direction is to investigate the benefits of incorporating ad hoc services (i.e., dynamic services). Considering the excess capacity of services from carriers, the online matching of contractual requests, spot requests, dedicated services, and ad hoc services gives rise to a new variant of the dynamic shipment matching problem in synchromodal transportation. Third, due to the existence of traffic congestion and terminal congestion in synchromodal transportation, travel time of services and transfer time at terminals are usually uncertain. Combining multiple uncertainties in dynamic shipment matching is a promising research direction.
References
AlbaredaSambola M, Fernández E, Laporte G (2014) The dynamic multiperiod vehicle routing problem with probabilistic information. Comput Oper Res 48:31–39. https://doiorg.libproxy.viko.lt/10.1016/j.cor.2014.02.010
Arslan AM, Agatz N, Kroon L, Zuidwijk R (2019) Crowdsourced delivery—a dynamic pickup and delivery problem with ad hoc drivers. Transp Sci 53(1):222–235. https://doiorg.libproxy.viko.lt/10.1287/trsc.2017.0803
Ayar B, Yaman H (2011) An intermodal multicommodity routing problem with scheduled services. Comput Optim Appl 53(1):131–153. https://doiorg.libproxy.viko.lt/10.1007/s105890119409z
Chang TS (2008) Best routes selection in international intermodal networks. Comput Oper Res 35(9):2877–2891. https://doiorg.libproxy.viko.lt/10.1016/j.cor.2006.12.025
Crainic TG, Fu X, Gendreau M, Rei W, Wallace SW (2011) Progressive hedgingbased metaheuristics for stochastic network design. Networks 58(2):114–124. https://doiorg.libproxy.viko.lt/10.1002/net.20456
Crainic TG, Hewitt M, Rei W (2014) Scenario grouping in a progressive hedgingbased metaheuristic for stochastic network design. Comput Oper Res 43:90–99. https://doiorg.libproxy.viko.lt/10.1016/j.cor.2013.08.020
Crainic TG, Perboli G, Rosano M (2018) Simulation of intermodal freight transportation systems: a taxonomy. Eur J Oper Res 270(2):401–418. https://doiorg.libproxy.viko.lt/10.1016/j.ejor.2017.11.061
Demir E, Burgholzer W, Hrušovský M, Arıkan E, Jammernegg W, Woensel TV (2016) A green intermodal service network design problem with travel time uncertainty. Transp Res Part B Methodol 93:789–807. https://doiorg.libproxy.viko.lt/10.1016/j.trb.2015.09.007
Dong JX, Lee CY, Song DP (2015) Joint service capacity planning and dynamic container routing in shipping network with uncertain demands. Transp Res Part B Methodol 78:404–421. https://doiorg.libproxy.viko.lt/10.1016/j.trb.2015.05.005
Gade D, Hackebeil G, Ryan SM, Watson JP, Wets RJB, Woodruff DL (2016) Obtaining lower bounds from the progressive hedging algorithm for stochastic mixedinteger programs. Math Program 157(1):47–67. https://doiorg.libproxy.viko.lt/10.1007/s101070161000z
Gendreau M, Jabali O, Rei W (2016) 50th anniversary invited article—future research directions in stochastic vehicle routing. Transp Sci 50(4):1163–1173. https://doiorg.libproxy.viko.lt/10.1287/trsc.2016.0709
Giusti R, Manerba D, Bruno G, Tadei R (2019) Synchromodal logistics: an overview of critical success factors, enabling technologies, and open research issues. Transp Res Part E Logist Transp Rev 129:92–110. https://doiorg.libproxy.viko.lt/10.1016/j.tre.2019.07.009
Guo W, Atasoy B, van Blokland WB, Negenborn RR (2020) A dynamic shipment matching problem in hinterland synchromodal transportation. Decis Support Syst 134:113289. https://doiorg.libproxy.viko.lt/10.1016/j.dss.2020.113289
Hrušovský M, Demir E, Jammernegg W, Woensel TV (2016) Hybrid simulation and optimization approach for green intermodal transportation problem with travel time uncertainty. Flex Serv Manuf J 30(3):486–516. https://doiorg.libproxy.viko.lt/10.1007/s1069601692671
Ichoua S, Gendreau M, Potvin JY (2003) Vehicle dispatching with timedependent travel times. Eur J Oper Res 144(2):379–396. https://doiorg.libproxy.viko.lt/10.1016/s03772217(02)001479
Li L, Negenborn RR, Schutter BD (2015) Intermodal freight transport planning—a receding horizon control approach. Transp Res Part C Emerg Technol 60:77–95. https://doiorg.libproxy.viko.lt/10.1016/j.trc.2015.08.002
Meng Q, Zhao H, Wang Y (2019) Revenue management for container liner shipping services: critical review and future research directions. Transp Res Part E Logist Transp Rev 128:280–292. https://doiorg.libproxy.viko.lt/10.1016/j.tre.2019.06.010
Mes MRK, Iacob ME (2015) Synchromodal transport planning at a logistics service provider. In: Logistics and supply chain innovation. Springer, pp 23–36. https://doiorg.libproxy.viko.lt/10.1007/9783319222882_2
Moccia L, Cordeau JF, Laporte G, Ropke S, Valentini MP (2010) Modeling and solving a multimodal transportation problem with flexibletime and scheduled services. Networks 57(1):53–68. https://doiorg.libproxy.viko.lt/10.1002/net.20383
Najmi A, Rey D, Rashidi TH (2017) Novel dynamic formulations for realtime ridesharing systems. Transp Res Part E Logist Transp Rev 108:122–140. https://doiorg.libproxy.viko.lt/10.1016/j.tre.2017.10.009
Ritzinger U, Puchinger J, Hartl RF (2015) A survey on dynamic and stochastic vehicle routing problems. Int J Prod Res 54(1):215–231. https://doiorg.libproxy.viko.lt/10.1080/00207543.2015.1043403
Rivera AEP, Mes MR (2017) Anticipatory freight selection in intermodal longhaul roundtrips. Transp Res Part E Logist Transp Rev 105:176–194. https://doiorg.libproxy.viko.lt/10.1016/j.tre.2016.09.002
Rockafellar RT, Wets RJB (1991) Scenarios and policy aggregation in optimization under uncertainty. Math Oper Res 16(1):119–147. https://doiorg.libproxy.viko.lt/10.1287/moor.16.1.119
Ruszczyński A, Shapiro A (2003) Stochastic programming models. In: Handbooks in operations research and management science. Elsevier, pp 1–64. https://doiorg.libproxy.viko.lt/10.1016/s09270507(03)100011
Schilde M, Doerner K, Hartl R (2011) Metaheuristics for the dynamic stochastic dialaride problem with expected return transports. Comput Oper Res 38(12):1719–1730. https://doiorg.libproxy.viko.lt/10.1016/j.cor.2011.02.006
SteadieSeifi M (2017) Multimodal transportation for perishable products. PhD thesis, Technische Universiteit Eindhoven
SteadieSeifi M, Dellaert N, Nuijten W, Woensel TV, Raoufi R (2014) Multimodal freight transportation planning: a literature review. Eur J Oper Res 233(1):1–15. https://doiorg.libproxy.viko.lt/10.1016/j.ejor.2013.06.055
Sun Y, Hrušovský M, Zhang C, Lang M (2018) A timedependent fuzzy programming approach for the green multimodal routing problem with rail service capacity uncertainty and road traffic congestion. Complexity 2018:1–22. https://doiorg.libproxy.viko.lt/10.1155/2018/8645793
van Heeswijk WJA, Mes MRK, Schutten JMJ, Zijm WHM (2016) Freight consolidation in intermodal networks with reloads. Flex Serv Manuf J 30(3):452–485. https://doiorg.libproxy.viko.lt/10.1007/s1069601692591
van Riessen B, Negenborn RR, Lodewijks G, Dekker R (2014) Impact and relevance of transit disturbances on planning in intermodal container networks using disturbance cost analysis. Marit Econ Logist 17(4):440–463. https://doiorg.libproxy.viko.lt/10.1057/mel.2014.27
van Riessen B, Negenborn RR, Dekker R (2016) Realtime container transport planning with decision trees based on offline obtained optimal solutions. Decis Support Syst 89:1–16. https://doiorg.libproxy.viko.lt/10.1016/j.dss.2016.06.004
Verweij B, Ahmed S, Kleywegt AJ, Nemhauser G, Shapiro A (2003) The sample average approximation method applied to stochastic routing problems: a computational study. Comput Optim Appl 24(2/3):289–333. https://doiorg.libproxy.viko.lt/10.1023/a:1021814225969
Wang X, Kopfer H (2015) Rolling horizon planning for a dynamic collaborative routing problem with fulltruckload pickup and delivery requests. Flex Serv Manuf J 27(4):509–533. https://doiorg.libproxy.viko.lt/10.1007/s1069601592128
Wang Y, Meng Q (2021) Optimizing freight rate of spot market containers with uncertainties in shipping demand and available ship capacity. Transp Res Part B Methodol 146:314–332. https://doiorg.libproxy.viko.lt/10.1016/j.trb.2021.02.008
Watson JP, Woodruff DL (2010) Progressive hedging innovations for a class of stochastic mixedinteger resource allocation problems. CMS 8(4):355–370. https://doiorg.libproxy.viko.lt/10.1007/s1028701001254
Yang J, Jaillet P, Mahmassani H (2004) Realtime multivehicle truckload pickup and delivery problems. Transp Sci 38(2):135–148. https://doiorg.libproxy.viko.lt/10.1287/trsc.1030.0068
Acknowledgements
This research is supported by the China Scholarship Council under Grant 201606950003, the project “Complexity Methods for Predictive Synchromodality” (Project 439.16.120) of the Netherlands Organisation for Scientific Research (NWO), and the Natural Sciences and Engineering Council of Canada (NSERC) through its Cooperative Research and Development Grants Program.
Author information
Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Ethical approval
This article does not contain any studies with human participants or animals performed by any of the authors.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix
Appendix
The detailed information of barge, train and truck services is presented in Tables 5, 6 and 7. The barge and train connections are derived from European Gateway Services (http://www.europeangatewayservices.com/en/). We assume there exists truck connections between all the terminals. The distance of services used in this paper is obtained from European Gateway Services, InlandLinks (https://www.inlandlinks.eu/en), and Google maps.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Guo, W., Atasoy, B., van Blokland, W.B. et al. Anticipatory approach for dynamic and stochastic shipment matching in hinterland synchromodal transportation. Flex Serv Manuf J 34, 483–517 (2022). https://doiorg.libproxy.viko.lt/10.1007/s10696021094285
Accepted:
Published:
Issue Date:
DOI: https://doiorg.libproxy.viko.lt/10.1007/s10696021094285
Keywords
 Synchromodal transportation
 Dynamic shipment matching
 Stochastic spot requests
 Anticipatory approach