Horizontal Cooperation in Dial-a-Ride Services

Abstract

A dial-a-ride system is an application of demand-dependent, collective people transportation. Each user requests a trip between an origin and a destination of choice, to which a number of service level requirements are linked. The service provider attempts to develop efficient vehicle routes and time schedules, respecting these requirements and the technical constraints of a pickup and delivery problem. A frequent objective is to minimize operational costs subject to full demand satisfaction and side constraints, but service level criteria may be optimized as well. Balancing the human and economic perspectives involved in solving such a Dial-a-Ride Problem (DARP) is essential for organizing quality-oriented, yet efficient transportation of users with special needs, such as door-to-door transportation for elderly and disabled. In light of the ageing population, dial-a-ride systems are gaining importance to complement regular transportation modes. They also fulfill a social role, preventing isolation of vulnerable groups in society.

The current practice consists in that users choose a particular service provider to submit their request. If multiple providers operate in the same area, they solve separate routing problems based on the requests they received. However, research related to freight transportation shows that horizontal cooperation between carriers may allow them to obtain joint operational benefits. The aim of the present research is to determine whether these findings also apply to passenger transportation, which is characterized by tighter quality requirements. Horizontal cooperation may be established in two distinct manners. On the one hand, service providers may exchange requests that are difficult to serve in their own routes. This implies that vehicle routes are optimized from a more global point of view. On the other hand, service providers may achieve additional savings through a reallocation of vehicles among their depots. If reviewing this decision on a daily basis is impracticable, the best allocation can be determined in the medium term based on the distribution of requests.

To account for the presence of several providers, a multi-depot variant of the DARP is adopted. Horizontal cooperation is modeled through the possibility of exchanging requests and/or vehicles among these depots. Computational tests are carried out using a new large neighborhood search (LNS) algorithm, which efficiently solves the problem variant under consideration. Different data sets are used, ranging from artificial benchmark instances to data with real-life characteristics, such as clustered requests. The results show that both types of horizontal cooperation cause considerable reductions in the (joint) distance traveled, as well as in the required fleet size. The magnitude of the operational savings depends on the service level offered. Besides, a pattern can be observed in the choice of which requests are exchanged among the service providers. These results provide support for the creation of an overarching body which collects all user requests in a certain area, after which a globally optimal route planning can be constructed. Anyway, the service providers involved should make clear agreements regarding the allocation of costs and revenues.