## 3 Model for Vehicle Routing Problem
### Mathematical Model for VRPSDP-TW-LO  
In this section, we describe the mixed integer programming (MIP) model devised for VRPSDP-TW-LO. Table 1 summarizes the notations used in the MIP formulation. Using the flow-arc formulation [7], the vehicle routing problem can be described as follows. Let \(G=(V,A)\) be a graph where \(V=(v_{0},\cdots,v_{n+1})\) is the set of vertices and \(A=\left\{\left(v_{i},v_{j}\right):i\
eq j\wedge i,j\in V\right\}\) is the set of arcs. Note that both \(v_{0}\) and \(v_{n+1}\) denote the depot. Thus, any tour which starts and ends at the depot can be represented as a path from \(v_{0}\) to \(v_{n+1}\). Each vertex \(v_{i}\) in \(V\) has an associated demand \(g_{i}\geq 0\), a pickup quantity \(p_{i}\geq 0\), and a time window \([e_{i},l_{i}]\). Especially, the depot has \(g_{0}=g_{n+1}=0\), \(p_{0}=p_{n+1}=0\), and \([-\infty,+\infty]\). For \begin{table}
\begin{tabular}{c l} \hline \hline
**Notation** & **Description** \\ \hline \(N\) & Set of customers (0 th customer represents the depot) \\ \hline \(K\) & Set of vehicles \\ \hline \(C\) & Set of capacities of vehicles \\ \hline \(T\) & Set of maximum travel time of vehicles \\ \hline \(c_{ij}\) & Travelling cost from customer \(i\) to \(j\) \\ \hline \(p_{i}\) & Number of empty trays at customer \(i\) from the previous planning horizon \\ \hline \(g_{i}\) & Number of non-empty trays requested for customer \(i\) \\ \hline \([e_{i},l_{i}]\) & Time window for customer \(i\) \\ \hline \(s_{i}\) & Service time for customer \(i\) \\ \hline \(t_{ij}\) & Travel time from customer \(i\) to \(j\) \\ \hline \(C_{lo}\) & Penalty cost per left-over tray \\ \hline \(C_{e}\) & Penalty cost for violating time window to arrive earlier \\ \hline \(C_{l}\) & Penalty cost for violating time window to arrive late \\ \hline \(M\) & Large number \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations and descriptions. we introduce the set of customers, \(N=\{v_{1},\cdots v_{n}\}=V\backslash\{v_{0},v_{n+1}\}\). The topology of the underlying graph is assumed to be given in the cost matrix \(\big{(}c_{ij}\big{)}\) and the travel-time matrix \(\big{(}t_{ij}\big{)}\) for \(i,j\in N\cup\{v_{0},v_{n+1}\}\). The decision variables for the proposed model are defined as follows:  
* \(x_{ij}^{k}\): the binary variable whose value is 1 if a vehicle \(k\) travel from customer \(i\) to \(j\) and 0 otherwise;
* \(f_{i}^{k}\): the number of empty trays loaded on the vehicle \(k\) at customer \(i\);
* \(y_{i}^{k}\): the number of trays (both empty and non-empty trays) loaded on the vehicle \(k\) when it departs from customer \(i\);
* \(t_{i}^{k}\): the time at which a vehicle \(k\) departs from customer \(i\);
* \(ze_{i}^{k}\): the binary variable whose value is 1 if a vehicle \(k\) arrives at customer \(i\) earlier than \(e_{i}\) and 0 otherwise;
* \(z_{i}^{k}\): the binary variable whose value is 1 if a vehicle \(k\) arrives at customer \(i\) later than \(l_{i}\) and 0 otherwise;
* \(zw_{i}^{k}\): the binary variable whose value is 1 if a vehicle \(k\) arrives at customer \(i\) within the time window \([e_{i},l_{i}]\) and 0 otherwise. The objective function is defined as follows: \[\text{minimize}\sum_{k=1}^{K}\sum_{i=0}^{N+1}\sum_{j=0}^{N+1}c_{ij}x_{ij}^{k} +C_{lo}\sum_{k=1}^{K}\sum_{i=1}^{N}\Big{(}p_{i}-f_{i}^{k}\Big{)}+\sum_{k=1}^{ K}\sum_{i=1}^{N}\Big{(}C_{e}ze_{i}^{k}+C_{l}z_{i}^{k}\Big{)}\] (1) A feasible solution for the proposed model satisfies the following constraints. * Path constraints: for each vehicle, a tour which starts and ends at the depot can be represented as a path from \(v_{0}\) to \(v_{n+1}\).