Profits in the Dial-a-Ride Problem

Established demand-responsive transportation systems provide customized door-to-door transportation services, such as dial-a-ride services. Unfortunately, these services are only available to a limited number of users, which represents a drawback. A higher contribution to mobility-as-a-service solutions could be achieved. In this research, common practices are slightly modified. First, the user offers a price for the transportation service to be provided, which is constrained by budgetary considerations. Second, if the user determines the price to be paid, there is no obligation for the service provider to accept the raised requests, despite moral concerns. Accordingly, the operator collects all relevant requests for a planning horizon and makes a decision as to which of the requests will be served (and which will be rejected). Revenue is realized if the transport request is fulfilled, while rejection of requests is free of charge. The decision situation is highly dependent on the perspective and goals of the service provider, and thus different backgrounds are taken into account. However, request selectivity violates an essential assumption of dial-a-ride problems and leads to selective dial-a-ride problems. Profits, which have received little attention, are taken into account. A literature review on profits applied in selective pickup and delivery problems and selective dial-a-ride problems follows. A more formal problem definition is outlined, and parameterizable programs are presented. Advanced reformulation and tightening techniques are applied and a tabu search heuristic is presented, which is able to cope with three variants. Computational results are reported and conclusions are drawn.