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