
\documentstyle[amssymb,11pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.50.0.2953}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Created=Wed Oct 20 14:24:53 1999}
%TCIDATA{LastRevised=Friday, September 05, 2008 17:26:31}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{Language=American English}

\textheight236mm
\textwidth161mm
\marginparsep4.0mm
\oddsidemargin0.6mm
\evensidemargin0.6mm
\marginparwidth11.8mm
\topmargin-20mm
\headsep33pt
\renewcommand{\baselinestretch}{1.3}
\parskip0.75ex plus0.10ex minus0.25ex
\topsep0pt
\newlength{\defaultparindent}
\setlength{\defaultparindent}{\parindent}
\setlength\paperheight{11in}\setlength\paperwidth{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.0in}
\newenvironment{Plain Text}{}{}
\newenvironment{annotation Text}{}{}
\newenvironment{annotation Reference}{}{}
\newenvironment{Default Paragraph Font}{}{}
\newtheorem{lemma}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}
\newtheorem{ex}{Example}
\newenvironment{pf}{\noindent\underline{Proof} }{
\hspace*{\fill} $\bigcirc$ \\}
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bea}{\begin{eqnarray}}
\newcommand{\eea}{\end{eqnarray}}
\newcommand{\beas}{\begin{eqnarray*}}
\newcommand{\eeas}{\end{eqnarray*}}
\newcommand{\trsp}{{\it{\top}}}
\newcommand{\defeq}{\buildrel \rm \triangle \over =}
\newcommand{\eqmaybe}{\buildrel \rm ? \over =}
\newcommand{\dto}{\buildrel {\cal D} \over \to}
\newcommand{\mto}{\buildrel {\cal M} \over \to}
\newcommand{\pto}{\buildrel p \over \to}
\newcommand{\iid}{{\em i.i.d.}}
\newcommand{\E}{\textsf{E}}
\newcommand{\var}{{\rm var}}
\newcommand{\cov}{{\rm cov}}
\newcommand{\vep}{\varepsilon}
\newcommand{\R}{{\bf R}}
\newcommand{\Z}{{\bf Z}}
\newcommand{\tzero}{{\tilde t}_0}
\newcommand{\tone}{{\tilde t}_1}
\newcommand{\ttwo}{{\tilde t}_2}
\newcommand{\ttilde}{{\tilde t}}
\newcommand{\mutop}{{\bar \mu}}
\let\implies=\Longrightarrow

%\long\def\symbolfootnote[#1]#2{\begingroup \def\thefootnote{\fnsymbol{footnote}}\footnote[#1]{#2}\endgroup}

\input{tcilatex}
\begin{document}


\setcounter{page}{1} \renewcommand{\theequation}{A\arabic{equation}} %
\setcounter{equation}{0}

\renewcommand{\thefigure}{A\arabic{figure}} \setcounter{figure}{0}

\renewcommand{\thetable}{A\arabic{table}} \setcounter{table}{0}

\newpage
\noindent
\begin{center}
{\Large \textbf{Online Appendix for:\\  \textquotedblleft Going Bunkers: The Joint Route
Selection and Refueling Problem\textquotedblright}}
\end{center}

{\large{
\begin{center}
{\sf Omar Besbes}\footnote{The Wharton School, University of Pennsylvania.
(\texttt{obesbes@wharton.upenn.edu})} \hspace{20mm}
{\sf Sergei Savin}\footnote{Graduate School of Business,
Columbia University.
(\texttt{svs30@columbia.edu})} 
\end{center}}}

%{\LARGE {\bf Appendices for \textquotedblleft Going Bunkers: Joint Route Selection and Inventory Replenishment Problem\textquotedblright} }

\setcounter{footnote}{0}
\setcounter{page}{1}
\vspace*{1.2cm}



\appendix

This is a supplement to the paper \textquotedblleft Going Bunkers: The Joint Route Selection and Refueling Problem\textquotedblright and is organized as follows. Appendix A provides the proofs of the results,  Appendix B focuses on  the estimation details of the fuel pricing model presented in Section 4, and Appendix C is dedicated to a numerical study for the liner case, complementing Section 5.

\section{Proofs}

{\bf Proof of Proposition 1} %Propositions 5.3.3 and 4.3.3 in

We establish the result using value iteration. We introduce a modified
system to obtain an equivalent discrete-time average cost problem 
%so that a relative value iteration algorithm is guaranteed to converge on the auxiliary problem
(see Bertsekas(2000)). We let $\beta $ denote a constant in $(0,\min_{i}\tau
_{ij(i)})$, $\widetilde{w}\left( i,I,{\bf P}\right) =w\left( i,I,{\bf P}%
\right) /\beta $ and $\widetilde{P}_{i}=P_{i}/\tau _{ij(i)}$. In addition,
we let $\nu_{(i,I,{\bf P}),(j,I^{\prime},{\bf P}^{\prime})}(u)$ denote the
transition probability from a state $(i,I,{\bf P})$ to a state $(j,I^{\prime
},{\bf P}^{\prime })$ under a given replenishment decision $u$. We now
define $\widetilde{\nu}_{(i,I,{\bf P),}(j,I^{\prime },{\bf P}^{\prime }{\bf )%
}}(u)=(\beta /\tau _{ij(i)})\nu_{(i,I,{\bf P}),(j,I^{\prime},{\bf P}^{\prime
})}(u)$ for $(i,I,{\bf P})\neq (j,I^{\prime },{\bf P}^{\prime })$ and $%
\widetilde{\nu}_{(i,I,{\bf P),}(i,I,{\bf P)}}(u)=1-(\beta /\tau _{ij(i)})$,
and let $\widetilde{{\Bbb E}}_{{\bf P}^{^{\prime }}|{\bf P}}$ denote the
expectation under $\widetilde{\nu}$. Then $\mu $ and $\widetilde{w}$ satisfy 
\[
\widetilde{w}\left( i,I,{\bf P}\right) =-\mu +\min_{q\in Q\left(
i,j,I\right) }\left( \widetilde{P}_{i}q+\widetilde{{\Bbb E}}_{{\bf P}%
^{^{\prime }}|{\bf P}}\left[ \widetilde{w}\left( j(i),I+q-d_{ij(i)},{\bf P}%
^{^{\prime }}\right) \right] \right) , 
\]%
and the optimal policies are identical for both problems. Now, relative
value iteration is guaranteed to converge to the solution of the Bellman
equation since the modified system is aperiodic (cf. Prop 4.3.1 in
Bertsekas(2000)). 
%\textbf{no need for auxiliary system since modified system is aperiodic...}
We let $\widetilde{w}_{k}$ denote the sequence of functions obtained through
relative value iteration. The recursion takes the following form: 
\begin{eqnarray}
\widetilde{w}_{k+1}\left( i,I,{\bf P}\right) &=&\min_{q\in Q\left(
i,j,I\right) }\left( \widetilde{P}_{i}q+\widetilde{{\Bbb E}}_{{\bf P}%
^{^{\prime }}|{\bf P}}\left[ \widetilde{w}_{k}\left( j(i),I+q-d_{ij(i)},{\bf %
P}^{^{\prime }}\right) \right] \right)  \nonumber  \label{eq:101} \\
&&-\min_{q\in Q\left( i_{0},j(i_{0}),I_{0}\right) }\left( \widetilde{P}%
_{0,i}q+\widetilde{{\Bbb E}}_{{\bf P}^{^{\prime }}|{\bf P}_{0}}\left[ 
\widetilde{w}_{k}\left( j(i_{0}),I_{0}+q-d_{i_{0}j(i_{0})},{\bf P}^{^{\prime
}}\right) \right] \right) ,
\end{eqnarray}%
where $(i_{0},I_{0})$ is an arbitrary location/inventory state. We have 
\begin{eqnarray}
&&\lim_{k\rightarrow \infty }\widetilde{w}_{k}\left( i,I,{\bf P}\right) =%
\widetilde{w}\left( i,I,{\bf P}\right) , \\
&&\mu =\lim_{k\rightarrow \infty }\min_{q\in Q\left(
i_{0},j(i_{0}),I_{0}\right) }\left( \widetilde{P}_{i_{0}}q+\widetilde{{\Bbb E%
}}_{{\bf P}^{^{\prime }}|{\bf P}_{0}}\left[ \widetilde{w}_{k}\left(
j(i_{0}),I_{0}+q-d_{i_{0}j(i_{0})},{\bf P}^{^{\prime }}\right) \right]
\right) .
\end{eqnarray}

We next show that if $\widetilde{w}_{k}\left( i,I,{\bf P}\right) $ is a
piecewise linear convex function with respect to $I$ with changes of slope
that belong to $B(i)$, then so is $\widetilde{w}_{k+1}\left( i,I,{\bf P}%
\right) $.

Suppose that $\widetilde{w}_{k}\left( i,I,{\bf P}\right) $ is a piecewise
linear convex function with respect to $I$ with changes of slope that belong
to $B(i)$. Consider equation (\ref{eq:101}) defining $\widetilde{w}%
_{k+1}\left( i,I,{\bf P}\right) $, the second term is independent of $I$ and
hence we need only focus on the first term. Define 
\begin{eqnarray}
f_{k}\left( i,y,{\bf P}\right) := &&\widetilde{P}_{i}y+\widetilde{{\Bbb E}}_{%
{\bf P}^{^{\prime }}|{\bf P}}\left[ \widetilde{w}_{k}\left( j(i),y-d_{ij(i)},%
{\bf P}^{^{\prime }}\right) \right] , \\
g\left( i,I,{\bf P}\right) := &&\min_{q\in Q\left( i,j,I\right) }\left( 
\widetilde{P}_{i}q+\widetilde{{\Bbb E}}_{{\bf P}^{^{\prime }}|{\bf P}}\left[ 
\widetilde{w}_{k}\left( j(i),I+q-d_{ij(i)},{\bf P}^{^{\prime }}\right) %
\right] \right)  \nonumber \\
&=&-\widetilde{P}_{i}I+\min_{d_{ij(i)}\leq y\leq C}\left( f_{k}\left( i,y,%
{\bf P}\right) \right) .  \label{eq:102}
\end{eqnarray}%
Since $\widetilde{w}_{k}(j(i),y,{\bf P}^{^{\prime }})$ is piecewise linear
convex in $y$ with changes of slopes in $B(j(i))$, $f_{k}\left( i,y,{\bf P}%
\right) $ is piecewise linear convex (with respect to $y$) with changes of
slope in the set $\{b+d_{ij(i)}:b\in B(j(i)),b+d_{ij(i)}\leq C\}=B(i)$. Let $%
y_{k}^{\ast }(i,P)$ denote a minimizer in (\ref{eq:102}); it is possible to
select it such that it occurs at a slope change, i.e., $y_{k}^{\ast
}(i,P)\in B(i)$. We then have 
\begin{eqnarray}
&&g\left( i,I,{\bf P}\right)  \nonumber \\
&=&\widetilde{P}_{i}(y_{k}^{\ast }(i,P)-I)^{+}+\widetilde{{\Bbb E}}_{{\bf P}%
^{^{\prime }}|{\bf P}}\left[ \widetilde{w}_{k}\left( j(i),I+(y_{k}^{\ast
}(i,P)-I)^{+}-d_{ij(i)},{\bf P}^{^{\prime }}\right) \right]  \nonumber \\
&=&1\{I\leq y_{k}^{\ast }(i,P)\}\left[ \widetilde{P}_{i}(y_{k}^{\ast
}(i,P)-I)+\widetilde{{\Bbb E}}_{{\bf P}^{^{\prime }}|{\bf P}}\left[ 
\widetilde{w}_{k}\left( j(i),y_{k}^{\ast }(i,P)-d_{ij(i)},{\bf P}^{^{\prime
}}\right) \right] \right]  \nonumber \\
&&+1\{I>y_{k}^{\ast }(i,P)\}\widetilde{{\Bbb E}}_{{\bf P}^{^{\prime }}|{\bf P%
}}\left[ \widetilde{w}_{k}\left( j(i),I-d_{ij(i)},{\bf P}^{^{\prime
}}\right) \right]  \label{eq:103}
\end{eqnarray}%
In the expression above, the first term is clearly piecewise linear with
changes of slope contained in $B(i)$ since $y_{k}^{\ast }(i,P)\in B(i)$. Now
the same holds for the second term by the assumption on $\widetilde{w}_{k}$.
We deduce that $g\left( i,\cdot ,{\bf P}\right) $ is piecewise linear with
changes of slope contained in $B(i)$. Next, we check that $g(i,\cdot ,{\bf P}%
)$ is convex. 
\begin{eqnarray}
&&g\left( i,I+1,{\bf P}\right) -g\left( i,I,{\bf P}\right)  \nonumber \\
&=&-1\{I+1\leq y_{k}^{\ast }(i,P)\}\widetilde{P}_{i}  \nonumber \\
&&+1\{I+1>y_{k}^{\ast }(i,P)\}\widetilde{{\Bbb E}}_{{\bf P}^{^{\prime }}|%
{\bf P}}\left[ \widetilde{w}_{k}\left( j(i),I+1-d_{ij(i)},{\bf P}^{^{\prime
}}\right) -\widetilde{w}_{k}\left( j(i),I-d_{ij(i)},{\bf P}^{^{\prime
}}\right) \right]
\end{eqnarray}%
For $I\leq y_{k}^{\ast }(i,P)-1$, the right-hand-side above reduces to the
constant $-\widetilde{P}_{i}$. For $I\geq y_{k}^{\ast }(i,P)$, the
right-hand-side above reduces to $\widetilde{w}_{k}\left( j(i),I+1-d_{ij(i)},%
{\bf P}^{^{\prime }}\right) -\widetilde{w}_{k}\left( j(i),I-d_{ij(i)},{\bf P}%
^{^{\prime }}\right) $ which is non-decreasing by the convexity assumption
on $\widetilde{w}_{k}$. In order to establish convexity of $g\left( i,I,{\bf %
P}\right) $, we are only left to check that 
\[
\widetilde{{\Bbb E}}_{{\bf P}^{^{\prime }}|{\bf P}}\left[ \widetilde{w}%
_{k}\left( j(i),y_{k}^{\ast }(i,P)+1-d_{ij(i)},{\bf P}^{^{\prime }}\right) -%
\widetilde{w}_{k}\left( j(i),y_{k}^{\ast }(i,P)-d_{ij(i)},{\bf P}^{^{\prime
}}\right) \right] \geq -\widetilde{P}_{i}, 
\]%
which can be rewritten as 
\[
f_{k}\left( i,y_{k}^{\ast }(i,P)+1,{\bf P}\right) -f_{k}\left( i,y_{k}^{\ast
}(i,P),{\bf P}\right) \geq 0. 
\]%
The latter is clearly true since $f$ is minimized at $y_{k}^{\ast }(i,P)$.
We conclude that $g\left( i,I,{\bf P}\right) $ is a piecewise linear convex
function with changes of slope contained in $B(i)$, which in turn implies
that $\widetilde{w}_{k+1}\left( i,I,{\bf P}\right) $ is a piecewise linear
convex function with changes of slope contained in $B(i)$.

We have hence established that the value iteration step preserves the
convexity and piecewise linearity (with slope changes in $B(i)$) properties.
This implies that that the limit function $\widetilde{w}$ is a piecewise
linear convex function with respect to $I$, with changes of slope contained
in $B(i)$.

Returning to Bellman's equation for the modified system, the optimal policy
solves 
\begin{eqnarray}
\min_{q\in Q\left( i,j,I\right) }\left( \widetilde{P}_{i}q+{\Bbb E} _{{\bf P}%
^{^{\prime }}|{\bf P}}\left[ \widetilde{w}\left( j(i),I+q-d_{ij(i)},{\bf P}%
^{^{\prime }}\right) \right] \right)
\end{eqnarray}
An argument similar to the one provided above establishes that the optimal
policy is of the order-up-to type. There exist location and price dependent
levels $S\left(i,{\bf P}\right)$ such that $q^*\left( i,I,{\bf P}\right) =
(S\left(i,{\bf P}\right)-I)^+$. In addition, those can be chosen so that $%
S\left(i,{\bf P}\right) \in B(i)$. This concludes the proof. $\square$

\medskip
{\bf Proof of Proposition 2}

Consider again the value iteration procedure detailed in (\ref{eq:101}) in
the proof of Proposition 1. Define 
\begin{eqnarray}
f_k \left( i,y,P_{0},{\bf \epsilon ,\alpha } \right) := \widetilde{P}_{i}y+ 
\widetilde{{\Bbb E}}_{P_{0}^{\prime }|P_{0},{\bf \epsilon }^{\prime },{\bf %
\alpha } ^{\prime }|{\bf \alpha }} \left[ \widetilde{w}_k\left(
j(i),y-d_{ij(i)},P_{0}^{\prime },{\bf \epsilon }^{\prime },{\bf \alpha }%
^{\prime }\right)\right],  \label{A1add}
\end{eqnarray}
%\begin{equation}
%f_{k-1}(i,y,P_{0},{\bf \epsilon ,\alpha })=P_{i}y+e^{-\beta \tau _{ij^{\ast
%}(i)}}{\Bbb E}_{P_{0}^{\prime }|P_{0},{\bf \epsilon }^{\prime },{\bf \alpha }%
%^{\prime }|{\bf \alpha }}\Bigl[J_{k-1}(j^{\ast }(i),y-d_{ij^{\ast
%}(i)},P_{0}^{\prime },{\bf \epsilon }^{\prime },{\bf \alpha }^{\prime })%
%\Bigr],  \label{A1add}
%\end{equation}%
where $P_{0}^{\prime }$, $\epsilon ^{\prime }$, and ${\bf \alpha }^{\prime }$
denote the crude oil price, the local price disturbance vector and the
demand-supply\ state vector at the time the liner arrives at port $j^{\ast
}(i)$. For all $0 \le y \le C-1$, let 
\begin{eqnarray}
\Delta_{k}(i,y,P_{0},{\bf \epsilon ,\alpha }) &:=& f_k \left( i,y+1,P_{0},%
{\bf \epsilon ,\alpha } \right) - f_k \left( i,y,P_{0},{\bf \epsilon ,\alpha 
} \right).
\end{eqnarray}
We have that 
\begin{equation}
\widetilde{w}_{k+1}(i,I,P_{0},{\bf \epsilon ,\alpha })=\min_{\max \left(
I,d_{ij^{\ast }(i)}\right) \leq y\leq C}\left( f_{k}(i,y,P_{0},{\bf \epsilon
,\alpha })\right) -P_{i}I  \label{A1}
\end{equation}%
Now, relax the lower bound constraint to $d_{ij^{\ast }(i)}$, and let $%
S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha })$ be an optimal fuel-up-to level
(i.e. the solution of $\min_{d_{ij^{\ast }(i)}\leq y\leq C}f_{k}(i,y,P_{0},%
{\bf \epsilon ,\alpha })$). Note that $w_{k}$ is convex in $I$ and hence so
is $f_{k}(i,y,P_{0},{\bf \epsilon ,\alpha })$ as a function of $y$. This
implies that at $S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha })$, the following
conditions need to be satisfied 
\begin{eqnarray}
\Delta_{k}(i,S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha }),P_{0},{\bf \epsilon
,\alpha }) &\ge &0 \mbox { if } d_{ij^{\ast }(i)} \le S_{k}^{{}}(i,P_{0},%
{\bf \epsilon ,\alpha }) \le C-1  \nonumber \\
\Delta_{k}(i,S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha })-1,P_{0},{\bf %
\epsilon ,\alpha }) &\le &0\mbox { if } d_{ij^{\ast }(i)}+1 \le
S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha }) \le C.  \label{A2}
\end{eqnarray}

