Numerical Results

Let \(o, 1, 2, 3, ..., 15, d\) be nodes where \(o\) and \(d\) are the same nodes. First of all, we consider test problems in order to observe the feasibility and solvability of the models. We test our models on the sets of 5, 10, and 15 customers. We use the same set of data to examine the feasibility and solutions of the model. Clearly, our models are more general. However, we use this data set as a special case. Second of all, we randomly generate demands, service times, time windows of the customers, and distances between nodes as in Tables 2–6. The demands of customers are given in Tables 4–6.

Table 2 Distance from a node \(i\) to a node \(j\)

\(d_{i,j}\)
 \(o, d\)
 1
 2 3
 4
 5
 6
 7
 8 9
 10
 11 12
 13
 14
 15
\(o\)
 0
 5
 11
 10
 8 7
 10
 12
 14 16 18 14 8
 2 14
 15
1 5 0 6 8 8 8 6 8 10 12 14 18 20 24 8 6
2 11 6 0 4 7 9 5 10 12 20 25 4 5 6 8 5
3 10 8 4 0 6 10 7 9 12 11 10 8 3 8 10 12
4 8 8 7 6 0 6 5 10 15 10 12 8 6 4 4 6
5 7 8 9 10 6 0 5 12 8 9 10 8 5 12 11 9
6 10 6 5 7 5 5 0 3 6 9 12 15 14 12 16 11
7 12 8 10 9 10 12 3 0 10 12 14 16 18 14 8 2
8 14 10 12 12 15 8 6 10 0 6 8 10 12 14 18 20
9 16 12 20 11 10 9 9 12 6 0 6 6 8 8 10 12
10 18 14 25 10 12 10 12 14 8 6 0 5 13 18 22 20
11 14 18 4 8 8 8 15 16 10 6 5 0 4 8 12 14
12 8 20 5 3 6 5 14 18 12 8 13 4 0 6 9 12
13 2 24 6 8 4 12 12 14 14 8 18 8 6 0 1 2
14 14 8 8 10 4 11 16 8 18 10 22 12 9 1 0 3
15 15 6 5 12 6 9 11 2 20 12 20 14 12 2 3 0

Table 3 The time windows for each node \(i\).


 \(o, d\)
 1
 2 3
 4
 5
 6
 7
 8 9
 10
 11 12
 13
 14
 15
\(a_i\)
 6
 10
 16
 13
 15
 8
 10
 8
 13
 10 11 9 9
 9
 10
 10
\(b_i\)
 20
 11
 20
 16
 17
 9
 12
 10
 14 17 14 11 12 10
 15
 17

Table 4 The demand at the node \(i\) for five customers.

\(dm_{i,p}\)
 \(o, d\)
 1
 2 3
 4
 5
\(p_1\)
 0
 100
 200
 200
 300
 50
\(p_2\)
 0
 100
 100
 70
 30
 20

Table 5 The demand at the node \(i\) for ten customers.

\(dm_{i,p}\)
 \(o, d\)
 1
 2 3
 4
 5
 6
 7
 8 9
 10
\(p_1\)
 0
 50
 100
 120
 40
 30
 60
 80
 50
 130
 40
\(p_2\)
 0
 100
 90
 70
 30
 20
 50
 30
 40 60 80

Table 6 The demand at the node \(i\) for fifteen customers.

\(dm_{i,p}\)
 \(o, d\)
 1
 2 3
 4
 5
 6
 7
 8 9
 10
 11 12
 13
 14
 15
\(p_1\)
 0
 20
 100
 30
 40
 10
 30
 30
 60
 10 20 40 20
 100
 20
 40
\(p_2\)
 0
 80
 60
 70
 30
 20
 40
 40
 10 20 70 20 50 10
 50
 30

