Single-Vehicle Routing and Scheduling to Minimize the Number of Delays

In this paper we examine the following problem arising in vehicle routing and in production scheduling. Consider a single uncapacitated vehicle and n customers j with deadlines d_j. The objective is to minimize the number of deliveries completed after their deadline. This problem is NP-hard, but a class of solvable cases can be characterized. An integer linear programming formulation is proposed, and the problem is solved optimally by means of a specialized enumerative algorithm. Computational results are presented for problems involving up to 100 customers.