多约束条件下物流配送最佳路径选择研究

 1. 引言物流企业一直以来关注的重点是物流配送的运输成本问题。线上购物逐渐成为购物的主流方式，降低运输成本、改善物流配送模式、精准提高配送效率。新零售的出现改变了传统的消费方式，新零售环境对物流配送速度、成本等提出了更高的要求[1]，需采取有效对策优化物流配送路径满足用户需求，应对市场环境的变化，通过改进和规划最合适的配送路径有效降低配送成本[2]。2. 理论基础与方法选择2.1物流配送与最佳路径物流配送定位是按照用户订货要求，物流基地理货并将配好的货物送交收货人的一种方式[3]。配送路径是否合理直接影响物流配送的成本，选取路径优化目标是路径规划的前提[4]。物流配送除了人员的开仓、检仓等以外，运输问题更值得关注[5]。此研究主要考虑行进路径的约束条件贴合实际得出的最优路径。最短路问题是解决配送路径方案的关键因素，最短路是指两个地点间从多条路径中选择路径最短的路，根据不同要求定义不同。曹旭通过Floyd算法求两个旅游景点间最短路，通过Matlab实验仿真验证算法的有效性[6]，用C语言编码求解最短路问题[7]。刘臣宇用Dijkstra标号法特有的优势解决复杂的直送式配送运输问题，找到配送的最短路线，编程计算得到最短距离[8]。本研究在多个约束条件下生成各路段所在权值的复杂最短路问题，是一个优化的最短路问题。2.2最短路求解算法Dijkstra经典算法主要是解决的单源最短路问题[9]，是目前解决最短路较好的算法，而物流配送问题是典型的直送式配送运输问题[10]，仅需算出当前两个地点之间的最短路径，因此Dijkstra算法能适用于物流配送的最佳路径选择[11]。3. 多约束条件下物流配送最佳路径模型建立3.1问题描述物流配送最短路问题求解的是两点之间路径最短，但实际上最佳路径的影响因素较多，在不同的约束条件下生成的路径不一定相同。研究根据实际情况的约束条件来进行考虑，将时间最少、最短路程以及最低费用三个条件下生成的权值进行融合，根据具体要求设置时间和费用阈值。求两地之间最佳路径，如下图1,Vs点与Vt点表示始点与终点，中间点表示可能经过的途经点，现求Vs点到Vt点最佳路径，将城市物流网抽象为图结构G,V表示图中所有顶点的集合，E表示顶点到顶点之间连接的集合，其中（Vs,V1）表示顶点到顶点之间的一条弧连接，W表示两个顶点之间的权值，Wx表示边x的权值。图1 物流配送最佳路径网络图3.2模型建立物流配送运输道路的选择不是唯一的，可能受多个约束条件影响，研究主要考虑时间和费用因素，表示为时间阈值T和费用阈值M。每条道路的权值是可以根据时间和费用的约束变化来快速选择最佳的路径。配送运输道路权值模型假设货车的正常行驶速度为V0（单位为Km/h），对于Vs到Vt途经的路径道路假设都有行驶速度限制，且最高行驶速度为V’[E(i,j）]，其中i,j表示途径的城市点，E(i,j）表示城市i与j之间的道路，设定城市i到城市j之间的堵车系数为C[E(i,j）]，车辆实际行驶速度为：设城市之间的路程为S[E(i,j）]，路程行驶的时间为：物流配送的运输费用是车辆完成货物运输各项费用的总和[12]，包括油费、车辆耗损费、车辆维修费等，将车辆行驶中所有其他的费用设为C[E(i,j）]，为默认动态固定常数值。运输费用为：公式3-4将行驶时间和路程乘积表示为运输费用，可知运输费用与时间和路程都成正比关系，加上对时间和费用的限制可得道路E(i,j），即城市i点到j点之间的权值表示为：其中T为时间阈值，由于两城市之间每条道路的时间差距不大，故为公式能更好地运用，对此值设置的默认值一般较大，一般设置在50左右为最合理。其中M为费用阈值，默认值为1。故权重的计算公式为费用阈值与道路实际费用乘积加上时间阈值与行驶时间乘积，这个计算权重的模型可以通过修改相应时间和费用权值来满足不同需求。4. 数值分析假设求从Vs到Vt时间和费用都同等考虑，默认正常速度V0为60km/h，其他运输费用C[E(i,j）]默认100，时间阈值T默认50，费用阈值M默认1。拥堵系数在实际情况中是动态变化的，故用python编程算出理想速度与限度之间的差距生成出每条路径的拥堵系数，利用公式3-2来算出行驶路径的实际速度和时间如表1。表1 路径拥堵系数、实际速度及行驶时间由公式3-5可知路径的运输费用和每条路径的权重如下表2。由表2可知各个路径的权重之后，将权重赋予物流配送城市网络图中如图2。利用Dijkstra标号法，直到把终点被标志成永久标记结点为止，最终得出：弧（V6,Vt）的终点Vt标号为（600,V6），表示从Vs到Vt的距离为600，并且Vs到Vt的最短路径中Vt的前一个点为V6，到此所有点都已标号，可得从Vs到Vt的最短路径距离是600，最短路径为Vs-V3-V6-Vt。表2 各路径运输费用及相应权重图2 物流配送网络权重图5. 结语物流配送运输的成本过高一直是物流行业重视的问题，如何在满足约束要求的情况下选择最佳路径实现成本最小或时间最快到达的目标很重要。传统的最短路问题仅是考虑路程的情况下求得最短的路径，忽视了道路上可能发生的其他情况，本文就是受道路上其他约束条件的启发，考虑时间和费用两个因素，将最少时间和最小成本进行融合得到新的权值，并附有时间和费用阈值，确保在两者均衡条件下来寻找时间最短、成本最低的最佳路径，而不仅是最短路，符合现实情况的需要，可以在两地物流配送运输问题中以供选择。