Preference-Based Multi-Objective Optimization for Synchromodal Transport Using Adaptive Large Neighborhood Search

Literature Review

This paper studies transshipment, synchronization, and preferences-based multi-objective optimization in ST. Therefore, the presented literature review focuses on these three distinctive aspects as well as literature that studies multi-objective optimization for intermodal transport.

MOO for Intermodal Transport

Two types of problems are considered in the literature. The service network design problem relates to choosing services and optimizing vehicle frequencies in the transport network. Route optimization involves the planning decisions of routes and modes. The methods for solving MOO used in different studies are different. Table 1 provides a summary of models in the literature to position the present work. As mentioned above, the vehicle routing component has many benefits; taking synchronization into account is conducive to making full use of limited resources, and considering preferences is important to solve the conflicts among objectives. However, vehicle routing, synchronization, and preferences are rarely considered in the literature and these are the core contributions of this paper. Furthermore, an ALNS algorithm is used to solve the problem, and the procedures within ALNS are tailored to be specific to the synchromodal case which is another distinction of this paper.

OPEN IN VIEWER

Table 1.

Comparison of Models in the Literature

Article	Problem definition	Objectives	Vehicle routing	Synchronization	Preferences	Solution method
Kalinina et al. ( 3 )	SND	c, e, t	×	×	×	ε
Xiong and Wang ( 26 )	RO	c, t	×	×	×	GA
Baykasoglu and Subulan ( 27 )	SND	c, e, t	×	×	✓	CP, FGP
Ji and Luo ( 28 )	SND	c, t	×	×	×	HEDA
Mnif and Bouamama ( 29 )	SND	c, t	×	×	×	FA
Chen et al. ( 30 )	RO	c, t, cc	×	×	×	NNCM
This paper	RO	c, e, t	✓	✓	✓	ALNS

Note: c = cost; e = emission; t = time; cc = container usage cost; RO = route optimization; SND = service network design; GA = genetic algorithm; FA = firework algorithm; HEDA = hybrid estimation of distribution algorithm; NNCM = normalized normal constraint method; ε  =  ε -constraint method; CP = compromise programming; FGP = fuzzy goal programming approach.

Problem Description

The main research question of this study is: How can ST be optimized according to the preferences of the carrier? To answer this research question, three key research problems need to be solved, as shown in Figure 2:

Solving Problem 1 (P1) is the basis for solving Problem 2 (P2) and Problem 3 (P3). All methods for these problems are used to establish the preference-based MOO model for ST, which will be used to obtain attractive solutions for DMs.

OPEN IN VIEWER

Figure 2.

Key research problems in this study.

Mathematical Model

The notations of the mathematical model are given in Table 2. A MOO model for the PDPT in ST is given by Equations 1–32 as described below. Three objectives, that is, minimizing cost, emissions, and time, are considered, as Equations 1–3 show. The cost objective consists of transportation cost of containers, fuel cost, transshipment cost, and cost associated with waiting, service, and transshipment time. “Emissions” in this paper refers to CO₂ emissions. There are different ways to calculate such emissions in the literature ( 31 ), and the activity-based method is one of the popular methods because activity data is easier to obtain compared with other methods ( 32 , 33 ). Therefore this work uses the activity-based method and calculation of CO₂ emissions based on vehicle type, distance, and amount of containers ( 34 ). For different modes the emissions factor e k is different and detailed data are shown in the Case Study section. The time objective includes the time on the route and waiting time at terminals. Because this paper considers vehicle, container routing, and transshipment, both vehicle and container flows are modeled and transshipment constraints are designed, which are illustrated in detail in Equations 4–32.

min F cost = ∑ k ∈ K ∑ ( i , j ) ∈ A ∑ r ∈ R ( c k 1 d ij + c k 2 τ ij ) y ij kr q r + ∑ k ∈ K ∑ ( i , j ) ∈ A ( c k 3 d ij x ij k + c k 4 ( t ¯ i k − t i k ) ) + ∑ k , l ∈ K , k ≠ l ∑ r ∈ R ∑ i ∈ T c k 5 q r s ir kl + ∑ k ∈ K ∑ ( i , j ) ∈ A ∑ r ∈ R c k 6 e k y ij kr q r d ij / 1000

(1)

min F emissions = ∑ k ∈ K ∑ ( i , j ) ∈ A ∑ r ∈ R e k y ij kr q r d ij

(2)

min F time = ∑ k ∈ K ∑ ( i , j ) ∈ A τ ij x ij k + ∑ k ∈ K ∑ ( i , j ) ∈ A ( t ¯ i k − t i k )

(3)

OPEN IN VIEWER

Table 2.

Notation Used in the Model

