需求可拆分的车辆路径问题的分段求解  

Two-stage Algorithm for Split Delivery Vehicle Routing Problem

作　　者：刘旺盛[1,2] 黄娟[1] 

机构地区：[1]集美大学航海学院,福建厦门361021 [2]厦门大学信息科学与技术学院,福建厦门361005

出　　处：《集美大学学报（自然科学版）》2011年第1期38-44,共7页Journal of Jimei University：Natural Science

基　　金：福建省自然科学基金项目(2010J01359)

摘　　要：将需求可拆分的车辆路径问题分成两阶段求解,针对单车场、单车型、无时间窗要求、纯装货或纯卸货情况,分别设计了先分组后路径及先路径后分组算法求解.通过实验表明,在成本上,先分组后路径求得的解好于先路径后分组求得的解,且比现有蚁群算法和禁忌搜索算法求得的成本更低,但先路径后分组的方法可以避免一个点的需求被拆分成两次以上满足,求解速度也更快.SDVRP was split into two stages to solve. In light of single-depot and single-type vehicle, with no time window, and with pure loading or discharge, two types of two-stage heuristic algorithm were de- signed, cluster-first-route-second method, and route-first-cluster-second method. Experiments showed that the solutions by the first method at cost were better than the second method, and than the existing ant colony algorithm and tabu search algorithm. However, the second method could save the demand of a demand point from being split into twice over to meet, and its speed of getting solutions was also faster.

关 键 词：车辆路径问题 需求可拆分 两阶段算法 先分组后路径 先路径后分组 

分 类 号：TP14[自动化与计算机技术—控制理论与控制工程]