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 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 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.
A route is a sequence of locations served by one vehicle. A route schedule consists of pairs of scheduled times for each of the locations in the route. The scheduled times of a route location are the scheduled arrival time at the location and the scheduled departure time from the location. A current solution of the dynamic PDPTW consists of a set of routes and their schedules.
All the three industrial problems are dynamic PDPTW problems. Our solution methodology for all the three problems of the industrial partners consists of first building feasible routes by an insertion-like procedure and then improving the routes when the time allows. Four algorithms have been adopted and implemented for solving the routing subproblem of the dynamic PDPTW:
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.
A neighborhood search procedure explores a neighborhood of a current
solution, and under certain conditions performs a move into one of the
neighboring solutions. This is the new current solution, and the
procedure continues in the same manner until a stopping criterion is
met. A neighborhood may be defined in many different ways.
We have chosen the neighborhood based on the concept of ejection
chains, where neighboring solutions of the current solutions are
built in the following way:
a request is taken from one route and moved to another route, thus
forcing a request from that route to move to yet another route, and so
on.
The chain may include each route at most once.
It may be of any length smaller than the number of routes, and it may
be cyclic or not.
Currently, we are working on generalizing the ejection chain method by
letting more than one job from a route to be ejected and moved to more
than one route.
Future plans
Our ongoing investigations, results obtained in the past and feedback received from our industrial partners culminated in interesting new challenges. The core of our future plan is to investigate these problems, that are fundamental in nature that interests the academic community and important to our partners.
Improving our solution algorithms and investigating the trade-off between computational efficiency and running time will be the primary focal point. Our research group is uniquely positioned to investigate this since we have up-to-date data from our partners on past deliverables along with the experience gained from the previous phase of the project.
Column generation approaches are routinely used in Vehicle routing literature. While this general philosophy is applicable in various routing and scheduling problems, the quality and efficiency of the approach depends on the ability to generate appropriate columns which in turn reduces to another optimization problem. Because of the additional restrictions in our applications and the context in which the column generation is used, a practically viable column generation method for our problems needs much more sophistication than straightforward adaptations of the method. We believe that various partial information generated in the search for improving columns could guide future searches for columns. Our preliminary investigation in this direction is very encouraging and it will be one of our active research area in this phase of project.
Very large scale neighborhood (VLSN) search algorithms are known to produce good solutions for various practical optimization problems [1]. Our group members are active 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 [48,49,51]. How to extend this approach to our routing and scheduling problems that has 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 our ejection chain algorithms developed in the previous phase of this project could viewed as a VLSN search algorithm.
Another direction we plan to investigate is how to solve some of the subproblems that we encountered in our heuristics by means of exact optimization algorithms such as branch and cut. For the primary problem, using an exact optimization technique is not desirable because, for our applications, quick computation of solutions that are reasonable good, gets priority. However, solving some of the subproblems to optimality could significantly improve solution quality at the cost of reasonable increase in running time. This part of the project requires thorough investigation of valid inequalities for various subproblems that we have identified.
Investigations of the problems discussed above necessitates development of new mathematical tools, clever applications of existing tools, and systematic experimentation. Continuous feed back from our industrial partners are also crucial to the success of the project. New industrial partners will be added to the project if a suitable match is identified.