>The indexes on the table are:
>
>PK (primary)
>location_id+depot_code+DTOC(delivery_date)+....

This won't necessarily affect your speed issues but look at DTOS() (date-to-string) for indexes instead of DTOC().

? DTOS(DATE()) && "20030605"

DTOS() is consistent whether you're using DMY or MDY, and always contains four digits for the year. It sorts nicely where DTOC() values don't.