路径长度受限的随机需求VRP的模型和算法  

Model and heuristic algorithm of vehicle routing problem for path length constraint stochastic demand

作　　者：刘浩[1] 钱小燕[1] 

机构地区：[1]南京工业大学理学院,江苏南京210009

出　　处：《南京工业大学学报（自然科学版）》2005年第3期36-38,共3页Journal of Nanjing Tech University(Natural Science Edition)

基　　金：航空基础科学基金(97J52091)

摘　　要：路径长度受限的随机需求VRP在生产、生活中有着广泛的应用。给出了路径长度受限的随机需求VRP问题的线性整数规划模型,在不允许部分服务和仅能服务失败一次的策略下设计了一个启发式算法。该算法以离散优化中广泛应用的扫描算法为基础生成服务的一个初始可行方案,然后利用模拟退火算法改进得到近似最优解。对需求为二项分布的50个结点、1个服务中心的问题进行了数值试验,数值结果表明该算法对求解路径长度受限的随机需求VRP是有效的。Vehicle Routing Problem is an important branch of Operations Research,and an NP-complete problem of combinatorial optimization. It is commonly useful in daily life. The vehicle routing problem in the case of stochastic demand with path length constraint was discussed . Under the strategy in which only one time routing failure and no part service exists, a simple algorithm is proposed. The approach is based on the sweep and the simulated annealing technique, which is widely used in discrete optimization. Numerical test with fifty nodes and one deport under the binary distribution was performed. A good result is obtained.

关 键 词：随机需求 路径长度 整数规划模型 VRP问题 启发式算法 近似最优解 可行方案 扫描算法 离散优化 算法改进 模拟退火 二项分布 数值试验 服务中心 数值结果 应用 结点 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] F253.4[自动化与计算机技术—计算机科学与技术]