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问题的启发式算法
为了克服精确算法的不足,可以运用一些经验法则来降低优化模型的数学精确程度,并通过模仿人的跟踪校正过程来求取运输系统的满意解,为此专家们主要把精力花在构造高质量的启发式算法上。启发式算法能同时满足详细描绘和求解问题的需要,较精确式算法更加实用。
目前己经提出的启发式算法很多,按照Cesar Reg的分类法,基本可以分为构造启发式算法(节约算法、最邻近法、插入法、扫描法)、两阶段启发式算法、不完全优化算法和智能化启发式算法(禁忌搜索算法、模拟退火法、遗传算法、神经网络算法、蚁群算法、微粒群算法等)四类。启发式算法中由Clarke 和Wright 在1964 年提出的节约法(简记为C-W算法)具有非常典型的代表性。
3 C-W算法的应用
3.1 定义与原理
C-W算法是根据物流中心的运输能力和物流中心到各送/ 取货点以及各个送/ 取货点之间的距离,制订使总的车辆运输吨公里数(或者时间或者费用)最小的方案。
C-W算法的基本思路如图1所示,已知P点为配送中心,它分别向用户A 和B送货。设P点到用户A 和用户B 的距离分别为a 和b。用户A 和用户B 之间的距离为c,现有两种送货方案,如图1(a)和(b)所示。
在图1(a)中配送距离为2(a+b);图1(b)中,配送距离为a+b+c。对比这两个方案,2(a+b)-(a+b+c)=a+b-c,很明显,由三角形的几何性质可知, 三角形中任意两条边的边长之和大于第三边的边长。即:a+b-c>0 。连接AB所得的节约量是a+b-c。
3.2 实例
为了使C-W算法体现较为明了,选取较典型的实例介绍。假设配送中心使用同类型的配送车(主要是装载量和容积相同),保证一条线路上各用户的货运量之和不大于车辆的载重量。
基本资料介绍:
现有6个用户(标号是1,…,6),各个用户的货运量是gi(吨)(i=1,…,6),这些用户由配送中心(标号是0)发出的载重量为8吨的车辆完成配送任务,要求最后的路线安排使总距离最小。具体数据见表1、表2。
首先,把各个点单独与配送中心相连,构建仅含一个点的初始路线,得到总的距离为:2*(40+60+75+90+200+100)=1130km
然后,连接两两用户到同一条线路上得到节约值(节约量公式a+b-c),节约值越大,说明两用户连在一起时运距减少的越多,如果是负值就不应该把两用户连在同一条线路上。
C-W算法解题步骤:
1)计算各用户之间的节约值(节约量公式a+b-c)
例如:连接用户1和用户2时,节约量=40+60-65=35
连接用户3和用户5时,节约量=75+200-50=225,类似可以得到其他,如表3。
2)按照从大到小的顺序排序,见表4。
表4 节约里程排序表
3)连接点对,见表5。
根据表,得到最后的路线安排如下:
0-3-5-6-0
0-1-2-4-0
比初始路线节约运距:230+225+50+35=540km
通过使用C-W算法,对配送线路进行组合以后,由原来的6条初始化线路,减少到2条组合线路, 运行距离从开始的1130km 缩短为590 km ,节约的里程相当可观。不难明白, 中国的物流行业是一座金山。只有不断进行物流管理和技术创新,提高物流效率, 才可能大幅降低整个业务成本。
参考文献:
[1] 李如姣.“节约里程法”在某物流公司配送中心的实际运用[J].科技咨询,2008(28):156-158.
[2] 方金城,张岐山.物流配送车辆路径问题(VRP)算法研究[J].徐州工程学院学报,2007(2):84-88.
[3] 朱晓兰,赵一飞.C-W 节约算法在装配企业采购物流中的应用[J].上海交通大学学报,2007(9):1420-1424.
[4] 吴清一.物流管理[M].北京:中国物资出版,2003:214-216.