Stochastic stay times for interrelated trips in the rural dial-a-ride problem

This paper presents a stochastic version of the dial-a-ride problem with interrelated trips. Interrelated trips refer to transportation requests where travelers need to arrive at meeting locations simultaneously or where round trips involve a specific amount of time spent at destination locations, such as for medical consultations. In this variant of the problem, the durations of the travelers’ stays are considered to be stochastic. Traveler lateness is incredibly challenging in such interrelated transportation schedules because delays can propagate across different vehicles. This is especially relevant for rural dial-a-ride systems, where travelers are restricted to a small choice of transportation services. A purposeful decision making is therefore required to orchestrate the service operations of such vehicle fleets. Hence, we look at smart ways how to enhance the reliability and attractiveness of these systems. Our approach involves a careful examination of how to approximate the distributions of the arrival and service start times of the vehicles at each customer location. To create more reliable schedules, we utilize a chance constraint and incorporate it together with enhanced feasibility checks into an Adaptive Variable Neighborhood Search metaheuristic. The obtained solutions are evaluated in a simulation environment. Through computational experiments, we explore the balance between operational costs and service reliability, as well as the effects of various service policies for managing delayed travelers (e.g., wait or go at meeting requests) on punctuality at subsequent locations.’ • We consider a dial-a-ride problem where users’ stay times at locations are uncertain. • We thoroughly compute the arrival time distributions of vehicles at each location. • We use chance constraints in an adaptive variable neighborhood search heuristic. • We analyze the trade-off between operational costs and service reliability.