We assume that there are two vehicle types:  \(\nu_1\) and \(\nu_2\) and two product types: \(p_1\) and \(p_2\). For a general number of vehicles and products, some modifications can be easily done. We define our compartment in Table 7. We only allow a maximum of two trips per day for each vehicle. Obviously, for more general maximum number of trips per day, a small modification can be easily done as well too. For the parameters related to cost function, we let the unit penalty of the earliness \(p_e\) be 100 units and we let unit penalty of lateness \(p_1\) be 200 units. The cost of travel and loading are shown in Tables 8 and 9. Let also the lower bound of hard time window for the node \(i\) be \(LB_i = a_i -0.5\). The upper bound of hard time window for the node \(i\) is \(UB_i = b_i + 1\) and the service time for each node \(s_i\) is 10 unit times and \(\nu\) is 20-unit distance per unit time.

Table 7 The capacity for compartment \(k\) of vehicle \(k\).

\(C_{k,t}\)
 \(t_1\)
 \(t_2\)
 \(t_3\)
\(\nu_1\)
 200
 200
 100
\(\nu_2\)
 300
 300
 200

Table 8 The fixed cost of travelling \(TC_k\) per k.m. and the capacity \(Cp_k\) of vehicle \(k\).


 \(\nu_1\)
 \(\nu_2\)
\(TC_k\)
 10
 6
\(Cp_k\)
 500
 800

Table 9 The cost of loading for product \(p\) by each vehicle \(k\).

\(LC_{k,p}\)
 \(p_1\)
 \(p_2\)
\(\nu_1\)
 10
 6
\(\nu_2\)
 4
 8

All models have been coded and solved by AIMMS 3.13. They were run on a computer equipped with a processor Intel Core i5 at 2.3 GHz and 2 GB of RAM memory. The optimal solutions are obtained in Tables 10–12. The average run time for each case is included in Tables 10–12. As one can see, our model can be executed by an available solver on a personal computer in a reasonable time. We present the detailed optimal results of model 3 in the case of 15 customers for the effectiveness of the model. The optimal solutions are presented in Tables 13–16.

Table 10 The solution for five customers.

Model 1 Model 2 Model 3
Objective value 60346 61016 60476
Loading cost 59860 60500 59860
Travel cost 486 516 486
Penalty cost — — 130
Vehicle 1
Trip 1
Trip 2
0 → 1 → d
0 → 5 → d 
 0 → 5 → d
0 → 1 → d
 0 → 5 → d
0 → 1 → d
Vehicle 2
Trip 1
Trip 2		 0 → 3 → 2 → d
0 → 4 → d 		  0 → 4 → 3 → d
0 → 2 → d		  0 → 4 → d
0 → 3 → 2 → d
Times (seconds)
  0.37 0.27
0.5

Table 11 The solution for ten customers.

Model 1 Model 2 Model 3
Objective value 106574 110744 109130
Loading cost 105620 109780 107840
Travel cost 954 964 1010
Penalty cost — — 280
Vehicle 1
Trip 1
Trip 2
0 → 5 → 10 → d
0 → 4 → d 
 0 → 7 → d
0 → 1 → 6 → 8 → d
 0 → 6 → 7 → d
0 → 1→ 10 → d
Vehicle 2
Trip 1
Trip 2		 0 → 6 → 8 → 0 → d
0 → 1 → 2→ 3 → 7 → d 		  0 → 5 → 9 → 10 → d
0 → 3 → 2 → 4 → d		  0 → 5 → 9 → 8 → d
0 → 3 → 2 → 4→ d
Times (seconds)
 28 5
 11

Table 12 The solution for fifteen customers.

Model 1 Model 2 Model 3
Objective value 74548 107098 83228
Loading cost 73540 105900 81760
Travel cost 1008 1198 1078
Penalty cost — — 390
Vehicle 1
Trip 1
Trip 2
0 → 4 → 5 → d
0 → 12 → 3 → 10 → d 
 0 → 5 → 7 → → d
0 → 1 → 6 → 3 → 14 →  d
 0 → 5 → 12 → 11 → d
