We consider the problem of deploying a connected car, capable of V2X communication, to propagate data to groups of evacuation shelters that have lost mobile network connectivity. The problem is a combination of two subproblems: first of finding the optimal order in which the destinations should be visited, and second of finding the optimal path in a road network that allows a connected car to deliver information to all prescribed shelters. We develop a genetic algorithm with double chromosome encoding to simultaneously solve both subproblems. One chromosome encodes the solution to the routing problem, the other to the path-planning problem. Experimental results demonstrate that our algorithm is capable of finding the optimal solution with reasonable accuracy and precision.