Berth Allocation Problem in Real Time

Nitish Umang* Michel Bierlaire*

* TRANSP-OR, Ecole Polytechnique Fdrale de Lausanne

10th Joint Operations Research Days June 28-29, Neuchatel, Switzerland

Contents

Motivation Research Objectives Deterministic Berth Allocation Problem Real Time Recovery in BAP Preliminary Results Conclusions and Future Work

Motivation
International shipping tonnage in solid bulk and liquid bulk trade has registered an increase by 52% and 48% respectively. The total volume of dry bulk cargoes loaded in 2008 stood at 5.4 billion tons, accounting for 66.3 per cent of total world goods loaded (UNCTAD, 2009) Bulk port terminals have received significantly less attention than container terminals in the field of large scale optimization High level of uncertainty in bulk port operations due to weather conditions, mechanical problems etc. Disrupt the normal functioning of the port Require quick real time action.

Very few studies address the problem of real time recovery in port operations, while the problem has not been studied at all in context of bulk ports. Our research problem derives from the realistic requirements at the SAQR port, Ras Al Khaimah, UAE

Schematic Diagram of a Bulk Terminal

YARD SPACE
cargo blocks w= 2 SILICA SAND w= 4 CLAY w= 6 SODA ASH w= 5 w= 1 ANIMAL FEED w= 3 GRAIN ROCK AGGREGATES w= 11 ROCK FACTORY CONVEYOR w= 8 CEMENT w= 7 w= 9 FELDSPAR
LIMESTONE

w= 12 OIL TANK TERMINAL w= 10 COAL

PIPELINE

sections along the quay k=1 k=2 k=4

k=3

Vessel berthed at section k=5 carrying cement k=5 k=6

k=7

k=8

Vessel 1

QUAY SPACE

Vessel 2

Vessel 3

Research Objectives

Study the crucial problems of

Berth Allocation : scheduling and assignment of vessels to sections along the quay Yard Assignment : assignment of vessels and cargo types to specific locations on the yard

Large Scale Integrated Planning: Integration of the berth allocation and yard assignment for better coordination between berthing and yard activities

Develop real time and robust optimization algorithms to account for uncertainties in arrival times and handling times of vessels, and other unforeseen disruptions and delays in operations.

The focus of this talk is solving the berth allocation problem in real time for a given baseline schedule.

Research Objectives
Develop real time algorithms for disruption recovery in berth allocation problem (BAP) For a given baseline berthing schedule, minimize the total realized costs of the updated schedule as actual arrival data is revealed. The total realized costs include
The total service cost of all vessels berthing at the port which is the sum total of the handling times and berthing delays of all vessels berthing in the planning horizon. Inconsistent cost of rescheduling over space and time to account for the cost of re-allocating human labor, handling equipment and availability of cargo.

Literature Review

Very scarce studies on real time and robust algorithms in container terminals . To the best of our knowledge, no literature on bulk ports. Comprehensive literature surveys on BAP in container terminals can be found in Steenken et al. (2004), Stahlobock and Voss (2007), Bierwirth and Meisel (2010). OR literature related to BAP under uncertainty in container terminals

Pro-active Robustness

Stochastic programming approach used by Zhen et al. (2011), Han et al. (2010) Define surrogate problems to define the stochastic nature of the problem: Moorthy and Teo (2006), Zhen and Chang (2012), Xu et al. . (2012) and Hendriks et al. (2010)

Reactive approach or disruption management

Zeng et al.(2012) and Du et al. (2010) propose reactive strategies to minimize the impact of disruptions.

Baseline Schedule

Any feasible berthing assignment and schedule of vessels along the quay respecting the spatial and temporal constraints on the individual vessels

Best case: Optimal solution of the deterministic berth allocation problem (without accounting for any uncertainty in arrival information)

Deterministic BAP: Problem Definition

Find

Optimal assignment and schedule of vessels along the quay (without accounting for any uncertainty in arrival information)

Given

Expected arrival times of vessels Handling times dependent on

Cargo type on the vessel (the relative location of the vessel along the quay with respect to the
cargo location on the yard)

Number of cranes operating on the vessel

Objective

Minimize total service times (waiting time + handling time) of vessels berthing at the port

BAP Solution
Quay length

Vessel 1

Vessel 2