Sets
R	Set of requests
K	Set of vehicles
N	Set of terminals
A	Set of arcs. For i , j ∈ N , the arc from i to j is denoted by ( i , j ) ∈ A
T ⊆ N	Set of transshipment terminals
o ( k ) / o ′ ( k ) ⊆ N	Initial/final depot of vehicle k ∈ K
p ( r ) / d ( r ) ⊆ N	Pickup/delivery terminal of request r ∈ R
Variables
x ij k	Binary variable; 1 if vehicle k ∈ K uses the arc ( i , j ) ∈ A , 0 otherwise
y ij kr	Binary variable; 1 if request r ∈ R transported by vehicle k uses arc ( i , j ) ∈ A , 0 otherwise
z ij k	Binary variable; 1 if terminal i ∈ N precedes (not necessarily immediately) terminal j ∈ N in the route of the vehicle k ∈ K , 0 otherwise
s ir kl	Binary variable; 1 if request r ∈ R is transferred from vehicle k ∈ K to vehicle l ≠ k at node i ∈ N , 0 otherwise
t i k / t ¯ i k	The arrival/departure time of vehicle k ∈ K at terminal i ∈ N
t ′ i k	The service start time of vehicle k ∈ K at terminal i ∈ N
Parameters
u k	Capacity (TEU) of vehicle k ∈ K
e k	Emissions (kg) per km/TEU of vehicle k ∈ K
q r	Quantity (TEU) of request r ∈ R
τ ij k	The transportation time (in hours) on arc ( i , j ) ∈ A for vehicle k ∈ K
[ a p ( r ) , b p ( r ) ]	The pickup time window for request r ∈ R
[ a d ( r ) , b d ( r ) ]	The delivery time window for request r ∈ R
t ″ i k / t ′″ i k	The transshipment/service time (in hours) for vehicle k ∈ K at terminal i ∈ N
v k	Speed (km/h) of vehicle k ∈ K . The upstream speed and downstream speed for a same barge are different
d ij	Distance (km) between terminal i ∈ N and j ∈ N
c k 1 − 6	c k 1 / c k 2 are unit (one container) cost (euro) of transportation per km/hour using k ∈ K . c k 3 is the fuel cost per km of vehicles. c k 4 is the cost per hour of waiting time, transshipment time, and service time at a terminal. c k 5 is the transshipment cost per container. c k 6 is the carbon tax coefficient per ton

Constraints (4)–(21) are the spatial constraints. Constraints (4)–(11) are typical constraints in PDP. Constraints (4) and (5) ensure that a vehicle begins and ends at its begin and end depot, respectively. Constraints (6) and (7) ensure that containers for each request must be picked and delivered at its pick up and delivery terminal, respectively. Constraints (8)–(10) are the subtour elimination constraints, which provide tight bounds among several polynomial-size versions of subtour elimination constraints ( 35 ). Constraint (11) is the capacity constraint.

∑ j ∈ N x ij k ≤ 1 ∀ k ∈ K , ∀ i = o ( k )

(4)

∑ j ∈ N x ij k = ∑ j ∈ N x jl k ∀ k ∈ K , ∀ i = o ( k ) , ∀ l = o ′ ( k )

(5)

∑ k ∈ K ∑ j ∈ N y ij kr = 1 ∀ r ∈ R , ∀ i = p ( r )

(6)

∑ k ∈ K ∑ j ∈ N y ji kr = 1 ∀ r ∈ R , ∀ i = d ( r )

(7)

x ij k ≤ z ij k ∀ i , j ∈ N , ∀ k ∈ K

(8)

z ij k + z ji k = 1 ∀ i , j ∈ N , ∀ k ∈ K

(9)

z ij k + z jl k + z li k ≤ 2 ∀ i , j , l ∈ N , ∀ k ∈ K

(10)

∑ r ∈ R q r y ij kr ≤ u k x ij k ∀ ( i , j ) ∈ A , ∀ k ∈ K

(11)

Flow conservation constraints of both vehicles and requests are handled by Constraints (12)–(15). Constraint (12) represents flow conservation for vehicle flow and (13)–(14) represent flow conservation for request flow. Constraint (13) is for transshipment terminals, and Constraint (14) is for regular terminals. Constraint (15) links y and x variables to guarantee that, for a request to be transported by a vehicle, that vehicle needs to be traversing the associated arc.

∑ j ∈ N x ij k − ∑ j ∈ N x ji k = 0 ∀ k ∈ K , ∀ i ∈ N \ o ( k ) , o ′ ( k )

(12)

∑ k ∈ K ∑ j ∈ N y ij kr − ∑ k ∈ K ∑ j ∈ N y ji kr = 0 ∀ r ∈ R , ∀ i ∈ T \ p ( r ) , d ( r )

(13)

∑ j ∈ N y ij kr − ∑ j ∈ N y ji kr = 0 ∀ k ∈ K , ∀ r ∈ R , ∀ i ∈ N \ T , p ( r ) , d ( r )

(14)

y ij kr ≤ x ij k ∀ ( i , j ) ∈ A , ∀ k ∈ K , ∀ r ∈ R

(15)

Constraints (16)–(18) facilitate transshipment. Constraint (16) ensures that the transshipment occurs only once in the transshipment terminal. Furthermore, Constraints (17) and (18) allow the transshipment only when the request is transported by both vehicles k and l .

∑ j ∈ N y ji kr + ∑ j ∈ N y ij lr ≤ s ir kl + 1 ∀ r ∈ R , ∀ i ∈ T , ∀ k , l ∈ K , k ≠ l

(16)

