兼顾成本和失败概率的随机需求车辆路径问题模型及算法
随机需求的车辆路径问题是指确切知道顾客是否被服务,但不能获得其准确的需求量,而只知道其概率分布的一类车辆路径问题.大量的现实问题,如物流公司上门取货,押钞车上门取款等,都可以归为此类问题.本文首先分析了现有的带补偿的随机规划模型(SPR)和机会约束模型(CCP),指出前者可能导致路径成本小而失败概率较高,后者只考虑控制路线发生失败概率,而不计算其成本.随后,建立了能够兼顾路线失败概率和路线期望费用的机会约束的带补偿随机规划模型(CCSPR),并设计了一种禁忌搜索算法对模型进行求解.通过与现有SPR模型及CCP模型进行对比,发现CCSPR模型能够在兼顾路线成本的前提下降低路线失败的概率,提高整体服务水平.
车辆路径问题 机会约束规划 随机规划 禁忌搜索
张宏兵 戚铭尧 彭昕 缪立新
清华大学深圳研究生院
国内会议
北京
中文
462-469
2009-11-14（万方平台首次上网日期，不代表论文的发表时间）