论文部分内容阅读
摘要:现代社会企业要想在竞争中获得优势,不能一味地从提高生产技术、裁员、降低制作成本等传统方面入手,而是要靠降低物流成本。传统的方法降低所谓的成本都是有限的,而物流方面得到优化的话则可以大大降低一些不必要的成本,这方面有很大的潜力和发展空间。目前,物流已经被很多大型企业看作是企业的第三利润源泉。因此本文在建立一个集成优化平台的基础上,从如何优化配送车辆调度的角度来探究如何为企业带来最大的经济效益。本文主要是对配送车辆的调度优化问题进行研究,首先介绍国内外对此的研究现状以及未来的发展趋势,然后引入模糊理论的知识对车辆调度优化问题进行研究,最后通过遗传算法进行建模,并且用matlab来实现其算法。
关键词:车辆调度;模糊理论;遗传算法;优化平台
中图分类号:F224 文献标识码:A 文章编号:1003-2177(2017)16-0021-04
1 研究背景
我国是一个食品生产和消费大国,食品的安全问题也一直是人们最为关心的[1]。再加上近年来,特别是电子商务的飞速发展使得物流行业又得到了较快的发展和重视,当代已经把物流产业的发展作为衡量一個国家现代化程度和综合国力的重要标志之一[2],许多企业也因此不得不将物流配送纳入了自己的利益考虑之中,与此同时,物流行业的大力发展也带动了整个国民经济的高速发展[3],有数据显示,截止到2016年2月我国公路货运量已经达到了404756万吨,同比增长率1.3%,到2014年我国物流总成本达到了10.6万亿元,其中交通运输费用占到了总成本的80%以上[4],由此可以看出大部分的费用还是发生在运输上,而这部分的费用恰好可以通过配送车辆调度优化的方法加以改善,从而降低成本。因此,综上所述,对于现代的物流产业来说如何更好地优化配送车辆调度是一个焦点问题了。而车辆调度优化就是以满足客户需求和降低运输成本为主要目标的,企业要想获得最大化的利润就要最大程度地对车辆调度进行优化。
2 模型的建立
2.1 问题说明
本文以配送成本最低为目标函数,研究单配送中心VRP问题,且配送车辆最终返回到配送中心[5]。建立相应的数学模型最终通过matlab建立的优化平台来进行优化,并得出最终的较满意的解。
2.2 模型的假设
(1)配送车辆的载货量不能超过车辆的最大载货量;
(2)天气情况、道路状况等外部环境会对车辆的配送产生一定的影响;
(3)参加配送的车辆数不能超过配送中心可提供的车辆数;
(4)车辆到达每个客户的时间是不确定的;
(5)每个客户都要被服务,且每个客户点只能由一辆车进行配送;
(6)车辆都在预定时间内送达。
2.3变量说明
K —配送车辆数的最大值;
— 车辆k的最大载货量;
c—空车行驶单位里程时的成本;
n —客户节点的数量;
—从i到j的距离;
di —客户i的需求量;
Wg—车辆的当前物流量;
—单位物流量的货物单位里程增加的成本系数。
2.4 配送成本分析
车辆调度的配送成本由固定成本和可变成本组成,固定成本主要是指车辆空车行驶时的成本,可变成本是指车辆载货时行驶的成本,随着时间的变化而变化。相应的公式如下所示。
(1)空车的行驶成本:
(2-1)
(2)装载货物时的成本:
(2-2)
其中,K为需要配送的车辆数,n为客户点的总数,i、j为当前访问的客户点,c为空车行驶单位里程的成本,dij为两节点之间的行驶距离,Wg为当前的货物量,di为当前节点需要的货物量,为系数,则式(2-1)表示车辆空载时的行驶成本,式(2-2)表示车辆在完成了当前客户点的配送任务后,前往下一个客户点产生的行驶成本。
2.5 模型建立
目标函数:
Min
(2-3)
S.t.,... (2-4)
(2-5)
(2-6)
模型的相关说明如下:式(2-3)表示以配送成本最低为目标函数,其中配送成本包括空车行驶的成本、装载货物时行驶的成本以及超出预约时间的惩罚成本这三部分,式(2-4)表示每个客户节点只能由一辆车进行访问,同一个节点不会有几辆不同的车访问,式(2-5)表示每辆车都可以对相应的客户节点访问,最终形成一条完整的回路,式(2-6)表示每辆车只能从一个客户节点返回配送中心,且该客户节点不会重复。
3 改进的遗传算法
3.1 改进的遗传算法的种群初始化
基本的遗传算法采用的都是二进制编码的方式,而本文采取自然数编码来产生初始解[6]。即假定有9个顾客点,编号分别为1-9,一个配送中心,编号为0,先确定有n辆车进行配送,然后在数字为1-9的序列中插入n 1个0,然后再生成m个这样的全排列即可[7],即类似于像0135068904270这样的则表示的是用3辆车进行配送,配送路径分别是0-1-3-5-0、0-6-8-9-0、0-4-2-7-0。
3.2 改进的遗传算法的选择操作
以配送成本为适应度函数,根据适应度值的大小,选择前90%的方案进入到下一代。
3.3 改进的遗传算法的交叉操作
大多数遗传算法都是用单点交叉的方法,该方法最大的缺点就是在很大程度上需要交换父代双方相当多的基因,很有可能破坏一些较优秀的个体。因此本文采用一种新的方法,即双切点交叉法,例如对下面这个染色体进行交叉操作: 這样得到的新的个体具有很强的适应性,且对父代染色体的改变不会很大,非常适用于对VRP问题的研究。
3.4 改进的遗传算法的变异操作
本文采用随机变异的方法,具体操作如下:
父代染色体:0824109607350
随机选取一小段进行变异,例如取4至9之间的基因位,进行随机的顺序交换即可,则变异后的染色体为:
子代染色体1:0821049607350
子代染色体2:0821904607350等。
4 算例分析
4.1 实例验证
为了验证该遗传算法的有效性,本文以杭州市的西湖区和江干区的共9个配送点为例进行分析[8]。配送中心的编号设置为0,其余9个客户点的编号设置为1-9,总共需要3辆车进行配送,每辆车的行驶速度为45km/h,运输成本为2元/公里,载重量为2t,各配送点之间的距离以及需求量如表4-1所示:
该集成优化平台的界面如图4-1所示:
左边3个按钮的功能是将产生的初始解输入到excel中,以便记录并修改每次的方案,成本计算按钮的功能是计算出每个方案的空车行驶的成本和装载货物的成本,如图4-2所示:
在数据优化(遗传算法)中是利用本文改进的遗传算法来实现对路径的优化的,优化的结果将实时显示在excel中,excel的主要功能就是存放数据,如图4-3所示:
由图可知方案四经过一次遗传算法之后被迭代为新的方案。
4.2 结果分析
利用改进的遗传算法借助于MATLAB7.0,在经过大约80次迭代之后,发现方案2是比较令人满意的方案,即比较满意的路径为:0-1-2-3-4-0,0-5-7-9-0,0-6-8-0,该配送路径所需的成本约为258.74元。利用该改进的遗传算法能够大大减少算法迭代的次数,从而找到比较满意的解。
5 结语
现代物流发展迅速,要想在企业竞争中占据优势,就必须降低物流配送等环节的成本,但是要想更好的发展我国的物流行业,从企业层面讲,要想解决目前物流行业存在的问题,就必须需要各企业之间相互协同[9]。当然根据配送货物的不同类型,针对其特点可以提出具体的更加合理的配送路径及管理方法,不能仅仅依靠配送路径的优化来降低成本,要使物流在加工、运输、仓储和销售各个环节紧密结合,用统一的方法才能确保货物的质量安全[10]。因此对于配送路径的优化的研究具有重大的意义。
参考文献
[1]繆小红.第3方冷链物流配送路径优化研究[J].运筹与管理,2011,20(4):1.
[2]赵燕伟,张景玲.物流配送的车辆路径优化方法[M].北京:科学出版社,2014.
[3]汪利军.基于改进遗传算法的城市配送车辆调度优化研究[D].长沙:长沙理工大学,2007.
[4]繆小红,周新年,巫志龙.生鲜食品冷链物流研究进展探讨[J].物流技术,2009,28(2):24-27.
[5]曾华.随机顾客和需求的配送优化[D].济南:山东大学,2012.
[6]邓丽君.基于客户满意度的物流配送车辆调度优化模型与算法研究[D].北京:北京交通大学,2012.
[7]弓晋丽,程志敏.基于Matlab物流配送路径优化问题遗传算法的实现[J].物流科技,2006,29(131):104.
[8]齐佳婷.城市农产品冷链物流配送车辆路径问题研究[D].杭州:浙江理工大学,2016.
[9]P.Humphreys,J.Matthews and M.Kumaraswamy.Pre-construction Project Partnering:from Adversarial to Collaborative Relationships[J].Supply Chain Management:An International Journal,2003,8(2):166-178.
[10]Sun Yan,Cai Huawei,Zheng Limin,et al.Development and characterization of a new amylase type time-temperature indicator[J].Food control,2008,19(3):315-319.
关键词:车辆调度;模糊理论;遗传算法;优化平台
中图分类号:F224 文献标识码:A 文章编号:1003-2177(2017)16-0021-04
1 研究背景
我国是一个食品生产和消费大国,食品的安全问题也一直是人们最为关心的[1]。再加上近年来,特别是电子商务的飞速发展使得物流行业又得到了较快的发展和重视,当代已经把物流产业的发展作为衡量一個国家现代化程度和综合国力的重要标志之一[2],许多企业也因此不得不将物流配送纳入了自己的利益考虑之中,与此同时,物流行业的大力发展也带动了整个国民经济的高速发展[3],有数据显示,截止到2016年2月我国公路货运量已经达到了404756万吨,同比增长率1.3%,到2014年我国物流总成本达到了10.6万亿元,其中交通运输费用占到了总成本的80%以上[4],由此可以看出大部分的费用还是发生在运输上,而这部分的费用恰好可以通过配送车辆调度优化的方法加以改善,从而降低成本。因此,综上所述,对于现代的物流产业来说如何更好地优化配送车辆调度是一个焦点问题了。而车辆调度优化就是以满足客户需求和降低运输成本为主要目标的,企业要想获得最大化的利润就要最大程度地对车辆调度进行优化。
2 模型的建立
2.1 问题说明
本文以配送成本最低为目标函数,研究单配送中心VRP问题,且配送车辆最终返回到配送中心[5]。建立相应的数学模型最终通过matlab建立的优化平台来进行优化,并得出最终的较满意的解。
2.2 模型的假设
(1)配送车辆的载货量不能超过车辆的最大载货量;
(2)天气情况、道路状况等外部环境会对车辆的配送产生一定的影响;
(3)参加配送的车辆数不能超过配送中心可提供的车辆数;
(4)车辆到达每个客户的时间是不确定的;
(5)每个客户都要被服务,且每个客户点只能由一辆车进行配送;
(6)车辆都在预定时间内送达。
2.3变量说明
K —配送车辆数的最大值;
— 车辆k的最大载货量;
c—空车行驶单位里程时的成本;
n —客户节点的数量;
—从i到j的距离;
di —客户i的需求量;
Wg—车辆的当前物流量;
—单位物流量的货物单位里程增加的成本系数。
2.4 配送成本分析
车辆调度的配送成本由固定成本和可变成本组成,固定成本主要是指车辆空车行驶时的成本,可变成本是指车辆载货时行驶的成本,随着时间的变化而变化。相应的公式如下所示。
(1)空车的行驶成本:
(2-1)
(2)装载货物时的成本:
(2-2)
其中,K为需要配送的车辆数,n为客户点的总数,i、j为当前访问的客户点,c为空车行驶单位里程的成本,dij为两节点之间的行驶距离,Wg为当前的货物量,di为当前节点需要的货物量,为系数,则式(2-1)表示车辆空载时的行驶成本,式(2-2)表示车辆在完成了当前客户点的配送任务后,前往下一个客户点产生的行驶成本。
2.5 模型建立
目标函数:
Min
(2-3)
S.t.,... (2-4)
(2-5)
(2-6)
模型的相关说明如下:式(2-3)表示以配送成本最低为目标函数,其中配送成本包括空车行驶的成本、装载货物时行驶的成本以及超出预约时间的惩罚成本这三部分,式(2-4)表示每个客户节点只能由一辆车进行访问,同一个节点不会有几辆不同的车访问,式(2-5)表示每辆车都可以对相应的客户节点访问,最终形成一条完整的回路,式(2-6)表示每辆车只能从一个客户节点返回配送中心,且该客户节点不会重复。
3 改进的遗传算法
3.1 改进的遗传算法的种群初始化
基本的遗传算法采用的都是二进制编码的方式,而本文采取自然数编码来产生初始解[6]。即假定有9个顾客点,编号分别为1-9,一个配送中心,编号为0,先确定有n辆车进行配送,然后在数字为1-9的序列中插入n 1个0,然后再生成m个这样的全排列即可[7],即类似于像0135068904270这样的则表示的是用3辆车进行配送,配送路径分别是0-1-3-5-0、0-6-8-9-0、0-4-2-7-0。
3.2 改进的遗传算法的选择操作
以配送成本为适应度函数,根据适应度值的大小,选择前90%的方案进入到下一代。
3.3 改进的遗传算法的交叉操作
大多数遗传算法都是用单点交叉的方法,该方法最大的缺点就是在很大程度上需要交换父代双方相当多的基因,很有可能破坏一些较优秀的个体。因此本文采用一种新的方法,即双切点交叉法,例如对下面这个染色体进行交叉操作: 這样得到的新的个体具有很强的适应性,且对父代染色体的改变不会很大,非常适用于对VRP问题的研究。
3.4 改进的遗传算法的变异操作
本文采用随机变异的方法,具体操作如下:
父代染色体:0824109607350
随机选取一小段进行变异,例如取4至9之间的基因位,进行随机的顺序交换即可,则变异后的染色体为:
子代染色体1:0821049607350
子代染色体2:0821904607350等。
4 算例分析
4.1 实例验证
为了验证该遗传算法的有效性,本文以杭州市的西湖区和江干区的共9个配送点为例进行分析[8]。配送中心的编号设置为0,其余9个客户点的编号设置为1-9,总共需要3辆车进行配送,每辆车的行驶速度为45km/h,运输成本为2元/公里,载重量为2t,各配送点之间的距离以及需求量如表4-1所示:
该集成优化平台的界面如图4-1所示:
左边3个按钮的功能是将产生的初始解输入到excel中,以便记录并修改每次的方案,成本计算按钮的功能是计算出每个方案的空车行驶的成本和装载货物的成本,如图4-2所示:
在数据优化(遗传算法)中是利用本文改进的遗传算法来实现对路径的优化的,优化的结果将实时显示在excel中,excel的主要功能就是存放数据,如图4-3所示:
由图可知方案四经过一次遗传算法之后被迭代为新的方案。
4.2 结果分析
利用改进的遗传算法借助于MATLAB7.0,在经过大约80次迭代之后,发现方案2是比较令人满意的方案,即比较满意的路径为:0-1-2-3-4-0,0-5-7-9-0,0-6-8-0,该配送路径所需的成本约为258.74元。利用该改进的遗传算法能够大大减少算法迭代的次数,从而找到比较满意的解。
5 结语
现代物流发展迅速,要想在企业竞争中占据优势,就必须降低物流配送等环节的成本,但是要想更好的发展我国的物流行业,从企业层面讲,要想解决目前物流行业存在的问题,就必须需要各企业之间相互协同[9]。当然根据配送货物的不同类型,针对其特点可以提出具体的更加合理的配送路径及管理方法,不能仅仅依靠配送路径的优化来降低成本,要使物流在加工、运输、仓储和销售各个环节紧密结合,用统一的方法才能确保货物的质量安全[10]。因此对于配送路径的优化的研究具有重大的意义。
参考文献
[1]繆小红.第3方冷链物流配送路径优化研究[J].运筹与管理,2011,20(4):1.
[2]赵燕伟,张景玲.物流配送的车辆路径优化方法[M].北京:科学出版社,2014.
[3]汪利军.基于改进遗传算法的城市配送车辆调度优化研究[D].长沙:长沙理工大学,2007.
[4]繆小红,周新年,巫志龙.生鲜食品冷链物流研究进展探讨[J].物流技术,2009,28(2):24-27.
[5]曾华.随机顾客和需求的配送优化[D].济南:山东大学,2012.
[6]邓丽君.基于客户满意度的物流配送车辆调度优化模型与算法研究[D].北京:北京交通大学,2012.
[7]弓晋丽,程志敏.基于Matlab物流配送路径优化问题遗传算法的实现[J].物流科技,2006,29(131):104.
[8]齐佳婷.城市农产品冷链物流配送车辆路径问题研究[D].杭州:浙江理工大学,2016.
[9]P.Humphreys,J.Matthews and M.Kumaraswamy.Pre-construction Project Partnering:from Adversarial to Collaborative Relationships[J].Supply Chain Management:An International Journal,2003,8(2):166-178.
[10]Sun Yan,Cai Huawei,Zheng Limin,et al.Development and characterization of a new amylase type time-temperature indicator[J].Food control,2008,19(3):315-319.