车辆路径问题(VehicleRoutingProblem，简称VRP)是物流学中的一个重要研究领域，也是运筹学领域最近十年研究最活跃、发展最迅速的主题之一，于1959年由Dantzig和Ramser首次提出，一般定义为：对一系列发货点和收货点，组成适当的行车路径，使车辆有序的通过它们，在满足一定约束条件的情况下，达到一定的目标。VRP是NP难题。几十年来，这一问题引起运筹学、计算科学、图论和网络分析、随机过程等学科的专家和运输计划制定者和管理者的极大重视，进行了大量的理论研究和实验分析，取得了很大进展。 在实际生产生活中，不同的领域不同情况下人们对于目标的喜好有所不同，在今天这个高速运转的社会里，人们已经不满足于期望成本最小化，而将目标指向了期望系统时间最小化，最大程度的提高效率。Bertsimas和Ryzin最早以系统时间最小化作为目标研究随机动态VRP，本文在他们的研究基础上，研究了单车场、多车辆、具有随机需求量、以最小化系统时间的期望值为目标的随机动态车辆路径问题，推导出了系统时间期望的下界，为判断策略的优劣提供了一个时间指标。 第一章介绍VRP问题的研究背景、意义以及发展状况。 第二章介绍了VRP问题的定义和组成要素，给出了本文所具体研究的问题的抽象描述，并且对在本文中出现的一些符号进行了说明。 第三章讨论了无容量约束的具有随机需求量的随机动态VRP问题，推导出了无容量约束情况下系统时间期望的下界，分两类情况：交通畅通(LightTraffic)和交通密集(HeavyTraffic)。 第四章讨论了有容量约束的具有随机需求量的随机动态VRP问题，推导出了有容量约束情况下系统时间期望的下界，分两类情况：交通畅通(LightTraffic)和交通密集(HeavyTraffic)。 本文中的定理通过排队系统的稳定性条件得出系统时间期望的下界，这为分析运作策略的渐近性能提供了一个指标，将运作策略下系统时间与这个下界进行比较，可以指导物流管理中的策略选择。