C-W启发式算法

2024-06-12

C-W启发式算法（共3篇）

C-W启发式算法篇1

0 引言

制造业的激烈竞争,使Just in Time(JIT)的采购方式受到越来越多的企业的关注,这种源自于日本丰田汽车公司准时制生产的采购方式,要求既要能保证物资的供应,又要降低库存量、缩短订货提前期、提高产品质量、降低采购成本。在这种采购方式下,车辆的提早或延迟到达原材料供应地均会产生附加成本。因此制造企业在制定其生产调度和运输调度策略时,必须从全局出发,考虑供应链整体动作成本最小化。作为整个供应链中的一环,在进行车辆的运输调度时,必须考虑与生产之间的有效衔接。

受到外资第三方物流公司大举进入中国的影响,近年来,我国的物流企业有了较大的发展,第三方物流(Third Party Logistics,3PL)日益成熟,相当数量的制造商开始有选择性的将物流业务外包给3PL以有效衔接生产、提高JIT采购水平、降低采购成本。研究表明,供应链中第三方物流运输调度问题主要分为两类:生产企业主导和3PL主导[1]。

目前研究多关注第一种3PL运输调度问题。Ruiz Torres和Tyworth(1997)[2]用仿真模型测试了一些简单的调度法则,证明在生产和运输中采用恰当的调度法则可使整个系统的效率大大提高。Chang和Lee(2001)[3]的研究目标是最小化所有作业的生产和运输总时间。Garcia et al.(2004)[4]考虑多生产工厂的系统,目标是决定最优的订单至车辆的装载,使系统利润最大化。但在最终模型求解的过程中,由于精确算法(包括直接树搜索算法、动态规划法和整数线性规划法三类)只能有效求解中小规模的确定性问题,当求解大规模问题时,无法在有限时间里找到满意的次优解或可行解。因此,在实际应用中,人工智能算法应用更广泛。

1 C-W节约算法研究与改进

Clarke和Wright在1964年提出的节约法(简称为C-W算法)是启发式算法中的一种,用来解决车辆数不固定的运输调度问题[5]。由于算法的简单实用,又能很容易的将真实世界的一些约束条件包含进算法模型中,因此在调度规划模型中得到了广泛应用。但国内使用该算法解决运输调度优化问题的研究还比较少。

目前有关C-W算法的研究多用于物流配送,如连锁超市、烟草配送等,且带时间窗约束的改进算法研究较多,但却少有将该算法应用于采购物流领域的。从物流布局来看,采购物流的VRP问题也可以用配送领域的C-W算法来解决。但必须满足两个前提条件:(1)整个供应链由生产企业主导;(2)采购所需原材料的生产过程平稳有序,采购企业可以使用JIT的生产方式。

1.1 基本数学模型

1.1.1 假设下列条件已知

(1)生产商的原材料仓库与供应商、供应商与供应商之间的距离。令Ci,j为i到j的距离,若i或j等于0,则为收货仓库;若i或j不等于0,则为供应商。N为供应商和生产商的集合。δ为单位距离的运输成本。

(2)每次取货时,向供应商采购产品的数量。令Wi为从供应商i处采购的原材料重量(i=1,2,…,n)。

(3)不同车型的载重量。令Qk为车辆k的最大载重量。K为车辆集合,k∈K。

1.1.2 数学模型

由于采购取货的基本目标是总运输距离最小化,因此目标函数为:

其中,约束条件(1)表示车辆k从点i到点j,其中i≠j;i,j∈N;约束条件(2)表示供应商i处的原材料由车辆k收取,其中i≠0;约束条件(3)表示每一采购路线上采购数量受车辆最大载重量的限制;约束条件(4)表示每个采购商处必须有一辆车去取货;约束条件(5)表示如果车辆k至采购商j处取货,则k必从点i到达点j;约束条件(6)表示若车辆k至采购商i处取货,则k必在该处取完货后到达采购商j。

1.2 修正的数学模型

上述基本数学模型只对车辆的最大载重量做了限定,朱晓兰(2007)[6]在其研究中增加了车辆容积和取货周期内车辆最远行驶距离两个约束条件;李静(2007)[7]不仅考虑了车辆容积问题,同时考虑货物的形状对装载容积的影响,以总容积乘以经验系数来考虑容积约束问题。但是关于时间对运输影响的研究则不多见。在众多企业努力提高JIT采购水平时,忽略运输时间显然是与实际不相符的。

因此在基本C-W算法模型中加入容积约束以及运输提前或延迟对目标函数的影响。

(1)容积约束

其中Vi为车辆在供应商i处的容积,Vc,k为车辆k的最大容积。

(2)时间的约束

LEij———连接供应商i与供应商j后,车辆到达供应商j的时间比原线路上车辆到达供应商j时间的提前量(延迟量)

di———为到达供应商i处的规定时间

dij———为从供应商i处到供应商j处的规定时间

Ti———为在供应商i处的装货时间

ETi———为供应商i处允许的最早开始时间,车辆早于此时间则会等待

LTi———为供应商i处允许的最迟开始时间,车辆晚于此时间则会延迟

则:

设车辆经过供应商j之后所需要经过的供应商为r,当LEij<0,若,,则在经过供应商j之后车辆到过其他供应商时不需要等待,否则,要等待;当LEij>0时,若,则在经过供应商j之后车辆到过其他供应商时不会出现延迟,否则需要延迟进行。

1.3 修正的C-W算法

