摘要
VRP问题是运筹学的一个重要分支 ,是组合优化的一个 NP难题 ,在日常生活中应用广泛。本文讨论了单类型车辆随机需求 VRP问题 ,在路由仅能失败一次和不允许部分服务的策略下首先给出了一个快速扫描模拟退火算法 ,该算法操作方便 ,考虑了各需求结点的几何位置 ,然后对需求满足二项分布的 VRP问题作了策略分析 ,得到了在我们的策略下的一些理论结果 ,最后对需求为二项分布的五十个结点、一个服务中心的问题作了数值试验 ,数值结果表明该算法对求解单类型车辆随机需求 VRP是有效的。
Vehicle routing Problem is an important branch of operation research,is an NP hard problem of combinatorial optimization,It is commonly useful in daily life.In this paper,we discuss the vehicle routing problem with one type of vehicle in the case of stochastic demand.Under the strategy that there is only one time of routing failure and no part service,we give a fast scanning simulated annealing algorithm which is easy to accomplish and concerning about the geometric position Then we introduce the analysis of the strategy under binomial distribution,at last we have done the digital experiment which has fifty nodes and one depot.The numeral result appoves that is a better result.
出处
《南京建筑工程学院学报》
2001年第4期25-29,共5页
Journal of Nanjing Architectural and Civil Engineering Institute(Natural Science)
基金
航空基础科学基金(97J52 0 91 )
关键词
运筹学
VRP问题
随机需求
模拟退火
车辆
operation research
vehicle routing problem
stochastic demand
simulated annealing
routing failure
