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

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:

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)

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)

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