Design, Operations, & Production Systems Lab (DeOPSys) |
2003 - 2010, Phd Thesis Title:Real-Time Vehicle Routing: The Cases of Vehicle Delay and Vehicle Breakdown |
C.V. ( Greek Version English Version) |
My research focuses on real time management of a delayed/immobilized delivery vehicle in city logistics. We define the three following operational research problems and we propose ways to solve them.
1. A delivery vehicle delays and thus, cannot serve all its clients in its initial preplanned route. This resembles the Orienteering Problem which is a known OR problem.
2. A delivery vehicle, member of a vehicle fleet, fails and thus cannot serve any remaining clients of its initial preplanned route.
The 1st problem is a single vehicle re-planning problem and is modeled based on the formulation of the well known orienteering problem (OP). A novel approach is proposed to provide an efficient, near-optimal solution. This approach decomposes the problem into smaller sub-problems, taking advantage of the geographical distribution of clients into clusters (neighborhoods and/or suburbs). The available vehicle time is distributed to each cluster by solving a non-linear optimization problem. Within each cluster an established OP heuristic is used to determine the clients to be served and the vehicle route.
The 2nd problem deals with situations in which an unexpected event immobilizes a vehicle of a distribution fleet and the initial client set of the vehicle should be served by other vehicles of the fleet. We model this problem as a Team Orienteering Problem, constraining all tours to an upper time or length limit. The problem usually requires an effective solution within a very restrictive time fraction. We propose an effective heuristic to provide efficient solutions to this problem. To test the quality of the solutions obtained we use a Genetic Algorithm to determine high quality solutions and compare to the ones obtained from the heuristic.