Vehicle Routing Problem for Multiple Product Types, Compartments, and Trips with Soft Time Windows

Site: Saylor Academy
Course: BUS606: Operations and Supply Chain Management
Book: Vehicle Routing Problem for Multiple Product Types, Compartments, and Trips with Soft Time Windows
Printed by: Guest user
Date: Saturday, July 13, 2024, 1:29 PM

Description

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.

Abstract

This paper presents a mathematical model to solve the vehicle routing problem with soft time windows (VRPSTW) and distribution of products with multiple categories. In addition, we include multiple compartments and trips. Each compartment is dedicated to a single type of product. Each vehicle is allowed to have more than one trip, as long as it corresponds to the maximum distance allowed in a workday. Numerical results show the effectiveness of our model.


Source: P. Kabcome and T. Mouktonglang, https://www.hindawi.com/journals/ijmms/2015/126754/
Creative Commons License This work is licensed under a Creative Commons Attribution 3.0 License.

Introduction

The vehicle routing problem (VRP) is a well-known problem in the operation research and combinatorial optimization presented by Dantzig and Ramser. The VRP is also an important problem in the fields of transportation, distribution, and logistics. The context is planning the route to deliver goods from a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. According to the importance of the VRP, there are so many literatures which refer to the models and the solution of the VRP. Many papers present the different views of the problem, the different features of the system, and the different approaches to solve the problem.

The vehicle routing problem with time windows (VRPTW) is a variant of the VRP (Figure 1). A solution of the VRPTW is a set of routes consisting of sequences of customers. Each route is assigned to arrive within their time windows. In addition, if a vehicle arrives before (or after) the lower (or upper) bound of the customer's time window, the vehicle cannot deliver goods to the customer. An exception of VRPTW problem is that the time windows can be violated if the penalty is paid. In this case, it is called the vehicle routing problem with soft time windows (VRPSTW). In VRPSTW, each customer i has a desirable time window with the highest satisfaction [a_i, b_i] as and a hard time window [LB_i, UB_i]. A soft time window is shown in Figure 2. In the intervals  [LB_i, a_i] and [b_i, UB_i] the service is allowed for some penalty fee.

Figure 1 Service time interval in VRPTW.



Figure 2 Service time interval in VRPSTW.



The vehicle routing problem with multiple trips (VRPMT) is another variant of the classical VRP. Each vehicle can be scheduled for more than one trip, as long as it corresponds to the maximum distance allowed in the workday.

The vehicle routing problem with multiple compartments (VRPMC) is also a special case of the VRP. Each compartment of the vehicle has a limit and is dedicated to a single type of products.

Many papers present the different views of VRP; there has not been any VRP mathematical model for multiple compartments, trips, and time windows. Several papers presented VRP for single product type. However, in "A mixed-binary linear model for fleet routing and multiple product-type distribution," the author presents a model on distributing multiple items for customer.

In this paper, we address the mathematical model for the VRP for multiple product types, compartments, and trips with soft time windows (VRPMPCMTSTW). The proposed VRP can be regarded as the extension to three problems which are

(i) the vehicle routing problem with multiple compartments,

(ii) the vehicle routing problem with multiple trips,

(iii) the vehicle routing problem with soft time windows.

The summary of the three mentioned problems is presented in Table 1. It is clear that our mathematical model solves the classical VRP since it is a special case for the VRP with multiple compartments, trips, and time windows. The time window cases are studied because they are more practical and the soft time window cases are further investigated due to the feasibility of the problem and, in some cases, due to the fact that it reduces the total cost.

Table 1 Comparison of the problems.


VRP VRPMC VRPMT VRPSTW This study

Vehicle Heter/homo Single Heter/homo Heter/homo Heter/homo
Compartment Single Multiple Single Single Multiple
Trip Single Single Multiple Single Multiple
Time window Not considered Not considered Not considered Considered Considered


In this paper, we present our mathematical models in three cases to see the development process of our study. In the first case, we consider the VRP for multiple product types, compartments, and trips where there is not a time window (model 1). Then we consider the case with time window (model 2) and, finally, the case with soft time window (model 3).