% This implies that the necessary first-order optimality conditions are satisfied for some subgradient of $f_{k-1}(i,y,P_{0},{\bf \epsilon ,\alpha }) $ at $S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha })$. These first-order conditions are given by
%\begin{eqnarray}
%\frac{\partial f_{k-1}(i,S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha }),P_{0},{\bf \epsilon ,\alpha })}{%
%\partial y} &\geq &0\mbox { if }S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha }%
%)=d_{ij^{\ast }(i)},  \nonumber \\
%&=&0\mbox { if }d_{ij^{\ast }(i)}<S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha }%
%)<C,  \nonumber \\
%&\leq &0\mbox { if }S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha })=C.
%\label{A2}
%\end{eqnarray}%
Now, the fuel-up-to level $S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha })$ is
non-increasing in $\epsilon _{i}$ if $\Delta_{k}(i,y,P_{0},{\bf \epsilon
,\alpha })$ is non-decreasing in $\epsilon _{i}$. The latter is clearly
satisfied, since 
\begin{eqnarray}
&& \hspace*{-1.5cm} \Delta_{k}(i,y,P_{0},{\bf \epsilon ,\alpha })  \nonumber
\\
&=& \widetilde{P}_{i}+ \widetilde{{\Bbb E}}_{P_{0}^{\prime }|P_{0},{\bf %
\epsilon }^{\prime },{\bf \alpha } ^{\prime }|{\bf \alpha }} \left[ 
\widetilde{w}_k\left( j(i),y-d_{ij(i)},P_{0}^{\prime },{\bf \epsilon }%
^{\prime },{\bf \alpha }^{\prime }\right) - \widetilde{w}_k\left(
j(i),y+1-d_{ij(i)},P_{0}^{\prime },{\bf \epsilon }^{\prime },{\bf \alpha }%
^{\prime }\right)\right]  \nonumber \\
&=& (\gamma P_{0} + \alpha_i + \epsilon_i)/\tau_{ij(i)}  \nonumber \\
& & + \widetilde{{\Bbb E}}_{P_{0}^{\prime }|P_{0},{\bf \epsilon }^{\prime },%
{\bf \alpha } ^{\prime }|{\bf \alpha }} \left[ \widetilde{w}_k\left(
j(i),y-d_{ij(i)},P_{0}^{\prime },{\bf \epsilon }^{\prime },{\bf \alpha }%
^{\prime }\right) - \widetilde{w}_k\left( j(i),y+1-d_{ij(i)},P_{0}^{\prime },%
{\bf \epsilon }^{\prime },{\bf \alpha }^{\prime }\right)\right]
\end{eqnarray}
and the second term does not depend on $\epsilon _{i}$. %\begin{equation}
%P_{i}+e^{-\beta \tau _{ij^{\ast }(i)}}{\Bbb E}_{P_{0}^{\prime }|P_{0},{\bf %
%\epsilon }^{\prime },{\bf \alpha }^{\prime }|{\bf \alpha }}\Bigl[\frac{%
%\partial J_{k-1}(j^{\ast }(i),y-d_{ij^{\ast }(i)},P_{0}^{\prime },{\bf %
%\epsilon }^{\prime }{\bf ,\alpha }^{\prime })}{\partial I}\Bigr]  \label{AA3}
%\end{equation}%
%is nondecreasing in $\epsilon _{i}$. This condition is clearly satisfied,
%since the second term does not depend on $\epsilon _{i}$.

