Transcript Gizem Özbaygın

Review of real-time vehicle schedule recovery
methods in transportation services
Monize Sâmara Visentini
Denis Borenstein
Jing-Quan Li
Pitu B. Mirchandani
Prepared by: Gizem Özbaygın
Outline
•
Introduction
•
Basic models and problem formulation
•
Schedule recovery
•
•
road-vehicle services
•
train services
•
airline services
Conclusion and future research
Introduction
•
Many optimization-based algorithms for vehicle scheduling problem
(VSP)
•
Disruption of planned schedules due to unforeseen events (weather
conditions,disasters,accidents, vehicle breakdowns, etc.)
•
Rescheduling under disruptions — real-time vehicle schedule recovery
problem (RTVSRP)
•
Main objective of the paper: review & synthesise the literature on
ground and airline transportation
Introduction
•
Until recently, real-time vehicle schedule recovery decisions by human schedulers, based on experience &
common sense
•
New information and communication technologies — real-time information available
•
Increased capacity of the computers — possible to implement real-time disruption recovery algorithms at
reasonable costs
•
An interesting approach to disruption problems: robust scheduling
•
•
(incorporate the possibility of disruptions during the schedule design to enhance potential recovery actions, such as
adding buffers or slack time between operations in schedules or having standby vehicles and part-time crews)
Ahuja et al. (2009) — robust optimization theory in transportation systems
•
Huisman et al. (2004), Kramkowski et al. (2009), and Amberg et al. (2012) — robust bus scheduling
•
Zwaneveld et al. (1996), Zwaneveld et al. (2001), Fischetti et al. (2009), and Caprara et al. (2010) — robust train
scheduling
•
Ageeva (2000), Lan et al. (2006), Lee et al. (2007), Weide et al. (2009), Borndörfer et al. (2009), and Dück et al. (2012)
— robust aircraft scheduling
Introduction
•
•
Modeling RTVSRP — an underlying network structure representing the problem to describe
•
how vehicles can be rescheduled
•
the current planned schedule
•
the current situation when the disruption occurred
•
technical and timing constraints
Differs from VSP — the underlying network depends on
•
existing situation
•
feasible alternatives to address the disruption
•
Main challenge of RTVSRP — dynamic environment: while the rescheduling is being performed, the status of the
transportation system is changing at the same time.
•
For use in real-world, quick solutions required!!!
Introduction
•
A comprehensive review on methods for real-time vehicle schedule recovery in
transportation services
•
Focus: Recovery of planned vehicle schedules in case of severe disruptions
(breakdowns, accidents, delays, etc.)
•
Real-time vehicle schedule recovery problems (RTVSRP):
•
vehicle rescheduling for road-based services
•
train-based rescheduling
•
airline schedule recovery problems
Basic Models & Problem
Formulation
•
•
Problem statement
•
a set of depots (or stations)
•
a set of vehicles
•
a series of trips with fixed starting and ending times or with service time windows
•
the travel times between all pairs of locations
•
a serious disruption that interrupts at least one currently scheduled trip
•
the current location and the current status of the vehicles in the system
•
find a feasible schedule that optimizes a set of objectives — trips are either rescheduled (possibly with delays) or
canceled, each vehicle performs a feasible sequence of trips.
Vehicle rescheduling problem (VRSP), train rescheduling problem (TRP), aircraft rescheduling problem
(ARP)
Basic Models & Problem
Formulation
•
Rescheduling strategies: dynamic, predictive (off-line), reactive (on-line)
•
Dynamic — trains dispatched using local information with a decentralized control method based on
rules (widely used by human schedulers)
•
Predictive — within robust scheduling contexts, to generate schedules able to handle minor
disturbances
•
Reactive — find a new schedule after one or several events occur, including severe disruptions,
minimizing some measure of the effects
•
Ionescu et al. (2010) — comparison of 3 strategies for ARP using data from a European airline
with 2 evaluation criteria: punctuality of flight arrival & run-time efficiency.
•
The dynamic strategy — quick but poor solutions
•
Predictive approach — not as practicable as the reactive strategy
Basic Models & Problem
Formulation
•
Types of network representations used
•
Connection Networks (CN): activity-on-node networks (nodes — trips, stations, airports, etc., arcs —
connections between nodes)
•
Time-line networks (TLN): activity-on-edge networks (all events -represented in nodes- of a resource -such as
station, airport, and track segments- placed on a corresponding time-line. Arcs connect events in the same timeline involving the same resource, or in different time-lines involving different resources)
•
Time-band networks (TBN): developed by Argüello et al. (1997) specifically for aircraft recovery (nodes —
specific activities at a station during a time segment, arcs — arrivals to or departures from a station)
•
RTVSRP — formulated based on the classical network problem formulations (such as the minimum cost
flow problem, the multi-commodity network flow, and the set packing problem)
•
A generic formulation based on a CN with nodes representing trips, arcs connecting two compatible pair of
trips
•
(Trips i and j are compatible if the same vehicle can reach the starting point of trip j after finishing trip i & the
vehicle has technical and capacity attributes to perform both the trips)
Basic Models & Problem
Formulation
•
•
Sets
•
A: set of trips being served by vehicles at the instant of a disruption
•
N: set of all future service trips (including the disrupted trip) numbered according to nondecreasing starting times
•
A ∪ B: set of all unfinished trips
•
Z: set of all compatible pair of trips (i, j), in which j starts after F
Decision variables
•
xkij : 1 if vehicle k is assigned to trip j after trip i; 0 o.w.
•
zi : 1 if service trip i is cancelled; 0 o.w.
•
sti : starting time of trip i
Basic Models & Problem
Formulation
•
Parameters
•
Bi = prescribed starting time of trip i
•
Wi = prescribed time of trip i
•
Tij = travel time from the ending point of trip i to the starting time of trip j.
•
Di = maximum delay allowed for trip i.
•
U = service time at station
•
Pi = trip i delay cost
•
Ci = trip i cancelation cost
•
F = time of the disruption
minimize the weighted sum of operations, delay, penalty, and trip cancellation
costs
minimize the weighted sum of operations, delay, penalty, and trip cancellation
costs
flow conservation for each vehicle
minimize the weighted sum of operations, delay, penalty, and trip cancellation
costs
flow conservation for each vehicle
any trip is either served or cancelled
minimize the weighted sum of operations, delay, penalty, and trip cancellation
costs
flow conservation for each vehicle
any trip is either served or cancelled
equates the starting time of trips in A to their prescribed starting times
minimize the weighted sum of operations, delay, penalty, and trip cancellation
costs
flow conservation for each vehicle
any trip is either served or cancelled
equates the starting time of trips in A to their prescribed starting times
trips in N cannot start earlier than the prescribed starting time
minimize the weighted sum of operations, delay, penalty, and trip cancellation
costs
flow conservation for each vehicle
any trip is either served or cancelled
equates the starting time of trips in A to their prescribed starting times
trips in N cannot start earlier than the prescribed starting time
delay restrictions for trips in N
minimize the weighted sum of operations, delay, penalty, and trip cancellation
costs
flow conservation for each vehicle
any trip is either served or cancelled
equates the starting time of trips in A to their prescribed starting times
trips in N cannot start earlier than the prescribed starting time
delay restrictions for trips in N
future trip j cannot start before traveling & unloading of its preceding trip i
minimize the weighted sum of operations, delay, penalty, and trip cancellation
costs
flow conservation for each vehicle
any trip is either served or cancelled
equates the starting time of trips in A to their prescribed starting times
trips in N cannot start earlier than the prescribed starting time
delay restrictions for trips in N
future trip j cannot start before traveling & unloading of its preceding trip i
domain restrictions for decision variables
Basic Models & Problem
Formulation
•
•
RTVRSP as the real-time schedule recovery of machines mainly in the
railway transportation (Raheja and Subramaniam 2002)
•
vehicles as jobs
•
trips/block segments as machines
•
allocation of a vehicle to a trip as processing a job by a machine for a given
amount of time
Based on similarities, TRP was formulated as a job shop problem with some
additional constraints (Sahin 1999; D’ Ariano et al. 2007a; D’ Ariano et al.
2008)
Schedule Recovery for Road Vehicle
Services
•
Vehicle rescheduling context and recovery decision process
•
Schedule recovery models and solution approaches
Rescheduling context and decision
process
•
VRSP arises in a road-vehicle (bus/truck) type transportation system when a serious
disruption presents itself
•
Examples: Traffic accidents, medical emergencies, vehicle breakdowns, etc.
•
Dynamic rescheduling of the fleet s.t. all trips scheduled prior to a disruption
•
•
either completed in a reasonable amount of time
•
or canceled
Instances of VRSP happen in applications such as school bus transportation, public
transit services, industrial/hospital refuse collection, mail delivery, etc.
Rescheduling context and decision
process
Vehicle Rescheduling Models
•
Bunte and Kliewer (2009) presented a comprehensive overview on vehicle scheduling models
•
Huisman et al. (2004) — predictive rescheduling
•
environment with significant traffic jams
•
a cluster-reschedule heuristic for the “dynamic” VSP problem
•
disruption: delays
•
a multi-depot VSP (MDVSP) based model solved sequentially: (1) cluster the trips using static VSP,
(2) reschedule for each depot
•
tests with real data of a public transport company — the number of trips starting late can be reduced
by employing a few extra vehicles
Vehicle Rescheduling Models
•
Li et al. (2004) — reactive scheduling
•
disruptions: vehicle breakdowns or severe vehicle accidents
•
problem modeled as several VSPs (each corresponding to a different vehicle as an alternative for backing
up the disrupted trip)
•
each backup vehicle k ∈ K generates a CN, G (k ), referred as a “feasible network”
•
parallel auction algorithm to find all possible backup vehicles for a serious disruption
•
improved solution times by introducing common feasible network (CFN) -the intersection of all possible
feasible networks (better initial assignment)
•
algorithm performs well for large problem sizes
•
two restrictive assumptions: (i) rescheduled trips, except the disrupted one, cannot suffer delays, (ii) no
restrictions on the number of trips that may be reassigned
Vehicle Rescheduling Models
•
Li et al. (2007b) — a decision support system (DSS)
•
to facilitate a practical application for rescheduling trucks for solid waste collection in a Brazilian city
•
the problem of recovery from severely disrupted trips, minimizing disruption costs
•
SDVRSP modeled as a sequence of SDVSPs — quasi-assignment formulation
•
combined forward–backward auction algorithm
•
experiments with randomly generated instances
•
DSS has potential as an effective and efficient tool for real-time operational planning in
transportation/logistic companies
Vehicle Rescheduling Models
•
Ernst et al. (2007) — reactive scheduling
•
Dynamic Vehicle Assignment and Scheduling System (D-VASS)
•
dynamic scheduling of vehicles
•
a large New Zealander recreational-vehicle-rental company
•
responding to availability queries by reservation staff
•
incorporating new bookings into the schedule
•
responding to operational contingencies (e.g. vehicle breakdowns, late
returns)
Rescheduling train services during
disruptions
•
Rail transportation services: passenger traffic & freight shipping
•
Train scheduling - difficult due to its size & inter-dependencies
between the train movements and operational constraints
•
Train rescheduling considerations
•
Train rescheduling models
Train rescheduling considerations
•
Major complexity — “snow ball effect”
•
Some constraints related to train scheduling
•
•
Trains cannot share the same track in opposite directions at the same time: to avoid collisions, railway
networks are often composed of blocks)
•
Diversities in railway infrastructure: some blocks are single-tracked, others are double-tracked or even ntracked
•
Heterogeneous traffic: heavy cargo trains and passenger trains can share the same track
•
Minimum and maximum idle times at each station: although can be changed in case of a disruption, it
can cause itinerary problems to passengers.
More details on the constraints related to train scheduling given in Cordeau et al. (1998) and
Jespersen-Groth et al. (2009).
Train rescheduling considerations
•
TRP consists of
•
defining a new re-allocation of trains to blocks
•
modifying the original timetable wrt technical and commercial constraints
•
•
usually attempting to minimize the total train (or passenger) delay
The new schedule should be
•
consistent with the current state of the system
•
generated very quickly (already some delays)
Train rescheduling considerations
Train rescheduling models
•
Törnquist (2006) presented an overview of research on train scheduling and
dispatching
•
21/48 papers focusing on rescheduling
•
major objective: minimisation of the total delay
•
This review includes work reported after 2005
•
Different infrastructure representations: lines and general networks, bidirectional or
unidirectional tracks, parallel tracks, etc.
•
In general, more than 30 trains cannot be tackled efficiently.
Train rescheduling models
•
Törnquist and Persson (2007) — rescheduling of n-tracked railway traffic
•
railway network with several merging and crossing points
•
MILP formulation based on an event-driven representation of time (event: the conditional resource
request by a train for a segment of a track)
•
two alternative objective functions: total final delay of traffic & total costs incurred by delays of
trains at the final destinations
•
only few modifications in the initial timetable can produce a good solution
•
different strategies, such as “allow swaps of tracks but maintain order” tested on large size
problems
•
The solution approaches — well in terms of run-time efficiency & solution quality
Train rescheduling models
•
Nielsen (2008) — a generic framework for rolling stock rescheduling problem
MILP formulation — simultaneously minimizing
•
•
•
# of canceled trips
•
changes to the original schedule
•
changes on the planned end-of-day balance of rolling stock for every depot
Nielsen (2011) — rescheduling of passenger railway rolling stock
•
model involves real-life aspects and penalizes cancelations of trains, changes on shunting processes,
carriage kilometers, seat shortage kilometers, deviations from the planned end-of-day rolling stock balances
on each depot
•
extension of the previous model considering passenger flow dynamics & passenger behaviour
•
an iterative solution technique integrating the rolling stock assignment optimization with passenger flow
simulation
Train rescheduling models
•
Berger et al. (2011a) — train disposition problem
•
whether a train should wait for an incoming delay train or not
•
event-graph representation
•
formulated based on the uncapacitated multi-commodity flow
•
major objective: satisfaction of passengers through
•
•
total lateness at the destination
•
deviation from original plans of passengers
•
# of passengers unable to reach their destination
experiments with data from German Railways — the approach is fast & practicable
Train rescheduling models
•
Fekete et al. (2011) — schedule recovery of rail-based urban mass transit
systems
•
ILP formulation based on the event-activity network, suggested by Serafini
and Ukovich (1989)
•
focus: scenarios including a bottleneck (e.g. shutdown of the direction of a
track)
•
objective: maximize the number of trips that will still be completed after the
disruption
•
real-life scenarios considered — good solutions within a minute
Train rescheduling models
•
Several papers on train conflict detection & resolution (CDR)
•
CDR — altering dwell times, train speeds, train ordering and routing
•
Modeling and solution methods use alternative graph formulations
•
Alternative graph — to address scheduling problems for which
response time is critical in evaluating a method
•
Main advantage of alternative graph based models: network topology
represented at the level of railway signals & operational rules.
Train rescheduling models
block sections, junctions, shared
resources
nodes: train-block section pairs
alternative arcs: two paired arcs
with a small circle
α: time required to pass through all
track segments
Airline schedule recovery problem
•
Most studied class of problems in RTVSRP
•
Fast & reliable recovery methods — important to airline companies (serious
operational & economic outcomes caused by a disruption in the airline traffic)
•
Passenger delay is especially a major issue for the companies due to capacity
related issues at busy airports
•
Development of optimization models for airline schedule recovery is a
challenge
•
Aircraft rescheduling considerations
•
Aircraft rescheduling models
Aircraft rescheduling considerations
•
Flexibilities & slack in the original schedule — reduces the need to reschedule in small disruptions
•
In severe disruptions, rescheduling is usually necessary
bad weather conditions, safety emergencies, unplanned events affecting airport infrastructure & air traffic control
•
•
Three types of disruptions(Bisaillon et al. 2011)
•
Flight disruption (delay or cancellation)
•
Aircraft disruption (temporary unavailability) — receiving less attention in the literature
•
Airport disruption (temporary reduction in departure/arrival capacities)
•
issuing of a Ground Delay Program (GDP) — increase the time gap between successive landings for operational
safety
•
Many resources to be rescheduled under a large disruption — usually in a sequential manner
•
Focus: ARP
Aircraft rescheduling considerations
Aircraft rescheduling models
•
Clausen et al. (2010) — a comprehensive survey on airline disruption management
•
Most mathematical models & solution techniques for ARP are similar to those for schedule
planning
•
ARP formulations based on network flow models, TLN, TBN, and the set partitioning model
on CN
•
Solution approaches involving out-of-kilter algorithm, B&B, Lagrangian relaxation, GRASP,
and TS
•
most approaches can account for some important real-life considerations
•
not practical for real-time applications due to long-lasting computational times
Aircraft rescheduling models - flight
disruption
•
Bertsimas and Patterson (2000)
•
multi-aircraft optimization model
•
objective: minimize weather delay costs considering deterministic weather scenarios
•
model as a dynamic network flow problem with some additional constraints
•
a mathematical programming approach: Lagrangian generation algorithm (LGA)
•
•
Lagrangian relaxation to produce aggregate flows
•
randomized rounding heuristic to decompose aggregate flows into flight paths for aircrafts
•
IP formulation to generate feasible and near-optimal flight routes
three scenarios to evaluate the algorithm performance —solution times between 116-330 seconds
Aircraft rescheduling models - flight
disruption
•
Løve et al. (2002)
•
ARP minimizing flights delay and cancelation costs
•
two local search approaches based on a network formulation (nodes - aircraft/flights,
edges - connecting aircraft nodes to flight nodes)
•
•
the steepest ascent local search (SALS)
•
the iterated local search
Tests on randomly generated data — SALS can find a local optimum in 2.11s on
average
Aircraft rescheduling models - airport
disruption
Filar et al. (2007)
•
•
a new optimization model named “model for adaptive rescheduling of flights in emergencies”
(MARFE)
•
rescheduling of both aircrafts on the ground and those in the air, respecting airport capacity levels
•
objective: minimize the sum of
•
•
delay costs
•
curfew violation costs
•
cancellation costs
•
diversion costs
less than 5 minutes to optimally solve problems (data from Sydney airport in Australia with 517
flights per day, 261 arrivals, and 256 departures)
Aircraft rescheduling models - airport
disruption
•
Petersen et al. (2012) — an innovative research, fully integrated ARP
•
optimization-based method to recover flight schedule, aircraft rotations, crew schedule, and passenger
itineraries
•
a routine to restrict problem size
•
flights directly affected by a resource at the airport
•
enlarged set of flights considering aircraft, crews, and passengers
•
disruptable flight set — all resources causing delay/cancelation
•
Benders decomposition based solution scheme
•
objective: minimize passenger delays (due to the integrated problem structure)
•
relatively good solutions (compared to sequential approach) obtained in reasonable times for several
disruption scenarios (data from an American regional company with 800 flights and 2 fleets)
Conclusion
•
Disruptions in transportation services can have huge impacts on quality and service levels, and incur
substantial costs
•
A state-of-the-art review in real-time vehicle schedule recovery modeling & solution approaches
considering road, railway, and airline based transportation services
•
Schedule recovery process (iterated until finding a feasible solution for all resources)
•
•
analysis of the disruption and its implications for the initial schedule
•
generation of schedule recovery plans sequentially: (1) reschedule vehicles, (2) reschedule crews
•
checking the impact on passengers
Two major challenges for recovery problem: (1) large amounts of real-time data required, (2) quick
solutions are needed
Conclusion
•
Most commonly used network structure: CN
•
TLN, TBN used 18% in train, 44% in airline
•
TBN better with lower disruption times, TLN better with larger disruption times (deeper level of
detail in TBN)
•
Some facts:
•
The literature on VRSP is very limited compared with train & aircraft recovery literatures.
•
Most papers consider delays as the only source of disruption; major technical failures/severe
accidents are not studied much
•
Quite few papers integrate vehicle, crew, and passenger recovery
Future research
•
Multi-objective approaches for RTVSRP (consider multiple,conflicting objectives)
•
Passenger disruption management
•
Consider stability as a performance measure index for robust scheduling & evaluate
rescheduling in transportation accordingly
•
Use of time-space networks for RTVRSP can lead to innovative & simpler models with
faster solution techniques (nodes representing specific locations at a particular time, arcs
representing possible transitions between nodes)
•
CP implementations to develop good & fast solution approaches to RTVRSP (quite
successful in scheduling)
Questions/Comments?