配送是物流系统中很重要的一个环节。在物流的各项成本中,配送成本占了相当高的比例。配送线路合理与否对配送速度、成本、效益影响很大,特别是多用户配送线路的确定更为复杂。因此,车辆路径问题(Vehicle Routing Problem,简记VRP)成为众多学者竞相研究的热门话题。在高度发展的商业社会中,消费者对时间的要求越来越严格,以往的到货“日”已转换成到货“时”。特别是随着Internet的普及,电子商务以及其他信息技术和信息服务的研究和发展,在现代的商务及企业管理过程中,滞后的物流供应管理成为一个亟待解决的问题,如何通过合理规划配送车辆路线,降低配送成本,来满足消费者日益多变的需求,吸引了企业决策者和理论研究者们的普遍关注。 车辆路径问题是配送系统中的核心问题,也是研究热点之一。路径安排合理能有效提高运输效率、降低服务成本。随着商品运输呈现出小批量、多品种、多频次、及时性等趋势,运输路径的优化更加复杂。 本文首先分析了目前车辆路径问题的研究现状,再结合实际提出了本文的研究问题——带软时间窗的车辆路径问题(VRPSTW)。通过对VRPSTW的数学建模,明确定义了问题的目标函数及约束条件,在比较了多种求解方法后,作者采用扫描法、并行遗传算法求解VRPSTW,其求解过程为:首先采用扫描法生成问题的一个初始解,然后采用遗传算法对初始解进行优化,得到一个最优或近似最优解。在用遗传算法优化初始解的过程中,针对本文研究问题的特点,作者设计了遗传编码、适应度函数以及遗传操作策略。因为遗传算法本身存在易“早熟收敛"的缺陷,所以在计算过程中还设计了并行策略,采用多个并行体同时计算,然后让各并行体间进行信息交换,有效的克服了遗传算法潜在的早熟现象,改善了遗传算法求解的性能,同时还加快了计算的速度。 最后根据提出的求解VRPSTW的方法用VC++编程在计算机上实现。计算结果表明了这种遗传算法解决此类问题的有效性。