From the above content, model 3 generalizes all previous models mentioned in this paper. It is worth pointing out that another goal of the formulation is to try to formulate the mathematical models which are feasible and solvable by available solvers in a reasonable time. In this research, all models are solved by using AIMMS 3.13 on a personal computer. The remainder of the paper is organized as follows. In Section 2, the problem is defined. Also the assumptions, notations, and mathematical models are presented. Section 3 contains the computational results of our formulations. We use the same set of data from "A mixed-binary linear model for fleet routing and multiple product-type distribution," to examine the feasibility and solutions of the model. Finally, in Section 4, we summarize our conclusion and provide pointers for further research.

Problem Formulation

In this section, we present a mathematical model for the vehicle routing problem for multiple product types, compartments, and trips with soft time windows. The following notations are introduced to formulate the mathematical model.

Sets (Indexes). Let G(N,A) be a directed graph where N is a set of vertices and A is a set of arcs (i, i) representing the connections between the depot and customers and among the customers, where i \neq j. Indeed, let 

N = {o, d, 1, 2, 3, ..., n} be a node set (o is origin and d is destination), 

N* = N/ {o, d}, 

A(i, j) : i, j \in N, i \neq j be the arc set, 

 K = {1, 2, 3, ...., \nu}  be a set of vehicles, 

P = {1, 2, 3, ...., p} be a set of product types, 

T = {1, 2, 3, ...., t} be a set of compartments, 

R = {1, 2, 3, ...., r} be a set of trips.

Parameters. Let 

ds_{i,j} be a distance between customers  i and j, 

t_{i,j} be a time (hour) from customers i to j (e.g., t_{i,j} = ds_{i,j} / \nu when \nu means traveling speed of each vehicle), 

dm_{i,p} be the demand of the customer i in product k, 

Cp_{k,t} be the capacity of a compartment t in the vehicle k, 

M be an arbitrary big number (e.g., M = \sum_k \sum_t Cp_{k,t} ), 

TC_k be the fixed cost per kilometer of running of each vehicle, 

LC_{k,p} be the cost per unit travel per unit of load of product type by the vehicle, 

s_i be a service time at the customer i, 

a_i be the lower bound of soft time window for the node i, 

b_i be the upper bound of soft time window for the node i, 

LB_i be the lower bound of hard time window for the node i, 

UB_i be the upper bound of hard time window for the node i, 

P_l be penalty cost per hour for the earliness, 

P_u be penalty cost per hour for the lateness.

Decision Variables. Consider

 X_{k, r, i, j}= \begin{cases}1, & \text { if a vehicle } k \text { travels directly from node } i \text { to } j \text { in a trip } r ; \\ 0, & \text { otherwise. }\end{cases} (1)

XT_{k, r, i, j,p} is the quantity of product type p to be transported from node i to node j by vehicle k in trip r, 

XL_{k, r, i, p} is the quantity of product type p to be disposed at node i by vehicle k in trip i, 

W_{k, r, i,} is the starting time of service in node i by the vehicle k in trip r, 

WL_{k, r, i,} = max{a_i - W_{k,r,i} ,0} is the violation degree of a lower bound of soft time window, 

is the violation degree of an upper bound of soft time window, and

U_{k, r, t, p}= \begin{cases}1, & \text { if a vehicle } k \text { delivers a product } p \text { in a compartment } t \text { in a trip } r ; \\ 0, & \text { otherwise. }\end{cases} (2)

The problem is solved under the following assumptions:

(1) Every customer can be served by one and only one vehicle.
(2) Every vehicle starts and ends only at the central depot.
(3) The total demand on one particular route must not exceed the capacity of the vehicle.
(4) Each customer must be served in the related hard time window.
(5) A service (wait) time in each customer is allowed.
(6) The hard time windows must not be violated.
(7) The soft time windows can be violated at a fixed cost.


Mathematical Model. The vehicle routing problem for multiple product types, compartments, and trips (model 1) can then be stated mathematically as follows:

\min \left\{\sum_{k} \sum_{r} \sum_{(i, j) \in A} \mathrm{ds}_{i, j} X_{k, r, i, j} T C_{k}+\sum_{k} \sum_{r} \sum_{p} \sum_{(i, j) \in A} X T_{k, r, i, j, p} \mathrm{ds}_{i, j} L C_{k, p}\right\} (3)

