Research Initiation Award: Optimal On-Line Policies for Dynamic and Stochastic Vehicle Routing and Related Problems

9309579帕帕斯塔夫鲁现实世界车辆路径问题的特点是关于未来客户和旅行时间的不准确或未知信息，不断变化的计划视野，排队考虑，重新排序和重新分配决策，以及包括等待时间和交付成本在内的各种性能标准。然而，经典的车辆路径模型是静态的，假设完全了解需求，忽略了排队效应，通常只考虑出行成本。直到最近，才有新的方法被研究，既考虑了问题的动态方面，也考虑了问题的随机方面。研究人员将结合运筹学、随机学和组合学两个领域的技术，分析各种随机和动态(主要是车辆路径)问题；这些问题比传统的确定性问题更适用。研究结果表明，该模型不仅可用于交通规划，还可用于其他以拥堵影响为主的问题，包括调度问题、装箱问题、设施选址问题以及计算机科学中一类特殊的信息检索问题。

9309579 Papastavrou Real-world vehicle routing problems are characterized by imprecise or unknown information about future customers and travel times, constantly changing planning horizons, queuing considerations, resequencing and reassignment decisions, and a variety of performance criteria that include waiting time and delivery costs. However, classical vehicle routing models are static, assume perfect knowledge of demands, ignore queuing effects and typically only consider travel costs. Only recently, have new approaches been investigated, taking into consideration both the dynamic and the stochastic aspects of the problems. The researchers will combine techniques from both areas of operations research, stochastics and combinatorics, to analyze a variety of stochastic and dynamic (mainly vehicle routing) problems; these problems are more applicable than their traditional deterministic counterparts. Research results will demonstrate that the models will not only be useful for transportation planning, but also for other classes of problems where congestion effects dominate; these include scheduling problems, bin-packing problems, facility location problems, and a special class of information retrieval problems in computer science.