Length of vessel

Vessel 3

Vessel 4

Berthing location Handling Time Berthing Time Time Horizon

Discretization
Vessel 1 Berth 1 Vessel 2 Berth 2 Discrete Layout Vessel 3 Berth 3

Vessel 1

Vessel 2 Continuous Layout

Vessel 3

Vessel 1 Section 1

Vessel 2

Vessel 3 Section 2 Section 3

Hybrid Layout

MILP Model
Objective Function

min

i N

(m

Ai + ci )

Decision variables: mi ci starting time of handling of vessel i N; total handling time of vessel i N;

MILP Model
Dynamic vessel arrival constraints
m i Ai 0 i N ,

Non overlapping constraints

j b s ( k k ) + B (1 yij ) k M i b s ( k k ) + Li k M

i, j N , i j, i, j N , i j, i, j N , i j,

m j + B (1 zij ) mi + ci y ij + y ji + zij + z ji 1

MILP Model
Section covering constraints

kM

i =1 sk

i N , i N ,

kM

( b k s ik ) + L i L

l M

( d ilk s li ) = x ik i N , k M ,

Draft Restrictions
( d k D i ) x ik 0 i N ,k M ,

MILP Model
Determination of Handling Times

Given an input vector of unit handling times for each combination of cargo type and section along the quay Specialized facilities (conveyors, pipelines etc.) also modeled as cargo types All sections occupied by the vessel are operated simultaneously

ci hkw pilk Qi sli

Qi

i N , k M , l M , w Wi

quantity of cargo to be loaded on or discharged from vessel i handling time for unit quantity of cargo w W and vessel berthed at section k M; fraction of cargo handled at section k M when vessel i is berthed at starting section l M

hkw
pilk

