C-W算法在配送车辆优化调度中的应用.doc

C-W算法在配送车辆优化调度中的应用 　　摘要:物流配送车辆优化调度是物流配送中非常关键的一个环节。文章简单介绍了当前最具有代表性的算法, 指出目前启发式算法是求解车辆路径问题的主要方法,并以C-W算法为典型,结合实例验证了其对解决配送车辆调度问题的适用性。 　　关键词:C-W算法;配送车辆优化调度;启发式算法 　　中图分类号:TP312文献标识码:A文章编号:1009-3044(2010)09-2132-02 　　Application of C-W Algorithm in Logistics Distribution Vehicle Scheduling 　　CAO Jing-xia1,2 　　(1.School of Information Engineering, Jiangnan University, Wuxi 2141222, China; 2.Jiangyin Polytechnic College, Jiangyin 214400, China) 　　Abstract: Logistics Distribution Vehicle Scheduling is a very crucial step in the process of logistic distribution. This paper briefly describes the most representative algorithm, points out that the heuristic algorithm is the main method to solve vehicle routing problem, and demonstrates its applicability to solving the problem of vehicle scheduling by citing the examples of C-W algorithm, a typical method among the heuristic algorithm. 　　Key words: C-W algorithm; delivery vehicle scheduling; heuristic algorithm 　　随着我国市场经济的建立和发展,作为“第三利润源泉”的物流日益受到政府有关部门和广大企业的重视,成为当前最重要的竞争领域。配送是物流活动中直接与消费者相连的环节,在物流的各项成本中,配送成本占了相当高的比例。配送车辆调度的合理与否对配送速度、成本、效益影响很大,采用科学、合理的方法来进行配送车辆调度,是物流配送中非常关键的一环。 　　1 物流配送车辆路径问题(VRP) 概述 　　物流配送车辆路径问题(Vehicle Routing Problem ,VRP) 最早是由Dantzig 和Ramser于1959年提出的,一经提出立即引起了运筹学、物流科学、计算机应用等学科专家和运输问题制定和管理者的极大关注。 　　该问题的研究目标是对一系列的顾客需求点设计适当的路线,使车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下, 达到一定的优化目标(如里程最短、费用最少、时间尽量少、车队规模尽量小、车辆利用率尽量高等)。 　　2 VRP问题的求解算法 　　VRP问题是组合优化领域著名的NP难题之一,即随着客户数量的增加,可选的配送路径方案数量将以指数速度急剧增长,即出现组合爆炸现象,因此通常的做法就是应用相关技术将问题分解或者转化为一个或者多个已经研究过的基本问题,再使用相对比较成熟的基本理论和方法求解。VRP问题的求解方法基本上可以分为精确算法和启发式算法两大类。 　　2.1 求解VRP问题的精确算法 　　求解VRP问题的精确算法主要运用线性规划、整数规划、非线性规划等数学规划技术来描述物流系统的数量关系,以便求得最优解。求解VRP问题常用的精确算法有分枝定界法、割平面法、动态规划法、网络流算法等。这些方法从理论上给出了VRP问题精确求法,在可以求解的情况下,其解通常要优于启发式算法。由于精确算法在求解时引入了严格的数学方法(手段),因而无法避开指数爆炸问题,使其获得整个系统的最优解越来越困难,因此,这些算法都是针对某一特定问题设计的, 适用能力较差, 在实际中其应用范围很有限。 　　2.2 求解VRP问题的启发式算法 　　为了克服精确算法的不足,可以运用一些经验法则来降低优化模型的数学精确程度,并通过模仿人的跟踪校正过程来求取运输系统的满意解,为此专家们主要把精力花在构造高质量的启发式算法上。启发式算法能同时满足详细描绘和求解问题的需要,较精确