Impact of soft ride time constraints on the complexity of scheduling in Dial-A-Ride problems

The Dial-a-Ride problem can contain various constraints for pickup-delivery requests, such as time windows and ride time constraints. Given a tour as a sequence of pickups and deliveries, there exist polynomial time algorithms to find a schedule respecting these constraints (provided that there exists one). However, if no such schedule exists, it is natural to ask for a schedule minimising constraint violations. We model a generic fixed-sequence scheduling problem, which we call Min Pickup-Delivery Scheduling, that allows violation of time window constraints (by late visits) and ride time constraints, both penalised with linear penalty functions. Although our model only considers these two types of time constraints, we show that it can express other common time constraints such as earliness and waiting times. We prove that Min Pickup-Delivery Scheduling is APX-hard, even in the very restrictive case where only the ride time constraints can be violated and the time windows have the same length. Conversely, when only the time window constraints can be violated (by late visits), we present a polynomial time algorithm to solve the problem. Then we focus on instances with some specific structural properties and present two polynomial-time algorithms: one for the case where all the ride time constraints are bounded by a constant, and a second one for the case where all the pickups precede all the deliveries in the sequence of stops.