Scheduling appointments for container truck arrivals considering their effects on congestion

Abstract

Trucking companies deliver a large number of containers every day to container terminals at hub ports. Truck drivers for the delivery operation can experience long waiting times when they arrive at peak hours. This study proposes a scheduling method for appointments that considers the cost of trucks staying in the terminal, demurrage cost, container delivery cost, number of appointments allowed at each time window and block, and number of trucks available during each time window. Unlike previous studies, this study considers the effects of the appointments on the waiting time at the terminal when the appointment schedule is constructed. This paper introduces a mathematical formulation and a heuristic algorithm based on the Frank–Wolfe algorithm to solve the problem within a reasonable computational time. Numerical experiments are conducted to compare the proposed algorithm with the other heuristic approaches and analyze the effects of the appointments using empirical data. In addition, the impact of appointments by multiple trucking companies is examined.

Appendices

Appendix 1: Proof of the convexity of $TC\left( X \right)$ (Property 1)

$$\begin{aligned} TC\left( X \right) & = \mathop \sum \limits_{i \in U} \mathop \sum \limits_{{b \in B_{i} }} \mathop \sum \limits_{t \in T} \left[ {cS_{ibt} \left( {Z_{bt} } \right) + d_{it} + ba_{it} } \right]X_{ibt} \\ & = \mathop \sum \limits_{{i \in U_{b} }} \mathop \sum \limits_{b \in B} \mathop \sum \limits_{t \in T} \left[ {cS_{ibt} \left( {Z_{bt} } \right) + d_{it} + ba_{it} } \right]X_{ibt} \\ & = \mathop \sum \limits_{{i \in U_{b} }} \mathop \sum \limits_{b \in B} \mathop \sum \limits_{t \in T} \left[ {cW_{bt} \left( {Z_{bt} } \right) + cs_{i} + d_{it} + ba_{it} } \right]X_{ibt} , \\ \end{aligned}$$

where $s_{i} = s_{I}$ when task $i$ is for inbound containers, while it is $s_{O}$ when task is for outbound containers.

$$TC\left( X \right) = \mathop \sum \limits_{b \in B} \mathop \sum \limits_{t \in T} \mathop \sum \limits_{{i \in U_{b} }} \left[ {cW_{bt} \left( {Z_{bt} } \right)X_{ibt} + \left( {cs_{i} + d_{it} + ba_{it} } \right)X_{ibt} } \right]$$

(10)

An attempt is made to show that the Hessian matrix ($h_{ij}$) is positive definite, where $h_{ij} = \frac{{\partial^{2} {\text{TC}}\left( {\text{X}} \right)}}{{\partial X_{ibt} \partial X_{jbt} }}$. Note that the second term in (10) vanishes in the second order derivatives of ($h_{ij}$). Therefore, this study will only show that $\mathop \sum \limits_{{i \in U_{b} }} W_{bt} \left( {Z_{bt} } \right)X_{ibt}$ is convex with respect to $(X_{ibt} | i \in U_{b} )$ for a given $b$ and $t$, which leads to the convexity of $TC\left( X \right)$ from the theory that the sum of the convex functions is again a convex function. Note that $Z_{bt} = \mathop \sum \limits_{{i \in U_{b} }} X_{ibt}$. The subscripts $b$ and $t$ were omitted in this proof for the simplicity. Then, $X_{i} = X_{ibt}$, $Z = Z_{bt}$, $U = U_{b}$, and $W = W_{bt} .$ Let $Y = X_{i}$, $F\left( Y \right) = \mathop \sum \limits_{k \in U} X_{k} W\left( {\text{Z}} \right)$.

$$\begin{aligned} \frac{\partial F\left( Y \right)}{{\partial X_{i} }} & = W\left( Z \right) + X_{i} \frac{\partial W\left( Z \right)}{{\partial X_{i} }} + X_{j} \frac{\partial W\left( Z \right)}{{\partial X_{i} }} + \mathop \sum \limits_{{k \in U - \left\{ {i, j} \right\}}} X_{k} \frac{\partial W\left( Z \right)}{{\partial X_{i} }} \\ & = W\left( Z \right) + X_{i} \frac{\partial W\left( Z \right)}{\partial Z}\frac{\partial Z}{{\partial X_{i} }} + X_{j} \frac{\partial W\left( Z \right)}{\partial Z}\frac{\partial Z}{{\partial X_{i} }} + \mathop \sum \limits_{{k \in U - \left\{ {i, j} \right\}}} X_{k} \frac{\partial W\left( Z \right)}{\partial Z}\frac{\partial Z}{{\partial X_{i} }} \\ & = W\left( Z \right) + X_{i} \frac{\partial W\left( Z \right)}{\partial Z} + X_{j} \frac{\partial W\left( Z \right)}{\partial Z} + \mathop \sum \limits_{{k \in U - \left\{ {i, j} \right\}}} X_{k} \frac{\partial W\left( Z \right)}{\partial Z} \\ & \left( {{\text{note}}\,{\text{that}}\frac{\partial Z}{{\partial X_{i} }} = 1\quad {\text{because}}\quad Z = \mathop \sum \limits_{i \in U} X_{i} } \right). \\ \end{aligned}$$

