Dynamic vehicle routing using hybrid genetic algorithms

Wan rong Jih*, Jane Yung jen Hsu

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

52 Scopus citations

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 languageEnglish
Pages (from-to)453-458
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
Volume1
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1999 IEEE International Conference on Robotics and Automation, ICRA99 - Detroit, MI, USA
Duration: 10 05 199915 05 1999

Fingerprint

Dive into the research topics of 'Dynamic vehicle routing using hybrid genetic algorithms'. Together they form a unique fingerprint.

Cite this