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

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

路径长度受限的随机需求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.