GSPP Model
Used in context of container terminals by Christensen and Holst (2008) Generate set P of columns, where each column p P represents a feasible assignment of a single vessel in both space and time Generate two matrices Matrix A = ( Aip ) ; equal to 1 if vessel i N is the assigned vessel in the feasible assignment represented by column p P
st ) ; equal to 1 if section sM is occupied at time Matrix B = ( b p t H in column p P

Note: Assume integer values for all time measurements

GSPP Formulation: A simple example

Vessel 1 x=0

Vessel 2 x=L

|N| = 2, |M| = 3, |H| = 3 Vessel 1 cannot occupy section 3 owing to spatial constraints (does not have conveyor facility), vessel 2 arrives at time t = 1 Constraint matrix P has 4 feasible assignments:
Vessel 1 Vessel 2 Section 1 , Time 1 Section 1, Time 2 Section 1, Time 3 Section 2, Time 1 Section 2, Time 2 Section 2, Time 3 Section 3, Time 1 Section 3, Time 2 Section 3, Time 3 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1

GSPP Model Formulation

Objective Function:

min
Constraints: ( A ip
p P

p P
p

(d

+ h

) = 1 ) 1

i N s M , t H
pP

p P

(b

st p

: delay in service associated with assignment

h p : handling time associated with assignment pP

: binary parameter, equal to 1 if assignment

pP

is part of the optimal solution

Generation of Instances

Instances based on data from SAQR port with quay length of 1600 meters and vessel lengths in the range 80-260 meters. Generate 6 instances sizes with |N| = 10, 25 and 40 vessels, and |M| = 10 and 30 sections, with 9 instances for each instance size. Handling times generated for 6 cargo types.
Yard Axis
Cement

(200,1100) Conveyor

(700,1200)
Grain (500,1000) Coal

(1200,1100) Pipeline (1100,800)

Clay

(200,600)

(0,0)

Quay Axis

section k

(1600,0)

Drafts of all vessels Di are less than the minimum draft along the quay.

Computational Results
Instances based on data from SAQR port All tests were run on an Intel Core i7 (2 2.80 GHz) processor and used a 32-bit version of CPLEX 12.2. Results inspired by port data show that the problem is complex ! MILP formulation fails to produce optimal results for even small instances with |N|= 10 vessels within CPLEX time limit of 2 hours. hours The performance of the GSPP model is quite remarkable!
Can solve instances up to |N| = 40 vessels Limitations: For larger instances, or longer horizon H solver runs out of memory (use dynamic column generation!)

Alternate heuristic approach based on squeaky wheel optimization (SWO) performs reasonably well for not so large instances. instances Optimality gap is less than 10% (with respect to exact solution obtained from GSPP approach) averaged over all tested instances.

Results Analysis
Time Axis

|N|=10, |M|=10, congested scenario

Time Axis

|N|=25, |M|=10, congested scenario

Conveyor

Pipeline Conveyor

Pipeli ne Conve yor Cement Grain Co nve yor

Conveyor Pipeline Grain Coal Pipeline Grain Coal Coal Coal Grain Cement Grain Clay Clay Clay Clay Clay Clay Coal Pipeline Grain Clay Coal Coal Cement Cement

Clay

C,P

C,P

Quay Axis

Quay Axis

Real Time Recovery in Berth Allocation Problem

Problem Definition: Real time recovery in BAP

Objective: For a given baseline berthing schedule, minimize the total realized costs including the total actual service costs and total cost of rescheduling in space and time

min Z =

(m
i N u

Ai + hi ) +

(c
i N u

| bi ( k ' ) bi ( k ) | + c 2 i | e ' i ei |)

Nu : set of unassigned vessels c1 : cost coefficient of shifting berthing location bi(k) : actual berthing location of vessel i bi(k) : estimated berthing location of vessel i c2: cost coefficient of departure delay i : service priority assigned to vessel i ei : actual departure time of vessel i ei: estimated departure time of vessel i

Problem Definition: Real time recovery in BAP

Solving the BAP as arrival delay information is released in real time

For each vessel i N, we are given an expected arrival time Ai which is known in advance.

The expected arrival time of a given vessel may be updated |P| times during the planning horizon of length |H| at time instants ti1, ti2tiP such that 0 ti1 < ti2 < ti3 . ti(P-1) < tiP < ai where ai is the actual arrival time of the vessel, and the corresponding arrival time update at time instant tiP is AiP for all i N.

Problem Definition: Real time recovery in BAP

To maximize revenues earned by the port while guaranteeing a minimum level of service, we propose that the bulk terminal managers adopt and implement certain strategic measures

Handling Time Restrictions: Impose an upper bound on the maximum handling time of a vessel i N if it arrives within a pre-defined defined arrival time window [Ai Ui, Ai+Ui]
Maximum Threshold Handling Time Arrival Time Window = 2Ui himax

hinom = hibaseline hibaseline

Ai - Ui

Ai

Ai +Ui

Actual Arrival Time

Problem Definition: Real time recovery in BAP

Penalty Cost on late arriving vessels: Impose a penalty fees on vessels arriving beyond the right end of the arrival window, Ai+Ui
Penalty Cost Arrival Time Window = 2Ui

gi slope = c3 c3 g i

Ai - Ui

Ai

Ai +Ui

ai

Actual Arrival Time

Solution Algorithms

Optimization based recovery algorithm

re-optimize optimize the berthing schedule of all unassigned vessels using set-partitioning set approach every time the arrival time of any vessel is updated and it deviates from its expected value. the berthing assignment of a vessel determined after its arrival update is frozen and unchangeable

Heuristic based recovery algorithm

If a vessel has arrived and current time in the planning horizon is greater than or equal to the estimated berthing time of the vessel (as per baseline schedule), assign it to the section(s) at which the total realized cost of all unassigned vessels at that instant is minimized Assumption : All other unassigned vessels are assigned to the estimated berthing sections as per the baseline schedule

min Z =

(m
i N u

Ai + h i ) +

(c
i N u

| b i ( k ' ) b i ( k ) | + c 2 i | e ' i e i |)

Optimization based Recovery Algorithm

Require: Baseline schedule of set N of vessels, set M of sections Initialize set Nu of unassigned vessels to N Initialize boolean array arrivalUpdated of size N = false forall i N Initialize counter = 0 while | Nu | > 0 and counter |H| do Initialize boolean shouldOptimize = false for i = 1 to N do if arrivalUpdated[i] = false and counter ai - and ai Ai then Set arrivalUpdated[i] = true Set Ai = ai Set shouldOptimize = true end if end for if shouldOptimize then Re-optimize forall i Nu end if for i = 1 to Nu do if counter = latest updated start time mi then Assign vessel i to latest updated location bi (k) Set Nu to Nu {i} end if end for counter++ end while

Heuristic based Recovery Algorithm

Require: Baseline schedule of set N of vessels, set M of sections Initialize set Nu of unassigned vessels to N Initialize boolean array arrivalUpdated of size N = false forall i N Initialize counter = 0 while | Nu | > 0 and counter |H| do for berthing Schedule: b do if [Link] AND ![Link] then Set boolean foundSection = false for k = 1 to M do if isStartSectionAvailable([Link],k) isStartSectionAvailable then foundSection = true; break; end if end for if foundSection AND counter [Link] then Scan the entire quay and assign the vessel to the set of sections with minimum total cost forall i Nu end if end if end for counter++ end while

Preliminary Results

|N|=25 vessels, |M|= 10 sections, c1 = 1.0, c2 = 0.002, Ui = 8 hours, = 5 hours, = 1.2, Dv = 5

Objective Function Value 1600 1400 1200 1000 800 600 0 10 20 30 40 50 60 Simulation Runs Optimization Solution 70 80 90 100

Best Solution

Heuristic Solution

Greedy Solution

Mean Gap with respect to the best solution

Greedy Approach 65.04 % Optimization based Approach 12.59 % Heuristic based Approach 14.01 %

Preliminary Results

|N|=25 vessels, |M|= 10 sections, c1 = 1.0, c2 = 0.002, Ui = 8 hours, = 5 hours, = 1.2, Dv = 15

1800 Objective Function Value 1600 1400 1200 1000 800 0 10 20 30 40 50 60 Simulation Runs Optimization Solution 70 80 90 100

Best Solution

Heuristic Solution

Greedy Solution

Mean Gap with respect to the best solution

Greedy Approach 57.46 % Optimization based Approach 21.85 % Heuristic based Approach 21.31 %

Summary of Results

Modeled and solved the dynamic, hybrid berth allocation problem in bulk ports Addressed the problem of recovering a baseline berthing schedule in bulk ports in real time as actual arrival data is revealed. Discussed strategies that the port can adopt and implement to maximize their revenues while ensuring a desired level of service Developed solution algorithms to solve the BAP in real time in bulk ports with the objective to minimize the total realized costs of the updated schedule. Conducted simple numerical experiments to validate the efficiency of the algorithms..

Ongoing and Future Work

More extensive numerical analysis to study the impact of

parameter values related to rescheduling of vessels including cost of shifting the vessel along the quay and cost of departure delay of a vessel bounds on the maximum handling times for vessels arriving within the prescribed arrival window. penalty cost function dependent on the late arriving vessels for arrival delay beyond the prescribed arrival window of the vessel

Develop a robust formulation of the berth allocation problem in bulk ports with a certain degree of anticipation of variability in information.

Thank you!

SWO Heuristic Approach

Introduced by Clements (1997), typically successful in problems where it is possible to quantify the contribution of each single problem element to the overall solution quality Construct/ Analyze/ Prioritize: Solution generated at each successive iteration is constructed and analyzed, results of analysis used to generate a new priority order
P1 Priority Space P2 P3
Construct Solution

S1

Solution Space

Construct Solution

S2 S3

Construct Solution

Moves in search space are motivated by the weak performing elements and not the overall objective function value

SWO Heuristic Approach

Construction heuristic: Returns a feasible berthing assignment for given priority order of vessels Initial Solution: First-Cum-First-Served Served ordering based on arrival times of vessels Algorithm: In each successive iteration, a new priority order is constructed based on the service quality measure of each berthing vessel in the previous solution

Service time of the vessel in the solution found in the last iteration Deviation of service time of vessel from the minimum service time possible for that vessel ( zero delay + minimum handling time ) Sum of service times of the vessel in all iterations completed so far!

If a priority order is already evaluated, introduce randomization by swapping two or more vessels, until we obtained a priority order that has not been evaluated so far Algorithm terminates after a preset number of iterations and best solution is selected as the final solution

Results and Analysis

|N| = 10 vessels, and |M| = 10 sections
Instance OFV A1 A2 A3 A4 A5 A6 A7 A8 A9 Mean 230.21 237.35 223.99 227.12 234.20 233.12 203.23 218.87 198.03 MILP Gap 0.01% 0.01% 0.01% 0.01% 0.01% 0.01% 0.00% 0.00% 0.00% Time 67.67 15.31 9.58 10.31 5.60 11.06 0.56 0.56 0.60 OFV 231.21 238.49 226.61 227.22 234.22 234.06 203.23 219.99 199.89 GSPP Time (H=150, ( h=1) 5.94 5.54 5.96 5.68 5.43 6.85 4.99 5.29 5.16 OFV 262.09 250.44 280.04 240.91 251.09 262.61 208.44 220.90 214.17 FCFS RE 13.36% 5.01% 23.58% 6.03% 7.20% 12.20% 2.57% 0.41% 7.14% 8.61% OFV 230.48 239.08 225.33 228.00 234.47 233.12 203.38 218.87 198.03 SWO RE -0.32% 0.25% -0.57% 0.35% 0.11% -0.40% 0.07% -0.51% -0.93% -0.22% Time 15.81 16.66 16.97 16.60 16.30 16.90 15.95 16.72 17.53

|N| = 10 vessels, and |M| = 30 sections

Instance OFV B1 B2 B3 B4 B5 B6 B7 B8 B9 Mean 188.39 178.07 200.16 182.57 178.48 199.82 173.02 162.51 175.29 MILP Gap 0.01% 0.01% 0.01% 0.01% 0.01% 0.01% 0.01% 0.00% 0.00% Time 15.80 15.78 1094.61 3.04 10.97 87.78 1.30 1.57 1.39 OFV 189.73 179.10 202.33 184.27 179.23 201.17 173.02 162.81 175.81 GSPP Time (H=150, ( h=1) 94.552 86.08 101.93 89.58 85.01 96.19 86.00 81.67 95.74 OFV 216.56 186.41 230.14 224.00 185.60 240.09 175.72 169.20 192.41 FCFS RE 14.14% 4.08% 13.74% 21.56% 3.55% 19.35% 1.56% 3.92% 9.44% 10.15% OFV 192.81 178.08 216.14 182.80 179.01 223.37 175.30 166.20 191.26 SWO RE 1.62% -0.57% 6.82% -0.80% -0.12% 11.04% 1.32% 2.08% 8.79% 3.35% Time 49.95 48.42 49.79 47.73 48.37 48.83 48.61 50.29 50.27

|N| = 25 vessels, and |M| = 10 sections

Instance OFV C1 C2 C3 C4 C5 C6 C7 C8 C9 Mean 812.32 783.45 903.51 795.71 751.19 874.53 735.13 689.37 800.00 MILP Gap 33.08% 30.27% 33.39% 23.18% 27.47% 24.50% 19.72% 22.26% 22.76% Time OFV 819.22 781.72 900.43 791.18 747.88 863.86 741.16 699.14 793.24 GSPP Time (H=150, ( h=1) 14.09 11.70 20.19 15.26 10.41 19.38 15.91 11.23 12.82 OFV 976.49 924.35 1107.59 877.90 846.26 979.26 840.85 761.48 936.55 FCFS RE 19.20% 18.25% 23.01% 10.96% 13.15% 13.36% 13.45% 8.92% 18.07% 15.37% OFV 869.31 825.92 929.32 852.03 774.17 898.44 806.23 735.46 872.76 SWO RE 6.11% 5.65% 3.21% 7.69% 3.51% 4.00% 8.78% 5.20% 10.03% 6.02% Time 22.29 22.58 22.24 23.28 22.16 23.19 22.54 22.32 23.56

|N| = 25 vessels, and |M| = 30 sections

Instance OFV D1 D2 D3 D4 D5 D6 D7 D8 D9 Mean 690.79 617.31 809.55 657.48 560.65 754.87 581.54 510.80 704.76 MILP Gap 23.14% 34.23% 30.75% 20.62% 25.96% 21.97% 8.36% 16.20% 19.18% Time OFV 670.42 591.06 784.94 636.19 556.37 739.44 590.24 506.30 677.97 GSPP Time (H=150, ( h=1) 219.04 185.44 387.40 220.40 172.09 253.67 194.80 167.09 200.63 OFV 857.99 723.13 984.28 778.50 622.14 909.53 731.55 565.87 848.97 FCFS RE 27.98% 22.34% 25.40% 22.37% 11.82% 23.00% 23.94% 11.77% 25.22% 21.54% OFV 785.91 667.20 866.82 728.60 614.72 836.23 706.82 565.87 778.67 SWO RE 17.23% 12.88% 10.43% 14.53% 10.49% 13.09% 19.75% 11.77% 14.85% 13.89% Time 105.36 96.03 105.66 100.95 91.35 102.34 100.82 111.46 99.87

|N| = 40 vessels, and |M| = 10 sections

Instance OFV E1 E2 E3 E4 E5 E6 E7 E8 E9 Mean 1243.64 1193.05 1341.65 1113.36 1105.34 1361.62 1011.20 1013.41 1181.97 MILP Gap 63.77% 59.69% 67.35% 59.53% 56.98% 68.15% 55.47% 53.02% 64.95% Time OFV 1140.60 1138.16 1249.06 1051.50 1063.85 1160.05 946.35 953.24 1071.46 GSPP Time (H=150, ( h=1) 41.73 18.80 139.47 30.87 19.06 167.58 26.04 20.03 94.88 OFV 1536.78 1571.07 1878.78 1408.95 1447.39 1903.39 1291.11 1183.57 1500.71 FCFS RE 34.73% 38.04% 50.42% 33.99% 36.05% 64.08% 36.43% 24.16% 40.06% 39.77% OFV 1289.88 1273.09 1416.54 1137.20 1202.50 1330.64 1148.14 1094.15 1296.79 SWO RE 13.09% 11.86% 13.41% 8.15% 13.03% 14.71% 21.32% 14.78% 21.03% 14.60% Time 28.24 28.44 31.50 30.11 32.06 34.01 31.69 32.01 35.64

|N| = 40 vessels, and |M| = 30 sections

Instance OFV F1 F2 F3 F4 F5 F6 F7 F8 F9 Mean 1193.42 913.59 + 902.74 881.37 1121.14 922.04 728.48 934.35 MILP Gap 70.56% 62.66% + 59.15% 61.20% 66.39% 62.05% 52.93% 58.59% Time + OFV 920.73 863.43 1089.48 856.41 786.27 1015.53 777.06 679.58 920.29 GSPP Time (H=150, ( h=2) 506.02 127.91 932.56 3341.62 137.91 2281.78 829.88 131.81 1767.57 OFV 1278.04 1168.60 1784.98 1143.59 973.94 1628.76 932.34 774.12 1458.45 FCFS RE 38.81% 35.34% 63.84% 33.53% 23.87% 60.39% 19.98% 13.91% 58.48% 38.68% OFV 1092.44 911.47 1411.24 1035.72 857.47 1286.73 932.34 745.00 1214.66 SWO RE 18.65% 5.56% 29.53% 20.94% 9.06% 26.71% 19.98% 9.63% 31.99% 19.12% Time 169.53 159.28 173.89 160.113 163.41 265.29 166.52 160.49 171.97

Results Analysis
Percentage gap in optimal service times between 10x10 and 10x30
30.00% 20.00% 10.00% 0.00% 1 2 3 4 5 6 Instance Index 7 8 9

Percentage gap in optimal service times between 25x10 and 25x30

30.00% 25.00% 20.00% 15.00% 10.00% 5.00% 0.00% 1 2 3 4 5 6 Instance Index 7 8 9 40.00% 30.00% 20.00% 10.00% 0.00%

Percentage gap in optimal service times between 40x10 and 40x30

4 5 6 Instance Index

Disruption: Arrival Delay Scenario

Vessel 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 EAT 3 3 3 2 2 2 2 1 4 2 2 0 1 0 1 4 4 5 1 0 3 3 5 0 1 AAT -1 -3 1 4 -2 4 4 0 12 1 4 4 -2 -2 -8 -4 -2 1 2 9 9 5 1 -2 10

Problem Definition: Real time recovery in BAP

Key Assumptions

Vessel Priorities: In practice, if a vessel with higher priority arrives late, it may still be given preference over a vessel with low service priority.

Release of information: Each incoming vessel updates its exact arrival time a certain fixed time period before its actual arrival time, and once updated it does not change again.

Future vessel arrivals: At any time instant t, the arrival time of an unassigned vessel i Nu that is not updated is assumed equal to the expected arrival time Ai if current time t is less than Ai - , or otherwise assumed equal to t + . (The handling time restrictions are imposed accordingly.)