Agregar optgroups para seleccionar usando JavaScript dinámicamente

Tengo un cuadro de selección poblado dinámicamente (por ajax) con opciones resultantes como esa:

<select id="destination" name="destination">
<option value="london-paris">London-Paris</option>
<option value="paris-london">Paris-London</option>

<option value="london-newyork">London-New-York</option>
<option value="newyork-london">New-York-London</option>

<option value="london-berlin">London-Berlin</option>
<option value="berlin-london">Berlin-London</option>

<option value="london-helsinki">London-Helsinki</option>
<option value="helsinki-london">Helsinki-London</option>

... en realidad hay más de ellos pero no la esencia

Lo que quiero es agrupar cada una de estas dos porciones de opción por optgroup usando Javascript (quizás usando Jquery o Mootools) después de que se cargue la lista, de modo que antes de cada uno de este grupo, agreguemos una etiqueta optgroup con etiqueta que obtenemos de la segunda opción HTML del grupo (en realidad, la palabra antes del guión):

<select id="destination" name="destination">
<optgroup label="Paris">
<option value="london-paris">London-Paris</option>
<option value="paris-london">Paris-London</option>
</optgroup>
<optgroup label="New-York">
<option value="london-newyork">London-New-York</option>
<option value="newyork-london">New-York-London</option>
</optgroup>
<optgroup label="Berlin">
<option value="london-berlin">London-Berlin</option>
<option value="berlin-london">Berlin-London</option>
</optgroup>
<optgroup label="Helsinki">
<option value="london-helsinki">London-Helsinki</option>
<option value="helsinki-london">Helsinki-London</option>
</optgroup>
</select>

Sin embargo, siempre hay dos destinos en cada grupo.

Por favor, consejos sobre cómo implementar esto Gracias de antemano.