Ci sono alcune cose inappropriate e che non vanno.

1) Non è di per sé sbagliato avere quel metodo statico che fornisce il VeicoliComparator (sebbene non ce n'è davvero bisogno). La cosa che non va è la parametrizzazione ad Object in Comparator<Object> . Come minimo avrebbe più senso Comparator<Veicolo>

2) v.equals(null) NON ha senso. Restituisce sempre false, è una specifica di equals! Se vuoi testare per uguale a null, allora v == null


Riguardo il cicla(), la questione richiede delle scelte. La lista elencoVeicoli non è già ordinata per efficienza. Con il addVeicolo puoi aggiungere veicoli nell'ordine che ti pare e quest'ordine è poi quello nella lista.
Ora:
a) nel cicla() fai una copia della lista (così non tocchi quella di Concessionario), ordini la lista-copia per efficienza e quindi la scorri con il for-each

oppure

b) La lista elencoVeicoli di Concessionario la tieni e mantieni ordinata per efficienza ad ogni veicolo aggiunto, tramite il concetto del "binary search". Così la lista è già ordinata e in cicla() la scorri subito.