Vehicle Routing Problem for Multiple Product Types, Compartments, and Trips with Soft Time Windows
Read this article. The paper presents a mathematical model to solve vehicle routing challenges. In your own words, explain what vehicle routing is and why it's important to a supply chain.
Numerical Results
Let be nodes where and 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 to a node
Table 3 The time windows for each node .
1 
2  3 
4 
5 
6 
7 
8  9 
10 
11  12 
13 
14 
15 

6 
10 
16 
13 
15 
8 
10 
8 
13 
10  11  9  9 
9 
10 
10 

20 
11 
20 
16 
17 
9 
12 
10 
14  17  14  11  12  10 
15 
17 
Table 4 The demand at the node for five customers.
1 
2  3 
4 
5 

0 
100 
200 
200 
300 
50 

0 
100 
100 
70 
30 
20 
Table 5 The demand at the node for ten customers.
1 
2  3 
4 
5 
6 
7 
8  9 
10 

0 
50 
100 
120 
40 
30 
60 
80 
50 
130 
40  
0 
100 
90 
70 
30 
20 
50 
30 
40  60  80 
Table 6 The demand at the node for fifteen customers.
1 
2  3 
4 
5 
6 
7 
8  9 
10 
11  12 
13 
14 
15 

0 
20 
100 
30 
40 
10 
30 
30 
60 
10  20  40  20 
100 
20 
40 

0 
80 
60 
70 
30 
20 
40 
40 
10  20  70  20  50  10 
50 
30 
We assume that there are two vehicle types: and and two product types: and . 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 be 100 units and we let unit penalty of lateness 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 be . The upper bound of hard time window for the node is and the service time for each node is 10 unit times and is 20unit distance per unit time.
Table 7 The capacity for compartment of vehicle .
200 
200 
100 

300 
300 
200 
Table 8 The fixed cost of travelling per k.m. and the capacity of vehicle .
10 
6 

500 
800 
Table 9 The cost of loading for product by each vehicle .
10 
6 

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 by a vehicle in a trip .
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 .
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 

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 in a compartment of vehicle .
Table 16 The quantity of product moved from node to node and delivered at node for fifteen customers.
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.