DTI - Universita' degli Studi di Milano
October 29, 2007, 14:15, Room GC B3 424 (click here for the map)
Due to their practical relevance, vehicle routing problems received a particular interest in the operations research during the last decades. In its simplest version, the problem consists in routing a fleet of vehicles in order to deliver goods to a set of customers, minimizing the operating costs. Several important variants have been addressed in the literature, commonly modeling capacities on the vehicles. While in all these variants it is assumed that each customer must be served by exactly one vehicle, relevant savings can be achieved by allowing multiple visits to each customer, each serving only a fraction of its demand. In this talk we describe the so-called Vehicle Routing Problem with Split Deliveries, which is by far less studied and understood than the classical one. We discuss its properties, we outline the main issues arising in the solution process and we present a modeling and algorithmic framework based on column generation. Finally, since the aim of the talk is to sketch our research directions, we discuss related open problems.