$$\begin{aligned} \frac{{\partial^{2} F\left( Y \right)}}{{\partial X_{i} \partial X_{j} }} & = \frac{\partial W\left( Z \right)}{\partial Z}\frac{\partial Z}{{\partial X_{j} }} + X_{i} \frac{{\partial^{2} W\left( Z \right)}}{{\partial Z^{2} }}\frac{\partial Z}{{\partial X_{j} }} + \frac{\partial W\left( Z \right)}{\partial Z} + X_{j} \frac{{\partial^{2} W\left( Z \right)}}{{\partial Z^{2} }}\frac{\partial Z}{{\partial X_{j} }} + \mathop \sum \limits_{{k \in U - \left\{ {i, j} \right\}}} X_{k} \frac{{\partial^{2} W\left( Z \right)}}{{\partial Z^{2} }}\frac{\partial Z}{{\partial X_{j} }} \\ & = 2\frac{\partial W\left( Z \right)}{\partial Z} + \mathop \sum \limits_{k \in U} X_{k} \frac{{\partial^{2} W\left( Z \right)}}{{\partial Z^{2} }}. \\ \end{aligned}$$

$$\begin{aligned} \frac{{\partial^{2} F\left( Y \right)}}{{\partial X_{i}^{2} }} & = \frac{\partial W\left( Z \right)}{\partial Z}\frac{\partial Z}{{\partial X_{i} }} + \frac{\partial W\left( Z \right)}{\partial Z} + X_{i} \frac{{\partial^{2} W\left( Z \right)}}{{\partial Z^{2} }}\frac{\partial Z}{{\partial X_{i} }} + X_{j} \frac{{\partial^{2} W\left( Z \right)}}{{\partial Z^{2} }}\frac{\partial Z}{{\partial X_{i} }} + \mathop \sum \limits_{{k \in U - \left\{ {i, j} \right\}}} X_{k} \frac{{\partial^{2} W\left( Z \right)}}{{\partial Z^{2} }}\frac{\partial Z}{{\partial X_{i} }} \\ & = \frac{\partial W\left( Z \right)}{\partial Z} + \frac{\partial W\left( Z \right)}{\partial Z} + X_{i} \frac{{\partial^{2} W\left( Z \right)}}{{\partial Z^{2} }} + X_{j} \frac{{\partial^{2} W\left( Z \right)}}{{\partial Z^{2} }} + \mathop \sum \limits_{{k \in U - \left\{ {i, j} \right\}}} X_{k} \frac{{\partial^{2} W\left( Z \right)}}{{\partial Z^{2} }} \\ & = 2\frac{\partial W\left( Z \right)}{\partial Z} + \mathop \sum \limits_{k \in U} X_{k} \frac{{\partial^{2} W\left( Z \right)}}{{\partial Z^{2} }}. \\ \end{aligned}$$

The Hessian matrix $H = \left[ {h_{ij} } \right] = \left( {2\frac{\partial W\left( Z \right)}{\partial Z} + \mathop \sum \limits_{k \in U} X_{k} \frac{{\partial^{2} W\left( Z \right)}}{{\partial Z^{2} }}} \right)J_{\left| U \right|}$, where $J_{\left| U \right|}$ is the $\left| U \right| \times \left| U \right|$ matrix of ones. It is known that $J_{\left| U \right|}$ is a positive semi definite matrix (Stanley 2013, Horn and Johnson 2013). From the assumption that $W\left( Z \right)$ is a non-decreasing and convex function of $Z$, $\frac{{\partial {\text{W}}\left( {\text{Z}} \right)}}{\partial Z} \ge 0$ and $\frac{{\partial^{2} {\text{W}}\left( {\text{Z}} \right)}}{{\partial Z^{2} }} > 0$, $H$ is a positive semi definite matrix. Hence, $TC\left( X \right)$ is convex. Q.E.D.

Appendix 2: Proof that the expression for the expected waiting time of M/M/1 queue satisfies the condition for Property 1

$W\left( Z \right) = \frac{Z}{{\mu \left( {\mu - Z} \right)}}$ in the M/M/1 queuing model, where $\mu$ represents the expected service rate of the server. Note that $\mu > Z$ must hold. $\frac{dW\left( Z \right)}{dZ} = \frac{1}{{\left( {\mu - Z} \right)^{2} }} > 0$.

$\frac{{d^{2} W\left( Z \right)}}{{dZ^{2} }} = \frac{2}{{\left( {\mu - Z} \right)^{3} }} > 0$. Hence, the conclusion holds. Q.E.D.