网站原创摘 要：作为企业的“第三利润源泉”,物流日益受到企业的关注.但物流运输成本过高,日渐成为制约我国物流业发展的主要瓶颈.文中对国内外前沿成果进行分析和归纳的基础上,介绍了主要的SD求解算法,并针对不足提出了新的求解途径.
关 键 词 ：需求可拆分车辆路径问题；精确算法；启发式算法
一、引言
伴随着全球经济一体化,社会分工日趋细化,配送功能从企业中外包出来.在我国,第三方物流作为一个新兴产业,于20世纪80年代后期开始快速发展.但由于起步较晚,物流运作水平与发达国家相比仍存在较大差距,其中最突出的问题就是物流成本高.国家发改委、国家统计局和中国物流与采购联合会联合发布的2012年统计数据显示[1],全国社会物流总费用为9.4万亿元,占GDP的比重为18%,而同期新加坡、美国等发达国家物流总费用占GDP比重仅为8%-10%.运输成本是物流成本的重要组成部分,2011年与2012年的全国物流运行统计数据显示,全国社会物流总费用中运输成本分别为4.4万亿元与4.9万亿元,占社会物流总费用的比重分别为52.8%与52.5%,以上数据显示,我国运输成本占物流总费用比例高,且增长较快,因此降低运输成本,无疑是提高运输质量与效率,促进物流产业发展的重要途径.
配送中心是物流配送网络的枢纽,是企业实施供应链管理的重要设施之一.配送中心接受并处理末端用户的订货信息,根据客户的需求进行配送.其主要任务是处理不确定环境下的订单整合（Order Consolidation,OC）和车辆路径问题（Vehicle Routing Problem,）.是物流配送优化的核心环节,配送路线的规划合理与否都将对配送成本、时间和效率产生较大的影响,特别是在有着多客户需求且其路径规划比较复杂的情况下,如何确定合理的配送路线,是配送规划过程中一项非常重要的工作.
二、SD的常用求解算法
SD是传统的一个较新分支.自从SD被提出后,对其求解算法的研究一直是研究的重点和难点.Archetti et al. （2005）指出[2],当Q等于2时,具备整数需求的SD可以在多项式时间里得到相对满意的解；当Q>2时,SD则成为一个NP-hard问题.而在Archetti et al. （2010）的研究里[2],通过对特定图中和SD的计算复杂度进行研究,其结果表明,在某些特定的图中,SD的计算复杂度不会难于.目前,关于SD的主要求解算法主要分为精确算法和启发式算法两大类：
(一) 精确算法
精确算法可以求得问题的最优解,但是,其计算时间会随问题规模的扩大呈指数增长,因此,精确算法只适用于求解小规模问题.第一种精确算法由Dror et al. （1994）于1994年提出[2],在其研究中,他们提出了一个集合新的有效不等式类的弧流列方程式,其实验结果证明不等式在求解下界上得到显著改善,在大多数的算例中,对上下界差值的改善超过30%.Desaulniers （2010）设计了一种分支定价法优化带时间窗的SDTW的运输成本[2].当需求确定且顾客数目小于100时,该优化方法表现优异.Gulczynski et al. （2010）研究了带最小运输量约束的SD[2],并建立了一个混合整数规划模型优化该问题的运输成本.Hertz et al. （2012）对有一个拥有不同车型的车队和很多仓库[4],并且顾客需求量大于车载容量的水泥运输问题进行了研究.在他们的论文中,他们提出了一个两阶段整数线性规划模型解决这种SD.
| 有关论文范文主题研究: | 关于算法的论文范文资料 | 大学生适用: | 学术论文、高校大学论文 |
|---|---|---|---|
| 相关参考文献下载数量: | 81 | 写作解决问题: | 写作参考 |
| 毕业论文开题报告: | 论文任务书、论文结论 | 职称论文适用: | 核心期刊、初级职称 |
| 所属大学生专业类别: | 写作参考 | 论文题目推荐度: | 优质选题 |
(二) 启发式算法
当问题规模较大,利用精确算法无法在有效时间内求得最优解时,通常釆用启发式算法求取“近优解”或“满意解”.Dror & Trudeau （1989,1990）提出了第一个基于局部搜索的启发式算法[2].Archetti et al. （2006）提出了一种禁忌搜索算法[2],实验证明虽然计算速度相对较慢,但此算法在计算效率上明显优于Dror & Trudeau提出的基于局部搜索的启发式算法.Boudia et al.（2007）在遗传算法的基础上提出了一种文化基因算法[2],该算法对局部搜索过程进行强化,并整合距离策略以控制群体的多样性.通过与Archetti et al. （2006）的算例集进行对比测试[3],发现禁忌搜索算法在某些算例上其计算结果优于Archetti et al. （2006）提出禁忌搜索算法.除此以外,为了规避单一算法计算速度慢或者计算效率过低的问题,Chen et al. （2007）、Archetti et al. （2008）和Jin et al. （2008）提出了三种不同的混合启发式算法[2],其中前两种算法的实验结果与Archetti et al. （2006）相比在很多的算例上,都得到了不同程度的改进.而Jin et al. （2008）相对割平面法在Belenguer et al. （2000）所测试的12个算例中的6个中,都能够求得更好的上下界.[2]
三、结论
通过对SD的常用算法进行总结和归纳,我们发现SD的复杂性决定了利用精确算法和传统的启发式算法很难得到满意的解,精确算法可以得到相对精确地最优解,但是运算效率较低；启发式算法运行时间较短,很容易陷入局部最优,或者出现无法收敛的现象.但随着计算机硬件和软件的进步,现代启发式算法的运行效率得到很大的改善.从文献检索的结果看,目前,已经有学者开始采用以现代启发式优化算法为核心,结合系统仿真的方法对SD问题进行建模与优化.随着全球供应链管理观念的流行,物流管理的水平日益成为衡量一个国家综合能力的重要指标,对SD问题进行研究不仅可以很大程度上减少国内物流运输成本过高的现状,而且具有很高的经济意义.