基于物流配送的车辆路径优化问题综述

基于物流配送的车辆路径优化问题综述

龚晶

中国石化集团胜利石油管理局有限公司运输分公司

山东省东营市257000

摘要：物流是物流企业满足客户需求的过程,从供应点到货物通过运输、储存、配送和处理多道工序到指定地点,被誉为促进经济发展的“第三利润源泉”,伴随着信息技术的不断发展,物流的各个方面都得到了进一步优化,特别是物流运输和仓储,实现了智能运输和仓储。但是物流和信息分配和情报还有待进一步改进,主要是因为物流和分配相对于其他环节比较复杂,在很多情况下涉及到双向运输,在双向运输的情况下,运输车辆路线规划也面临着一定的复杂性,需要考虑到客户的需求,还需要考虑运输成本、运输条件等因素,因此,目前在物流配送中,双向运输车辆的规划问题是物流企业在进行路线规划时需要综合考虑的因素,以便制定合理的分配方案,根据双向运输车辆路径优化的复杂性,选择蚁群算法来解决这一复杂问题,然后通过仿真验证蚂蚁群算法下形成的分配方案,从而解决双向运输车辆路径优化问题。

关键词：物流配送；车辆路径；优化问题

引言

城市是商业活动的主要场所,是物流配送的主要区域。如今,交通拥堵已成为城市路网常态,越来越多的城市采取部分区域限行措施,电动车等新能源汽车逐渐应用于城市配送。而电动车存在续航能力不足、充电时间长及配套设施不完善等限制,在未来较长的一段时间内,电动车和燃油车将同时并存于城市物流系统内。因此,研究电动车和燃油车混合的车辆路径规划,更符合城市物流实际情况。

1双向运输车辆路径概述

所谓的双向运输车辆路径是按照预先确定的配送计划方案,运输车辆根据客户的订单信息,从配送中心的位置开始接收客户的订单,并且在车辆到达时,不仅卸载客户需要的货物,而且还将客户返回点货物运送到配送中心,总之,车辆在同一客户点,需要路径时完成任务。由于需要交付和取货,正向物流和逆向物流都涉及,因此本文中的双向运输车辆路径主要是对应于正向逆向物流的运输路径。前向物流相应的运输车辆路径起点是供应链上游,终点是下游供应链,前向物流相应的运输车辆路径是供应链中自上而下的货物运输路径;逆向物流完全对应于运输车辆的相反路径,是供应链中从底部到顶部的返回运输方式。逆向物流运输的货物通常是在生产和分销过程中形成的废物或损坏和有缺陷的产品,逆向物流将在这个过程中进行一系列的工作,如检查,分类,回收和二次处理。逆向物流一般较难预测,产品损坏程度不同,处理不确定,因此逆向物流下的物流成本也很复杂,需要通过科学计算来实现准确的成本核算。

2问题描述

某城市配送中心同时采用电动车与燃油车服务客户(图1)。限行区域、充电站位置、车辆容量、客户位置、需求量和服务时间已知。各客户需求量均小于车辆容量,能且只能被一辆车服务一次。

图1混合车辆配送路径示意图

为了明确本文适用范围,提出如下假设:1)燃油车服务非限行区域的客户,电动车服务限行区域内的客户;2)燃油车在行驶过程中产生油耗与碳排放,在服务时间内发动机关闭,不产生油耗与碳排放;3)电动车从配送中心出发时电池满电,在配送途中电量不足时就近进入充电站充电;4)电动车采用部分充电策略,配送途中最多只允许充电一次;5)车辆具有固定使用成本,根据使用时间计算驾驶员工资。决策问题:如何合理规划车辆路径,使得所有车辆的固定使用成本、驾驶员工资、电动车充电成本、燃油车油耗与碳排放成本之和最小。

3物流配送运输车辆路径的优化要素