s ir kl ≤ ∑ j ∈ N y ji kr ∀ r ∈ R , ∀ i ∈ T , ∀ k , l ∈ K , k ≠ l

(17)

s ir kl ≤ ∑ j ∈ N y ij lr ∀ r ∈ R , ∀ i ∈ T , ∀ k , l ∈ K , k ≠ l

(18)

Characteristics of ST are considered in Constraints (19)–(21). Constraint (19) avoids vehicles running on unsuitable routes, for example, trucks cannot run on inland waterways. Constraint (20) takes care of predefined routes for certain vehicles, for example, trains have fixed routes and terminals. Constraint (21) ensures the transshipment occurs in the right transshipment terminal, because some transshipment terminals only allow the transshipment between two specific modes. When containers need to be transferred from barges to trucks, terminals that only allow transshipment between barges and trains will not be considered.

x ij k = 0 ∀ k ∈ K mode ∀ ( i , j ) ∈ A \ A mode

(19)

x ij k = 0 ∀ k ∈ K certain ∀ ( i , j ) ∈ A \ A predefined

(20)

s jr kl = 0 ∀ k ∈ K mode 1 ∀ l ∈ K mode 2 , ∀ j ∈ T \ T mode 1 mode 2 , ∀ r ∈ R

(21)

Constraints (22)–(30) are the temporal constraints. Constraint (22) guarantees that the arrival time of vehicle is earlier than the service start time. Constraint (23) maintains that the departure happens only after the service is completed. Constraint (24) ensures that the time on the route is consistent with the distance traveled and speed, and that M is a large enough positive number. Constraints (25) and (26) take care of the time windows. These constraints give the possibility of waiting at terminals when a vehicle arrives earlier. Constraint (27) adds the service time of pickup and delivery.

t i k ≤ t ′ i k ∀ i ∈ N , ∀ k ∈ K

(22)

t ′ i k ≤ t ¯ i k ∀ i ∈ N , ∀ k ∈ K

(23)

t ¯ i k + τ ij k − t j k ≤ M ( 1 − x ij k ) ∀ ( i , j ) ∈ A , ∀ k ∈ K

(24)

a p ( r ) ≤ t ′ p ( r ) k , t ¯ p ( r ) k ≤ b p ( r ) ∀ r ∈ R , ∀ k ∈ K

(25)

a d ( r ) ≤ t ′ d ( r ) k , t ¯ d ( r ) k ≤ b d ( r ) ∀ r ∈ R , ∀ k ∈ K

(26)

t ′ p ( r ) / d ( r ) k + t ″ ′ p ( r ) / d ( r ) k = t ¯ p ( r ) / d ( r ) k ∀ r ∈ R , ∀ k ∈ K

(27)

Constraints (28)–(30) include time constraints for transshipment. If there is a transshipment from vehicle k to vehicle l , but vehicle l arrives before vehicle k departs, then Constraint (28) allows vehicle l to wait until vehicle k completes its unloading. Constraints (29) and (30) add transshipment time at the transshipment terminal.

t ¯ i k − t ′ i l ≤ M ( 1 − s ir kl ) ∀ r ∈ R , ∀ i ∈ T , ∀ k , l ∈ K , k ≠ l

(28)

t ¯ i k − t ′ i k = t ″ i k s ir kl ∀ r ∈ R , ∀ i ∈ T , ∀ k , l ∈ K , k ≠ l

(29)

t ¯ i l − t ′ i l = t ″ i l s ir kl ∀ r ∈ R , ∀ i ∈ T , ∀ k , l ∈ K , k ≠ l

(30)

Constraints (31) and (32) set variables x and y as binary variables.

x ij k ∈ { 0 , 1 } ∀ ( i , j ) ∈ A , ∀ k ∈ K

(31)

y ij kr ∈ { 0 , 1 } ∀ ( i , j ) ∈ A , ∀ k ∈ K , ∀ r ∈ R

(32)

With regard to complexity, there are a total of | N | 2 | K | x -variables and | N | 2 | K | | R | y -variables. In the worst case, | R | is bounded by | N | 2 . The total number of variables is bounded by O ( | N | 4 | K | ) .

Solution Methodology

This section solves the research problems one by one. First, to solve the PDPT, an ALNS approach is developed and the ALNS structure is described. Next, to make full use of available resources, the synchronization methods between vehicles/modes are proposed. Finally, to solve the conflicts between objectives and obtain preferred solutions, the weight interval method proposed by Szlapczynska and Szlapczynski ( 20 ) is used to add vague preferences to the MOO model. Note that both preferences and synchronization are incorporated into ALNS.

ALNS Algorithm

Solving the MOO problem to optimality by the exact approach often needs multiple runs for different objectives and a long computation time. In the authors’ previous work ( 12 ), Gurobi was used to solve a similar PDPT in inland waterway transport, and the results showed that it took more than 12 h when there were more than six requests. Therefore, heuristics are needed to solve MOO. ALNS has already been used for VRP successfully and it performs well on large-scale instances ( 11 , 14 , 16 ). The adaptive nature of ALNS, that is, choosing operators according to their past performances, is a significant advantage over other approaches. Therefore, ALNS is chosen for solving the optimization problem in this study.