根据Clarke和Wright共同提出的C-W算法,本文做如下约定:(1)若只有1个供应商的线路0→i→0→称作初始线路;(2)包含2个及2个以上供应商的线路称作组合线路0→…→i→j→…→0→称作组合线路。根据上述修正后的模型,C-W算法步骤如下:

步骤1:将各供应商与工厂仓库相连,构成n条初始化线路。第i条线路的运输距离为DCi=C0,i+Ci,0。

步骤2:计算将两个供应商i,j连接在一条线路上的距离节约值将集合M内的元素Si,j按从大到小的顺序排列。

步骤3:考虑集合M内的第一个元素NSi,j所对应的供应商i,j是否满足下列条件之一:

(1)供应商i,j均在初始路线上;

(2)供应商i,j中有一个在其他组合线路中,并且是线路的起点或终点,另一个在初始线路上;

(3)供应商分别在两条不同的线路上,但一个是起点,另一个是终点。

若满足则转步骤4,否则转步骤8。

步骤4:根据供应商i,j处货物的重量和体积计算若将i,j连接,车辆的载重量和容积是否满足约束条件(1)和(7)。若满足,转向步骤6,否则转步骤5。

步骤5:从车辆集合K中选择更大的车型,转步骤4,如果已达可用车辆容量上限,则转步骤8。

步骤6:计算LEij,若LEij=0,转步骤7;若LEij<0且则转步骤7,否则转步骤8;若则转步骤7,否则转步骤8。

步骤7:连接供应商i和j,构成新组合线路。

步骤8:在集合M中消去元素Si,j,若M≠,转步骤3,继续探索新的组合方案。否则算法终止。

2 实例

案例描述:P0为一家生产手机的公司,生产过程以流水线装配为主,产品采用按订单生产,使用JIT的生产方式,采用3PL公司保障物料供应,3PL公司采取主动上门收货的采购模式。各供应商的货物供给量、货物体积及车辆到达时间要求如表1所示,其中3PL的运输车队于凌晨2点出发,假定车辆的时速为60km/h,固定装货时间为1分钟。车队有10吨货车1辆、5吨货车2辆,5吨和10吨货车的有效容积分别为12m3和20m3,选取9家具有代表性的供应商,各个供应商(P1,P2,…,P9)之间以及它们与P的地理位置如表2所示。

采用VC++编程求解。按照上述求解步骤,经计算产生三条线路:

P0→P1→P0该线路采用10t货车满载运输。

P0→P1→P8→P9→P7→P0该线路采用5吨货车满载运输,容积为10.4m3。

P0→P3→P2→P4→P6→P5→P0该线路采用5吨货车,载重量为4.8t,容积为8.7m3。

由此可见,通过该算法,各需求点都能得到较优的运输方案,供应商P1的供应量最大,可以采用整车运输的方式,其余各供应商采用5吨货车收取货物。

3 总结

本文研究了生产企业主导的第三方物流在JIT条件下的车辆调度问题。基本C-W算法可以保证运输路径的合理化,有效缩减了运输距离;加入到达时间约束后,使运输时间成为一项非常重要的决定因素。因此修正后的C-W算法可以较好地应用于JIT采购。本文建立模型还可以在多个方面进一步拓展,此外对于装卸货时间的动态变化等约束条件会使问题变得非常复杂,还有待作进一步的研究。

参考文献

[1]李昆鹏,马士华.基于JIT配送的3PL运输协调调度问题建模与分析[J].交通与计算机,2008(2):73-79.

[2]Ruiz Torres,A.J.,Tyworth,J.E.Simulation based approach to study the interaction of scheduling and routing on a logistic network[C]//Proceeding of the1997Winter Simulation Conference,1997.

[3]Chang,Y.C.,Lee,C.Y..Machine scheduling with job delivery coordination[J].European Journal of Operational Research,2004,158:470-487.

[4]Garcia,J.M.,Lozano,S.,Canca,D..Coordinated scheduling of production and delivery from multiple plants[J].Robotics and Computer Integrated Manufacturing,2004,20(3):191-198.

[5]祝崇隽,刘民,吴澄.供应链中车辆路径问题的研究进展及前景[J].计算机集成制造系统——CIMS,2001(7):1-6.

[6]朱晓兰,赵一飞.C-W节约算法在装配企业采购物流中的应用[J].上海交通大学学报,2007(9):1420-1424.

[7]李静,钟典钦.基于CW节约算法的ERP系统改进研究[J].计算机工程与设计,2007(11):5214-5217.

[8]林晓宇,李金铭,纪寿文.车辆路径问题Clarke-Wright算法的改进与实现[J].交通与计算机,2004(6):72-75.

C-W启发式算法篇2

一种基于启发式算法的等高线局部内插方法

在基于启发式内插等高线算法的`基础上提出了一种局部内插方法.首先利用Douglas-Peucker算法提取等高线的特征点,根据特征点判断等高线之间的相似性程度,找出导致等高线出现异常的特征点;然后将相似性程度很低的两条等高线自动分解为若干简单等高线再进行内插.有效地解决了局部弯曲很大、马鞍型地貌等复杂等高线的内插问题.算法已经在以Microstation为平台的数字制图系统中实现并逐渐实用化.

作者：安晓亚孙群肖强赵国成 AN Xiao-ya SUN Qun XIAO Qiang ZHAO Guo-cheng 作者单位：信息工程大学,测绘学院,河南,郑州,450052刊名：测绘科学技术学报 PKU英文刊名：JOURNAL OF GEOMATICS SCIENCE AND TECHNOLOGY年，卷(期)：25(1)分类号：P208关键词：先验知识等高线局部内插自动分解

C-W启发式算法篇3

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算法解题步骤：