Detect DS18B20 sensors and correctly assign them to relays
If you can easily disconnect the sensors one at a time then your way is fine. 

If you can't easily disconnect them then you can maybe use readings to set the order, although this depends on the environment. If, for example, all the sensors are generally room temperature then you have the code check the temp of all the sensors at start up. If it finds one sensor at less than 0C then assign that sensor to the least-recently-replaced relay index (also stored in EEPROM). 

Then when you want to put a sensor into the working set, hold an ice cube on it for a few seconds before powering up the controller. There are other combinations of this technique you can imagine that use a button or jumper wires to specifically set the index of the out-of-range-at-startup sensor. 

Alternately if you have an extra pin on the Arduino, then you can make a procedure where you connect a new sensor to that pin before attaching it to the string. You can make a rule like "if you ever see a sensor on pin X then remember its device ID and assign it to relay Y". There are lots of UI ways to pick Y. Note that you do not even need any extra hardware for this.