This award will support collaboratiave research between Dr. Amedeo Odoni, Massachusetts Institute of Technology and Dr. Patrick Jaillet, Center for Applied Mathematics, Ecole Nationale des Ponts et Chaussees, Noisy-le-Grand, France. The topics of the proposed research are in the emerging field of jprobabilistic combinatorial optimization problems (PCOP's and in the new field of dynamic routing problems with queuing effects. The investigators, who have a history of successful collaboration, will focus on two areas. The first component consists of acontinuation of previous joint efforts in the following three areas: 1) worst-case analysis of heuristics for PCOP's 2) multi-server and multi-facility PCOP's and 3) routing problems with general distributions. The second component of the research will explore new directions and will demonstrate how the powerful concepts that have been developed to date regarding PCOP's can be used in such contexts as the optimization of queuing systems and the design of dynamic routing strategies. This type of connection has never been explored previously. The project will benefit from the complementary expertise of the two investigators. Their past efforts have already resulted in pioneering work on probabilistic combinatorial optimization problems which have generated international interest in this field. Results of the proposed project will have many applications in areas of materials handling and product distribution.
