73 / 2024-04-19 08:05:05

A selective dial-a-ride problem with mean-variance risk index under uncertain travel time

Dial-a-ride, service requirement, mean-variance risk index, uncertain travel time

Problem definition: Motivated by real challenges faced by a non-emergency medical transportation service provider, we study a selective dial-a-ride problem with uncertain travel time and aim to optimize the service coverage subject to some service quality requirements. Methodology/results: To manage violations of service requirements, we introduce a mean-variance risk index. This index effectively controls both the likelihood and magnitude of such violations. Furthermore, it enables the development of practical optimization models. We construct a collective risk model specifically for dial-a-ride optimization and devise efficient branch-and-price-and-cut algorithms to handle the resulting nonlinear integer programs. To verify the efficiency of our proposed models and algorithm, we perform comprehensive experiments using both synthetic and real data. Managerial implications: Much of the dial-a-ride literature focuses on deterministic travel times. We highlight the importance of considering uncertain travel times. We have developed practical models and algorithms for non-emergency medical transportation. Our approach has proven to lead to a greater number of served requests with improved quality. As such, we demonstrate the practical value of advanced optimization techniques when dealing with real-world uncertainty.