ALNS was proposed in 2006 based on an extension of the large neighborhood search heuristic ( 36 ), and ALNS adopted an adaptive mechanism to make it robust in different scenarios. To solve the MOO problem and reduce the computation time, a preference-based ALNS is proposed, as shown in Algorithm 1. The input of the algorithm is vehicles information K and request information R , and the output is the non-dominated solution set X nd . R pool is a set of active requests that need to be inserted to routes. ALNS finds (near) optimal solutions by using removal and insertion operators. In the beginning, an initial solution X initial constructed by an insertion operator (such as Greedy Insertion used in this paper) is needed for the following iterations. If there are still active requests in R pool after using the Greedy Insertion operator, Random Removal and Greedy Insertion operators will be used alternately until R pool is empty. Then, ALNS searches solutions in a predefined number of iterations guided by objectives. At the beginning of every s iterations, the weights, that is, scores of past performance, of operators are refreshed and operators used in the next s iterations are chosen based on the weights. In each iteration, routes will be destroyed and repaired alternately until all requests are served, that is, a feasible solution is found. It is worth noting that the initial solution is obtained by using two operators, while the solutions in the following iterations are obtained using all operators with an adaptive mechanism.

OPEN IN VIEWER

Algorithm 1: ALNS algorithm for preference-based MOO

Input: K , R ; Output: X nd set X initial as empty routes of K ; set X and X nd as empty sets; R pool = R ; [ X initial , R pool ] = GreedyInsertion ( X initial , R pool ) ; while R pool is not empty do  [ X initial , R pool ] = RandomRemoval ( X initial ) ;  [ X initial , R pool ] = GreedyInsertion ( X initial , R pool ) ; end X last ← X initial ; Add X last to X ; repeat  refresh weights and choose operators at the beginning of every s iterations;   X current ← X last ; [ X current , R pool ] = RemovalOperator ( X current ) ; flag = False ;  While R pool is not empty do   if flag = = True then    [ X current , R pool ] = RemovalOperator ( X current )   else     flag = True   end   [ X current , R pool ] = InsertionOperator ( X current , R pool ) ;  end  if ∑ i = 1 n G i ( X current , X last ) > 0 then    X last ← X current  else    X last ← X current with probability p ;  end  Add X last to X ; Untila predefined number; for X in X do   nd = 1 // the solution is non-dominated solution when  for X ′ in X − X do   if ∑ i = 1 n G i ( X ′ , X ) > 0 then     nd = 0 ; break; // X is dominated by X’, break current loop   end  end  if nd = = 1 then   Add X to X nd ;  end end

At the end of the iteration, a decision is made whether to accept current solution X current obtained in this iteration by comparing it with the last solution X last obtained in the last iteration. If the current solution is worse than the last solution, it will be accepted with a probability p to avoid local optima more easily. Simulated annealing idea is used and probability p gradually declines to avoid local optima ( 36 ), as the following equation shows:

p = e ∑ i = 1 n G i ( X current , X last ) · ∑ n = 1 n F i ( X current ) T ,

(33)

where T > 0 is the temperature which starts from an initial temperature and gradually decreases in every iteration by cooling rate, c , where 0 < c < 1 . n is the number of objectives and F i ( X current ) is the i th objective of X current . ∑ i = 1 n G i ( X current , X last ) represents the dominance degree between X current and X last , which will be defined in Equation 38 when introducing the weight interval method.

After all solutions are obtained and stored in the solution set X , X nd is obtained by comparing all solutions through the dominance rule. X − X means the solution set without X .

The design of different operators is widely discussed in the literature ( 11 , 36– 39 ) as well as the authors’ previous paper ( 12 ). Besides traditional operators, including Greedy Insertion, Transshipment Insertion, Random Insertion, Worst Removal, and Random Removal operators, this work designs two customized operators, that is, Route Removal and Node Removal operators. The following introduces the customized operators in detail and the others are introduced briefly.

Greedy Insertion operator tries all possible solutions using one vehicle and more than one vehicle and inserts the request into the best route(s) ( 38 , 39 ).

Transshipment Insertion operator also inserts requests greedily, but it only tries solutions using more than one vehicle and transshipment ( 11 , 39 ).

Random Insertion operator chooses vehicles and positions randomly and inserts the request once the solution is feasible ( 37 , 40 ).

Worst Removal operator removes the requests with the highest cost in each route ( 38 , 39 ).

Random Removal operator selects part of vehicles and removes one request from each vehicle randomly ( 37 , 40 ).

Route Removal: because of the interdependence of vehicles in ST, insertion operators may not be able to find feasible solutions based on a few removals in a short time. In this case, the route needs to be cleared, which means all requests in a route are removed to the request pool. Another idea behind this operator is to guide the search in the direction of minimizing the number of used vehicles and making full use of capacity. First, this operator obtains a random number n with a given numerical distribution [ x 1 , x 2 , . . . , x 3 ] for [ 1 , 2 , . . . , m ] , where m is the number of routes which served requests, x 1 = 1 / ξ and x i = x i − 1 / ξ when i > 1 . Then, it chooses n vehicles according to a probability ψ = u k ava / ( ∑ k ∈ K 2 serve u k ava ) , where u k 2 ava is available capacity and K serve is a set of vehicles which have served requests. The vehicle whose capacity has not been fully made use of will have a higher probability of being cleared. In an extreme case, all routes will be cleared and all requests fill the request pool. In this case, this operator may change the search direction from the beginning and thus provide a larger neighborhood for insertion operators.

