Abstract
This paper presents a novel approach to solving the single-vehicle pickup and delivery problem with time windows and capacity constraints (or single-vehicle PDPTW). While dynamic programming has been used to find the optimal routing to a given problem, it requires time exponential in the number of tasks. Therefore, it often fails to find the solutions under real-time conditions in an automated factory. This research explores anytime problem solving using genetic algorithms. By utilizing optimal but possibly partial solutions from dynamic programming, the hybrid genetic algorithms can produce near-optimal solutions for problems of sizes up to 25 percent bigger than what can be solved previously. This paper reports the experimental results of the proposed hybrid approach with four different crossover operators as well as three mutation operators. The experiments demonstrated the advantages of the hybrid approach with respect to dynamic task requests.
| Original language | English |
|---|---|
| Pages (from-to) | 453-458 |
| Number of pages | 6 |
| Journal | Proceedings - IEEE International Conference on Robotics and Automation |
| Volume | 1 |
| State | Published - 1999 |
| Externally published | Yes |
| Event | Proceedings of the 1999 IEEE International Conference on Robotics and Automation, ICRA99 - Detroit, MI, USA Duration: 10 05 1999 → 15 05 1999 |