% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{enumerate}

\begin{document}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{ Branch-and-price for the multi-depot pickup and delivery problem with heterogeneous fleet
and soft time windows }

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}
\author{Andrea Bettinelli, Alberto Ceselli, Giovanni Righini}

\address{Dipartimento di Tecnologie dell'Informazione, Universit\`a degli Studi di Milano, via Bramante 65, 26013 Crema, Italy}
\ead{\{name.surname\}@unimi.it}

%\begin{abstract}
%The multi-depot pickup and delivery problem with heterogeneous fleet 
%and soft time windows (MDPDPHSTW) requires to find a minimum cost routing for a 
%fleet vehicles with different capacities and based at different depots, 
%satisfying a given set of customers. 
%A customer request is associated with two locations: a source
%where a certain demand must be picked up and a destination where this 
%demand must be delivered. 
%Each route must satisfy pairing constraints
%(pickup and delivery of a customer must both be visited in the same
%route) and precedence constraints (the delivery location must be visited
%after the corresponding pickup location).
%Further, each pickup and delivery location has a time window for the 
%service that can be violated at the cost of a linear penalty.
%In this work we propose a branch-and-price algorithm for the exact solution
%of the problem. It applies column generation techniques to an extended set 
%covering formulation. 
%The pricing problem is solved through a bidirectional dynamic programming
%method.
%\end{abstract}

\begin{keyword}
% keywords here, in the form: keyword \sep keyword
branch-and-price \sep pickup and delivery \sep soft time windows
\end{keyword}

\end{frontmatter}

% main text
\section{Introduction}

The multi-depot pickup and delivery problem with heterogeneous fleet 
and soft time windows (MDPDPHSTW) requires to find a minimum cost routing for a 
fleet vehicles with different capacities and based at different depots, 
satisfying a given set of customers. 
A customer request is associated with two locations: a source
where a certain demand must be picked up and a destination where this 
demand must be delivered. 
Each route must satisfy pairing constraints
(pickup and delivery of a customer must both be visited in the same
route) and precedence constraints (the delivery location must be visited
after the corresponding pickup location).
Further, each pickup and delivery location has a time window for the 
service that can be violated at the cost of a linear penalty.
This problem has application in various scenarios, such as urban courier
services, less-than-truckload transportation, door to door transportation
services.

The problem has been widely studied in the version with hard time windows
constraints (PDPTW).
Several exact approaches based on branch-and-cut \cite{Co06,RoCo07}
and branch-and-price \cite{DuDeSo91,SaSo98,RoCo09} have been proposed.
%Here we briefly recall some of the exact methods that has been proposed
%in the literature. Dumas et al. \cite{DuDeSo91} elaborated a column
%generation approach. They considered heterogeneous vehicles, time
%windows as well as multiple depots. 
%The largest instance solved with this approach contains 55 requests. 
%Another branch-and-price approach
%was described by Savelsberg and Sol \cite{SaSo98}. They used construction
%and improvement heuristics to solve the pricing subproblem and column
%management strategies to reduce the number of columns in the master
%problem.
%In 2006 Cordeau \cite{Co06} developed a branch-and-cut algorithm for the 
%dial-a-ride problem (DARP), later improved by Ropke et al. \cite{RoCo07}. 
%They compared different formulations of the DARP and PDPTW and introduced 
%new families of inequalities. 
%More recently, Ropke and Cordeau developed a branch-and-cut-and-price
%algorithm \cite{RoCo09} able to solve instances with up to 100 requests.
For comprehensive reviews on routing problems involving pickup and
delivery, the reader is referred to the works of Savelsberg and
Sol \cite{SaSo95}, Cordeau et al. \cite{CoLaRo08} and Parragh et
al. \cite{PaDoHa08}.
The soft time windows case was address in an early work by Sexton and Choi \cite{SeCh86}.
They developed a heuristic algorithm based on Benders' decomposition.
Recently, Liberatore et al. \cite{LiSaRi06} and Qureshi et al. \cite{QuTaYa09} 
proposed branch-and-price approaches for the vehicle routing problem with 
soft and semi-soft time windows.

In this work we propose a branch-and-price algorithm for
the MDPDPHSTW which combines ideas proposed in \cite{RoCo09} with
bidirectional label extension and decremental state space relaxation,
and uses a modified version of the algorithm developed by Liberatore
et al. \cite{LiSaRi06} to handle soft time windows.


\section{Problem description\label{sec:Problem-description}}

Given a set $\mathcal{K}$ of vehicle types, a set $\mathcal{H}$ of depots  
and a set $\mathcal{N}$ of customer requests, the problem can be defined 
on a directed graph $G=(V,A)$, where $V$ contains a vertex for each depot 
$h\in \mathcal{H}$ and for the pickup and delivery locations of each customer 
$i \in \mathcal{N}$. 
Non negative weights $d_{ij}$ and $t_{ij}$ are associated with each arc $(i,j)\in A$;
they represent the transportation cost and the traveling time respectively.
%Each customer $i\in\mathcal{N}$
%requires to pickup $q_{i}$ units of goods at a location $p_{i}$ 
%and to deliver them at another location $l_{i}$. 
%Let $P$ and $D$
%be the set of pickup and delivery locations respectively, and let
%$N$ be their union. 
A service time $s_{j}$ and a time window $[a_{j},b_{j}]$ are associated 
to each vertex $j\in V$;
if the service at location $j$ starts inside its time window no penalty is incurred,
otherwise a linear penalty, proportional to
the anticipation or delay through non-negative coefficients $\alpha_{j}$
and $\beta_{j}$ respectively, has to be paid. If we call $T_{j}$ the starting
time of service at location $j$, the penalty term $\pi(T_{j})$ is
defined as follows:
\[
\pi(T_{j})=
\begin{cases}
\alpha_{j}(a_{j}-T_{j}) & \textrm{if }T_{j} < a_{j}\\
0 			& \textrm{if }a_{j}\leq T_{j}\leq b_{j}\\
\beta_{j}(T_{j}-b_{j}) 	& \textrm{if }T_{j} > b_{j}.
\end{cases}
\]
Each vehicle type $k\in\mathcal{K}$
has given capacity $w_{k}$ and fixed cost $f_{k}$. 
A limited number of vehicles is available: 
at most $u_{hk}$ vehicles of type $k\in\mathcal{K}$
can be based at depot $h\in\mathcal{H}$. 

The objective is to minimize the sum of vehicles fixed costs and routing
costs (including penalties), satisfying the following conditions:
(a) all customers is served, 
(b) each customer is visited by only one vehicle,
(c) each route begins at a depot and ends at the same depot,
(d) the capacity of the associated vehicle is not exceeded,
(e) pickup and delivery of a customer are performed in the same route,
(f) the pickup vertices are visited earlier than the corresponding delivery vertices,
(g) the number of available vehicles of each type for each depot
is not exceeded.
%\begin{enumerate}[I]
%\item all customers must be served; 
%\item each customer must be visited by only one vehicle;
%\item each route begins at a depot and ends at the same depot; 
%\item the capacity of the associated vehicle is not exceeded; 
%\item pickup and delivery of a customer are performed in the same route;
%\item the pickup vertices are visited earlier than the corresponding delivery vertices;
%\item the number of available vehicles of each type for each depot
%must not be exceeded; 
%\end{enumerate}

\section{Formulation}

We consider a set covering formulation of the MDPDPHSTW.
We say that a route is feasible if it satisfies conditions (b), (c), (d),
(e) and (f). Let $\Omega_{hk}$ be the set of all feasible routes
using a vehicle of type $k\in\mathcal{K}$ from depot $h\in\mathcal{H}$.
We associate a binary variable $x_{r}$ with each feasible route, which 
takes value 1 if and only if route $r$ is selected. 
Let $a_{ir}$ be a binary coefficient with value 1 if and only if customer
$i$ is visited by route $r$. Let $c_{r}$ be 
the cost of route $r$; it is equal to the sum of the vehicle fixed
cost $f_{k}$ and the routing costs. With these definitions we obtain
the following integer linear programming model: 
\begin{align}
\min 		& \sum_{h\in\mathcal{H}}\sum_{k\in\mathcal{K}}\sum_{r\in\Omega_{hk}}c_{r}z_{r} & \label{mp:obj}\\
\textrm{s.t. } 	& \sum_{h\in\mathcal{H}}\sum_{k\in\mathcal{K}}\sum_{r\in\Omega_{hk}}a_{ir}z_{r}\geq1 & \forall i\in\mathcal{N} \label{mp:sc}\\
 		& \sum_{r\in\Omega_{hk}}z_{r}\leq u_{hk} & \forall h\in\mathcal{H},\ k\in\mathcal{K} \label{mp:card}\\
 		& z_{r}\in\left\{ 0,1\right\}  & \forall h\in\mathcal{H},\ k\in\mathcal{K},\ r\in\Omega_{hk}
\end{align}
Constraints (\ref{mp:sc}) are standard set covering constraints, modeling condition
(a), while (\ref{mp:card}) impose limits on the maximum number of available vehicles
of each type at each depot, modeling condition (g). The objective
is to minimize the overall cost of the selected routes. In the remainder
we indicate this formulation as Master Problem (MP). 


\section{Branch-and-price}

We solve the linear relaxation of the MP to obtain a lower bound which
is used in a tree search algorithm. The number of variables is exponential
in the cardinality of the customer set $\mathcal{N}$, thus we use
a column generation approach. 

Given a depot $h$ and a vehicle type $k$, the problem of
finding the most negative reduced cost column encoding a route for
vehicle $k$ using depot $h$ turns out to be a \emph{Resource Constrained
Elementary Shortest Path Problem} (RCESPP). 
We solve it by using a dynamic
programming algorithm whose structure is similar to the one proposed
in \cite{RoCo09}, enriched with bidirectional label propagation and
decremental state space relaxation techniques. Further, we need to
deal with soft time windows. For this purpose we modify the algorithm 
proposed by Liberatore et al. \cite{LiSaRi06} for the VRPSTW.
The key idea is to store the cost of a path as a convex piecewise linear 
function of the time and to perform partial dominance on time intervals.
In principle it would be necessary to solve, at each iteration, an instance
of RCESPP for every combination of depot and vehicle type, but in
practice it is possible to avoid multiple executions.
Two branching rules are used, one on the number of vehicles and the other 
one on the arcs used.
%First we try to branch on the number of
%vehicles. Let $\bar{z}_{r}$ be the, possibly fractional, optimal
%solution of the MP and $y=\sum_{k\in\mathcal{K}}\sum_{h\in\mathcal{H}}\sum_{r\in\Omega_{hk}}z_{r}$
%be the (possibly fractional) number of vehicles in such solution;
%we perform binary branching, imposing to use at least $\left\lceil y\right\rceil $
%vehicles in one child node and no more than $\left\lfloor y\right\rfloor $
%in the other.
%If $y$ is integer, we apply a different branching rule which forbids
%the use of some arcs. We choose the node with the largest number of
%fractionally used outgoing arcs in the optimal fractional solution
%of MP and we forbid to use half of its outgoing arcs in the first
%child node, and the other half in the second child node.



% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix

% \section{}
% \label{}

\bibliographystyle{plain}
\bibliography{pdp}


%\begin{thebibliography}{00}

% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}

%\bibitem{}

%\end{thebibliography}

\end{document}

