SINGLE-VEHICLE ROUTING AND SCHEDULING TO MINIMIZE THE NUMBER OF DELAYS

In, this paper we examine the following problem arising in vehicle rou ting and in production scheduling. Consider a single uncapacitated veh icle and n customers j with deadlines d(j). The objective is to minimi ze the number of deliveries completed after their deadline. This probl em is NP-hard, but a class of solvable cases cart be characterized. An integer linear programming formulation is proposed, and the problem i s solved optimally by means of a specialized enumerative algorithm. Co mputational results are presented for problems involving up to 100 cus tomers.