摘要: 针对随机动态装卸混合问题中存在的排队现象，运用排队论推导出需求稀少情况下随机动态装卸混合问题期望系统时间的下界；提出了一种实时优化策略——多车场随机队列中位策略；推导出需求稀少情况下，多车场随机队列中位策略和实际应用中广泛采用的随机队列中位策略的期望系统时间，并分析了期望系统时间的渐近性。模拟计算结果表明，需求稀少情况下，多车场随机队列中位策略明显优于随机队列中位策略；当需求强度趋于零时，多车场随机队列中位策略近似为最优策略。

关键词：动态车辆路径问题；随机车辆路径问题；排队论；装卸混合问题

0　引　言

车辆路径问题（vehicle routing problem， VRP）方面的研究在过去四五十年里取得了丰富的成果^[1][2]。不过，已有研究主要针对静态、确定的环境，即假定进行车辆路径优化时，所有的信息（包括与顾客有关的信息，如顾客的地理位置、顾客的需求量、顾客发出请求服务的时间、现场服务时间等；与车辆旅行有关的信息，如车辆的旅行速度、道路信息等）均已知，且在实施过程中，不再发生变化。这类问题称为静态车辆路径问题。然而，在车辆路径问题的大部分实际应用中，各种信息往往呈现随机性和动态性，即在进行车辆路径优化时，并非所有的信息都已知；有的信息在实施过程中才出现；部分已知信息在实施过程中将发生变化等。这类问题称为随机动态车辆路径问题。随机动态车辆路径问题的实际例子有旅行修理工、邮件快递服务、民用燃料油供应、动态拨召车辆问题（dial-a-ride）、出租车服务、紧急服务等^[3]。由于更接近现实，自Psaraftis^[4]提出“动态车辆路径问题”以来，随机动态车辆路径问题引起了越来越多的关注，逐渐成为研究热点。

    求解随机动态车辆路径问题，最直接的方法是每当有新的信息出现，或信息有变化时，就重新进行优化。但Bertsimas等^[5]研究表明，即便有足够的计算资源可供使用，这种重新优化的解决方法仍将遇到困难。这是因为多次优化将导致优化的时间消耗太长。因此，目前已有的求解随机动态车辆路径问题的策略有两种：一种是预优化策略，一种是实时优化策略。后一种策略是根据随机动态车辆路径问题中存在类似排队的现象，利用排队论来研究随机动态车辆路径问题。Psaraftis^[4]以最小化期望系统等待时间为目标，研究了动态旅行商问题的实时优化策略。Bertsimas等^[6]以最小化期望系统时间（系统时间包括系统等待时间和现场服务时间）为目标，研究了需求密集和需求稀少两种情形下，动态修理工问题期望系统时间的下界，提出了几种实时优化策略，对各种策略进行渐近性分析，分析了不同策略在不同需求强度下的表现。Bertsimas等^[7]在文献[6]的基础上，将研究对象推广至更为一般的情形，具体包括系统中服务车辆由一辆推广至多辆，车场由一个推广至多个，目标函数由最小化期望系统时间推广到最小化期望系统时间和平均旅行成本的混合函数；同时，推导出需求密集和需求稀少两种情形下，该问题期望系统时间的下界；提出了一些实时优化策略，并对各种策略进行渐近性分析。