Transcript Arc-based formulations for coordinated drayage problems

Arc-based formulations for
coordinated drayage problems
Christopher Neuman
Karen Smilowitz
Athanasios Ziliaskopoulos
INFORMS San Jose
November 18, 2002
Outline
•
•
•
•
•
Drayage and the problems in Chicago
Previous academic work
A new formulation
Results
Future directions
What is drayage?
• OED definition: originally a handcart; drayage –
process of draying.
• Now, the transportation of rail freight by truck,
usually occurring at the beginning or end of the
journey
• While a small (~5%) proportion of the distance of
an average container, is usually a large (~40%)
proportion of the cost (Reebie Associates)
The Chicago story
• A hub for rail freight transportation, and a
major origin and terminus for freight (large
manufacturing industry)
• 26 rail yards in/around Chicago; many are
landlocked (no brown/greenfield
alternatives) so no expansion
• Estimated 25,000 lifts (transfers on/off a
train) per day
Problems with drayage
• No coordination of cars based on area
•
•
•
•
origin/destination
Lack of uniform equipment
Fee structure penalizes agents
Train schedules/takedown times vary
City concerns: pollution, congestion, road
damage, safety
Trip type – Drop and Pick
Depot
Shipper
Consignee
RY 1
RY 2
Trip type – Stay With
CY 1
CY 2
Depot
Shipper
Consignee
RY 1
RY 2
Previous work in drayage
• Morlok and Spasovic (1990), Hallowell (1989):
drayage problems might be improved using OR
tools
•
•
•
•
•
Arc-based IP formulation
Multi-day model
Movement of tractors and containers separately
GAMS implementation
Optimality through two-phase method
A new formulation for the
drayage problem
• Aggregating customers limits usefulness to
drayage companies
• Time windows for each customer, deadline
and release times for containers
• Variables represent truck movement;
container movement inherent in network
structure
• One-day model, discretized time
Network: few nodes …
C
S
RY
CY
C
S
… many (feasible) arcs
Arcs have four indices {i,j,r,s}:
(i,j) origin and destination
Deadline: 15
RY
r: time truck leaves i
s: time truck can leave j
S
Time window: 6-18
This shows loaded arc
set only; depending on
(i,j) combination, may
have empty and bobtail
arc sets, defined if time
windows are feasible
Formulation
• Objective: Minimize total distance traveled
• Distance (and travel time) can be adjusted for timevariant congestion, construction
• Constraints:
• All loaded movements must be served, and empties
provided;
• Flow-balance constraints on each node
• Time-slice constraints
Results
# Cust
|A|
# trips
ObjFn
|A|
# trips
ObjFn
|A|
# trips
ObjFn
6
18677
2
170
20913
3
190
21962
2
202
10
54405
4
276
56004
4
338
49615
4
338
20
161566
8
1078
177164
6
1072
196231
7
916
30
344398
10
1398
351624
11
1426
332458
11
1418
CPLEX 8, Multiprocessor Machine with 1GB RAM computation time from 10 sec - 1 min
#RY = #Cust/3 ; #CY= #Cust/5; TW ~ N(8,2) hours
Future Directions
• Increase problem size (# customers, RY,
•
•
•
•
CY)
Use real data, generate more realistic data
Arc formulation as input to path-based
formulation
Incorporate more realistic trip types (DP
empties)
Allow penalized time window violations
Future Directions
• DSS for existing dispatchers
• 60% of a day’s trips known 3 days prior
• 90% known 1 day prior
• Dispatchers add non-model intelligence
• Dynamic replaces static
• New trip in existing sequence
• Variable or random dwell and travel times