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 field-tested 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 large-scale real-life 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 real-time environment where not all of the requests are known in advance. The methodology used for solving the dynamic PDPTW is an on-line 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 real-world data provided by Dynamex, FDM Software and Mobile Knowledge. Our online system for on-demand 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 off-line 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 on-the-fly. 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 (real-time) environment where not all of the requests are known in advance. The methodology used for solving the dynamic PDPTW is an on-line 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 point-to-point 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.