摘要：随机需求的车辆路径问题是指确切知道顾客是否被服务，但不能获得其准确的需求量，而只知道其概率分布的一类车辆路径问题。大量的现实问题，如物流公司上门取货，押钞车上门取款等，都可以归为此类问题。本文首先分析了现有的带补偿的随机规划模型（SPR）和机会约束模型（CCP），指出前者可能导致路径成本小而失败概率较高，后者只考虑控制路线发生失败概率，而不计算其成本。随后，建立了能够兼顾路线失败概率和路线期望费用的机会约束的带补偿随机规划模型（CCSPR），并设计了一种禁忌搜索算法对模型进行求解。通过与现有SPR模型及CCP模型进行对比，发现CCSPR模型能够在兼顾路线成本的前提下降低路线失败的概率，提高整体服务水平。

关键词：车辆路径问题 机会约束规划 随机规划 禁忌搜索

1.       引言

    确定性的车辆路径问题（Vehicle Routing Problem，VRP）是在顾客需求已知且不会发生改变的情况下，规划一条或多条车辆路径，使得服务所有顾客所需的行驶总里程（或时间、费用）最小。然而在现实生活中，大量情况下顾客需求在路径规划前是未知的，例如银行押钞车上门取款、物流公司上门揽货等等。尽管这类需求信息不能事先准确获得，但是根据历史数据可以得到其统计规律，从而估计其概率分布。针对这种情况，随机需求量车辆路径问题(Vehicle Routing Problems with Stochastic Demands，VRPSD)常被用来解决这类问题。