Galaxies can collide because the expansion of the universe is the expansion of space itself, not the movement of matter through space.
Local movement is independent of this overall expansion. The Andromeda galaxy is actually moving towards us.
The big bang was not like a normal explosion, in which fragments of a lump of matter are blown out. Rather, the big bang set space itself expanding.
A common cosmological analogy is to think of galaxies as paper dots on the surface of a balloon. As the balloon inflates, the galaxies move apart, because the very space between them grows.
In this analogy, it is the surface of the balloon, not the volume within, that represents the three-dimensional universe.
Galaxies may have their own trajectories across the surface of the balloon, pulled about by the gravity of other galaxies. This local movement is distinct from the expansion of space itself and means galaxies can collide.
The universe overall is expanding. But gravity makes sure not all matter is traveling away from the center. Look at the Earth as it orbits the sun.
Half our time is spent traveling away from the center of the universe, wherever or whatever that is, and the other half traveling back.