If you twist the pairs of relay wires (twisted together quite tightly), or buy "twisted pairs" the noise is "injected into both wires in phase which, at the arduino end, effectively cancels out the noise. Fitting a 0.1 mF capacitor at the input terminal to ground will also reduce the noise level.
I would also suggest lowering the system impedance, say 1k from input terminal to ground and 1k from 5v to the relay feeder wire. The 1k in the feeder wire will also provide short circuit protection from the 5v source into the "field". You are now sensing from 0v to +2.5 volt
You would also benefit from a) rerouting the signal cables away from the power cables and b) using shielded cables with the shield connected at the arduino gnd terminal ONLY (tape up the remote end of the shield so that it cannot connect to earth at the machine (otherwise you will get serious ground loop noise currents)