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

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

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.