Abstract—This paper proposes a new Parallel Hybrid Genetic Algorithm approach for Vehicle Routing Problem with Time Windows. The algorithm was developed to be executed on cloud computing web services and serves as an online application for real world problems. A new parallel scheme was proposed with shared resources of candidate solutions accessed by many asynchronous tasks. The algorithm was tested over the classical well-known benchmark and presented excellent results for some instances in a low computational time. The algorithm reaches the best-known solutions for many instances and found high competitive solutions. The excellent performance of the proposed approach indicates its potential to be applied in real world applications, running on cloud computing servers. ”