
Scheduling optimization

Our cooperation with Mobile Knowledge has
produced the Shared Ride Engine or SRE.
The SRE is a customized implemetation of the
Vehicle Routing Problem with Pickup and Delivery
and Time Windows. The SRE is capable of finding
excellent solutions to the problem within the
constraints imposed by the fleet of vehicles
such as vehicle capacity and wheelchair
accessability.
An interesting
additional constraint to the problem was Mobile
Knowledge's quality of service concept called
the Maximum relative passenger delay or
RPD. The RPD is defined to be total elapsed
time between the pick up and drop off divided by
the time it would take to go directly from the
pick up to the drop off location if no other
passengers were picked up or dropped off on the
way. The schedule produced by the SRE always
meet this additional constraint for every trip.
We are very excited to report that the SRE has
been successfully fieldtested by the company
and is now operational in commercial settings in
cities such as Chicago and Ottawa.

During our involvemenet with BC Ferries we
investigated the possibility of improving
existing schedules of ferries operated by BC
Ferries connecting gulf islands. We developed an
integer programming model, and a new heuristic
procedure based on the very large scale
neighbourhood which is searched successfully
using general purpose integer programming
solvers. The method proved to be very efficient
in solving largescale reallife problems. Our
research results confirmed ideas discussed by BC
ferries scheduling group internally based on
their experience. A research paper is under
preparation based on the mathematical model and
solution methods used in this project.

Our work on the Dynamic pickup and delivery
problems with time windows has produced a
prototype software capable of solving the
dynamic PDPTW problem. The dynamic PDPTW deals
with the problem in a realtime environment
where not all of the requests are known in
advance. The methodology used for solving the
dynamic PDPTW is an online approach  the
problem is being solved repeatedly as new
requests become known. Future requests are not
predicted nor stochastically modeled, i.e., the
algorithm optimizes only over known
requests.
We measured the performance of our prototype
against realworld data provided by Dynamex, FDM
Software and Mobile Knowledge. Our online system
for ondemand dispatching comprises two parts, a
part that prepares information and data
structures for fast travel time approximation
(will be discussed later), and a part for
solving the dynamic pickup and delivery problem
with time windows. The first part 
preprocessing for the travel time evaluation 
is an offline component that runs throughout
the day, incorporating any emergency road
conditions whenever they occur. The travel time
estimation between two locations in the city is
computed onthefly. The second part  the
solver of the dynamic PDPTW  is an online
component that solves the problem repeatedly as
new data (requests) come in.
Although we are not at the liberty to present
the specifics of the results, we can present the
following summary table for one of the data set.
Each of the projects involving the industrial
sponsors is a dynamic Pickup and Delivery
Problem with Time Windows PDPTW PDPTW deals
with finding a set of routes for serving a set
of transportation requests. Each transportation
request is defined by a pickup location, a
delivery location and a load. Each location has
a time window within which has to be served.
Rejection of a request is not allowed, and
entire request has to be served by one driver.
A certain number of vehicles is activated at the
beginning of a day, but if a new request cannot
be feasibly served by these active vehicles a
new vehicle is The dynamic PDPTW deals with the
problem in a dynamic (realtime) environment
where not all of the requests are known in
advance. The methodology used for solving the
dynamic PDPTW is an online approach  the
problem is being solved repeatedly as new
requests become known. Future requests are not
predicted nor stochastically
modeled, i.e., the algorithm optimizes
only over known requests.

Actual 
Us 
Jobs scheduled 
902 
902 
Total driving time 
79:50 hours 
70:00 hours 
Total driving distance 
2447.35 km 
2118.95 km 
Av. driving time per job 
5:18 min 
4.39 min 
Av. driving distance per job 
2.71 km 
2.35 km 
Number of vehicles used 
17 
13 

This power point presentation summarize the
techniques used to find good solutions to the
VRP.

Very large scale neighborhood (VLSN) search
algorithms are known to produce good solutions
for various practical optimization problems. Our
team members are active in this broad research
area. Combining VLSN search and variable
neighborhood search produced superior results in
some classes of optimization problems considered
by our group members. It may be noted that our
ejection chain algorithms developed for the
industrial problem can be viewed as a VLSN
search algorithm.
Travel time computation in urban networks
We have considered the problem of predicting travel
time in the Greater Vancouver area as well as in
Toronto and its suburbs. Our goal is a fast algorithm
for approximating pointtopoint shortest path/travel
times for any road network which does not require any
city specific massaging of data.
A prototype has been built to compute distances for
any city network. The approximate time needed to get
the travel time between any two intersections in the
network is found to be O(log n) (expected) for the
greater Vancouver area. The relative error of the
approximation, found experimentally, is 8 percent. The
optimal Dijkstra's path can be approximated to within
1 percent of the optimal by using the upper bound
extimates in A*like search. The advantages of the
designed algorithm are:
 both distances and travel times may be computed if
speed limits are known,
 the travel times depending on the time of the day
(or on day of the week) may be computed,
 traffic lights and stop signs may be taken into
account,
 suggested route between two points may be displayed,
and general directives may be given,
 the topology of the road network and natural
obstacles are taken into account.
Another project sponsored by Mobile Knowledge consist
of using real life GPS data points produced by a fleet
of vehicle to improve even further the accuracy
of current travel time compuation. This
project proved to be particularly challenging because
we were not allowed to use a digital map of the
underlying road network to help our travel time
prediction. The input for the entire model consists
solely of the enormous number of GPS points produced
by the fleet.
