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 1Trip 1 Trip 2 0 → 1 → d0 → 5 → d 0 → 5 → d 0 → 1 → d 0 → 5 → d 0 → 1 → d Vehicle 2Trip 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 1Trip 1 Trip 2 0 → 5 → 10 → d0 → 4 → d 0 → 7 → d 0 → 1 → 6 → 8 → d 0 → 6 → 7 → d 0 → 1→ 10 → d Vehicle 2Trip 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 1Trip 1 Trip 2 0 → 4 → 5 → d0 → 12 → 3 → 10 → d 0 → 5 → 7 → → d 0 → 1 → 6 → 3 → 14 →  d 0 → 5 → 12 → 11 → d 0 → 1→ 10 → d Vehicle 2Trip 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 → d0 → 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 d20 Vehicle 2 Trip 1 13 →9 14 →9.55 15 →10.2 7 → 10.8 6 →11.45 8 →12.5 9 → 13.3 d14.6 Trip 2 3 →15.6 2 →16.3 4 →17.15 d20

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.