Node Removal: most of the time, barges and trains in ST carry multiple requests, therefore removing part of the requests may not change the routes of vehicles. However, the cost savings are usually obtained from minimizing distance, that is, changing the routes of vehicles. To obtain better solutions quicker, the Node Removal operator is designed, which deletes visited terminals from the routes. Similar to the Route Removal operator, this operator chooses n vehicles based on a distribution and probability ψ . One terminal of each route is randomly chosen and all requests which visit this terminal will be removed.

Synchronization Between Vehicles

This work studies the synchronization among vehicles, which means that vehicles can cooperate to get the best solution when a vehicle influences other vehicles (especially when there is transshipment between vehicles/modes). For example, in the transshipment terminal, if the delivery vehicle arrives later than the planned time, the route plan of the pickup vehicle needs to be synchronized to find a suitable arrival time. Synchronization is considered after ALNS operators are used. If the current solution violates constraints, such as time constraints, the synchronization procedure will start and make other vehicles cooperate with the insertion/removal. After the synchronization, the feasibility of the solution will be rechecked.

Four cases are listed below to illustrate the synchronization among vehicles in ST.

Synchronization Case 1

When a request is transported by more than one vehicle, the time between these vehicles is synchronized, as shown in Figure 3a. The time from the arrival time till the service start time is the waiting time, and departure happens after service time or transshipment time is completed. In Figure 3a, the request is first transported by vehicle k and then transferred to vehicle l . At the transshipment terminal, vehicle k should arrive earlier than vehicle l . However, vehicle k arrives at transshipment terminal before vehicle l completes the unloading, therefore vehicle l waits for vehicle k .

OPEN IN VIEWER

Figure 3.

Synchronization cases: (a) case 1: time synchronization in the transshipment terminal, (b) case 2: complex transshipment situation, (c) case 3: synchronization with cross requests, and (d) case 4: synchronization of relevant routes.

Synchronization Case 2

Extended from case 1, a more complex situation is considered, as shown in Figure 3b. When request 1 is inserted in vehicle l , the pickup time of requests 3 and 4 will be influenced. If the waiting time for request 3 and 4 is changed, then the delivery time for requests 2, 3, and 4 need to be calculated based on both changes from insertion of request 1 and waiting time of request 3 and 4.

Synchronization Case 3

After the insertion, when there are cross requests, as shown in Figure 3c, the solution is infeasible. According to the time constraints, we have the following equations:

t Tp 2 < t Td 1 ,

(34a)

t Td 2 > t Tp 1 ,

(34b)

t Tp 2 > t Td 2 ,

(34c)

t Tp 1 > t Td 1 ,

(34d)

where t Tp means pickup time at transshipment terminal and t Td means delivery time at transshipment terminal. From Equation 34, we can get:

t Tp 1 > t Td 2 ,

(35)

which violates Equation 34b, therefore this solution is infeasible.

Synchronization Case 4

The synchronization for relevant vehicles is considered. Except for the situation described above, other vehicles may be influenced by the transshipment when one request is inserted or removed. As shown in Figure 3d, request 1 is inserted into the route of vehicle l , and then vehicle l is influenced by the transshipment of requests 2. Since the request 3 is transferred from vehicle l to vehicle m , the vehicle m (such vehicles called relevant vehicles) is also influenced. In this research, these relevant vehicles can cooperate with changes by extending or shortening the waiting time.

Weight Interval Method

MOO aims to yield a set of non-dominated solutions presenting the optimal trade-offs between different objectives. These solutions are obtained by the Pareto improvement, which means a change to a different solution that makes at least one objective better off without making any other objective worse off. Figure 4 gives the Pareto frontier of bi-objective optimization for ST, where different DMs have different preferred solutions. As shown in Figure 4, preferred solutions are non-dominated solutions, which are in line with DMs’ preferences. DM A mainly wants to minimize the cost, DM C prefers to reduce the transport time, and DM B wants to balance cost and time. Based on their preferences, they will choose their preferred solutions in the Pareto frontier. Therefore, it is important to consider DMs’ preferences in MOO. Integrating preferences into the MOO approach and guiding the search toward solutions that are considered relevant by the DM may yield two important advantages:

Instead of a diverse set of solutions, many of them clearly irrelevant to the DM, a search guided toward the DM’s preferences will yield a more fine-grained and suitable selection of alternatives.

By focusing the search onto the relevant part of the search space, the objective space and the computation time can be reduced, especially when solving real-life MOO problems ( 20 , 41 ).

Using the weight interval method proposed by Szlapczynska and Szlapczynski ( 20 ), the vague preferences are added to ALNS. The weight interval which is assigned to the i th objective is:

w i ∈ ( w i min , w i max ) ,

