\documentclass[a4,10pt,fleqn]{article}
\usepackage[a4paper,top=4.0cm,bottom=4.0cm,left=2.0cm,right=2.0cm]{geometry}

\usepackage{gastex}
\usepackage[english]{babel}
\usepackage{times}
\usepackage{pgf}
\usepackage{pstricks}
%\usepackage{graphicx}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amsmath}
\usepackage{comment}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Optimal order picking in automated warehouses}

An automated warehouses contains a matrix of locations where identical boxes are stored.
A given position in the matrix is the I/O interface.
A crane can visit the locations and the I/O position to execute pick-up and delivery operations.\\

Consider the following taxonomy:
\begin{enumerate}
	\item Capacity of the crane: 1, 2, $k>2$.
	\item Dimensions of the warehouse: 1 (locations along oone or two lines with an endpoint in the I/O position), 
	2 (locations organized in a matrix), 
	3 (every location has double depth and can host two boxes: one in the front position is directly accessible from the rail; the other one, in the rear position, can be accessed only after picking-up the box in the front position);
	\item Operations: pick-up only (P): they can be executed in any order; 
	delivery only (D): they must be executed according to the input sequence;
	both pick-up and delivery (PD);
	\item Fixed (F) or variable (V) sites; in the latter case not a single site but a subset of sites is associated with each order; one of themm must be visited to satisfy the order.
	\item Deadlines: without deadlines (N) or with deadlines (Y); deadlines are expressed as max number of trips before satisfying the order or as maximum allowed completion time.
	\item Objectives: minimize the total time (t), minimize the total energy consumption (e).
\end{enumerate}

Some simple variants have been proven to be polynomially solvable.
All complex (NP-hard) variants are still to be solved.\\

Assuming:
\begin{enumerate}
	\item Capacity: 2, $k>2$.
	\item Dimensions: 1, 2, 3.
	\item Operazions: pickup (P), delivery (D), mixed (PD).
	\item Sites: fixed (F) or variable (V).
	\item No deadlines.
	\item Objective: minimize the total distance traveled.
\end{enumerate}
we can classify models with a four fields notation.\\

Tha basic variation $2/1/P/F$ is polynomial.\\

The variants with one complicating feature are polynomial:
$k/1/P/F$, $2/2/P/F$ and $2/3/P/F$, $2/1/D/F$ and $2/1/PD/F$, $2/1/P/V$. \\

Among the variants with two complicating features, these are polynomial: 
$2/2/D/F$ and $2/3/D/F$, $2/2/P/V$ and $2/3/P/V$, $2/1/D/V$.\\

Variant $k/1/D/F$ is polynomial for $k$ fixed.\\

The variants $k/2/P/F$ e $k/3/P/F$ are likely to be NP-hard 
because they are special cases of the Capacitated VRP with unit demand (that is NP-hard).\\

The variant $k/1/P/V$ with two lines is polynomial.\\

The variant $2/1/PD/F$ on a single line is still open.\\

Among the variants with three complicating features these are polynomial:
$2/2/D/V$ and $2/3/D/V$.\\

All other variants are open. An optimization algorithm (dynamic programming, branch-and-bound...) is needed for each of them.\\

Reference: Barbato et al. (2019)\\

Suitable for a project for the O.R. Complements course or a master thesis.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

