problem.tex

\documentclass{article}

\begin{document}

The VRPTW is the same problem that VRP with the additional restriction that in VRPTW a time window is associated with each customer ${v \in V}$, defining an interval ${\left[ e_{0}, l_{0} \right]}$ wherein the customer has to be supplied. The interval ${\left[ e_{0}, l_{0} \right]}$ at the depot is called the scheduling horizon. Here is a formal description of the problem:\\ \ \\

The objective is to minimize the vehicle fleet and the sum of travel time and waiting time needed to supply all customers in their required hours. \\ \ \\

Let ${b_{0}}$ denote the beginning of service at customer ${v}$. Now for a route ${R_{i} = (v_{0}, v_{1}, …, v_{m}, v_{m+1})}$ to be feasible it must additionally hold ${e_{v_{i}} \leq b_{v_{i}} \leq l_{v_{i}}}$, ${1 \leq i \leq m}$, and ${b_{v_{m}} + \delta_{v_{m}} + c{v_{m,0}} \leq l_{0}}$. Provided that a vehicle travels to the next customer as soon as it has finished service at the current customer, ${b_{v_{i}}}$ can be recursively computed as ${b_{v_{i}} = \max{(e_{v_{i}},b_{v_{i-1}}+\delta_{v_{i-1}}+c_{v_{i-1},v_{i}})}}$ with ${b_{0} = e_{0}}$ and ${\delta_{0} = 0}$. Thus, a waiting time ${w_{v_{i}} = \max{(0,b_{v_{i}}-b_{v_{i-1}}-\delta_{v_{i}}-c_{i-1,i})}}$ may be induced at customer ${v_{i}}$. The cost of route ${i}$ is now given by \\ ${C_{VRPTW}(R_{i}) = \sum_{i=0}^{m} c_{i,i+1} + \sum_{i=1}^{m} \delta_{i} + \sum_{i=0}^{m} w_{v_{i}}}$. For a solution ${S}$ with routes ${R_{1}, …, R_{m}}$, the cost of ${S}$ is given by \\ ${F_{VRPTW}(S) = \sum_{i=1}^{m}(C_{VRPTW}(R_{i})+M}$, where ${M}$ is a large constant. ${M}$ is added because minimization of the fleet size is considered to be the primary objective of the VRPTW. ${S}$ is said to be feasible if all routes belonging to ${S}$ are feasible and its customer is served by exactly one route. As described by Solomon [Solomon 1995], we assume that initially all vehicles leave the depot at the earliest possible time ${e_{0}}$. Having obtained a solution of the VRPTW, we adjust the depot departure time of each vehicle to eliminate any unnecessary waiting time.

\end{document}