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:
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.