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.
An online dispatching system is being developed for each of the problems of our industrial sponsors. The real-world data provided by Dynamex and FDM Software are for the greater Vancouver area. The real world problem data provided by Mobile Knowledge is for the Ottawa area. 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.
The developed algorithm is tested on
real data coming from local and international companies. 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.
| 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 |
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.