0 → 1→ 10 → d
Vehicle 2
Trip 1
Trip 2		 0 → 1 → 2 → 11 → 9→ d
0 → 13 → 14→ 15 → 7 →  6 → 8 → d 		  0 → 13 → 12 → 11 → 10 → 9 → 8 → d
0 → 4 → 2 → 15 → d		 0 → 13 → 14 → 15 → 7 → 6 → 8 → 9 → d
0 → 3 → 2 → 4→ d
Times (seconds)
 287 1320
 1599

Table 13 The service time at node \(i\) by a vehicle \(k\) in a trip \(r\).

Vehicle 1
            
 
 Trip 1  5 →
7.75  
  12 →
8.5   		 11 →
 9.2
 d
 10.4		      
    
 
 Trip 2 1 →
11.15
 10 →
12.35
 d
20
   

 
Vehicle 2
            
 
 Trip 1  13 →
9
 14 →
9.55
  15 →
10.2
  7 →
10.8
  6 →
11.45
  8 →
12.5
 9 →
13.3
  d
14.6
 Trip 2 3 →
15.6
 2 →
16.3
  4 →
17.15
 d
20
       

Table 14 The violation degree of the bound for soft time at node \(i\).

\(WL_{k,r,i}\)
 1
 2   
3   
4
 5
 6   
7
 8 9   
10
 11 12
 13
 14
 15
Vehicle 1














 Trip 1          0.25              0.5      
 Trip 2                              
Vehicle 2














 Trip 1                0.5           0.45
 
Trip 2
                             
 \(WU_{k,r,i}\) 1
2
3
4
5
6
7
8
9
10
 11  12 13
14
15
 Vehicle 1
                              
Trip 1 
                             
 Trip 2  0.15                            
 Vehicle 2
                              
 Trip 1              0.8                
 Trip 2        0.15                      

Table 15 The load of the product \(p\) in a compartment \(t\) of vehicle \(k\).

 \(U_{k,r,t,p}\) Product 1
Product 2
Vehicle 1, trip 1    
 Compartment 1 1  
 Compartment 2 1  
 Compartment 3   1
Vehicle 1, trip 2    
 Compartment 1   1
 Compartment 2   1
 Compartment 3 1  
Vehicle 2, trip 1    
 Compartment 1 1  
 Compartment 2 1  
 Compartment 3   1
Vehicle 2, trip 2    
 Compartment 1 1  
 Compartment 2 1  
 Compartment 3   1

Table 16 The quantity of product \(p\) moved from node \(i\) to node \(j\) and delivered at node \(i\) for fifteen customers.

\(XT_{k,r,i,j,p}\)
  Product 1
Product 2
   Moved from \(i\) to \(j\)
Delivered at \(j\)
 Moved from \(i\) to \(j\)  Delivered at \(j\) 
Vehicle 1,  Trip 1



0-5 70
10
90
20
5-12 60
20
70
50
12-22
 40
 40
 20
 20
Vehicle 1,  Trip 2
        
0-1
  40  20  150 80
1-10 20
20
70
70
Vehicle 2,  Trip 1
        
0-13
  290  100 200
10
13-14  190 20
190
50
14-15
 170
40
140
30
15-17 130
 30  110 40
7-6  100 30
70
40
6-8
70
60
30
 10
 8-9 10
10
20
20
 Vehicle 2,  Trip 2
        
 0-3  170 30
160
70
 3-2 140
100
90
60
 2-4 40
40
30
30

From the numerical examples, it is to be expected that the optimal values for the case where time windows are allowed are less than the case where the time windows are not allowed. Detailed results on each problem can be found in Tables 10, 11, and 12 for the of cases models 1 and 2. However, there are a few cases where the time windows do not have any effect. In these cases, the optimal values for both cases should be coincided. As for the case with soft time windows, together with the penalty, we expect that the optimal value of the soft time windows case should obviously be less than the (hard) time windows since the feasible solution set for the soft time windows is strictly larger than the feasible solution set or the time windows. The results of this experiment are shown in Tables 10, 11, and 12 in cases of models 2 and 3.