为了实现物流配送中双向运输车辆的路径优化,还必须优化物流配送车辆路径,包括配送中心、客户、车辆、运输路线网络、货运等。这些优化元素的具体内容如下:(1)配送中心配送中心也是物流配送中心,通常在物流配送中心进行接收和处理最终客户的订单信息,然后根据客户需求在客户订单信息中对不同类别的货物进行分类,然后进行一系列操作,如收集,准备,分发,分销和交付在整个物流系统中,配送中心的数量和位置存在不确定性,需要根据客户数量和位置进行配置。(2)客户因素在配送、物流企业提供配送服务,是客户的对象,一般是指客户到仓库或零售店等地点,随着电子商务的不断发展,现有客户也是个体。在为客户提供送货服务时,往往会有一些限制,如客户对送货时间的要求,对送货次数的要求等。(3)车辆因素运输车辆是物流的重要运输手段,为了保证物流运输任务的顺利完成,为了提高物流配送率,有必要对物流配送地点和物品等因素进行综合考察,以确保产能得到充分有效的利用。有时,根据分销服务的需求选择具有不同载荷的运输车辆。车辆完成任务后,可以返回到起点并等待下一个任务。(4)运输路线网络因素在物流配送中所涉及的运动和相对停车的实际情况很多,对车辆路线规划的观察可以发现,运动是运输车辆制定配送任务的路线,而停车情况是车辆暂时在该节点上进行交付或接收,运输车辆的运动和停车情况形成运输路线网络。(5)货物的种类通常是由客户的需求决定的,货物在整个物流交付中具有基本特征,在物流交付中,不同类型的货物可以由同一车辆交付,也可以由不同车辆交付。

4 A公司快递配送问题求解

4.1遗传算法编码与解码

遗传算法的编码方式非常多，根据要解决的问题和模型的构建来进行选择。该公司快递配送属于典型的VRP问题，故采用序列编码。配送中心通过数字0来表示起点和终点，用1、2、3等数字来表示表格里对应标号的配送网点。从配送中心出发的车辆，根据配送需求前往对应标号的网点后返回配送中心，数字编码的顺序就是配送车辆先后前往网点的顺序。例如一串编码为0-5-7-2-4-0，就表示一辆配送车辆从配送中心出发，先前往网点5进行配送，然后依次前往网点7、网点2、网点4进行配送，最终回到配送中心。同时编码所得到的染色体还要进行解码，从配送中心0开始，按照配送车辆的快件数量约束放入染色体基因序列中。若到某一配送网点时发现不满足约束时，就需要取消当前车辆在此网点的编码并返回配送中心，由下一辆配送汽车为该网点提供服务。若解码后满足所有约束条件，所得到的基因序列便是符合要求的配送路径。

4.2改进蚁群算法设计

VRP为NP-hard问题,难以求得最优解,通常采用启发式算法求得满意解。MFVRP比VRP更复杂,求解更困难。蚁群算法属于启发式算法,具有启发式搜索、信息正反馈与分布计算等优点,能有效解决多种复杂组合优化问题。根据问题与模型的特点,本文设计一种改进蚁群算法求解,思路如下:1)针对蚁群算法容易陷入局部最优的缺陷,将所有蚂蚁随机放置在各个节点,增加蚂蚁搜索的随机性;2)针对蚁群算法收敛速度慢的缺陷,采用基于精英蚂蚁策略的信息素更新方法提高算法的收敛性能。

结束语

综上所述，在开展物流配送的过程中，双向运输车辆的路径优化问题比较复杂，为了节约物流成本，本文采用了蚁群算法对双向运输车辆的路径优化问题进行了计算和解决，并通过仿真研究对路径优化的结果进行了验证。通过验证得出最优路径符合实际需求的结论，可最大程度地减少车辆行驶的里程，从而使物流成本达到最小化，并提升物流企业的经济效益。

参考文献

[1]李佳慧。城市物流配送车辆路径优化方法研究[D]。长春理工大学,2021。

[2]尹艺珂。城市物流配送路径优化算法研究与应用[D]。西安石油大学,2021。

[3]魏远晗。城市大件物流运输车辆路径优化问题研究[J]。广西质量监督导报,2020(08):144-145。

[4]王晓琪。考虑碳排放的物流配送车辆路径问题优化研究[D]。山东科技大学,2020。

[5]胡虹。物流车辆路径优化问题的研究[D]。兰州交通大学,2020。