(36)

where 0 ≤ w i min < 1 , 0 < w i max ≤ 1 , and w i min ≤ w i max . The weight interval can represent vague preferences, such as linguistic terms.

OPEN IN VIEWER

Figure 4.

The Pareto frontier of bi-objective optimization for synchromodal transport.

Under the vague preferences, the Pareto dominance rule is extended from traditional Pareto dominance ( 20 ). In this paper, solution X dominates X ′ when:

∑ i = 1 n G i ( X , X ′ ) > 0 ,

(37)

where

G i ( X , X ′ ) = { w i min ( F i ( X ′ ) − F i ( X ) ) , F i ( X ′ ) − F i ( X ) ≥ 0 w i max ( F i ( X ′ ) − F i ( X ) ) , F i ( X ′ ) − F i ( X ) < 0

(38)

and n is the number of objectives.

In ALNS, vague preferences are considered when comparing solutions. Before comparison, all objectives are normalized.

Case Study

The proposed model is applied to a ST network in the Rhine-Alpine corridor, which runs from Rotterdam to Genoa along the Rhine River through Europe’s industrial heart. All experiments are implemented in Python 3.7 and run with 8 GB of memory and an Intel Core i7 CPU with two 1.90 GHz and 2.11 GHz cores.

We assume that shippers provide the request information (including pickup and delivery terminals, number of containers, and time windows), and carriers provide transport network information (including terminal location and type, distances among terminals, vehicle information, and cost data). The coefficients, such as carbon emission, loading/unloading time, and transshipment cost, are derived from Van Riessen et al. ( 6 ), Guo et al. ( 34 ), and Li et al. ( 42 ). The coefficients used are as follows: c k 1 / c k 2 / e k equal to 0.2758/30.98/0.8866, 0.0213/0.6122/0.2288, and 0.0635/7.54/0.3146 for trucks, barges, and trains, respectively. c k 3 / c k 4 / c k 5 / c k 6 / t ″ i k / t ′″ i k equal to 10/1/24/8/0.5/0.5, and they are the same for different modes. The parameter ξ in Route Removal and Node Removal operators is set as 1.3 in this paper. The instances used are available at a research data website (https://figshare.com/s/4f7f513488accd5ecddb).

The parameters in ALNS need to be tuned before the optimization. To do that, the Pareto frontiers need to be compared in MOO instead of solutions comparison in the parameter tuning of single-objective optimization. The average value of all non-dominated solutions’ objective function values represent the Pareto frontier in the frontiers comparison, as Equation 39 shows:

P = ∑ j = 1 m ∑ i = 1 n F i ( X j ) m ,

(39)

where P is the value which represents the Pareto frontier, m is the number of non-dominated solutions, n is the number of objectives, and F i ( X j ) is the i th normalized objective value of non-dominated solution X j . The parameters which generate minimum value P will be used in the optimization.

The parameters to be tuned include total iteration number, number of iterations for refreshing weights, initial temperature, and cooling rate. For example, the iteration number influences the quality of results, as shown in Figure 5, which shows Pareto frontiers for 10 requests and five vehicles under two objectives (cost and emission). Because P 3000 iterations is less than P 50 iterations , the Pareto frontiers with 3,000 iterations are better than frontiers with 50 iterations. It is worthy of note that these findings are only for this specific instance. Ideally, the parameters need to be tuned for each instance before the optimization.

OPEN IN VIEWER

Figure 5.

Pareto frontiers of bi-objective optimization under 50 iterations and 3,000 iterations: (a) regular Pareto frontier, (b) cost&emission: [0.1,0.9], (c) cost&emission: [0.25,0.75], (d) cost&emission: [0.33,0.66], (e) cost: [0.1,0.5], emission: [0.5,1.0], and (f) cost: [0.5,1.0], emission: [0.1,0.5].

The results for one of the experiments with five vehicles, 10 requests, and 10,000 iterations of ALNS are given in Figure 6. In this experiment, the objectives include cost and emissions. The requests and vehicles are randomly generated, and in total 19 terminals are used. The regular Pareto frontier, that is, Pareto frontier without preferences, is shown in Figure 6a. The other five figures compare the Pareto frontiers under different weight intervals with the regular Pareto frontier. Figure 6b to 6d, show the results when the weight interval narrows down from [0.1, 0.9] to [0.33, 0.66]. As the weight interval narrows down, the relative importance of cost and emissions is similar for both and therefore the trade-off between the objectives is more obvious. Figure 6e and 6f, show two opposite situations. In Figure 6e, the DM prefers to reduce emissions. In contrast, the DM favors reducing cost in Figure 6f.

OPEN IN VIEWER

Figure 6.

Pareto frontiers of bi-objective optimization: (a) regular Pareto frontier, (b) cost&emission: [0.1,0.9], (c) cost&emission: [0.25,0.75], (d) cost&emission: [0.33,0.66], (e) cost: [0.1,0.5], emission: [0.5,1.0], and (f) cost: [0.5,1.0], emission: [0.1,0.5].

It is interesting to investigate the following research question: What mode/route will the DMs with different preferences choose? To answer this research question, a case study is designed and five terminals are used, including two seaports (Rotterdam and Antwerp) and three inland terminals (Duisburg, Worth, and Basel). The transport network information is obtained from Contargo company (https://www.contargo.net/). Almost all modes can run between all terminals except for one situation: there is no train between Rotterdam and Antwerp. Table 3 shows the vehicle and request information. To guarantee that all modes have a similar chance to serve requests, different modes have the same number of vehicles, and there is no time window because vehicle speeds are different. Three objectives are considered: cost, emissions, and time.

OPEN IN VIEWER

Table 3.

Vehicle and Request Information

Vehicle	Capacity (TEU)	Speed (km/h)	Begin depot	Fixed route
Barge1	100	15	Antwerp	Free
Barge2	100	15	Rotterdam	Free
Truck1	50	75	Antwerp	Free
Truck2	50	75	Rotterdam	Free
Train1	75	45	Antwerp	Antwerp-Duisburg-Worth-Basel
Train2	75	45	Rotterdam	Rotterdam-Duisburg-Worth-Basel
Request	Pickup terminal	Delivery terminal	Time window	Load
0	Antwerp	Duisburg	Free	25
1	Rotterdam	Duisburg	Free	50
2	Antwerp	Worth	Free	25
3	Rotterdam	Worth	Free	50
4	Antwerp	Basel	Free	25
5	Rotterdam	Basel	Free	50
6	Duisburg	Worth	Free	25
7	Duisburg	Basel	Free	50
8	Worth	Basel	Free	25
9	Antwerp	Rotterdam	Free	50

In this case, 10 instances are generated from 10 requests, that is, the ith instance includes i request(s). For example, the fifth instance includes requests 0–4. The upper part of Table 4 shows regular (meaning no preferences) non-dominated solutions with request 1. Except for Truck1 in Solution 5, which is empty from Antwerp to Rotterdam, other vehicles transport request 1 on their routes. Solution 1 is also the best solution for cost minimization (single-objective optimization) and the barge is used in this solution. From these non-dominated solutions, we can see that different modes and routes are used after emission and time objectives are considered. This insight is useful to see the impact of different policies on transportation networks with regard to environmental considerations.

OPEN IN VIEWER

Table 4.

Regular Non-Dominated Solutions and Mode Shares of Different Cases

Solution	Cost (euro)	Time (h)	Emission (kg)	Vehicles and routes
1	4379.309	27.16	2158.728	Barge1: Antwerp → Duisburg
2	5979.755	10.387	2968.251	Train1: Antwerp → Duisburg
3	6756.684	15.831	2753.751	Barge1: Antwerp → Rotterdam;
				Train2: Rotterdam → Duisburg
4	6004.381	23.716	2373.228	Train1: Antwerp → Rotterdam;
				Barge2: Rotterdam → Duisburg
5	11394.345	10.254	6935.071	Truck1: Antwerp → Rotterdam → Duisburg;
				Train1: Antwerp → Rotterdam
6	10351.813	7.032	8365.071	Truck1: Antwerp → Duisburg
Name	Average cost (euro)	Average emission (kg)	Average time (h)	Share of barge (%)	Share of train (%)	Share of truck (%)
Regular	35710.5	31635.6	95.2	49.87	39.58	10.55
s1c1	30283.7	28549.2	96.0	64.93	33.97	1.1
s1c2	29628.0	28367.4	94.4	62.08	37.40	0.53
s1c3	27546.1	27457.4	98.6	73.37	26.16	0.48
s2c1	26966.5	27195.0	100.8	72.14	27.86	0
s2c2	28306.0	27068.6	103.0	72.13	27.39	0.48
s2c3	33250.9	30068.9	85.7	42.57	54.75	2.68
Average	30241.7	28620.3	96.3	62.44	35.30	2.26

Besides the regular case, two scenarios (each scenario includes three cases) with preferences are designed. The weight intervals of three objectives in the first scenario are the same but narrow down from case s1c1 (meaning scenario 1 case 1) to s1c3. The weight intervals of s1c1, s1c2, and s1c3 are [0.1,0.9], [0.25,0.75], and [0.33,0.66], respectively. In the second scenario, each case prefers one objective. Cases s2c1, s2c2, and s2c3 prefer minimizing cost, emissions, and time, respectively. The weight interval of the preferred objective is [0.5,1.0], and weight intervals of the other two objectives are [0.1,0.5]. For example, the weight intervals of s2c1 are Cost: [0.5,1.0], Emission&Time: [0.1,0.5].

For each instance, there are seven cases and each case is repeated three times to obtain the average value. Therefore, a total of 210 experiments were performed. In each experiment, ALNS runs for 1,000 iterations and the computation time depends on instance size. For the instances with one request and 10 requests, the computation times are around 1 min and 15 min, respectively. The share of used modes is calculated for every case, as shown in the bottom part of Table 4. The results show that the solution tends to be better when the weight narrows down in the first scenario (s1c1, s1c2, and s1c3) as the cost, emissions, and time reduce. The share of the barge in s1c3 is larger than in s1c2 because s1c3 sacrifices time in exchange for better cost and emission, thus making the overall result better. In the second scenario, the minimum value of each objective is in line with preferences. The parameters used in this paper set the barge as having the lowest cost, emissions, and speed, and the truck is the fastest but has the highest cost and emissions. Therefore, the barge is used the most when costs or emissions are prioritized. Nevertheless, when time is minimized (s2c3) the train’s share becomes the highest because the barge speed is too low and truck’s cost and emissions are high. The results are sensitive to the cost, emissions, and time parameters. When the parameters change in reality, the share of modes may also change. In inland waterway transport, there are more uncertainties than other modes, such as long waiting times, lock/bridge open time, and changing water level. In the meantime, compared with other modes, there may be limited depth and inadequate air draft in inland waterway transport. Therefore, although the results in this paper show the advantages of barges and encourage DMs to choose barges, barges are not utilized as frequently in reality. The uncertainties and limitations of modes will be considered in the future to make the model more practical.

The proposed model is also compared with a recent paper ( 34 ), using the same instances. Guo et al. ( 34 ) solved a similar ST planning problem with us and minimized the transport cost, but they did not consider preferences. Guo et al. ( 34 )’s instances are based on a transport network operated by European Gateway Services, which contains 116 vehicles (49 barges, 33 trains, and 34 trucks) and 10 terminals (three deep-sea terminals and seven inland terminals, and all terminals could be used as transshipment terminals). In the following results, the same cost objective is used as in Guo et al. ( 34 ). Table 5 shows the results of instances with five, 10, 20, and 30 requests under two conflicting objectives, that is, minimizing cost and time. Under the same setting, the proposed model can find the same solution as Guo et al. ( 34 ), and the results are not repeated in Table 5. In instances with five and 10 requests, the transport cost is the same as in Guo et al. ( 34 ) when the DM prefers the cost objective because the latter solution dominates other solutions. In instances with 20 and 30 requests, the transport cost is slightly higher than in Guo et al. ( 34 ) and the transport time decreases because the transport time of that solution cannot satisfy the preferences on both cost and time objectives. When the DM prefers the Time objective, the transport time is reduced more, and the mode shares of trains and trucks increase. This comparison shows that the proposed methodology finds the optimal solutions when the objective is the same and that the solutions can be adapted to the preferences of the carrier with a multi-objective setting with preferences.

OPEN IN VIEWER

Table 5.

Comparison with Guo et al. ( 34 )

Number of requests	Average cost (euro)	Average time (h)	Share of barge (%)	Share of train (%)	Share of truck (%)
5 ☆	4386	29	60	0	40
5 ○	4386	29	60	0	40
5 ◇	4386	29	60	0	40
10 ☆	25988	151	50	29	21
10 ○	25988	151	50	29	21
10 ◇	36351	127	47	28	25
20 ◇	44198	236	57	18	25
20 ○	44858	212	54	19	27
20 ◇	58787	163	52	26	22
30 ☆	65126	329	50	11	39
30 ○	69824	326	49	12	39
30 ◇	85484	271	48	11	41

Note: ☆ = benchmark ( 34 ); ○ = decision-maker (DM) prefers the Cost objective, and the weight intervals are = Cost [0.5, 1.0], Time [0.1, 0.5]; ◇ = DM prefers the Time objective, and the weight intervals are = Cost [0.1, 0.5], Time [0.5, 1.0].

Conclusion and Future Studies

In this research, a preference-based MOO (PMOO) model is developed to address the conflicts among multiple objectives of carriers in ST. Compared with models in the literature ( 3 , 28 , 30 ), the contributions of this work are the considerations of vehicle routing, synchronization, and preferences in ST. The VRP is regarded as a PDPT, and both vehicle routing and container flow are modeled to achieve the transshipment in ST. Because of the requirements of ST, the synchronization between vehicles is considered, which makes the model more flexible. Based on the optimization model, which considers vehicle routing and synchronization, the weight interval is incorporated into ALNS to represent the vague preferences of DMs. The case study on the Rhine-Alpine corridor verified that the proposed model provides non-dominated solutions which reveal DM preferences. Under different preferences in this paper, the barge is the most popular transport mode because of its low cost and low emissions. When a DM prefers to minimize transport time, transport modes with higher speed are used more frequently. It is worth noticing that the mode used is dependent on the input parameters. When these parameters change in another instance, the mode share may be different.

The proposed model is able to target a selected part of the Pareto frontier based on a DM’s vague preferences. This is a significant advantage for carriers in ST because they can just enter their linguistic preferences and then obtain solutions which reveal their preferences. Using the proposed model, DMs do not need to struggle to solve conflicts between their objectives from many solutions with different modes and routes. Compared with MOO without preferences, this model not only reduces the number of alternatives but also chooses solutions which are preferred by DMs.

The proposed model can be encapsulated in a software application in the intermodal transport domain. DMs enter transport network information, requests, and preferences into the software and then they will obtain preferred solutions. The model is designed for intermodal container transport, but it can also be applied to other transport domains if the shipments are non-splittable, such as truck-load transport. Moreover, this work combined PMOO and PDPT in ST, which may be helpful for solving similar problems in the VRP domain.

Future research will focus on the following aspects: