| 标题 | 一种解决配送规划问题的改进节约算法 |
| 范文 | 孙 焰 张 喆 摘要:车辆优化调度问题(VSP)是物流配送中广泛存在的一类问题,VSP问题属于NP-困难问题。在描述了简单VSP模型的基础上,对启发式算法中的C-W节约算法进行改进,将AK算法的思想运用其中,使计算结果的优化程度明显提高。 关键词:C-W节约算法;车辆调度问题;AK算法 中图分类号:TP301.6文献标识码:A Abstract: Vehicle scheduling problem is a widespread problem in losgistic distribution, it's a NP-hard problem. The description of VSP model was given and an improvement of a heuristic method called C-W algorithm was made based on it. The optimization results was impoved significantly after using the thinking of AK algorithm. Key words: C-W algorithm; vehicle scheduling problem; AK algorithm 物流配送是现代化物流系统中的一个重要环节。配送是将货物从物流节点送达收货人的过程。合理选择配送路径,对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较好的影响。配送规划问题可以简化为货运车辆优化调度问题(Vehicle Scheduling Problem,VSP),是指对一系列装货点和卸货点,组织适当的行车线路,使车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下,达到一定的目标(如里程最短、费用最少、时间尽量少、使用车辆数尽量少等)。 Dantzing和Ramser于1959年首次提出该问题[1]。由于VSP问题属于NP-困难问题,因此在实际中常采用启发式算法来求解。启发式算法的种类也很多,常见的有构造算法(如Clarke和Wright的C-W节约算法),两阶段算法和亚启发式算法(如模拟退火算法、遗传算法、神经网络算法等)。C-W节约算法是Clarke和Wright于1964年提出的,由于其简单性和一定程度的实用性,成为广泛使用的配送规划近似算法。然而,有些时候C-W算法的求解结果可能与最优解相差较大距离(见算例)。本文结合AK算法的思路对C-W节约算法进行改进,期望使节约算法更加实用。 1问题描述与模型建立 问题描述:有一个车场0,拥有m辆容量为W的车辆,第k辆车的最大运距为L,现有i项货运任务需要完成,每辆车所运送的货物量不超过其载重量并且走行路程不超过其运距,每个需求点必须有且只需一辆车送货。设N=1,2,…,n, N=1,2,…,m,I,I,…I是自然数集N=1,2,…,n的一个分划(I为第j辆车的送货点集),FP,P,…,P为过P,P,…,P个点的最小回路长。 配送规划的集合划分模型表示[2]为: minZ=FP∪P|j∈I s.t.I?奂N, j∈N I=N每个需求点必须至少有一辆车送货 I∩I=Φ, i≠j, 1≤i, j≤m每个需求点最多只需一辆车送货 R≤W, i∈N 每辆车总载重不超过载重限制 FP∪P|j∈I≤L, i∈N每辆车总行程不超过最大运距 其中,用车数k=SignI;第j辆车的送货点为I, j=1,2,…,m; 初始载货为R。 2改进的C-W节约算法 AK算法是一种启发式的搜索算法,一般被用来解决0-1背包问题。算法的基本思想是,首先将最多k件物品放入背包,如果这k件物品的总重大于包裹容量,则放弃它。否则,剩余容量再按物品重量从大到小的顺序装 入[3]。C-W节约算法中合并配送路径是从节约里程最大的点对开始合并,现将AK算法运用其中,首先选择任意小于等于k对的点对,如满足合并条件则进行合并,而后再按节约里程从大到小的顺序合并其他点对。针对从点对集中挑出不超过k对的点对的不同组合形成不同的方案,并比较每个方案的目标值,选择其中的最优的一个形成最终配送方案。 改进的C-W算法: 输入:需求点集N=1,2,…,n,各点需求量为R,各点间最短距离C,首先考虑合并的点对最大个数k,车辆集合N=1,2,…,m,各车辆最大载重量W,最大运距L; 输出:各车辆配送点集I,I,…,I。 Step1:将N按W从大到小排序,使得:W≥W≥…≥W,若m =S|S>0; i,j=1,2,…,n,并把集合M内的元素S按从大到小的顺序排列。 Step3:求初始可行解。首先采取单点配送,令I=j, j=1,2,…,n,令初始总运距为minz。 Step4:从集合M中任意取出不多于k个的元素组成子集T,若M中元素个数为r,则子集T共有q=C+C+…+C种,对于每种子集T执行下面的步骤: (1)对于子集T中的每个S,判断i和j合并的可能性(是否满足装载限制条件、最大运输距离约束、不在同一路径内以及合并次数不超过2),若不满足则跳出本次循环,继续从下一个子集T开始判断,若所有S均满足,则分别合并各个S中的i和j,构成新组合线路。 (2)考虑集合M中除去子集T后的第一个元素S,判断i和j合并的可能性,若不满足则从集合M中消去 S,若满足则合并i和j,若M=Φ,则转到步骤(3),否则重新执行步骤(2)。 (3)计算总运距Z=FP∪P|j∈I。 (4)如果minz>Z,则令minz=Z,并记录此时各车辆的配送点集I,I,…,I。 Step4执行q次后算法结束。此算法的时间复杂度为Okn。 3算例 某配送中心某天有6个客户的配送任务,各任务货运量为R(见图1、表1),配送中心现有载重量为4t的货车5辆,最大运距为45km,车辆由配送中心0出发,各点之间的距离由表2给出。 用传统C-W节约算法计算,合并2、3点,最终得到0-2-3-0、0-1-6-0、0-4-0、0-5-0,共用4辆车,总里程为109km。用改进后的方法计算,得到0-3-4-0,0-1-2-0,0-5-6-0,共用3辆车,总里程为96km。改进后的算法在优化程度上明显提高。 4结束语 本文在对VSP问题进行简单描述的基础上,对AK算法与传统的C-W节约算法进行有效的结合,提出了求解该问题的一种改进算法,通过这种方法能够避免在某些情况下C-W节约算法求解结果与最优解相差较大的问题。然而,本算法计算复杂度为Okn,较C-W节约算法的计算次数多,k的取值可根据问题的规模n和计算机的速度来确定。 参考文献: [1]Clarke G, Wright J. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operation Re, earch, 1964,12(4):12-18. [2] 孙焰. 现代物流管理技术[M]. 上海:同济大学出版社,2004. [3] 游维. 基于贪婪的0/1背包问题算法研究[J]. 计算机与现代化,2007(4):11-12. [4] 朱晓兰,赵一飞. C-W节约算法在装配企业采购物流中的应用[J]. 上海交通大学学报,2007,41(9):1422. [5] 张建勇,郭耀煌,李军. 一种具有模糊费用系数的VSP的修正C-W节约算法[J]. 西南交通大学学报,2004,39(3):281-282. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。