The Pickup and Delivery Problem with Time Windows (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 it has to be served. 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 added. 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.
Very large scale neighborhood (VLSN) search algorithms are known to
produce good solutions for various practical optimization
problems [1].
The neighborhood of a solution consists of set of solutions that may be derived by applying
certain changes to the solution.
Many simple local search procedures and many metaheuristics are neighborhood search procedures.
We have used the concept of 
improvement graph' to explore the neighborhood for local search [1].
The improvement graph consists of a set of nodes linked together by
edges. Each scheduled job-pair corresponds to a node in the
improvement graph. This is called a 1-node. In general a k-node is a
node in the improvement graph corresponding to k job-pairs. All
1-nodes are present in the improvement graph but only select subsets
of all k-nodes make it to the improvement graph. Because improvement
nodes correspond to scheduled job-pairs, it makes sense to talk
about a node's route. A node route in an improvement graph is just
the route in which its associated job-pair(s) is scheduled. There is
an edge between two nodes provided they are associated with different
routes. The edges are directed and are used to store two types of
weights, a path weight and a cycle weight. The cycle weight is
defined to be the change in the objective function when the job-pair
associated with the destination node is removed from its route and the
job-pair from the the source node is added to the destination route
(at the best possible location, using a greedy algorithm). Note that
the source job-pair is inserted into the destination route after the
destination job-pair is removed. The path weight is defined in
exactly the same way, except that the destination job-pair is not
removed from its route.
With these definitions, it is easy to see that a route-disjoint negative cycle in the improvement graph corresponds to a better schedule. The search for a negative cycle starts and ends at the same node; while this search is performed it is possible to make use of the path weight to find improvements that do not start and end at the same node. Therefore the search for improvements is reduced to finding route-disjoint negative paths and/or cycles in the improvement graph. Unfortunately, because of the route disjointness requirement, this problem is NP-hard. The algorithm we use to locate negative cycles is a considerable improvement of the method described in [1].
Our group 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 [42]. How to extend this approach to our routing and scheduling problems that have an on-line component is not immediately obvious. However, we believe further investigation on variations of this approach could lead to viable solution approaches. Investigating this will be another priority. It may be noted that ejection chain algorithms developed in the previous phase of this project could be viewed as a VLSN search algorithm.