I have a similar problem, just started my research and still haven't found an answer, but:
- there has been a recent post to the geoserver-dev list regarding an
ongoing GeoServer OpenLS services implementation
- the OpenRouteService states that "soon we will also make the
route service available as OGC-web service, that can be used through
http-based xml-requestes as specified in the OGC OpenLS Route
Service specification. This will allow developers to use this
servide in an open and interoperable way easily within their own
applications." However, source code doesn't seem to be publicly available.
- the OpenLayers OpenLS example (at the OpenLayers site) is using the above mentioned OpenRouteService.
- if OpenLS compliance is not a strict requirement, you might use Nominatim.
Anyhow, in either case I don't think you'll be able to use an OSM shapefile to support your service: a PostgreSQL+PostGIS+pgRouting database will most certainly be required.