The vehicle routing problem (VRP) is an attractive topic in logistics research work. Multi-vehicle routing problem with time window (MVRTW) is a variant of VRP, which accommodates realistic system specifics such as capacity of multi-vehicle, time constraint and network constraint (one-way, banning of turning movement etc.). To solve the MVRPTW, an improved approach combining geographical information system (GIS) with parallel genetic algorithm (PGA) is proposed. Shortest paths could be calculated by spatial analysis module and topology construction of road network in GIS. In order to strengthen the search ability, an adaptive generation mechanism of the initial population and the evolutionary operators are used in PGA. The suggested approach proved to be efficient by a practical case of Changchun City.