We now turn to the dependence on $P_{0}$. The fuel-up-to level $%
S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha })$ is non-increasing in $P_{0}$ if 
$\Delta _{k}(i,y,P_{0},{\bf \epsilon ,\alpha })$ is non-decreasing in $P_{0}$%
. Suppose the relative value iteration algorithm is started with $\widetilde{%
w}_{0}(\cdot )=0$ for all states, then the condition is satisfied at stage $%
k=0$. Suppose that it is also satisfied up to the stage $k$. At stage $k+1$,
we have for all $I\leq C-1$, 
\begin{eqnarray}
&&\hspace*{-1cm}w_{k+1}(i,I,P_{0},{\bf \epsilon },{\bf \alpha })  \nonumber
\\
&=&\widetilde{P}_{i}(S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha })-I)^{+}+%
\widetilde{{\Bbb E}}_{P_{0}^{\prime }|P_{0},{\bf \epsilon }^{\prime },{\bf %
\alpha }^{\prime }|{\bf \alpha }}\Bigl[w_{k}(j^{\ast
}(i),I+(S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha })-I)^{+}-d_{ij^{\ast
}(i)},P_{0}^{\prime },{\bf \epsilon }^{\prime }{\bf ,\alpha }^{\prime })%
\Bigr],%
\begin{array}{cc}
& 
\end{array}
\label{A3}
\end{eqnarray}%
and%
\begin{eqnarray}
&&\Delta _{k+1}(i,I,P_{0},{\bf \epsilon ,\alpha })  \nonumber \\
&=&-\widetilde{P}_{i}{\bf 1}\{I\leq S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha 
})\}  \nonumber \\
&&+{\bf 1}\{I>S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha })\}{\Bbb E}%
_{P_{0}^{\prime }|P_{0},{\bf \epsilon }^{\prime },{\bf \alpha }^{\prime }|%
{\bf \alpha }}\Bigl[\widetilde{w}_{k}(j^{\ast }(i),I+(S_{k}^{{}}(i,P_{0},%
{\bf \epsilon ,\alpha })-I)^{+}-d_{ij^{\ast }(i)}+1,P_{0}^{\prime },{\bf %
\epsilon }^{\prime }{\bf ,\alpha }^{\prime })  \nonumber \\
&&-\widetilde{w}_{k}(j^{\ast }(i),I+(S_{k}^{{}}(i,P_{0},{\bf \epsilon
,\alpha })-I)^{+}-d_{ij^{\ast }(i)},P_{0}^{\prime },{\bf \epsilon }^{\prime }%
{\bf ,\alpha }^{\prime })\Bigr],  \nonumber \\
&=&-\widetilde{P}_{i}{\bf 1}\{I\leq S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha 
})\}+{\bf 1}\{I>S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha })\}{\Bbb E}%
_{P_{0}^{\prime }|P_{0},{\bf \epsilon }^{\prime },{\bf \alpha }^{\prime }|%
{\bf \alpha }}\Bigl[\Delta _{k}(i,I-d_{ij^{\ast }(i)},P_{0},{\bf \epsilon
,\alpha })\Bigr]  \nonumber \\
&=&-\widetilde{P}_{i}+{\bf 1}\{I>S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha }%
)\}\Bigl[\widetilde{P}_{i}+\widetilde{{\Bbb E}}_{P_{0}^{\prime }|P_{0},{\bf %
\epsilon }^{\prime },{\bf \alpha }^{\prime }|{\bf \alpha }}\Bigl[\Delta
_{k}(i,I-d_{ij^{\ast }(i)},P_{0},{\bf \epsilon ,\alpha })\Bigr]\Bigr].
\label{A4}
\end{eqnarray}%
Let $j=$ $j^{\ast }(i)$ and $k=$ $j^{\ast }(j^{\ast }(i))$, $%
P_{0}^{{}}=P_{0}^{{}}(t),$ $P_{0}^{\prime }=P_{0}^{{}}(t+\tau _{ij})$ and $%
P_{0}^{^{\prime \prime }}=P_{0}^{{}}(t+\tau _{ij}+\tau _{jk}).$ Using the (%
\ref{A4}), we have 
\begin{eqnarray*}
&&\widetilde{P}_{i}+\widetilde{{\Bbb E}}_{P_{0}^{\prime }|P_{0},{\bf %
\epsilon }^{\prime },{\bf \alpha }^{\prime }|{\bf \alpha }}\Bigl[\Delta
_{k+1}(i,I-d_{ij^{\ast }(i)},P_{0},{\bf \epsilon ,\alpha })\Bigr] \\
&=&\widetilde{P}_{i}+\widetilde{{\Bbb E}}_{P_{0}^{\prime }|P_{0},{\bf %
\epsilon }^{\prime },{\bf \alpha }^{\prime }|{\bf \alpha }}\Bigl[-\widetilde{%
P}_{j}^{\prime }+{\bf 1}\{I>S_{k}^{{}}(i,P_{0},{\bf \epsilon ,\alpha })\}%
\Bigl[-\widetilde{P}_{k}^{\prime }+\widetilde{{\Bbb E}}_{P_{0}^{\prime
\prime }|P_{0}^{\prime },{\bf \epsilon }^{\prime \prime },{\bf \alpha }%
^{\prime \prime }|{\bf \alpha ^{\prime }}}\Bigl[\Delta
_{k}(i,I-d_{jk},P_{0}^{\prime },{\bf \epsilon ,\alpha ^{\prime }})\Bigr]%
\Bigr] \\
&=&\gamma P_{0}+\alpha _{i}+\epsilon _{i} \\
&&+\widetilde{{\Bbb E}}_{P_{0}^{\prime }|P_{0},{\bf \epsilon }^{\prime },%
{\bf \alpha }^{\prime }|{\bf \alpha }}\Bigl[-\gamma P_{0}^{\prime }-\alpha
_{j}^{\prime }-\epsilon _{j}^{\prime }+{\bf 1}\{I>S_{k}^{{}}(j,P_{0}^{\prime
},\epsilon ^{\prime }{\bf ,\alpha }^{\prime })\}\Bigl[\widetilde{P}%
_{k}^{\prime }+\widetilde{{\Bbb E}}_{P_{0}^{^{\prime \prime }}|P_{0}^{\prime
},{\bf \epsilon }^{^{\prime \prime }},{\bf \alpha }^{^{\prime \prime }}|{\bf %
\alpha }^{\prime }}\Bigl[\Delta _{k}(i,I-d_{jk},P_{0}^{\prime },{\bf %
\epsilon ,\alpha ^{\prime }})\Bigr]\Bigr] \\
&=&A+B,
\end{eqnarray*}%
where%
\begin{eqnarray}
\hspace*{-1cm}A &=&\gamma \bigl[P_{0}-\widetilde{{\Bbb E}}_{P_{0}^{\prime
}|P_{0}}[P_{0}^{\prime }]\bigr]+\alpha _{i}-\widetilde{{\Bbb E}}_{{\bf %
\alpha }^{\prime }|{\bf \alpha }}[\alpha _{j}^{\prime }]+\epsilon _{i}, 
\nonumber \\
\hspace*{-1cm}B &=&\widetilde{{\Bbb E}}_{P_{0}^{\prime }|P_{0},{\bf \epsilon 
}^{\prime },{\bf \alpha }^{\prime }|{\bf \alpha }}\Bigl[{\bf 1}%
\{I>S_{k}^{{}}(j,P_{0}^{\prime },\epsilon ^{\prime }{\bf ,\alpha }^{\prime
})\}\Bigl[\widetilde{P}_{k}^{\prime }+\widetilde{{\Bbb E}}_{P_{0}^{^{\prime
\prime }}|P_{0}^{\prime },{\bf \epsilon }^{^{\prime \prime }},{\bf \alpha }%
^{^{\prime \prime }}|{\bf \alpha }^{\prime }}\Bigl[\Delta
_{k}(i,I-d_{jk},P_{0}^{\prime },{\bf \epsilon ,\alpha ^{\prime }})\Bigr].%
\Bigr]
\end{eqnarray}%
We first analyze the term $B$. $\widetilde{P}_{k}^{\prime }+{\Bbb E}%
_{P_{0}^{^{\prime \prime }}|P_{0}^{\prime },{\bf \epsilon }^{^{\prime \prime
}},{\bf \alpha }^{^{\prime \prime }}|{\bf \alpha }^{\prime }}\Bigl[\Delta
_{k}(i,I-d_{jk},P_{0}^{\prime },{\bf \epsilon ,\alpha ^{\prime }})\Bigr]$ is
non-decreasing in $P_{0}^{\prime }$ by the induction hypothesis and note
that this expression is non-negative on the domain $\{I>S_{k}^{{}}(i,P_{0},%
{\bf P,\alpha })\}$ (by the optimality condition). The induction hypothesis
also implies that $S_{k}^{{}}(i,P_{0}^{\prime },\epsilon ^{\prime }{\bf %
,\alpha }^{\prime })$ is non-increasing in $P_{0}^{\prime }$ and hence ${\bf %
1}\{I>S_{k}^{{}}(i,P_{0}^{\prime },\epsilon ^{\prime }{\bf ,\alpha }^{\prime
})\}$ is non-decreasing in $P_{0}$. We deduce that the product term within
the outer expectation is non-decreasing in $P_{0}^{\prime }$.\ Assumption 1
(i) (the stochastic ordering of prices) now implies that $B$ is
non-decreasing in $P_{0}$.

Turning to $A$, one notes that the term $\gamma \bigl[P_{0}-{\Bbb E}%
_{P_{0}^{\prime }|P_{0}}[P_{0}^{\prime }]\bigr]$ is non-decreasing in $P_{0}$
by Assumption 1 (ii). We deduce that $\Delta_{k+1}(i,y,P_{0},{\bf \epsilon
,\alpha })$ is non-decreasing in $P_{0}$ . This is in turn implies that the
property is satisfied in the limit and the result follows. $\square $

\medskip
{\bf Proof of Proposition 3}

Let $I^{\prime }>I,$ both in $[0,C]$. By definition of $q^{\ast }(i,j,I,{\bf %
P}),$ we have 
\begin{eqnarray*}
q^{\ast }(i,j,I,{\bf P})=-I +\min \left( \arg \max_{y\in \widetilde{Q}%
(i,j,I)}\left( -P_{i}q+{\Bbb E}_{{\bf P}^{^{\prime }}|{\bf P},{\bf r}%
^{^{\prime }}}\left[ h\left( j,y-d_{ij},{\bf P}^{^{\prime }},{\bf r}%
^{^{\prime }}\right) \right] \right) \right) ,
\end{eqnarray*}%
where $\widetilde{Q}(i,j,I)=\{y|y\geq I,d_{ij}\leq y\leq C\}$ and $y$ is the
fuel-up-to\ level. Now, we have%
\begin{eqnarray}
&&I+q^{\ast }(i,j,I,{\bf P})  \nonumber \\
&=&\min \left( \arg \max_{y\in \widetilde{Q}(i,j,I)}\left(-P_{i}q+{\Bbb E}_{%
{\bf P}^{^{\prime }}|{\bf P},{\bf r}^{^{\prime }}}\left[ h\left( j,y-d_{ij},%
{\bf P}^{^{\prime }},{\bf r}^{^{\prime }}\right) \right] \right) \right) 
\nonumber \\
&\leq &\min \left( \arg \max_{y\in \widetilde{Q}(i,j,I^{\prime })}\left(
-P_{i}q+{\Bbb E}_{{\bf P}^{^{\prime }}|{\bf P},{\bf r}^{^{\prime }}}\left[
h\left( j,y-d_{ij},{\bf P}^{^{\prime }},{\bf r}^{^{\prime }}\right) \right]
\right) \right)  \nonumber \\
&=&I^{\prime }+q^{\ast }(i,j,I^{\prime },{\bf P}),  \label{qkj2}
\end{eqnarray}%
where the inequality follows from the fact that $I^{\prime }>I$. Hence, $%
I+q_{k}^{\ast }(i,j,I,{\bf P})$ is a non-decreasing function of $I$. $%
\square $

\iffalse{\bf Proof of Lemma \ref{lem:reach} }

Consider without loss of generality the point $z_{1}=(i_{1},I_{1})$.
Recalling that according to our assumptions, $i_{1}$ is reachable from $i$
in a finite number transitions. Consider such transitions while buying the
minimum possible fuel. Let $I_{1}^{(0)}$ denote the inventory when arriving
at $i_{1}$, which need not be equal to $I_{1}$. If $I_{1}^{(0)}\leq I_{1}$,
then moving from $(i_{1},I_{1}^{(0)})$ to $z_{2}=(i_{2},I_{2})$ is feasible
since $I_{1}-d_{ii^{\prime }}\leq I_{2}\leq C-d_{i_{1}i_{2}}$ implies $%
I_{1}^{(0)}-d_{i_{1}i_{2}}\leq I_{2}\leq C-d_{i_{1}i_{2}}$. Now, one can
move from $(i_{2},I_{2})$ to $(i_{1},I_{1})$ in a finite number of steps by
following the cycle and the result follows. Suppose, on the other hand, that 
$I_{1}^{(0)}>I_{1}$. Observe that on the cycle, the purchased quantity of
fuel at the node $z_{l}$ is given by $%
q_{i_{l},i_{l+1}}=I_{l+1}+d_{i_{l},i_{l+1}}-I_{l}$, $l=1,...,k$, where $%
i_{k+1}=i_{1},I_{k+1}=I_{1}$. Let $m^{\ast }$ be the maximum integer $m\geq
1 $ such that $I_{1}^{(0)}-\sum_{l=1}^{m-1}d_{i_{l}i_{l+1}}>I_{m}$. Starting
at $(i_{1},I_{1}^{(0)})$, consider the path that purchases nothing until
arriving to $i_{m^{\ast }}$, which is feasible by definition of $m^{\ast }$.
Then, at $i_{m^{\ast }}$, the inventory $I_{m}^{(}0)$ satisfies $I_{m^{\ast
}}^{(0)}\leq I_{m^{\ast }+1}-d_{i_{m^{\ast }}i_{m^{\ast }+1}}$. Consider the
purchase of $I_{m^{\ast }+1}-d_{i_{m^{\ast }}i_{m^{\ast }+1}}-I_{m^{\ast
}}^{(0)}\geq 0$, then we arrive at $(i_{m^{\ast }+1},I_{m^{\ast }+1})$ and
one can reach $(i_{1},I_{1})$ in a finite number of steps by following the
cycle. {\tt Notation!!! mod $k$ , for the cycle... could have many cycles
before reaching the point} $\square $ \fi

\medskip
{\bf Proof of Proposition 4}

a) Consider without loss of generality the point $z_{1}=(i_{1},I_{1})$.
Recall that, according to our assumptions, $i_{1}$ is reachable from $i$ in
a finite number transitions. Consider a vessel making such transitions while
buying the minimum possible amount of fuel necessary for such a trip. Let $%
I_{1}^{(0)}$ denote the level of fuel inventory that a vessel has when
arriving at $i_{1}$. Note that such inventory level need not be equal to $%
I_{1}$. If $I_{1}^{(0)}\leq I_{1}$, then moving from $(i_{1},I_{1}^{(0)})$
to $z_{2}=(i_{2},I_{2})$ in a single transition is feasible, since $%
I_{1}-d_{ii^{\prime }}\leq I_{2}\leq C-d_{i_{1}i_{2}}$ implies $%
I_{1}^{(0)}-d_{i_{1}i_{2}}\leq I_{2}\leq C-d_{i_{1}i_{2}}$. Now, one can
move from $(i_{2},I_{2})$ to $(i_{1},I_{1})$ in a finite number of steps by
following the cycle and the result follows. Suppose, on the other hand, that 
$I_{1}^{(0)}>I_{1}$. Observe that on the cycle, the purchased quantity of
fuel at the node $z_{l}$ is given by $%
q_{i_{l},i_{l+1}}=I_{l+1}+d_{i_{l},i_{l+1}}-I_{l}$, $l=1,...,k$, where $%
i_{k+1}=i_{1},I_{k+1}=I_{1}$. Let $m^{\ast }$ be the maximum integer $m\geq
1 $ such that $I_{1}^{(0)}-\sum_{l=1}^{m-1}d_{i_{l}i_{l+1}}>I_{m}$, where $%
i_{n}$ for $n>k$ is defined as $i_{n\func{mod}k}$.\ Starting at $%
(i_{1},I_{1}^{(0)})$, consider the path that purchases no fuel until
arriving at $i_{m^{\ast }}$. Such policy is feasible by definition of $%
m^{\ast }$. Then, at $i_{m^{\ast }}$, the inventory $I_{m}^{(0)}$ satisfies $%
I_{m^{\ast }}^{(0)}\leq I_{m^{\ast }+1}-d_{i_{m^{\ast }}i_{m^{\ast }+1}}$.
While $i_{m^{\ast }}$, consider the purchase of $I_{m^{\ast
}+1}-d_{i_{m^{\ast }}i_{m^{\ast }+1}}-I_{m^{\ast }}^{(0)}\geq 0$ units of
fuel. Then a vessel arrives at $(i_{m^{\ast }+1},I_{m^{\ast }+1})$ and can
now reach $(i_{1},I_{1})$ in a finite number of steps by following the cycle.

b) This part just indicates how to reach the optimal cycle in the
location-inventory space. $\square$

\newpage

{\bf Proof of Proposition 5}

Consider the revenue maximizing cycle ${\cal C}^{(r)}$. Let 
\[
k=\left\lfloor (C-d_{i_{m^{\ast }},i_{min}}-d_{i_{m^{\ast
}},i_{min}})/\sum_{i=1}^{m}d_{i,i+1}\right\rfloor , 
\]%
and note that $k\geq 1$ since $C\geq I_{{\cal C}^{(r)}}$. The associated
profit per unit of time corresponding to $\pi _{{\cal C}^{(r)}}$ is given by 
\begin{eqnarray*}
\lambda _{\pi _{{\cal C}^{(r)}}} &=&\frac{k\sum_{(i,j)\in {\cal C}%
^{(r)}}r_{ij}-P_{i_{\min }}\left[ k\sum_{(i,j)\in {\cal C}%
^{(r)}}d_{ij}+d_{i_{m^{\ast }},i_{min}}+d_{i_{min},i_{m^{\ast }}}\right] }{%
k\sum_{(i,j)\in {\cal C}^{(r)}}\tau _{ij}+\tau _{i_{m^{\ast }},i_{min}}+\tau
_{i_{min},i_{m^{\ast }}}} \\
&=&\frac{\sum_{(i,j)\in {\cal C}^{(r)}}[r_{ij}-P_{i_{\min
}}d_{ij}]+k^{-1}P_{i_{\min }}[d_{i_{m^{\ast
}},i_{min}}+d_{i_{min},i_{m^{\ast }}}]}{\sum_{(i,j)\in {\cal C}^{(r)}}\tau
_{ij}+k^{-1}[\tau _{i_{m^{\ast }},i_{min}}+\tau _{i_{min},i_{m^{\ast }}}]}.
\end{eqnarray*}%
Note that $\lambda ^{D}$ is upper bounded by the optimal profits in a system
where all prices are set at $P_{\min }$, and that in such a system, the
vessel maximizes profits by following ${\cal C}^{(r)}$ (see Section 6.2.1). Hence 
\begin{eqnarray*}
\frac{\lambda _{\pi _{{\cal C}^{(r)}}}}{\lambda ^{D}} &\geq &\frac{%
\sum_{(i,j)\in {\cal C}^{(r)}}[r_{ij}-P_{i_{\min }}d_{ij}]+k^{-1}P_{i_{\min
}}[d_{i_{m^{\ast }},i_{min}}+d_{i_{min},i_{m^{\ast }}}]}{\sum_{(i,j)\in 
{\cal C}^{(r)}}\tau _{ij}+k^{-1}[\tau _{i_{m^{\ast }},i_{min}}+\tau
_{i_{min},i_{m^{\ast }}}]}\frac{\sum_{(i,j)\in {\cal C}^{(r)}}\tau _{ij}}{%
\sum_{(i,j)\in {\cal C}^{(r)}}[r_{ij}-P_{i_{\min }}d_{ij}]} \\
&=&\frac{\sum_{(i,j)\in {\cal C}^{(r)}}[r_{ij}-P_{i_{\min
}}d_{ij}]+k^{-1}P_{i_{\min }}[d_{i_{m^{\ast
}},i_{min}}+d_{i_{min},i_{m^{\ast }}}]}{\sum_{(i,j)\in {\cal C}%
^{(r)}}[r_{ij}-P_{i_{\min }}d_{ij}]}\frac{\sum_{(i,j)\in {\cal C}^{(r)}}\tau
_{ij}}{\sum_{(i,j)\in {\cal C}^{(r)}}\tau _{ij}+k^{-1}[\tau _{i_{m^{\ast
}},i_{min}}+\tau _{i_{min},i_{m^{\ast }}}]} \\
&\geq &\biggl[1+k^{-1}\frac{\tau _{li^{\ast }}+\tau _{i^{\ast }l}}{%
\sum_{(i,j)\in {\cal C}^{(r)}}\tau _{ij}}\biggr]^{-1} \\
&\geq &1-k^{-1}\frac{d_{i_{m^{\ast }},i_{min}}+d_{i_{min},i_{m^{\ast }}}}{%
\sum_{(i,j)\in {\cal C}^{(r)}}d_{ij}}
\end{eqnarray*}%
Note that $C\geq k\sum_{(i,j)\in {\cal C}^{(r)}}d_{ij}+[d_{i_{m^{\ast
}},i_{min}}+d_{i_{min},i_{m^{\ast }}}]$ and hence $(1/C)k\sum_{(i,j)\in 
{\cal C}^{(r)}}d_{ij}\leq 1-2\zeta $. We deduce that 
\[
\frac{\lambda _{\pi _{{\cal C}^{(r)}}}}{\lambda ^{D}}\geq 1-\frac{2\zeta }{%
1-2\zeta }=\frac{1-4\zeta }{1-2\zeta }. 
\]%
This concludes the proof. $\square $

\medskip
{\bf Proof of Proposition 6}

Let $\hat{\lambda}$ denote the optimal profit per unit of time in a system
where for all $i \in {\cal N}$, the price at port $i$ is constant equal to $%
\underline{P}$ and for all arcs $(i,j) \in {\cal N}$, the rewards are
constant and equal to $\bar{r}_{ij}$. Let $\hat{{\cal C}}$ denote the
optimal (location) cycle corresponding to $\hat{\lambda}$. We have $\hat{\lambda} \ge
\lambda^*$ implying that $\lambda^* - \lambda_{OLC} \le \hat{\lambda} -
\lambda_{OLC}$. Below, we upper bound the  $\hat{\lambda} -
\lambda_{OLC}$.

Consider a system where all the fuel prices are set at $P_c = \underline{P}$ and rewards are set at their
steady-sate expectations and note in such a system, the optimal cycle to follow is the one followed by the OLC heuristic. Let us denote this cycle by ${\cal C}_{OLC}$. In particular, the profit per unit of time associated with this cycle in this system is no less
than the profit per unit of time generated when following $\hat{{\cal C}}$ and 
\begin{eqnarray*}
\frac{\sum_{(i,j)\in {\cal C}_{OLC}}{\Bbb E} [r_{ij}]-P_c d_{ij} }{\sum_{(i,j)\in {\cal C}_{OLC}}\tau _{ij}} 
&\ge&  \frac{\sum_{(i,j)\in \hat{{\cal C}}}{\Bbb E}[r_{ij}]-P_c d_{ij}}{\sum_{(i,j)\in \hat{{\cal C}}}\tau _{ij}} \\
&=&\frac{\sum_{(i,j)\in \hat{{\cal C}}}\bar{r}_{ij}-\underline{P}d_{ij}}{\sum_{(i,j)\in \hat{{\cal C}}}\tau_{ij}}-\frac{\sum_{(i,j)\in \hat{{\cal C}}}(\bar{r}_{ij}-{\Bbb E}[r_{ij}])}{\sum_{(i,j)\in \hat{{\cal C}}}\tau _{ij}} \\
&=&\hat{\lambda}-\frac{\sum_{(i,j)\in \hat{{\cal C}}}(\bar{r}_{ij}-{\Bbb E}[r_{ij}])}{\sum_{(i,j)\in \hat{{\cal C}}}\tau _{ij}} \\
&\geq &\hat{\lambda}-\frac{\sum_{(i,j)\in \hat{{\cal C}}}1}{\sum_{(i,j)\in \hat{{\cal C}}}\tau _{ij}}\Delta _{r}.
%&\geq &\hat{\lambda}-\omega \Delta _{r}-\rho (P_c-\underline{P}).
\end{eqnarray*}%
Now, in the true system, consider the policy that follows the cycle ${\cal C}_{OLC}$ and replenishes at each port the exact amount necessary to reach the next port on the cycle. Its performance is given by
\begin{eqnarray*}
\frac{\sum_{(i,j)\in {\cal C}_{OLC}}{\Bbb E} [r_{ij}]- {\Bbb E}_{\infty} [P_i] d_{ij} }{\sum_{(i,j)\in {\cal C}_{OLC}}\tau _{ij}},
\end{eqnarray*}%
and is dominated by the performance of the OLC heuristic as the latter follows the same route but optimizes the refueling amounts. Hence
\begin{eqnarray*}
\lambda_{OLC} &\ge& \frac{\sum_{(i,j)\in {\cal C}_{OLC}}{\Bbb E} [r_{ij}]- {\Bbb E}_{\infty} [P_i] d_{ij} }{\sum_{(i,j)\in {\cal C}_{OLC}}\tau _{ij}} \\
&=&  \frac{\sum_{(i,j)\in {\cal C}_{OLC}}{\Bbb E} [r_{ij}]-\underline{P} d_{ij} }{\sum_{(i,j)\in {\cal C}_{OLC}}\tau _{ij}} - \frac{\sum_{(i,j)\in {\cal C}_{OLC}} ({\Bbb E}_{\infty} [P_i]-\underline{P})d_{ij}}{\sum_{(i,j)\in {\cal C}_{OLC}}\tau _{ij}}\\
&\ge& \hat{\lambda}-\omega \Delta _{r} - \frac{\sum_{(i,j)\in {\cal C}_{OLC}} ({\Bbb E}_{\infty} [P_i]-\underline{P})d_{ij}}{\sum_{(i,j)\in {\cal C}_{OLC}}\tau _{ij}}\\
&\ge& \hat{\lambda}-\omega \Delta _{r}-\rho \Delta_{p}.
\end{eqnarray*}%
This completes the proof. $\square $

\medskip
{\bf Proof of Proposition 7}

Let $\hat{\lambda}$ denote the optimal profit per unit of time in a system
where for all $i \in {\cal N}$, the price at port $i$ is constant equal to $%
\underline{P}_i$ and for all arcs $(i,j) \in {\cal N}$, the rewards are
constant and equal to $\bar{r}_{ij}$. Let $\hat{{\cal C}}$ denote the
optimal (location-inventory) cycle corresponding to $\hat{\lambda}$. We have $\hat{\lambda} \ge
\lambda^*$ implying that $\lambda^* - \lambda_{OLIC} \le \hat{\lambda} -
\lambda_{OLIC}$. Below, we upper bound the $\hat{\lambda} -
\lambda_{OLC}$.

Consider a system where all the fuel prices and rewards are set at their
steady-sate expectations and note in such a system, $\lambda _{OLIC}$ is the
optimal profit per unit of time. In particular, $\lambda _{OLIC}$ is no less
than the long-run profit per unit of time generated when following $\hat{%
{\cal C}}$ and 
\begin{eqnarray*}
\lambda _{OLIC} &\geq &\frac{\sum_{(z,z^{\prime })\in \hat{{\cal C}}}{\Bbb E}%
[r_{ii'}]-{\Bbb E}_{\infty }[P_{i}](I^{\prime }-I+d_{ii'})}{\sum_{(z,z^{\prime
})\in \hat{{\cal C}}}\tau _{ii'}} \\
&=&\frac{\sum_{(z,z^{\prime })\in \hat{{\cal C}}}\bar{r}_{ii'}-\underline{P}%
_{i}(I^{\prime }-I+d_{ii'})}{\sum_{(z,z^{\prime })\in \hat{{\cal C}}}\tau
_{ii'}}-\frac{\sum_{(z,z^{\prime })\in \hat{{\cal C}}}(\bar{r}_{ii'}-{\Bbb E}%
[r_{ii'}])+({\Bbb E}_{\infty }[P_{i}]-\underline{P}_{i})(I^{\prime }-I+d_{ii'})%
}{\sum_{(z,z^{\prime })\in \hat{{\cal C}}}\tau _{ii'}} \\
&=&\hat{\lambda}-\frac{\sum_{(z,z^{\prime })\in \hat{{\cal C}}}(\bar{r}_{ii'}-%
{\Bbb E}[r_{ii'}])+({\Bbb E}_{\infty }[P_{i}]-\underline{P}_{i})(I^{\prime
}-I+d_{ii'})}{\sum_{(z,z^{\prime })\in \hat{{\cal C}}}\tau _{ii'}} \\
&\geq &\hat{\lambda}-\frac{\sum_{(z,z^{\prime })\in \hat{{\cal C}}}1}{%
\sum_{(z,z^{\prime })\in \hat{{\cal C}}}\tau _{ii'}}\Delta _{r}-\frac{%
\sum_{(z,z^{\prime })\in \hat{{\cal C}}}d_{ii'}}{\sum_{(z,z^{\prime })\in 
\hat{{\cal C}}}\tau _{ii'}}\widetilde{\Delta}_{p}  \\
&\geq &\hat{\lambda}-\widetilde{\omega} \Delta _{r}-\widetilde{\rho} \widetilde{\Delta}_{p}.
\end{eqnarray*}%
This yields the result. $\square $

\renewcommand{\theequation}{B\arabic{equation}} \setcounter{equation}{0}

\renewcommand{\thefigure}{B\arabic{figure}} \setcounter{figure}{0}

\renewcommand{\thetable}{B\arabic{table}} \setcounter{table}{0}

\section{Estimation Details of the Fuel Pricing Model}

\label{A:price}

Below we describe how we used the actual pricing data to estimate the
parameters associated with the price model (3). Let $k$
denote the number of price observations (days) and let $P_{ij}^{k}$ denote
the price at port $i=1,...,N$ on day $j=1,...,k$. The corresponding price of
crude oil on day $j=1,...,k$ is denoted as $P_{0j}^{k}$. Define 
\begin{equation}
\hat{\gamma}^{k}=\frac{\dsum\limits_{i=1}^{N}\dsum\limits_{j=1}^{k}P_{ij}^{k}%
}{N\dsum\limits_{j=1}^{k}P_{0j}^{k}}.  \label{gammak}
\end{equation}%
Note that in our model we assume that $\sum_{i=1}^{N}A_{i}=0$, so that we
get $\hat{\gamma}^{k}\rightarrow \gamma $ as $k\rightarrow \infty $ almost
surely. Similarly, define 
\begin{equation}
\hat{A}_{i}^{k}=\frac{\dsum\limits_{j=1}^{k}P_{ij}^{k}}{k}-\hat{\gamma}^{k}%
\frac{\dsum\limits_{j=1}^{k}P_{0j}^{k}}{k},i=1,...,N,  \label{Ak}
\end{equation}%
and note that $\hat{A}_{i}^{k}\rightarrow A_{i}$ as $k\rightarrow \infty $
almost surely. Further, let%
\begin{equation}
\overline{P}_{ij}^{k}=P_{ij}^{k}-\hat{\gamma}^{k}P_{0j}^{k}-\hat{A}%
_{i}^{k},i=1,...,N,j=1,...,k  \label{Pk}
\end{equation}%
denote the deviation of the fuel price at port $i=1,...,N$ on day $j=1,...,k$
from the \textquotedblleft average\textquotedblright\ behavior. If the fuel
price dynamics is described by the model (3), the
\textquotedblleft trajectory\textquotedblright\ of $\overline{P}_{ij}^{k}$
is a result of juxtaposition of two independent, mean-zero processes: a
two-state Markov process with amplitude $\delta _{i}$ and inertia parameter $%
\eta _{i}$ and the stationary process with standard deviation $\sigma _{i}$.
Given the state information for the port-specific Markov chains were not
available to us, we estimated the remaining price dynamics parameters
employing the following simple approach. Assuming that $\sigma _{i}$ is
substantially smaller than $\delta _{i}$, we can estimate the value of $\eta
_{i}$ as the fraction of days on which the sign of $\overline{P}_{ij}^{k}$
coincides with the sign of $\overline{P}_{i,j-1}^{k}$:%
\begin{equation}
\widehat{\eta }_{i}^{k}=\frac{\dsum\limits_{j=2}^{k}\left( \frac{\overline{P}%
_{ij}^{k}\overline{P}_{i,j-1}^{k}+\left\vert \overline{P}_{ij}^{k}\overline{P%
}_{i,j-1}^{k}\right\vert }{2\left\vert \overline{P}_{ij}^{k}\overline{P}%
_{i,j-1}^{k}\right\vert }\right) }{k-1},i=1,...,N\text{.}  \label{etak}
\end{equation}%
The adequacy of this assumption is confirmed post-factum by the values shown
in Table 1. In turn, the values of $\delta _{i}$ and $\sigma _{i}$
are estimated as%
\begin{equation}
\widehat{\delta }_{i}^{k}=\frac{\dsum\limits_{j=1}^{k}\left\vert \overline{P}%
_{ij}^{k}\right\vert }{k},i=1,...,N,  \label{deltai}
\end{equation}%
and%
\begin{equation}
\widehat{\sigma }_{i}^{k}=\sqrt{\frac{\dsum\limits_{j=1}^{k}\left(
\left\vert \overline{P}_{ij}^{k}\right\vert -\widehat{\delta }%
_{i}^{k}\right) ^{2}}{k-1}},i=1,...,N.  \label{sigmai}
\end{equation}

In our numerical analysis we use the parameter estimates obtained from the
prices for $N=18$ ports for the period of January-June 2005 ($k=98$ trading
days). Thus, in total, $18\times 98=1764$\ ($N\times k$) pricing data points
were used to estimate $4\times N+1=4\times 18+1=73$ parameters of our
bunkers pricing model.

Due to the absence of the port-specific information on the realized states
of the Markov chains $\alpha $, we could not provide reliable confidence
intervals for the parameter estimates in Table 1. However, in
order to get a sense of the goodness-of-fit for our model, we have also
calculated the resulting $R^{2}$ value for our model as well as $R^{2}$
value for a simpler model of bunkers price dynamics, which ignored the time
dynamics of the local supply corrections to bunkers prices, replacing them
by port-dependent constants ($P_{i}(t)=\gamma P_{0}(t)+A_{i}+\epsilon
_{i}(t) $, where $A_{i}$ is constant). The\ $R^{2}$ for our model turned out
to be $0.68$ as compared to $0.35$ for the simplified model. Clearly, the
presence of the Markov term ${\bf \alpha }$ accounts for a significant
fraction of the explanatory power of our model. As the value $\gamma =4.43$
indicates, the oil-price-related component $\gamma P_{0}(t)$ is responsible
for the bulk of the bunkers price value:\ for the average crude oil price
over the period of January-June 2005, $\$51.4$, its contribution is $\$227.7$%
. On a given day at a given port, this contribution accounts for about $%
80\%-90\%$ of the total bunker price.

We now turn attention to the estimation of the dynamics of the crude oil
prices. Below we use the actual WTI crude oil prices for the period of
January-June 2005 to fit both models described in (4) and (5). Figure \ref{Figure8rev} shows the histogram of actual relative daily
changes in oil prices for this period along with the plot of the PDF of the
corresponding best-fit normal random variable ($\mu _{0}=0.00,$ $\sigma
_{0}=0.03$). \FRAME{ftbpFU}{4.7694in}{3.5829in}{0pt}{\Qcb{Histograms of
actual and best-fit normal relative daily crude oil price changes for
January-June 2005.}}{\Qlb{Figure8rev}}{figure8rev.wmf}{\special{language
"Scientific Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display
"USEDEF";valid_file "F";width 4.7694in;height 3.5829in;depth
0pt;original-width 9.9998in;original-height 7.4996in;cropleft "0";croptop
"1";cropright "1";cropbottom "0";filename 'Figure8rev.wmf';file-properties
"XNPEU";}} The goodness-of-fit test measures for this model are:
Anderson-Darling, $AD=0.8089$, Kolmogorov-Smirnov, $KS=0.1106$, and
Chi-Square, $\chi ^{2}=27.04.$

The fit for the mean-reverting model,%
\begin{equation}
P_{0}(t+1)=\lambda P_{0}(t)+(1-\lambda )\widehat{P}_{0}+\varepsilon _{0}(t),%
\text{ }\varepsilon _{0}(t)\sim N\left( 0,\sigma _{0}\right) ,
\label{mean-fit}
\end{equation}%
with $\lambda =0.96$, $\widehat{P}_{0}=\$55.5$, and $\sigma _{0}=\$1.25$,
illustrated in Figure \ref{Figure9rev}, is near-perfect ($R^{2}=0.91$,
significance of $F=0$, $95\%$ CI for the slope value $\lambda $ is $\left[
0.90,1.02\right] $). The goodness-of-fit values measures for the normal
distribution of error terms for this model ($AD=0.7076$, $KS=0.1055$, $\chi
^{2}=20.75$) indicate a somewhat better fit than that for the GBM model. 
\FRAME{ftbpFU}{4.267in}{3.2076in}{0pt}{\Qcb{Actual and best-fit
mean-reverting values of the crude-oil prices for January-June 2005. }}{\Qlb{%
Figure9rev}}{figure9rev.wmf}{\special{language "Scientific Word";type
"GRAPHIC";maintain-aspect-ratio TRUE;display "USEDEF";valid_file "F";width
4.267in;height 3.2076in;depth 0pt;original-width 9.9998in;original-height
7.4996in;cropleft "0";croptop "1";cropright "1";cropbottom "0";filename
'Figure9rev.wmf';file-properties "XNPEU";}}

Based on these estimation results, we have selected the mean-reverting model
to represent stochastic crude oil price dynamics. In addition to the
goodness-of-fit arguments, computational arguments also favor selecting
mean-reverting dynamics over those of a GBM model since the former allow the
use of a finite number of prices for describing the state of the system in
the dynamic program (2). Indeed, since the limiting variance of the
mean-reverting process (\ref{mean-fit}), 
\begin{equation}
\lim_{t\rightarrow \infty }\left( \text{Var}[P_{0}\left( t\right) ]\right) =%
\frac{\left( 1.25\right) ^{2}}{1-\left( 0.96\right) ^{2}}=19.92,
\label{var-mean}
\end{equation}%
is finite (as opposed to the corresponding value for the GBM process), we
can use the finite-state approximation to represent this process. Consider
the \textquotedblleft limiting\textquotedblright\ value of the
mean-reverting process (\ref{mean-fit}), \ $\lim_{t\rightarrow \infty
}\left( {\Bbb E}[P_{0}\left( t\right) ]\right) =55.5$. Since the limiting
value of the standard deviation of $P_{0}(t)$ from this level, $\sqrt{19.92}%
=4.46$, we can limit our attention to the \textquotedblleft 2
deviations\textquotedblright\ price interval $\left[ 55.5-2\times
4.46,55.5+2\times 4.46\right] $, or, rounding, to $\left[ 46,62\right] $%
\footnote{%
In May of 2008, the crude oil has crossed a \$120/bbl barrier. This
development underscores a precarious nature of the process of forecasting
the crude oil prices, and suggests frequent recalibration of the forecasting
models.}. Noting that since according to (\ref{mean-fit}), the conditional
distribution of $P_{0}(t+1)$ is normal with mean $0.96P_{0}(t)+(1-0.96)%
\times 55.5$ and standard deviation of $\sigma _{0}=1.25$, we can use a
standard discretization procedure to approximate this continuous
distribution by a discrete one defined on the interval $\left[ P_{0}^{\min
},P_{0}^{\max }\right] $ with $P_{0}^{\min }=46$ and $P_{0}^{\max }=62$ as
follows. Letting, for any $P$, $f_{+}(P)=[P+0.5-(\lambda P_{0}(t)+\left(
1-\lambda \right) \widehat{P}_{0})]\sigma _{0}^{-1}$ and $%
f_{-}(P)=[P-0.5-(\lambda P_{0}(t)+\left( 1-\lambda \right) \widehat{P}%
_{0})]\sigma _{0}^{-1}$, we define 
\begin{equation}
\text{Prob}\left( P_{0}(t+1)=P|P_{0}(t)\right) =\left\{ 
\begin{array}{ll}
1-\Phi \left( f_{-}(P)\right) , & P=P_{0}^{\max }, \\ 
\Phi \left( f_{+}(P)\right) -\Phi \left( f_{-}(P)\right) , & P_{0}^{\min
}<P<P_{0}^{\max }, \\ 
\Phi \left( f_{+}(P)\right) , & P=P_{0}^{\min },%
\end{array}%
\right.  \label{discreteprob}
\end{equation}%
where $\lambda =0.96$, $\Phi (x)=\frac{1}{\sqrt{2\pi }}\int_{-\infty
}^{x}e^{-\frac{t^{2}}{2}}dt$ is the standard normal CDF, and $P_{0}(t)\in %
\left[ P_{0}^{\min },P_{0}^{\max }\right] $ .

\bigskip

\renewcommand{\theequation}{B\arabic{equation}} \setcounter{equation}{0}

\renewcommand{\thefigure}{B\arabic{figure}} \setcounter{figure}{0}

\renewcommand{\thetable}{B\arabic{table}} \setcounter{table}{0}

\section{Numerical Study of the Liner Case: Fuel-up-to Levels and Heuristic
Policies}

\label{sec:liner-num}

Below we report the results of a numerical study designed to provide
insights on the influence of various problem parameters as well as to test
the performance of possible heuristics. We start by introducing the data
that pertains to the network of ports and to the liner vessel.

\subsection{Network and Vessel Data}

We consider an example of a liner with fuel capacity of $3000$ metric tons
(mts) that operates between the following ports: Santa Marta in Colombia,
Moin in Costa Rica, Castilla in Honduras, Port Everglades in Florida and
Wilmington in Delaware. According to the time which has to be spent in each
port (which includes, e.g., the time associated with the loading/unloading
activities), the ship can only replenish fuel at Wilmington (port 1)\ or
Moin (port 2). The approximate fuel consumption for the trip from Wilmington
to Moin and from Moin to Wilmington are given by $400$ mts and $600$ mts,
respectively, and the time associated with any of the two trips is
approximately 5 days. Note that the two one-way consumption values differ as
the respective one-way routes include different stops.

Based on the above description, we model the network for the liner under
consideration as consisting of $N=2$ ports, with the following parameters: $%
\tau _{12}=\tau _{21}=5$, $d_{12}=400$ mts and $d_{21}=600$ mts. To simplify
computations, we assume that the liner can only replenish fuel by multiples
of 200 mts.

In our numerical study we use (3) as the model bunkers
price dynamics with parameters estimated using (\ref{gammak})-(\ref{sigmai}%
). The base-case values of the price parameters for the ports of Wilmington
and Moin are shown in Table \ref{tab7a}. 
\begin{table}[h!]
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
Parameter & Wilmington & Moin \\ \hline
$A$, $\$/$mts & $0.0$ & $-1.7$ \\ \hline
$\delta $, $\$/$mts & $29.2$ & $25.8$ \\ \hline
$\eta $ & $0.99$ & $0.97$ \\ \hline
$\sigma $, $\$/$mts & $14.4$ & $14.3$ \\ \hline
\end{tabular}%
\end{center}
\caption[smallcaption]{Parameters of the bunkers fuel price dynamics for the
ports of Wilmington and Moin.}
\label{tab7a}
\end{table}

We use a simple form for random price correction terms by assuming that $%
\varepsilon _{i}$ at port $i$ takes two values, $\pm \sigma _{i}$, w.p. 0.5
for each value. The oil price dynamics is taken to follow the mean-reverting
model (\ref{discreteprob}) with $\sigma _{0}=1.25$, $\lambda =0.96$, $%
P_{0}^{\min }=46$ and $P_{0}^{\max }=62$. In summary, the state space of the
resulting dynamic program contains $4352$ states.

For the base-case values of problem parameters, the optimal value of the
expected daily fuel cost, obtained by solving the DP (6), is $%
\$21,400$ per day. As an illustration of the optimal refueling policy,
Figure \ref{Figure10rev} shows the optimal fuel-up-to-levels as functions of
the oil price in the \textquotedblleft low price
corrections\textquotedblright\ states with $\alpha _{i}=A_{i}-\delta _{i}$, $%
\varepsilon _{i}=-\sigma _{i}$, $i=$WIL, MOI.\FRAME{ftbpFU}{4.1978in}{3.154in%
}{0pt}{\Qcb{Base-case scenario: critical refueling indices $S\left(
i,P_{0}\right) $ for $i=$WIL, MOI, and $P_{0}=46,...,62$ ($\protect\alpha %
_{i}=A_{i}-\protect\delta _{i}$, $\protect\varepsilon _{i}=-\protect\sigma %
_{i}$, $i=$WIL, MOI).}}{\Qlb{Figure10rev}}{figuresrev2_1.wmf}{\special%
{language "Scientific Word";type "GRAPHIC";maintain-aspect-ratio
TRUE;display "USEDEF";valid_file "F";width 4.1978in;height 3.154in;depth
0pt;original-width 9.9998in;original-height 7.4996in;cropleft "0";croptop
"1";cropright "1";cropbottom "0";filename
'FiguresRev2_1.wmf';file-properties "XNPEU";}}

In this case, MOI is the more expensive port out of the two for any oil
price level, and the refuel-up-to levels for MOI do not exceed those for
WIL. In addition, those levels naturally exhibit drops from
\textquotedblleft fuel-up-to-capacity\textquotedblright\ at both ports when
the oil price is at its lowest ($P_{0}=46$)\ to \textquotedblleft single
roundtrip\textquotedblright\ refueling at either port when the oil price
cannot be any higher ($P_{0}=62$). Note that even for the highest oil price
level the negative price corrections $\varepsilon _{i}=-\sigma _{i}$, $i=$%
WIL, MOI make it beneficial to move from \textquotedblleft refuel as little
as possible\textquotedblright\ to \textquotedblleft single
roundtrip\textquotedblright\ decisions at both ports.

\subsection{Fuel-up-to Levels: Sensitivity Properties}

In order to understand how the refueling decisions depend on the parameters
of the bunkers price dynamics, we would like to deviate from the base-case
by exploring a wider range of problem settings. In particular, we first
consider a variant of our problem for which the bunkers prices at both ports
at any point in time are completely determined by the value of the oil price
at that point in time (i.e., the case with $\delta _{\text{WIL}}=\delta _{%
\text{MOI}}=\sigma _{\text{WIL}}=\sigma _{\text{MOI}}=0$, while the rest of
the parameters are set at their base-case values). The resulting values of
the critical refueling indices $S\left( i,P_{0}\right) $ for $i=$WIL and $i=$%
MOI and for $P_{0}=[46,62]$ are shown in Figure \ref{Fig1rev}. In this case,
opposite to what we observed in the base-case setting, WIL is the more
expensive port out of the two for any price level, and the refuel-up-to
levels for WIL do not exceed those for MOI. As in the base scenario, those
levels exhibit sharp drops from \textquotedblleft
fuel-up-to-capacity\textquotedblright\ at both ports when the oil price is
at its lowest to \textquotedblleft refuel as little as
possible\textquotedblright\ at either port when the oil price is at its
highest.

Figure \ref{Fig2rev} shows how the critical refueling indices observed in
the previous \textquotedblleft zero-case\textquotedblright\ scenario change
when the daily adjustment factor $\varepsilon _{\text{WIL}}$ is introduced
(with the base-case value $\sigma _{\text{WIL}}=14.4$). Note that the
degeneracy of the base-case $S\left( \text{WIL}\right) $ curve from Figure %
\ref{Fig1rev} is lifted and the refueling indices for WIL \textquotedblleft
split\textquotedblright\ into two curves, one below (corresponding to $%
\varepsilon _{\text{WIL}}=14.4$) and one above (corresponding to $%
\varepsilon _{\text{WIL}}=-14.4$) the base-case curve. Such split is
expected in the view of higher-than-average (lower-than-average) prices in
WIL corresponding to the lower (higher)\ curve. Another interesting feature
depicted on Figure \ref{Fig2rev} is \textquotedblleft
lowering\textquotedblright\ of the critical index curve for MOI: for
example, when $P_{0}=51$, it is optimal when in MOI to fuel-up-to the level
corresponding to one round trip instead of up to vessel's capacity. Such a
change reflects the decreased attractiveness of MOI as a port of purchase in
presence of newly-found occasional bargain at WIL whenever $\varepsilon _{%
\text{WIL}}=-14.4$.

\FRAME{ftbpFU}{4.4045in}{3.307in}{0pt}{\Qcb{Critical refueling indices $%
S\left( i,P_{0}\right) $ for $i=$WIL, MOI and $P_{0}=46,...,62$ ($\protect%
\delta _{i}=\protect\sigma _{i}=0$, $i=$WIL, MOI).}}{\Qlb{Fig1rev}}{%
figuresrev2_2.wmf}{\special{language "Scientific Word";type
"GRAPHIC";maintain-aspect-ratio TRUE;display "USEDEF";valid_file "F";width
4.4045in;height 3.307in;depth 0pt;original-width 9.9998in;original-height
7.4996in;cropleft "0";croptop "1";cropright "1";cropbottom "0";filename
'FiguresRev2_2.wmf';file-properties "XNPEU";}}

\FRAME{ftbpFU}{4.3526in}{3.2673in}{0pt}{\Qcb{Critical refueling indices $%
S\left( i,P_{0}\right) $ for $i=$WIL, MOI$,$ $\protect\sigma _{{\rm WIL}%
}=14.4,$ and $P_{0}=46,...,62$ ($\protect\delta _{{\rm WIL}}=\protect\delta %
_{{\rm MOI}}=\protect\sigma _{{\rm MOI}}=0$).}}{\Qlb{Fig2rev}}{%
figuresrev2_3.wmf}{\special{language "Scientific Word";type
"GRAPHIC";maintain-aspect-ratio TRUE;display "USEDEF";valid_file "F";width
4.3526in;height 3.2673in;depth 0pt;original-width 9.9998in;original-height
7.4996in;cropleft "0";croptop "1";cropright "1";cropbottom "0";filename
'FiguresRev2_3.wmf';file-properties "XNPEU";}}Figure \ref{Figure3rev} probes
the effects of the presence of the supply correction at WIL. In this example
the amplitude $\delta _{\text{WIL}}$ of the WIL supply correction is set at
the base-case value of $29.2$. Note that an important difference between the
critical index curves in this case and those of Figure \ref{Fig2rev} is the
splitting off of the MOI curve corresponding to the states with
\textquotedblleft high\textquotedblright\ WIL\ prices from the curve
corresponding t{}he \textquotedblleft low\textquotedblright\ WIL\ prices.
While in the case of random price corrections depicted in Figure \ref%
{Fig2rev} the value of correction observed at WIL does not influence
refueling decision made at the same time in MOI, this is not the case when
such price corrections follow high-inertia Markov pattern: a
\textquotedblleft high\textquotedblright\ price observed at WIL at the time
of MOI\ refueling decision has 99\% chance of remaining \textquotedblleft
high\textquotedblright\ when the vessel arrives at WIL, thus raising the
refueling level at MOI, as in the case of $P_{0}=53$. Similarly, a
\textquotedblleft low\textquotedblright\ WIL price has 99\% chance of
remaining \textquotedblleft high\textquotedblright\ when the vessel arrives
at WIL, thus lowering the refueling level at MOI, as in the case of $%
P_{0}=53 $. Note that this argument remains valid only if the inertia
coefficient $\eta _{\text{WIL}}$ is above 0.5 - i.e., if observed
\textquotedblleft high\textquotedblright\ price makes the \textquotedblleft
high\textquotedblright\ price more likely to be observed next day. When $%
\eta _{\text{WIL}}$ drops below 0.5, the argument is reversed:
\textquotedblleft high\textquotedblright\ price today makes
\textquotedblleft low\textquotedblright\ price more likely tomorrow. This
case is illustrated in Figure \ref{Figure4rev} where $\eta _{\text{WIL}%
}=0.01 $: the MOI curves corresponding to \textquotedblleft
high\textquotedblright\ and \textquotedblleft low\textquotedblright\ WIL\
prices are, naturally, reversed as compared to Figure \ref{Figure3rev}.

\FRAME{ftbpFU}{4.1857in}{3.1436in}{0pt}{\Qcb{Critical refueling indices $%
S\left( i,P_{0},\protect\alpha _{{\rm WIL}}\right) $ for $i={\rm WIL},{\rm %
MOI}$, $\protect\delta _{{\rm WIL}}=29.2,$ and $P_{0}=46,...,62$ ($\protect%
\sigma _{{\rm WIL}}=\protect\delta _{{\rm MOI}}=\protect\sigma _{{\rm MOI}%
}=0 $).}}{\Qlb{Figure3rev}}{figuresrev2_4.wmf}{\special{language "Scientific
Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display "USEDEF";valid_file
"F";width 4.1857in;height 3.1436in;depth 0pt;original-width
9.9998in;original-height 7.4996in;cropleft "0";croptop "1";cropright
"1";cropbottom "0";filename 'FiguresRev2_4.wmf';file-properties "XNPEU";}}

\FRAME{ftbpFU}{4.2065in}{3.1583in}{0pt}{\Qcb{Critical refueling indices $%
S\left( i,P_{0},\protect\alpha _{{rmWIL}}\right) $ for $i={\rm WIL},{\rm MOI}
$, $\protect\delta _{{\rm WIL}}=29.2,$ $\protect\eta _{{\rm WIL}}=0.01$, and 
$P_{0}=46,...,62$ ($\protect\sigma _{{\rm WIL}}=\protect\delta _{{\rm MOI}}=%
\protect\sigma _{{\rm MOI}}=0$).}}{\Qlb{Figure4rev}}{figuresrev2_6.wmf}{%
\special{language "Scientific Word";type "GRAPHIC";maintain-aspect-ratio
TRUE;display "USEDEF";valid_file "F";width 4.2065in;height 3.1583in;depth
0pt;original-width 9.9998in;original-height 7.4996in;cropleft "0";croptop
"1";cropright "1";cropbottom "0";filename
'FiguresRev2_6.wmf';file-properties "XNPEU";}}

\subsection{Numerical Results on Heuristic Policies}

In our numerical study we also investigated the impact of the variations in
the values of the local supply correction parameters, the local supply
inertias and daily adjustment factor volatilities on the optimal cost
performance. In addition we tested the performance of several heuristics
that could serve as alternatives to the optimal policy in cases where the
dynamic program (6) is too large to solve to optimality. For
that purpose, we computed the long-run average daily cost $\mu ^{\pi }$
associated with each of the following five policies\footnote{%
Note that while in the previous section we have analyzed the properties of
the finite-horizon problem, here we focus on the long-run expected cost per
day, as this profit measure is independent of initial conditions.}:

\begin{enumerate}
\item $\mu ^{\text{opt}}$ - the value of the optimal policy.

\item $\mu ^{\text{M}}$ - the value of the policy defined as follows:
whenever in Wilmington, buy up to $400$ mts and whenever in Moin, buy up to $%
600$ mts. Note that this policy only buys the fuel necessary to get to the
next location; in that sense, it is fully myopic.

\item $\mu ^{\text{MW}}$ - the value of the policy defined as follows:
whenever in Wilmington, buy up to $1000$ mts and whenever in Moin, buy up to 
$600$ mts. Note that when using this policy, the shipping company
effectively only purchases fuel at Wilmington after the first cycle.

\item $\mu ^{\text{MM}}$ - the value of the policy defined as follows:
whenever in Wilmington, buy up to $400$ mts and whenever in Moin, buy up to $%
1000$ mts. Note that when using this policy, the shipping company, after the
first cycle, only purchases fuel at Moin.

\item $\mu ^{\text{CE}}$ - the value of the \textquotedblleft certainty
equivalence\textquotedblright\ policy: at each stage, the policy is computed
assuming that the prices will stay constant at their current levels for all
future periods.
\end{enumerate}

For each policy $\pi $, we define the associated optimality ratio as: ${\cal %
R}^{\pi }=(\mu ^{\pi }-\mu ^{\text{opt}})/\mu ^{\text{opt}}$. Note that
currently, the marine shipping company always purchases fuel in Wilmington
and thus, essentially, follows the policy $\pi =$MW.

First, we have computed the optimality ratios for four heuristic policies
for the base-case scenario described in Section 4 and
Table \ref{tab7a}. The \textquotedblleft certainty
equivalence\textquotedblright\ heuristic CE exhibits the best performance
with the daily expected cost of $\$22,397$ per day (as compared with the
optimal value of $\$21,400/$day)\ and the optimality ratio of ${\cal R}^{%
\text{CE}}=4.66\%$. Other heuristics show the following performances: ${\cal %
R}^{\text{M}}=13.68\%$, ${\cal R}^{\text{MW}}=13.87\%$, ${\cal R}^{\text{MM}%
}=13.56\%$. Strong performance of the CE\ heuristic is helped by a high
values of $\eta _{\text{WIL}}$\ and $\eta _{\text{MOI}}$ and, thus, by high
inertia exhibited by differences in prices in Wilmington and Moin. In the
remainder of the Section we investigate the effects of some of parameters of
the bunkers price dynamics on the performance of the above heuristic
policies.

{\bf The effect of the supply correction amplitude $\delta $}$_{\text{WIL}}$%
{\bf .} In order to isolate the effects of the corrections due to supply
availability, we first assume that $\sigma _{\text{WIL}}=\sigma _{\text{MOI}%
}=0$, i.e., that there is no daily random correction in addition to the
supply correction. Also, we assume that $\delta _{\text{MOI}}=0$ and analyze
the performance of the policies outlined above as $\delta _{\text{WIL}}$ is
varied. Throughout, $\eta _{\text{WIL}}$ is set to $0.99$ reflecting a
base-case level inertia in the balance of demand and supply factors at
Wilmington. Note that in this setting, the fuel prices at Moin are
exclusively driven by the oil price $P_{0}$ while the prices at Wilmington
are driven by both $P_{0}$ and the supply correction $\alpha _{\text{WIL}}$. 
\begin{table}[h!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
$\delta _{\text{WIL}}$ & $R^{\text{M}}(\%)$ & $R^{\text{MW}}(\%)$ & $R^{%
\text{MM}}(\%)$ & $R^{\text{CE}}(\%)$ \\ \hline\hline
0 & 2.87 & 3.30 & 2.58 & 2.58 \\ \hline
10 & 4.36 & 4.71 & 4.13 & 2.23 \\ \hline
20 & 6.73 & 7.00 & 6.56 & 2.32 \\ \hline
30 & 9.40 & 9.57 & 9.28 & 2.54 \\ \hline
\end{tabular}%
\end{center}
\caption[smallcaption]{Relative performance of heuristics as a function of $%
\protect\delta _{\text{WIL}}$ ($\protect\sigma _{\text{WIL}}=\protect\sigma %
_{\text{MOI}}=0$, $\protect\delta _{\text{MOI}}=0$).}
\label{tabdelta2a}
\end{table}

As the results of Table \ref{tabdelta2a} indicate, the performances of all
the heuristics tend to degrade as $\delta _{\text{WIL}}$ increases. While
the optimality ratio for the policies M, MW\ and MM degrades from
approximately $3\%$ when $\delta _{\text{WIL}}=0$ to about $10\%$ when $%
\delta _{\text{WIL}}=30$, the performance of CE\ is quite robust and the
error does not go above $2.6\%$ - the effect which, as in the base scenario,
is largely due to strong inertia of local supply corrections to bunkers
prices.

{\bf The effect of the supply correction inertia }$\eta _{\text{WIL}}${\bf .}
As in the previous setting, we use $\sigma _{\text{WIL}}=\sigma _{\text{MOI}%
}=0$ and $\delta _{\text{MOI}}=0$. We now fix $\delta _{\text{WIL}}$ at its
base-case value of $29.2$ and analyze how the relative performance of the
heuristics is influenced by changes in the value of $\eta _{\text{WIL}}$. As
before, the prices at Moin are exclusively driven by the oil price $P_{0}$
while the prices at Wilmington are driven by both $P_{0}$ and the supply
correction $\alpha _{\text{WIL}}$.

\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
$\eta _{\text{WIL}}$ & $R^{\text{M}}(\%)$ & $R^{\text{MW}}(\%)$ & $R^{\text{%
MM}}(\%)$ & $R^{\text{CE}}(\%)$ \\ \hline\hline
0.1 & 10.70 & 11.17 & 10.39 & 4.41 \\ \hline
0.5 & 10.94 & 11.40 & 10.63 & 4.13 \\ \hline
0.6 & 10.94 & 11.40 & 10.63 & 4.13 \\ \hline
0.7 & 10.94 & 11.40 & 10.63 & 4.12 \\ \hline
0.8 & 10.93 & 11.39 & 10.62 & 4.08 \\ \hline
0.9 & 10.70 & 11.17 & 10.39 & 3.93 \\ \hline
\end{tabular}%
\end{center}
\caption[smallcaption]{Relative performance of heuristics as a function of $%
\protect\eta _{\text{WIL}}$ ($\protect\delta _{\text{WIL}}=29.2$, $\protect%
\sigma _{\text{WIL}}=\protect\sigma _{\text{MOI}}=0$, $\protect\delta _{%
\text{MOI}}=0$).\ }
\label{table:q1a}
\end{table}

In Table \ref{table:q1a}, we observe that changes in $\eta _{\text{WIL}}$
have overall small effects on the performance of the four heuristics.
However, it is interesting to note that the results presented confirm the
intuition about the CE\ heuristic. As $\eta _{\text{WIL}}$ increases, the
supply correction $\alpha _{\text{WIL}}$ varies in a relatively slow
fashion, which improves the performance of the CE heuristic. This is what we
observe in the last column of Table \ref{table:q1a}.

{\bf The effect of volatility characterized by }$\sigma _{\text{WIL}},$ $%
\sigma _{\text{MOI}},$ $\delta _{\text{WIL}},$ $\delta _{\text{MOI}}${\bf .}
In Table \ref{table:sig1a}, we assume $\delta _{\text{WIL}}=\delta _{\text{%
MOI}}=0$, set $\sigma _{\text{WIL}}=\sigma _{\text{MOI}}$, and analyze the
performance of the four policies as the value of $\sigma _{\text{WIL}}$ is
increased. Note that in this setting, the prices at Moin and Wilmington are
driven by the oil price $P_{0}$ and a daily random correction in the absence
of any supply corrections. On the other hand, in Table \ref%
{table:sig_delta1a}, we fix the values of $\eta _{\text{WIL}}$ and $\eta _{%
\text{MOI}}$ at their base-case levels of $0.99$ and $0.97$, respectively,
set $y=\delta _{\text{WIL}}=\delta _{\text{MOI}}=\sigma _{\text{WIL}}=\sigma
_{\text{MOI}}$ and analyze the performance of the heuristics as the value $y$
is increased. 
\begin{table}[tbp]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
$\sigma _{\text{WIL}}$ & $R^{\text{M}}(\%)$ & $R^{\text{MW}}(\%)$ & $R^{%
\text{MM}}(\%)$ & $R^{\text{CE}}(\%)$ \\ \hline
5 & 3.30 & 3.47 & 3.12 & 2.92 \\ \hline
10 & 5.93 & 6.11 & 5.74 & 5.54 \\ \hline
15 & 8.85 & 9.03 & 8.65 & 8.44 \\ \hline
20 & 11.96 & 12.15 & 11.76 & 11.54 \\ \hline
\end{tabular}%
\end{center}
\caption[smallcaption]{Relative performance of heuristics as a function of $%
\protect\sigma _{\text{WIL}}=\protect\sigma _{\text{MOI}}$ ($\protect\delta %
_{\text{WIL}}=\protect\delta _{\text{MOI}}=0$).\ }
\label{table:sig1a}
\end{table}
\begin{table}[tbp]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
$y$ & $R^{\text{M}}(\%)$ & $R^{\text{MW}}(\%)$ & $R^{\text{MM}}(\%)$ & $R^{%
\text{CE}}(\%)$ \\ \hline
5 & 4.10 & 4.26 & 3.91 & 2.56 \\ \hline
10 & 7.66 & 7.84 & 7.47 & 4.80 \\ \hline
15 & 11.60 & 11.79 & 11.40 & 7.34 \\ \hline
20 & 15.88 & 16.09 & 15.68 & 10.09 \\ \hline
\end{tabular}%
\end{center}
\caption[smallcaption]{Relative performance of heuristics as a function of $%
y=\protect\sigma _{\text{WIL}}=\protect\sigma _{\text{MOI}}=\protect\delta _{%
\text{WIL}}=\protect\delta _{\text{MOI}}$ ($\protect\eta _{\text{WIL}}=0.99$%
, $\protect\eta _{\text{MOI}}=0.97$).}
\label{table:sig_delta1a}
\end{table}

The results of Table \ref{table:sig1a} indicate that all heuristics have
comparable performances. However, Table \ref{table:sig_delta1a} identifies
the CE\ heuristic as the best performer. This performance advantage stems
from the fact that the CE\ heuristic is able to exploit high values of $%
\delta _{\text{WIL}}=\delta _{\text{MOI}}$ combined with high inertia of the
local supply correction factors.

\end{document}
