论文部分内容阅读
摘 要:为了降低配送成本、提高客户满意度,本文结合实际物流配送活动中客户的同时取送货需求,构建以物流成本最小为目标、带同时取送货的选址路径模型,并设计了随机变邻域禁忌搜索算法求解模型。最后进行数值实验,表明本文提出的模型和算法的正确性和有效性。
关键词:选址路径问题 同时取送货 禁忌搜素算法
一、引言
对快递企业的配送网络建设而言,同时考虑正向发件网络和逆向收件网络,不仅能有效降低企业物流成本,同时对提高客户满意度有重要意义。本文以快递企业物流配送网络为研究对象,考虑客户同时取送货需求,在优化配送中心位置和数量的同时确定最佳的配送路线,以期降低快递企业成本并提高客户满意度。
二、问题模型
在一个包含m个候选配送中心、n个客户需求点的物流配送网络中,每个客户同时具有送货和取货的需求,车辆由配送中心出发,同时满足客户的送货和取货需求,最后返回配送中心。决策目标是最小化物流成本,需要考虑以下问题:(1)确定配送中心的数目和位置;(2)确定最佳的车辆配送路径。
1.模型假设。每个客户仅被访问一次,且配货和集货需求同时满足;每个配送中心的总存量不能超过其容量限制;每辆车的起终点必须为同一个配送中心,车辆在每个节点的负载量始终不能超过其载重限制。
2.模型参数描述。
三、禁忌搜索算法
禁忌搜索算法在解决选址路径问题上十分高效,本文选用禁忌搜索算法求解模型。禁忌搜索算法是一种基于邻域搜索技术的算法,邻域操作方法对算法的搜索效率和搜索质量有很大影响,故设计随机变邻域策略生成鄰域解。
1.解的表示。选址路径问题解由三段构成,选址方案编码段、路径方案编码段、车辆编码段,编码长度为m+n+k,详见表1。其中,m指候选配送中心的数量;n指需要服务的客户数量;k指使用的车辆数。
2.邻域搜索策略。共设计5种邻域搜索策略,reverse、insert、swap、open、close,详见图1。其中,选址编码段邻域搜索策略包括swap、open、close,路径编码段邻域搜索策略包括reverse、insert、swap。每次迭代时,选址和路径编码段从各自对应的邻域搜索策略中随机选择一种产生邻域解。图1 邻域搜索策略
四、算例分析
在Prodhon提出的标杆算例集20-5-1a基础上增加取货数据构成本文的测试算例,其中取货量数据根据salhi的方式生成。其中,车载量为70,车辆单位运输成本为100,车辆固定发车成本为1000,候选配送中心节点数据见表2,客户节点数据见表3。
使用Matlab编程,实验参数设置如下,迭代步数=500,允许解未改进次数=100,邻域解个数=100,禁忌长度=15。对算例重复仿真20次,最优选址路径方案见表4。
五、结语
本文结合取送货一体化配送模式,构建快递网点选址和配送路线规划模型,并设计随机变邻域禁忌搜素算法求解模型,同时利用仿真数据验证了模型和算法的有效性。下一步将考虑物流配送网络中的不确定因素,如供需不确定、配送时间不确定等,更高效灵活的满足物流配送企业的实际需求。
参考文献:
[1]Karaoglan I, Altiparmak F. A Hybrid Genetic Algorithm for the Location-Routing Problem with Simultaneous Pickup and Delivery [J]. Industrial Engineeering & Management Systems, 2010, 10(1):1-6.
[2]Christian Prins, Caroline Prodhon, Roberto Wolfler Calvo. A Memetic Algorithm with Population Management (MA|PM) for the Capacitated Location-Routing Problem [J]. Lecture Notes in Computer Science, 2006, 3906:183-194.
[3]Salhi S, Nagy G. A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problems with Backhauling [J]. Journal of the Operational Research Society, 1999, 50(10):1034-1042.
作者简介:黄丽萍,女,福建宁德人,福州大学经济与管理学院硕士研究生,研究方向:物流管理与物流工程。张妹燕,女,福建宁德人,福州大学经济与管理学院硕士研究生,研究方向:物流管理与物流工程。
关键词:选址路径问题 同时取送货 禁忌搜素算法
一、引言
对快递企业的配送网络建设而言,同时考虑正向发件网络和逆向收件网络,不仅能有效降低企业物流成本,同时对提高客户满意度有重要意义。本文以快递企业物流配送网络为研究对象,考虑客户同时取送货需求,在优化配送中心位置和数量的同时确定最佳的配送路线,以期降低快递企业成本并提高客户满意度。
二、问题模型
在一个包含m个候选配送中心、n个客户需求点的物流配送网络中,每个客户同时具有送货和取货的需求,车辆由配送中心出发,同时满足客户的送货和取货需求,最后返回配送中心。决策目标是最小化物流成本,需要考虑以下问题:(1)确定配送中心的数目和位置;(2)确定最佳的车辆配送路径。
1.模型假设。每个客户仅被访问一次,且配货和集货需求同时满足;每个配送中心的总存量不能超过其容量限制;每辆车的起终点必须为同一个配送中心,车辆在每个节点的负载量始终不能超过其载重限制。
2.模型参数描述。
三、禁忌搜索算法
禁忌搜索算法在解决选址路径问题上十分高效,本文选用禁忌搜索算法求解模型。禁忌搜索算法是一种基于邻域搜索技术的算法,邻域操作方法对算法的搜索效率和搜索质量有很大影响,故设计随机变邻域策略生成鄰域解。
1.解的表示。选址路径问题解由三段构成,选址方案编码段、路径方案编码段、车辆编码段,编码长度为m+n+k,详见表1。其中,m指候选配送中心的数量;n指需要服务的客户数量;k指使用的车辆数。
2.邻域搜索策略。共设计5种邻域搜索策略,reverse、insert、swap、open、close,详见图1。其中,选址编码段邻域搜索策略包括swap、open、close,路径编码段邻域搜索策略包括reverse、insert、swap。每次迭代时,选址和路径编码段从各自对应的邻域搜索策略中随机选择一种产生邻域解。图1 邻域搜索策略
四、算例分析
在Prodhon提出的标杆算例集20-5-1a基础上增加取货数据构成本文的测试算例,其中取货量数据根据salhi的方式生成。其中,车载量为70,车辆单位运输成本为100,车辆固定发车成本为1000,候选配送中心节点数据见表2,客户节点数据见表3。
使用Matlab编程,实验参数设置如下,迭代步数=500,允许解未改进次数=100,邻域解个数=100,禁忌长度=15。对算例重复仿真20次,最优选址路径方案见表4。
五、结语
本文结合取送货一体化配送模式,构建快递网点选址和配送路线规划模型,并设计随机变邻域禁忌搜素算法求解模型,同时利用仿真数据验证了模型和算法的有效性。下一步将考虑物流配送网络中的不确定因素,如供需不确定、配送时间不确定等,更高效灵活的满足物流配送企业的实际需求。
参考文献:
[1]Karaoglan I, Altiparmak F. A Hybrid Genetic Algorithm for the Location-Routing Problem with Simultaneous Pickup and Delivery [J]. Industrial Engineeering & Management Systems, 2010, 10(1):1-6.
[2]Christian Prins, Caroline Prodhon, Roberto Wolfler Calvo. A Memetic Algorithm with Population Management (MA|PM) for the Capacitated Location-Routing Problem [J]. Lecture Notes in Computer Science, 2006, 3906:183-194.
[3]Salhi S, Nagy G. A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problems with Backhauling [J]. Journal of the Operational Research Society, 1999, 50(10):1034-1042.
作者简介:黄丽萍,女,福建宁德人,福州大学经济与管理学院硕士研究生,研究方向:物流管理与物流工程。张妹燕,女,福建宁德人,福州大学经济与管理学院硕士研究生,研究方向:物流管理与物流工程。