subject to: \sum_{j} X_{k, r, i, j}-\sum_{j} X_{k, r, i, j}=\left\{\begin{array}{ll}-1, & i=o ; \\1, & i=d ; \\0, & \text { otherwi7D\end{array} \quad \forall i \in N, \forall k \in K, \forall r \in R\right. (4)

\sum_{k} \sum_{r} \sum_{j} X_{k, r, i, j}=1 ; \quad \forall i \in N^{*} (5)

\sum_{j} X_{k, r, i, j} \leq 1 ; \quad \forall i \in N^{*}, \forall k \in K, \forall r \in R (6)

\sum_{j \in N^{*}} X T_{k, r, o, j, p} \leq \sum_{t} U_{k, r, t, p} \mathrm{Cp}_{k, t} ; \quad \forall k \in K, \forall r \in R, \forall p \in P (7)

\sum_{k} X L_{k, r, i, p}=\mathrm{dm}_{i, p} ; \quad \forall i \in N^{*}, \forall p \in P (8)

\sum_{k} \sum_{r} \sum_{j} X T_{k, r, i, j, p}=\sum_{j \in N^{*}} \mathrm{dm}_{j, p} ; \quad \forall i \in N^{*}, \forall p \in P (9)

\sum_{i} X T_{k, r, i, n, p}-X L_{k, r, n, p}=\sum_{j} X T_{k, r, n, j, p} ; \quad \forall i \in N^{*}, \forall k \in K, \forall r \in R, \forall p \in P (10)

X T_{k, r, i, j, p} \leq X_{k, r, i, j} M ; \quad \forall i, j \in N, \forall k \in K, \forall r \in R, \forall p \in P (11)

 XT_{k,r,i,d,p} = 0;  \; \forall i \in N, \forall k \in K, \forall r \in R,  \forall p \in P (12)

 X_{k,i,i} = 0;  \; \forall i \in N, \forall k \in K, (13)

 X_{k,o,d} = 0;  \; \forall k \in K, (14)

\sum_{p} U_{k, r, t, p} \leq 1 ; \quad \forall t \in T \forall k \in K (15)

We minimize objective function (3) which consists of two components. The first component represents traveling cost. It depends on distances covered by vehicles and the fixed costs per unit distance. The second component is defined as the fleet cost which is equal to the sum of the costs related to the loading and distance. Constraints (4) are the flow conservation of a vehicle. That is, for i=o, every vehicle starts only once at the depot and no arc terminates at node o, and also, for i=d, every vehicle ends only once at the depot and no arc originates from node d, and i \in N* indicate that exactly one vehicle enters and leaves each customer node. Constraints (5) require the fact that each customer is serviced exactly once. Constraints (6) state that all customers must be assigned to at most one vehicle. Constraints (7) ensure that the total number of quantity transported does not exceed the vehicle's capacity. Constraints (8) state that the sum of the quantities of product type disposed at a customer by all the vehicles must be equal to the demand for product p. Constraints (9) represent the sum of quantities of the product type to be transported by the vehicle to the customer from the depot node (o). It should in total be greater than the total sum of the demands at all customers. Constraints (10) state that the quantity of product transported to a customer minus the quantity disposed at that customer must be equal to the quantity transported to the next customer by the vehicle. Constraints (11) represent the transported quantity. That is, variable XT_{k,i,j,p} = 0 if route segment (i, i) is not used by vehicle k; otherwise it should not exceed the total tonnage capacity of vehicle k. Constraints (12) state that each vehicle must not load at the depot. Constraints (13) and (14) are the flow conservation constraints which describe the vehicle path. Constraints (15) define a limit for each compartment to be dedicated to a single type of product.

This model can be extended to the model called vehicle routing problem for multiple product types, compartments, and trips with time windows (model 2). In the next model, we include the time windows for each node. Consider
\left(W_{k, r, i}+t_{i, j}+s_{i}-W_{k, r, j}\right) X_{k, r, i, j} \leq 0 (16)

\forall i, j \in N, \forall k \in K, \forall r \in R

Constraints (16) ensure feasibility of the time schedule; that is,

W_{k,r,j} must be greater than or equal to \(\) whenever the vehicle k travels fromi to j. By rewriting constraints (16), they can be replaced with the following constraints:

W_{k, r, i}-W_{k, r, j}+\left(b_{i}+t_{i, j}+s_{i}-a_{j}\right) X_{k, r, i, j} \leq b_{i}-a_{j}; (17)

\forall i, j \in N, \forall k \in K, \forall r \in R

a_{i} \leq W_{k, r, i} \leq b_{i} ; \quad \forall i \in N^{*}, \quad \forall k \in K, \quad \forall r \in R (18)

Constraints (18) ensure that the starting time of a service does not violate the given hard time window.

Proposition 1. Constraints

W_{k, r, i}+t_{i, j}+s_{i}-W_{k, r, j}

\leq\left(1-X_{k, r, i, j}\right) \max \left(0, b_{i}+t_{i, j}-a_{j}\right) ; (19)

\forall i, j \in N, \forall k \in K, \forall r \in R

are valid for model 2. Moreover, any W_{k, r, i}, W_{k, r, j}, X_{k, r, i, j} that satisfies constraints (19) satisfies constraints (17).

Proof of Proposition 1 is straightforward and, thus, we omit it.

The vehicle routing problem for multiple product types, compartments, and trips with time windows can be stated as follows:

\min \left\{\sum_{k} \sum_{r} \sum_{(i, j) \in A} \mathrm{ds}_{i, j} X_{k, r, i, j} T C_{k}+\sum_{k} \sum_{r} \sum_{p} \sum_{(i, j) \in A} X T_{k, r, i, j, p} \mathrm{ds}_{i, j} L C_{k, p}\right\} (20)

subject to: (4) - (15), (18), (19)

W_{k, r+1, o} \geq W_{k, r, d} ; \quad \forall k \in K

Constraints (18) assure that the starting time of services does not violate the given hard time windows. Constraints (21) assure that the starting time in next trip of each vehicle is satisfied.

Finally we consider the complete the generalization of all models mentioned in this paper. We include soft time windows for each time window allowing the vehicle to enter the depot earlier or later with some penalties. The vehicle routing problem for multiple product types, compartments, and trips with soft time windows (model 3) can then be stated mathematically as

\min \left\{\sum_{k} \sum_{r} \sum_{(i, j) \in A} \mathrm{ds}_{i, j} 
X_{k, r, i, j} T C_{k}+\sum_{k} \sum_{r} \sum_{p} \sum_{\{(i, j) e A} X 
T_{k, i, j, p} \mathrm{ds}_{i, j} L C_{k, p}+\sum_{k} \sum_{r} 
\sum_{i}\left(P l W l_{k, r, i}+P u W u_{k, r, i}\right)\right\} (22)

subject to: (4) - (15) , (22),

W_{k, r, i}+t_{i, j}+s_{i}-W_{k, r, j} \leq\left(1-X_{k, r, j, j}\right) \max \left(0, \mathrm{UB}_{i}+t_{i, j}-\mathrm{LB}_{j}\right) ; \quad \forall i, j \in N, \forall k \in K, \forall r \in R (23)

\mathrm{LB}_{i} \leq W_{k, r, t} \leq \mathrm{UB}_{i} ; \quad \forall i \in N^{*}, \forall k \in K, \forall r \in R

W l_{k, r, i} \geq a_{i}-W_{k, r, j} ; \quad \forall i, j \in N^{*}, \forall k \in K

W u_{k, r, i} \geq W_{k, r, i}-b_{i} ; \quad \forall i, j \in N^{*}, \forall k \in K (24)

The objective function differs from models 1 and 2 by adding the third component. The objective function is to minimize the sum of the cost of traveled distances, total of costs related to loading products, and the total penalties of the outrage from soft time windows. We then replaced constraints (19) and (18) by constraints (23). Constraints (24) determine the violation degree of the lower and upper bound of soft time windows for each node.

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.

Conclusion

In this paper, we present a mathematical model for the vehicle routing problem for multiple product types, compartments, and trips with soft time windows. We have verified our feasibilities and attended the optimal solution for the problems. We use the software package AIMMS to solve the problems on a personal computer. The run times are acceptable. Numerical results show the effectiveness of our model.