Minimum Collaboration in Dial-a-Ride Problems with Additional Services

The integration of supplementary services, a circumstance that has been researched in the previous chapter, may be hindered by the lack of cooperation of the dial-a-ride provider. In conclusion, there is no safety for the partner who requests the support that at least some services will be accepted. There remains some uncertainty for the requesting partner with regard to the decision-making process. To mitigate this uncertainty in the collaboration, a prize-collecting dial-a-ride problem with additional services is investigated, which safeguards the fundamental principles of the framework. On the one hand, the dial-a-ride provider is obliged to fulfill a minimum threshold. In conclusion, imposing this threshold ensures a certain commitment of the dial-a-ride provider to accept a set of supplementary services. Conversely, the health care provider is obliged to assign a rating to each request, which could also be understood as revenue from the perspective of the dial-a-ride provider. In summary, these two obligations introduce some more reliability into the planned collaboration. Any accepted request decreases the remaining budget for the acceptance of the other requests made accordingly. Consequently, the health care provider has to evaluate wisely. Furthermore, it should be noted that this evaluation process introduces additional complexity for the dial-a-ride provider in identifying a solution. The number of additional jobs may vary in order to exceed the minimum level of collaboration threshold. This chapter outlines related literature and a more formal problem statement. A program is proposed using insights obtained from previous studies. Afterward, a variable neighborhood search heuristic is presented due to the computational limits for the exact algorithms. A summary of the computational results for both exact and heuristic methods is presented before concluding with findings and suggestions for future research directions.