Četvrtak, 26. jul 2005. u 14h, sala 2, MI SANU BG:

Dr. Maurizio Bruglieri, DEI, Politecnico di Milano, Italy
A PARTICULAR VEHICLE ROUTING PROBLEM ARISING IN THE COLLECTION AND DELIVERY OF SPECIAL WASTE

Abstract: We consider the collection of recyclable waste, where some collection points are located in the city suburbs or at some other strategic sites. Several containers are present at each collection point, one for each type of collected waste material. Containers can be of different type. Users bring their waste and dispose it into the appropriate container. Once a container is full, a disposal request is issued, consisting of the following two actions, to be carried out not necessarily in this order:
i) the full container is brought to a disposal plant to be emptied;
ii) an empty container of the same kind is brought to the collection point.
A fleet of homogeneous vehicles and additional empty containers are available at the depot. Each vehicle can carry a single container at a time, either empty or full. Given a set of service requests, the aim is to determine vehicle routes starting and ending at the depot involving pick-up of full containers at collection points, dumping operations at appropriate disposal plants, delivery of empty containers, while minimizing both the number of vehicles and the global traveled time. The problem can be seen as a particular Asymmetric Vehicle Routing Problem on a suitable graph whose peculiar structure suggests several types of neighborhood. In the present work we exploit these neighborhoods within both a GRASP and a Tabu Search framework, starting from a solution yielded by a modified Clarke and Wright algorithm. We compare the results of the two methods.

Četvrtak, 28. jul 2004. u 15h, sala 2, MI SANU:

Dr. Leo Liberti, DEI, Politecnico di Milano, Italy
COMPACT LINEARIZATION OF BILINEAR PRODUCTS IN 0-1 PROGRAMMING PROBLEMS WITH ASSIGNMENT CONSTRAINTS

We present a compact linearization for a broad class of bilinear 0-1 mixed-integer problems subject to assignment constraints (the idea is based on the concept of "reduction constraint", presented in full generality last year in a seminar at SANU). We apply the linearization to three classes of problems: quadratic assignment, multiprocessor scheduling with communication delays, and graph partitioning, and show that it yields faster solution times.